Optimal Algorithms for Scheduling Divisible Workloads on Heterogeneous Systems

Olivier Beaumont 1, 2 Arnaud Legrand 3 Yves Robert 3
2 SCALAPPLIX - Algorithms and high performance computing for grand challenge applications
INRIA Futurs, Université Bordeaux Segalen - Bordeaux 2, Université Sciences et Technologies - Bordeaux 1, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
3 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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 the processors and/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 solution on a large variety of platforms, especially when the communication-to-computation ratio is not very high (the difficult case).
Type de document :
Communication dans un congrès
IPDS'2003, Parallel and Distributed Processing Symposium, 2003, Feb 2003, Nice, France. IEEE Computer Society Press, 2003, <10.1109/IPDPS.2003.1213202>
Liste complète des métadonnées

https://hal.inria.fr/hal-00789449
Contributeur : Arnaud Legrand <>
Soumis le : lundi 18 février 2013 - 11:51:41
Dernière modification le : vendredi 11 septembre 2015 - 01:06:01

Identifiants

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Yves Robert. Optimal Algorithms for Scheduling Divisible Workloads on Heterogeneous Systems. IPDS'2003, Parallel and Distributed Processing Symposium, 2003, Feb 2003, Nice, France. IEEE Computer Society Press, 2003, <10.1109/IPDPS.2003.1213202>. <hal-00789449>

Partager

Métriques

Consultations de la notice

285