Wavefront algorithms and transparent data access

Cette thèse introduit deux outils pour l'accès performant aux données d'un algorithme à front d'onde dans un contexte d'exécution out-of-core. Ces algorithmes sont facilement parallélisables en utilisant des techniques de macro-pipelining, qui permettent un recouvrement des calculs et des communications. Le premier outil part du constat que les performances des opérations de lecture/écriture dans une telle situation sont désastreuses: les données sont éclatées sur disque et leur rapatriement en mémoire est long et coûteux. Le nouvel agencement de données sur disque proposé permet de résoudre ces problèmes en accédant aux données uniquement de manière contiguë. Si ce premier outil décrit comment accéder aux données, le deuxième est un modèle de synchronisation qui décrit quand y accéder. En effet, l'exécution parallèle et concurrente des algorithmes à front d'onde nécessite un contrôle strict des temps d'accès et des temps d'attente. Le modèle présenté dans cette thèse remplit ce rôle, tout en donnant des garanties de propriétés intéressantes pour les applications itératives: verrouillage pro-actif, évolution sans interblocages, progression homogène des tâches. L'utilisation de ces deux outils a été intensivement testée sur un benchmark de référence et expérimentée sur des machines de la plate-forme Grid'5000.This thesis introduces two tools for efficiently access data of a wavefront algorithm in an out-of-core execution context. These algorithms are easily to parallelize by using macro-pipelining techniques which allow to overlap computations and communications. The first tool is build on the observation that input/output operations in such a situation have disastrous performance: data is scattered on disk and getting them in and out of memory is long and expensive. The new data layout on disk that is proposed resolves these issues by accessing data only in a contiguous way. If the first tool describes how to access data, the second one is a synchronization model that describes when to access them. Indeed, concurrent and parallel execution of wavefront algorithms require strict control over accessing and waiting periods. The model presented in this thesis fulfills this role while providing guarantees on interesting properties for iterative applications: proactive locking, deadlock-free evolution, homogeneous progression of tasks. The usage of these two tools has been intensively tested on a reference benchmark and experimented on machines from the Grid'5000 platform