Non-clairvoyant reduction algorithms for heterogeneous platforms

Abstract : We revisit the classical problem of the reduction collective operation in a heterogeneous environment. We discuss and evaluate four algorithms that are non-clairvoyant, i.e., they do not know in advance the computation and communication costs. On the one hand, \bins and \fibo are static algorithms that decide in advance which operations will be reduced, without adapting to the environment; they were originally defined for homogeneous settings. On the other hand, \dyn and \dynnc are fully dynamic algorithms, for commutative or non-commutative reductions. With identical computation costs, we show that these algorithms are approximation algorithms. When costs are exponentially distributed, we perform an analysis of \dyn based on Markov chains. Finally, we assess the relative performance of all four non-clairvoyant algorithms with heterogeneous costs though a set of simulations.
Type de document :
Communication dans un congrès
HeteroPar'2013, in conjunction with Euro-Par 2013, Aug 2013, Aachen, Germany. 2013
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00926093
Contributeur : Equipe Roma <>
Soumis le : jeudi 9 janvier 2014 - 10:07:56
Dernière modification le : mardi 11 décembre 2018 - 10:58:09
Document(s) archivé(s) le : jeudi 10 avril 2014 - 14:40:37

Fichier

heteropar.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00926093, version 1

Citation

Anne Benoit, Louis-Claude Canon, Loris Marchal. Non-clairvoyant reduction algorithms for heterogeneous platforms. HeteroPar'2013, in conjunction with Euro-Par 2013, Aug 2013, Aachen, Germany. 2013. 〈hal-00926093〉

Partager

Métriques

Consultations de la notice

298

Téléchargements de fichiers

287