Linear‐Time Approximation Schemes for Scheduling Malleable Parallel Tasks

Linear‐Time Approximation Schemes for Scheduling Malleable Parallel Tasks

0.00 Avg rating—0 Votes
Article ID: iaor20121098
Volume: 32
Issue: 3
Start Page Number: 507
End Page Number: 520
Publication Date: Mar 2002
Journal: Algorithmica
Authors: ,
Keywords: computational analysis: parallel computers, combinatorial optimization
Abstract:

A malleable parallel task is one whose execution time is a function of the number of (identical) processors alloted to it. We study the problem of scheduling a set of nindependent malleable tasks on a fixed number of parallel processors, and propose an approximation scheme that for any fixed ϵ > 0 , computes in O(n)time a non‐preemptive schedule of length at most (1+ϵ)times the optimum.

Reviews

Required fields are marked *. Your email address will not be published.