Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Overlapping Computations and Communications with I/O in Wavefront Algorithms

Eddy Caron 1 Frédéric Desprez 1 Frédéric Suter 2 
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
2 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Several numerical computation algorithms exhibit dependences that lead to a wavefront in the computation. Depending on the data distribution chosen, pipelining communication and computation can be the only way to avoid a sequential execution of the parallel code. The computation grain has to be wisely chosen to obtain at the same time a maximum parallelism and a small communication overhead. On the other hand, when the size of data exceeds the memory capacity of the target platform, data have to be stored on disk. The concept of out-of-core computation aims at minimizing the impact of the I/O needed to compute on such data. It has been applied successfully on several linear algebra applications. In this paper we apply out-of-core techniques to wavefront algorithms. The originality of our approach is to overlap computation, communication, and I/O. An original strategy is proposed using several memory blocks accessed in a cyclic manner. The resulting pipeline algorithm achieves a saturation of the disk resource which is the bottleneck in out-of-core algorithms.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 2:51:52 PM
Last modification on : Wednesday, October 26, 2022 - 8:14:53 AM


  • HAL Id : inria-00071247, version 1


Eddy Caron, Frédéric Desprez, Frédéric Suter. Overlapping Computations and Communications with I/O in Wavefront Algorithms. [Research Report] RR-5410, RR-2004-58, INRIA LIP - ENS Lyon. 2004. ⟨inria-00071247⟩



Record views


Files downloads