Non‐clairvoyant reduction algorithms for heterogeneous platforms1. (30th July 2014)

• Record Type: Journal Article
• Authors: Benoit, A.; Canon, L.‐C.; Marchal, L.
• Other Names: Drira Khalil guestEditor.; Reddy Sumitra guestEditor.; Bientinesi Paolo guestEditor.; Herrero José R. guestEditor.; Quintana‐Ortí Enrique S. guestEditor.; Strzodka Robert guestEditor.
• Is Part Of: Concurrency and computation. Volume 27:Number 6(2015:Apr.)
• Page Start: 1612
• Page End: 1624
• Publication Date: 2014-07-30
• Subjects: scheduling -- reduction -- approximation algorithms -- non‐clairvoyant algorithms; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.3347
• Languages: English
• ISSNs: 1532-0626

Abstract

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.