Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Wednesday, December 3, 2014 - 11:13:38 AM
Last modification on : Friday, September 30, 2022 - 4:12:08 AM
Long-term archiving on: : Saturday, April 15, 2017 - 2:40:43 AM


Files produced by the author(s)



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⟩



Record views


Files downloads