Skip to Main content Skip to Navigation
Conference papers

Out-of-Core Wavefront Computations with Reduced Synchronization

Pierre-Nicolas Clauss 1 Jens Gustedt 1 Frédéric Suter 1
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Matrix computation algorithms often exhibit dependencies between neighboring elements inside loop nests such that the frontier between computed elements and those to be computed wanders in form of a 'wave' through the matrix. Macro-pipelining techniques can achieve an efficient parallelization of such algorithms by overlapping communication and computation. Usually these techniques are limited to situations where all the data to be processed fits into main memory, whereas for larger data the I/O usage pattern for external storage requires special attention. The work [CDS05] presented a first extension of the wavefront framework to these so-called out-of-core problems. The present paper proposes a redesign of their algorithm that minimizes both overhead and perturbations coming from communications. To tackle the issue of non-contiguous I/O, we also propose an optimized data layout. These two major modifications of the original algorithm eventually allow us to present a third improvement as our implementation shortens the transition phase between two consecutive iterations of the wavefront algorithm. Experiments performed with the parXXL library show that we can significantly reduce the time lost during inefficient I/O operations and thus obtain faster computations.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00176084
Contributor : Jens Gustedt <>
Submitted on : Tuesday, October 2, 2007 - 1:49:05 PM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM
Long-term archiving on: : Monday, September 24, 2012 - 1:01:20 PM

File

cs07_th.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00176084, version 1

Collections

Citation

Pierre-Nicolas Clauss, Jens Gustedt, Frédéric Suter. Out-of-Core Wavefront Computations with Reduced Synchronization. 16th Euromicro International Conference on Parallel, Distributed and network-based Processing, Feb 2008, Toulouse, France. pp.293-300. ⟨inria-00176084⟩

Share

Metrics

Record views

321

Files downloads

334