A comparison of heuristics for scheduling DAGs on multiprocessors

Author

Mccreary, C.L. ; Khan, A.A. ; Thompson, J.J. ; McArdle, M.E.

Author_Institution

Dept. of Comput. Sci. & Eng., Auburn Univ., AL, USA

fYear

1994

fDate

26-29 Apr 1994

Firstpage

446

Lastpage

451

Abstract

Many algorithms to schedule directed acyclic graphs (DAGs) on multiprocessors have been proposed, but there has been little work done to determine their effectiveness. Since multiprocessor scheduling is an NP-hard problem, no exact tractable algorithm exists, and no baseline is available from which to compare the resulting schedules. This paper is an attempt to quantify the differences in a few of the heuristics. The empirical performance of five heuristics is compared when they are applied to ten specific DAGs which represent program dependence graphs of important applications. The comparison is made between a graph based method a list scheduling technique and three critical path methods

Keywords

computational complexity; directed graphs; multiprocessing systems; parallel programming; programming theory; scheduling; NP-hard problem; critical path methods; directed acyclic graphs; graph based method; heuristics; list scheduling technique; multiprocessor scheduling; multiprocessors; parallel programming; performance; program dependence graphs; scheduling; tractable algorithm; Clustering algorithms; Computer science; Costs; Multiprocessing systems; NP-hard problem; Parallel machines; Performance analysis; Processor scheduling; Scheduling algorithm; Tree graphs;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing Symposium, 1994. Proceedings., Eighth International

Conference_Location

Cancun

Print_ISBN

0-8186-5602-6

Type

conf

DOI

10.1109/IPPS.1994.288264

Filename

288264