Abstract
DSC: Scheduling parallel tasks on an unbounded number of processors
by: T. Yang and A. Gerasoulis
Abstract:
We present a low complexity heuristic named the Dominant Sequence Clusteringalgorithm (DSC) for scheduling parallel tasks on an unbounded number ofcompletely connected processors. The performance of DSC is comparable or evenbetter on average than other higher complexity algorithms. We assume no taskduplication and nonzero communication overhead between processors. Finding theoptimum solution for arbitrary directed acyclic task graphs (DAGs) isNP-complete. DSC finds optimal schedules for special classes of DAGs such asfork, join, coarse grain trees and some fine grain trees. It guarantees aperformance within a factor of two of the optimum for general coarse grainDAGs. We compare DSC with three higher complexity general schedulingalgorithms: the ETF by Hwang, Chow, Anger and Lee, Sarkar\'s clusteringalgorithm, and the MD by Wu and Gajski. We also give a sample of importantpractical applications where DSC has been found useful.Note: To appear in IEEE Trans. on Parallel and Distributed Systems.
Keywords:
Clustering, directed acyclic graph, heuristic algorithm,optimality, parallel processing, scheduling, task precedence.
Date:
April 1994
Document: 1994-12
