Non-clairvoyant reduction algorithms for heterogeneous platforms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Concurrency and Computation: Practice and Experience Année : 2015

Non-clairvoyant reduction algorithms for heterogeneous platforms

Résumé

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.
Fichier principal
Vignette du fichier
ccpe.pdf (518.54 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01090232 , version 1 (03-12-2014)

Identifiants

Citer

Anne Benoit, Louis-Claude Canon, Loris Marchal. Non-clairvoyant reduction algorithms for heterogeneous platforms. Concurrency and Computation: Practice and Experience, 2015, 27 (6), pp.1612-1624. ⟨10.1002/cpe.3347⟩. ⟨hal-01090232⟩
224 Consultations
142 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More