Task scheduling algorithms for heterogeneous processors
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 16 (10975209), 3-14
- https://doi.org/10.1109/hcw.1999.765092
Abstract
Scheduling computation tasks on processors is the key issue for high-performance computing. Although a large number of scheduling heuristics have been presented in the literature, most of them target only homogeneous resources. The existing algorithms for heterogeneous domains are not generally efficient because of their high complexity and/or the quality of the results. We present two low-complexity efficient heuristics, the Heterogeneous Earliest-Finish-Time (HEFT) algorithm and the Critical-Path-on-a-Processor (CPOP) algorithm for scheduling directed acyclic weighted task graphs (DAGs) on a bounded number of heterogeneous processors. We compared the performances of these algorithms against three previously proposed heuristics. The comparison study showed that our algorithms outperform previous approaches in terms of performance (schedule length ratio and speedup) and cost (time-complexity).Keywords
This publication has 13 references indexed in Scilit:
- Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- An Effective and Practical Performance Prediction Model for Parallel Computing on Nondedicated Heterogeneous NOWJournal of Parallel and Distributed Computing, 1996
- Task clustering and scheduling for distributed memory parallel architecturesIEEE Transactions on Parallel and Distributed Systems, 1996
- A Static Scheduling Algorithm Using Dynamic Critical Path for Assigning Parallel Algorithms onto MultiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1994
- A genetic algorithm for multiprocessor schedulingIEEE Transactions on Parallel and Distributed Systems, 1994
- DSC: scheduling parallel tasks on an unbounded number of processorsIEEE Transactions on Parallel and Distributed Systems, 1994
- A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architecturesIEEE Transactions on Parallel and Distributed Systems, 1993
- A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessorsJournal of Parallel and Distributed Computing, 1992
- Scheduling parallel program tasks onto arbitrary target machinesJournal of Parallel and Distributed Computing, 1990
- Parallel Gaussian elimination on an MIMD computerParallel Computing, 1988