A Comparison of Multiprocessor Scheduling Heuristics
- 1 August 1994
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 9, 243-250
- https://doi.org/10.1109/icpp.1994.19
Abstract
Many algorithms for scheduling DAGs on multi-processors 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.Keywords
This publication has 15 references indexed in Scilit:
- A comparison of heuristics for scheduling DAGs on multiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A Comparison of Multiprocessor Scheduling HeuristicsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1994
- Parallax: a tool for parallel program schedulingIEEE Parallel & Distributed Technology: Systems & Applications, 1993
- A fast static scheduling algorithm for DAGs on an unbounded number of processorsPublished by Association for Computing Machinery (ACM) ,1991
- A note on Graham's boundInformation Processing Letters, 1990
- Scheduling parallel program tasks onto arbitrary target machinesJournal of Parallel and Distributed Computing, 1990
- Scheduling with sufficient loosely coupled processorsJournal of Parallel and Distributed Computing, 1990
- Automatic determination of grain size for efficient parallel processingCommunications of the ACM, 1989
- Scheduling Precedence Graphs in Systems with Interprocessor Communication TimesSIAM Journal on Computing, 1989
- Multiprocessor scheduling with interprocessor communication delaysOperations Research Letters, 1988