Non‐clairvoyant reduction algorithms for heterogeneous platforms1. (30th July 2014) - Benoit, A.; Canon, L.‐C.; Marchal, L.
Summary: We revisit the classical problem of the reduction collective operation in a heterogeneous environment. We discuss and evaluate four algorithms that are non‐clairvoyant, that is, they do not know in advance the computation and communication costs. On the one hand, Binomial‐stat andFibonacci‐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 andNon‐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. Copyright © 2014 John Wiley & Sons, Ltd.