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

Abstract

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+.