Expression d'algorithmes scientifiques et gestion performante de leur parallélisme avec PRFX pour les grappes de SMP

Nous proposons un mode d'expression destiné à l'implémentation performante des algorithmes parallèles scientifiques, notamment irréguliers, sur des machines à mémoires distribuées hétérogènes (e.g. grappes de SMP). Ce mode d'expression parallèle est basé sur le langage C et l'API de la bibliothèque PRFX. Le découpage de l'algorithme en tâches est obligatoire mais les synchronisations et communications entre ces tâches sont implicites. L'identification des tâches et de leurs caractéristiques (identificateur de la fonction cible, paramètres, coût) doit être effectuée via l'interface de la bibliothèque PRFX. Cette interface doit également être utilisée pour allouer et libérer les données ainsi que pour déclarer les accès des tâches aux données. La structuration des données (référencement par pointeurs) est aisée car PRFX fournit un espace d'adressage global. D'autres fonctionnalités optionnelles de la bibliothèque PRFX permettent d'exprimer des optimisations génériques et lisibles. En effet, il est possible d'appliquer dans le cas des programmes prévisibles (i.e. structurés par un jeu de données d'entrée), des heuristiques d'ordonnancement globales paramétrées par des modèles de coût et guidées par le programmeur (e.g. spécification d'un placement initial). Le support utilise une iso-mémoire assurant la validité des pointeurs en mémoire distribuée. Il adopte un fonctionnement de type inspection/exécution. L'inspecteur modélise l'exécution de l'algorithme parallèle par un DAG de tâches. Ce type de fonctionnement et ce modèle sont adaptés à l'exploitation performante des programmes irréguliers prévisibles. Les tâches et leurs accès aux données sont capturés dans ce DAG lors de l'inspection statique consistant en une pré-exécution partielle du programme. Les communications et synchronisations sont déduites de l'analyse des accès aux données faite par l'inspecteur. Ensuite, un ordonnanceur séquentiel applique l'heuristique d'ordonnancement intégrant les optimisations explicitées par le programmeur. Enfin, un exécuteur parallèle exécute le DAG de tâches en respectant l'ordonnancement des tâches et des communications. Il exploite la performance des communications unilatérales pour les communications inter-noeuds et tire profit de la mémoire partagée d'un noeud avec des threads. Dans ce cadre, nous avons validé notre approche par l'implémentation d'algorithmes scientifiques (résolution de l'équation de Laplace, factorisation LU de matrices pleines et factorisation de matrices creuses par la méthode de Cholesky) et par des expérimentations en vraie grandeur sur des grappes de SMP IBM® NH2 et p690+.We present a programing model aimed to efficiently implement parallel scientific algorithms, in particular irregular ones, onto distributed memory machines like clusters of SMP nodes. This programming model is based on the C language and calls to our PRFX library. The programmer must split its algorithm into tasks nervertheless synchronizations and communications between tasks are implicit. These tasks operate on data that are dynamically allocated in an iso-memory and may access sub-data through the declaration of their geometry with stencils. Data structures (with pointers) may be easily implemented thanks to the global address space provided. We also provide functionalities to take into account the static properties of irregular algorithms (with structuring data) like scheduling heuristics using cost functions and an initial task mapping. Our parallel runtime uses an iso-memory keeping pointer validity through migration in the distributed memory. It adopts an inspection/execution scheme. Our inspector modelizes the parallel execution by a task DAG which is well suited to predicitble irregular algorithms. Tasks and their accesses are statically analyzed by the inspector. This allows to build data dependencies thanks to a partial pre-execution of the code, and to produce a task DAG with all necessary information for the static scheduler and the parallel executor. Then, a static sequential scheduler applies a heuristic taking into account the optimizations specified by the programmer. Finally, the parallel executor executes the tasks and the communications of the DAG with respect to this schedule. Our parallel executor uses POSIX threads with one-sided communications and works on shared and distributed memory machines. We validate its performances by experimental results for a Laplace equation solver, a LU factorization of dense matrices and a sparse Cholesky factorization algorithm on SMP IBM® cluster with NH2 and p690+ nodes