Skip to Main content Skip to Navigation

A Realistic Model and an Efficient Heuristic for Scheduling with Heterogeneous Processors

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.
Document type :
Complete list of metadatas
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:07:58 AM
Last modification on : Thursday, January 9, 2020 - 9:56:02 AM


Files produced by the author(s)


  • HAL Id : hal-02101846, version 1



Olivier Beaumont, Vincent Boudet, Yves Robert. A Realistic Model and an Efficient Heuristic for Scheduling with Heterogeneous Processors. [Research Report] LIP RR-2001-37, Laboratoire de l'informatique du parallélisme. 2001, 2+18p. ⟨hal-02101846⟩



Record views


Files downloads