Heterogeneity Considered Harmful to Algorithm Designers

Olivier Beaumont 1 Vincent Boudet 1 Arnaud Legrand 1 Fabrice Rastello 1 Yves Robert 1
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this paper, we deal with algorithmic issues on heterogeneous platforms. We show that static scheduling and load-balancing strategies are absolutely needed to achieve good performances, in contrast to situation for homogeneous parallel machines where dynamic schemes often turn out to be very satisfactory. However, we also show that static strategies targeted to heterogeneous platforms are difficult to design and implement: intuitively, data distribution must obey a much more refined model than standard block-cyclic distributions to equally balance the load between processors of different speeds. Technically, we state several NP-completeness results that demonstrate the intrinsic difficulty of static load-balancing on heterogeneous platforms.
Type de document :
Rapport
[Research Report] 2000-24, 2000
Liste complète des métadonnées

https://hal.inria.fr/hal-00856642
Contributeur : Equipe Roma <>
Soumis le : lundi 2 septembre 2013 - 10:21:56
Dernière modification le : vendredi 20 avril 2018 - 15:44:24

Identifiants

  • HAL Id : hal-00856642, version 1

Collections

Citation

Olivier Beaumont, Vincent Boudet, Arnaud Legrand, Fabrice Rastello, Yves Robert. Heterogeneity Considered Harmful to Algorithm Designers. [Research Report] 2000-24, 2000. 〈hal-00856642〉

Partager

Métriques

Consultations de la notice

234