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
2 ALGORILLE - Algorithms for the Grid

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.

Plusieurs algorithmes de calcul numérique exhibent des dépendances qui entraînent un front d’ondes dans le calcul. Selon la distribution de données choisie, pipeliner les communications et les calculs peut être le seul moyen d’éviter une exécution séquentielle du code parallèle. Le grain de calcul doit être choisi intelligemment pour obtenir dans le même temps un maximum de parallélisme et un faible surcoût de communication. D’un autre côté, lorsque la taille des données excède la capacité mémoire de la plate-forme cible, les données doivent être stockées sur disque. Le concept de calcul out-of-core tend à minimiser l’impact des entrées/sorties nécessaires à un calcul sur de telles données. Ce concept a déjà été appliqué avec succès sur plusieurs applications d’algèbre linéaire. Dans cet article, nous appliquons des techniques out-of-core aux algorithmes par vagues. L’originalité de notre approche est de recouvrir le calcul, les communications et les entrées/sorties. Nous proposons une stratégie originale utilisant plusieurs blocs de mémoire accédés cycliquement. L’algorithme pipeliné qui en résulte parvient `a saturer la ressource disque qui constitue le goulot d’étranglement des algorithmes out-of-core.

Mots clés: wavefront algorithm; overlap

Mots clés: Out-of-Core; pipeline; algorithme par vague; recouvrement

Domaines: Autre [cs.OH]

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⟩