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 metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01090232
Contributor : Equipe Roma <>
Submitted on : Wednesday, December 3, 2014 - 11:13:38 AM
Last modification on : Wednesday, September 16, 2020 - 10:42:47 AM
Long-term archiving on: : Saturday, April 15, 2017 - 2:40:43 AM

File

ccpe.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

477

Files downloads

326