A comparison of heuristics for scheduling DAGs on multiprocessors
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 446-451
- https://doi.org/10.1109/ipps.1994.288264
Abstract
Effective and efficient automated parallelization of code is an objective of much research in parallel computing. One of the steps in going from serial source code to parallel executable code is scheduling -- the assignment of tasks to processors. Researchers often use a graphical intermediate representation of the program such as a program dependence graph (PDG) to help identify groups of tasks that can be executed in parallel and tasks that are to be scheduled on the same processor. Because the scheduling problem is NP-hard, many heuristic solutions have been proposed. This research is a comparison of some of the proposed solutions for the scheduling problem.Keywords
This publication has 10 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 clustering heuristics for scheduling directed acyclic graphs on multiprocessorsJournal of Parallel and Distributed Computing, 1992
- Hypertool: a programming aid for message-passing systemsIEEE Transactions on Parallel and Distributed Systems, 1990
- Scheduling parallel program tasks onto arbitrary target machinesJournal of Parallel and Distributed Computing, 1990
- Towards an Architecture-Independent Analysis of Parallel AlgorithmsSIAM Journal on 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
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961