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.
Type de document :
Communication dans un congrès
Julien Bourgeois and François Spies and Didier El Baz. 16th Euromicro International Conference on Parallel, Distributed and network-based Processing, Feb 2008, Toulouse, France. IEEE, pp.293-300, 2008
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00176084
Contributeur : Jens Gustedt <>
Soumis le : mardi 2 octobre 2007 - 13:49:05
Dernière modification le : dimanche 20 mai 2018 - 20:20:10
Document(s) archivé(s) le : lundi 24 septembre 2012 - 13:01:20

Fichier

cs07_th.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00176084, version 1

Collections

INRIA | GRID5000 | LORIA | UNIV-LORRAINE

Citation

Pierre-Nicolas Clauss, Jens Gustedt, Frédéric Suter. Out-of-Core Wavefront Computations with Reduced Synchronization. Julien Bourgeois and François Spies and Didier El Baz. 16th Euromicro International Conference on Parallel, Distributed and network-based Processing, Feb 2008, Toulouse, France. IEEE, pp.293-300, 2008. 〈inria-00176084〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

268

Téléchargements de fichiers

136

Contact


archive-ouverte@inria.fr