Optimal algorithms for scheduling divisible workloads on heterogeneous systems

Abstract : In this paper, we discuss several algorithms for scheduling divisible loads on heterogeneous systems. Our main contributions are (i) new optimality results for single-round algorithms and (ii) the design of an asymptotically optimal multi-round algorithm. This multi-round algorithm automatically performs resource selection, a difficult task that was previously left to the user. Because it is periodic, it is simpler to implement, and more robust to changes in the speeds of processors or communication links. On the theoretical side, to the best of our knowledge, this is the first published result assessing the absolute performance of a multi-round algorithm. On the practical side, extensive simulations reveal that our multi-round algorithm outperforms existing solutions on a large variety of platforms, especially when the communication-to-computation ratio is not very high (the difficult case).
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02102118
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:14:45 AM
Last modification on : Sunday, April 28, 2019 - 1:23:02 AM

File

RR2002-36.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102118, version 1

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Yves Robert. Optimal algorithms for scheduling divisible workloads on heterogeneous systems. [Research Report] LIP RR-2002-36, Laboratoire de l'informatique du parallélisme. 2002, 2+23p. ⟨hal-02102118⟩

Share

Metrics

Record views

23

Files downloads

59