Scheduling DAGs on Message Passing m-Processor Systems

Sanjeev BASKIYAR  

IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.7   pp.1497-1507
Publication Date: 2000/07/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Systems
clustering,  DAG,  longest path,  multiprocessors,  non-preemptive scheduling,  

Full Text: PDF(1.3MB)>>
Buy this Article

Scheduling directed a-cyclic task graphs (DAGs) onto multiprocessors is known to be an intractable problem. Although there have been several heuristic algorithms for scheduling DAGs onto multiprocessors, few address the mapping onto a given number of completely connected processors with an objective of minimizing the finish time. We present an efficient algorithm called ClusterMerge to statically schedule directed a-cyclic task graphs onto a homogeneous completely connected MIMD system with a given number of processors. The algorithm clusters tasks in a DAG using a longest path heuristic and then iteratively merges these clusters to give a number of clusters identical to the number of available processors. Each of these clusters is then scheduled on a separate processor. Using simulations, we demonstrate that ClusterMerge schedules task graphs yielding the same or lower execution times than those of other researchers, but using fewer processors. We also discuss pitfalls in the various approaches to defining the longest path in a directed a-cyclic task graph.