page 1  (30 pages)
2to next section

A Comparison of Multiprocessor Scheduling Heuristics ?

A. A. Khan, C. L. McCreary, M. S. Jones Department of Computer Science and Engineering Auburn University Auburn, AL 36849 aakhan@eng.auburn.edu, mccreary@eng.auburn.edu, msjones@eng.auburn.edu

Contact person: Dr. Carolyn McCreary, Tel: (205)844-6308, Fax: (205)844-6329

Abstract

Many algorithms for scheduling DAGs on multiprocessors have been proposed, but there has been little work done to determine their effectiveness. Since multi-processor scheduling is an NP-hard problem, no exact tractible algorithm exists, and no baseline is available from which to compare the resulting schedules. Furthermore, performance guarantees have been found for only a few simple DAGs. This paper is an attempt to quantify the differences in five of the heuristics. Classification criteria are defined for the DAGs, and the differences between the heuristics are noted for various criteria. The comparison is made between a graph based method, two critical path methods, and two list scheduling heuristics. The empirical performance of the five heuristics is compared when they are applied to the randomly generated DAGs.

?This work is supported by NSF grant number CCR-9203319