A Static Scheduling Algorithm Using Dynamic Critical Path for Assigning Parallel Algorithms onto Multiprocessors
- 1 August 1994
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 9, 155-159
- https://doi.org/10.1109/icpp.1994.46
Abstract
An algorithm for compile-time static scheduling of task graphs onto multiprocessors is proposed. The proposed algorithm, which is called Dynamic Critical Path (DCP) scheduling algorithm, is different from previously reported algorithms in a number of ways. First, it determines the critical path of the task graph and selects the next node to be scheduled in a dynamic fashion. Second, it rearranges the schedule on each processor dynamically in the sense that the positions of the nodes in the partial schedules are not fixed until all nodes have been considered. Third, it uses an intelligent way to select a suitable processor for a node by looking ahead the potential start times of the remaining critical nodes on that processor and by scheduling relatively less important nodes to the processors already in use. Four related scheduling algorithms are also discussed. Although these algorithms are efficient in general, they possess drawbacks which can lead to poor performance. The proposed DCP algorithm overcomes the drawbacks of these algorithms and outperforms them by a considerable margin. Despite having a number of new features, the DCP algorithm is fast, efficient in terms of the number of processors used and is equally suitable for different types of graph structures.Keywords
This publication has 12 references indexed in Scilit:
- A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architecturesIEEE Transactions on Parallel and Distributed Systems, 1993
- Analysis and evaluation of heuristic methods for static task schedulingJournal of Parallel and Distributed Computing, 1990
- 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
- Using dual approximation algorithms for scheduling problems theoretical and practical resultsJournal of the ACM, 1987
- Solving Linear Algebraic Equations on an MIMD ComputerJournal of the ACM, 1983
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a SurveyPublished by Elsevier ,1979
- Deterministic Processor SchedulingACM Computing Surveys, 1977
- A comparison of list schedules for parallel processing systemsCommunications of the ACM, 1974
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961