A comparative study of multiprocessor list scheduling heuristics
- 1 January 1994
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 68-77
- https://doi.org/10.1109/hicss.1994.323184
Abstract
Many multiprocessor list scheduling heuristics that account for interprocessor communication delay have been proposed in recent years. However, no uniform comparative study of published heuristics has been performed in almost 20 years. This paper presents the results of a large quantitative study using random, but program-like input graphs. We found differences in the performance of the various heuristics related to the amount of parallelism in the input graph. As well, we found that no single heuristic consistently produces the best schedules under call program structures and multiprocessor configurations. Finally we propose enhancements to existing heuristics as well as our own heuristic, DS, which strikes a good balance between performance and scheduling (i.e. compile) time.<>Keywords
This publication has 10 references indexed in Scilit:
- Declustering: a new multiprocessor scheduling techniqueIEEE Transactions on Parallel and Distributed Systems, 1993
- A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architecturesIEEE Transactions on Parallel and Distributed Systems, 1993
- Scheduling parallel program tasks onto arbitrary target machinesJournal of Parallel and Distributed Computing, 1990
- Scheduling of Precedence-Constrained Tasks on MultiprocessorsThe Computer Journal, 1990
- Scheduling Precedence Graphs in Systems with Interprocessor Communication TimesSIAM Journal on Computing, 1989
- Practical Multiprocessor Scheduling Algorithms for Efficient Parallel ProcessingIEEE Transactions on Computers, 1984
- A Preliminary Evaluation of the Critical Path Method for Scheduling Tasks on Multiprocessor SystemsIEEE Transactions on Computers, 1975
- A comparison of list schedules for parallel processing systemsCommunications of the ACM, 1974
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961