Skip to Main content Skip to Navigation
Reports

Non-clairvoyant reduction algorithms for heterogeneous platforms

Abstract : In this paper, we revisit the classical problem of the reduction collective operation, in a dynamic and heterogeneous environment. We discuss and evaluate four algorithms. 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 defined originally 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 with constant or asymptotic ratios. When costs are exponentially distributed, we perform an analysis of \dyn based on Markov chains. Finally, we assess the performance of the algorithms though a set of simulations.
Complete list of metadata

https://hal.inria.fr/hal-00832102
Contributor : Equipe Roma <>
Submitted on : Monday, June 10, 2013 - 2:04:35 PM
Last modification on : Monday, November 16, 2020 - 9:58:10 AM

File

RR-8315.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00832102, version 2

Citation

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

Share

Metrics

Record views

24

Files downloads

19