Scheduling Divisible Workloads on Heterogeneous Platforms

Olivier Beaumont 1, 2 Arnaud Legrand 3 Yves Robert 3
1 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 workloads 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 solutions on a large variety of platforms, especially when the communication-to-computation ratio is not very high (the difficult case).
Type de document :
Article dans une revue
Parallel Computing, Elsevier, 2003, 29, pp.1121―1152. <10.1016/S0167-8191(03)00095-4>
Liste complète des métadonnées

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

Identifiants

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Yves Robert. Scheduling Divisible Workloads on Heterogeneous Platforms. Parallel Computing, Elsevier, 2003, 29, pp.1121―1152. <10.1016/S0167-8191(03)00095-4>. <hal-00789431>

Partager

Métriques

Consultations de la notice

218