A realistic model and an efficient heuristic for scheduling with heterogeneous processors
Authors:
- O. BeaumontOBO. Beaumont
- V. BoudetVBV. Boudet
- Y. RobertYRY. Robert
- 1 January 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 14 pp
Abstract
Scheduling computational tasks on processors is a 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. Moreover, these heuristics often rely on a model where the number of processors is bounded but where the communication capabilities of the target architecture are not restricted. In this paper, we deal with a more realistic model for heterogeneous networks of workstations, where each processor can send and/or receive at most one message at any given time-step. First, we state a complexity result that shows that the model is at least as difficult as the standard one. Then, we show how to modify classical list scheduling techniques to cope with the new model. Next we introduce a new scheduling heuristic which incorporates load-balancing criteria into the decision process of scheduling and mapping ready tasks. Experimental results conducted using six classical testbeds (LAPLACE, LU, STENCIL, FORK-JOIN, DOOLITTLE, and LDMt) show very promising results.Keywords
This publication has 18 references indexed in Scilit:
- A dynamic matching and scheduling algorithm for heterogeneous computing systems2002
- A new task mapping technique for communication-aware scheduling strategies2002
- Task allocation on a network of processorsIEEE Transactions on Computers, 2000
- Scheduling Problems in a Practical Allocation ModelJournal of Combinatorial Optimization, 1997
- Task scheduling in multiprocessing systemsComputer, 1995
- DSC: scheduling parallel tasks on an unbounded number of processorsIEEE Transactions on Parallel and Distributed Systems, 1994
- Models of machines and computation for mapping in multicomputersACM Computing Surveys, 1993
- On the granularity and clustering of directed acyclic task graphsIEEE 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
- Parallel Gaussian elimination on an MIMD computerParallel Computing, 1988