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, Binomial-stat and Fibonacci-stat 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, Tree-dyn and Non-Commut-Tree-dyn are fully dynamic algorithms, for commutative or non-commutative reductions. We show that these algorithms are approximation algorithms with constant or asymptotic ratios. We assess the relative performance of all four non-clairvoyant algorithms with heterogeneous costs through a set of simulations. Our conclusions hold for a variety of distributions.
Type de document :
Article dans une revue
Concurrency and Computation: Practice and Experience, Wiley, 2015, 27 (6), pp.1612-1624. 〈10.1002/cpe.3347〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01090232
Contributeur : Equipe Roma <>
Soumis le : mercredi 3 décembre 2014 - 11:13:38
Dernière modification le : mardi 11 décembre 2018 - 10:58:05
Document(s) archivé(s) le : samedi 15 avril 2017 - 02:40:43

Fichier

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

Identifiants

Citation

Anne Benoit, Louis-Claude Canon, Loris Marchal. Non-clairvoyant reduction algorithms for heterogeneous platforms. Concurrency and Computation: Practice and Experience, Wiley, 2015, 27 (6), pp.1612-1624. 〈10.1002/cpe.3347〉. 〈hal-01090232〉

Partager

Métriques

Consultations de la notice

270

Téléchargements de fichiers

80