HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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

Cited literature [28 references]  Display  Hide  Download

Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Tuesday, June 11, 2013 - 10:01:27 AM
Last modification on : Monday, May 16, 2022 - 4:46:01 PM
Long-term archiving on: : Tuesday, April 4, 2017 - 7:17:48 PM


Files produced by the author(s)


  • HAL Id : hal-00832102, version 3


Anne Benoit, Louis-Claude Canon, Loris Marchal. Non-clairvoyant reduction algorithms for heterogeneous platforms. [Research Report] RR-8315, INRIA. 2013. ⟨hal-00832102v3⟩



Record views


Files downloads