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 :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101846
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:07:58 AM
Last modification on : Sunday, May 19, 2019 - 1:20:43 AM

File

RR2001-37.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101846, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

7

Files downloads

25