Skip to Main content Skip to Navigation
Reports

Scheduling Associative Reductions with Homogeneous Costs when Overlapping Communications and Computations

Louis-Claude Canon 1 Gabriel Antoniu 1
1 KerData - Scalable Storage for Clouds and Beyond
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
Abstract : Reduction is a core operation in parallel computing. Optimizing its cost has a high potential impact on the application execution time, particularly in MPI and MapReduce computations. In this paper, we propose an optimal algorithm for scheduling associative reductions. We focus on the case where communications and computations can be overlapped to fully exploit resources. Our algorithm greedily builds a spanning tree by starting from the sink and by adding a parent at each iteration. Bounds on the completion time of optimal schedules are then characterized. To show the algorithm extensibility, we adapt it to model variations in which either communication or computation resources are limited. Moreover, we study two specific spanning trees: while the binomial tree is optimal when there is either no transfer or no computation, the Fibonacci tree is optimal when the transfer cost is equal to the computation cost. Finally, approximation ratios of strategies that are derived from those trees are drawn.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-00675964
Contributor : Louis-Claude Canon <>
Submitted on : Friday, March 2, 2012 - 2:38:15 PM
Last modification on : Friday, March 6, 2020 - 1:18:15 AM
Document(s) archivé(s) le : Friday, November 23, 2012 - 3:31:12 PM

File

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

Identifiers

  • HAL Id : hal-00675964, version 1

Citation

Louis-Claude Canon, Gabriel Antoniu. Scheduling Associative Reductions with Homogeneous Costs when Overlapping Communications and Computations. [Research Report] RR-7898, INRIA. 2012. ⟨hal-00675964⟩

Share

Metrics

Record views

422

Files downloads

572