Soutenance mémoire
Télécharger le fichier pdf d’un mémoire de fin d’études
Optimisation du sch´ema de compilation
Le sch´ema de compilation pr´esent´e en 2.1 peut ˆetre appliqu´e successivement `a toutes les instructions ´el´ementaires du programme s´equentiel pour obtenir un programme spmd parall`ele distribu´e. Le cas de son application sur machine `a messages a ´et´e l’objet d’une description d´etaill´ee [4] et d’une preuve [16].
Cependant, le nombre de synchronisations et d’´evaluations de gardes ainsi que la granularit´e des communications d´egradent fortement l’efficacit´e du code produit.
L’optimisation du sch´ema passe tout d’abord par l’augmentation du grain d’application du sch´ema, le code produit pouvant ´egalement ˆetre ult´erieurement optimis´e.
Il est souhaitable que le sch´ema de compilation puisse ˆetre appliqu´e non pas seulement aux instructions ´el´ementaires mais `a des groupes d’instructions. Ceci permet en effet de r´eduire le nombre de synchronisations produites, de factoriser les gardes et de regrouper les mouvements de donn´ees.
Les regroupements d’instructions qu’il est possible de construire techniquement et qui pr´esentent un int´erˆet pour factoriser les tests sont repr´esent´es par les boucles et plus particuli`erement les boucles parall`eles. Le compilateur peut effectuer une analyse de d´ependances sur le code source afin de les d´etecter. Il existe ´egalement des m´ethodes de transformation de programmes permettant de faire apparaˆıtre ce genre de boucles `a partir de boucles comportant des d´ependances. L’application de ces techniques pour application d’un sch´ema de compilation optimis´e est ´etudi´ee dans [79].
La d´efinition des op´erations de la machine abstraite est ´elargie de sorte que le compilateur puisse traduire les instructions du programme s´equentiel groupe par groupe. Pour passer des instructions ´el´ementaires aux groupes d’instructions (i.e. les boucles parall`eles), nous param´etrons les r´ef´erences aux variables par des variables libres (i.e. les variables d’it´eration). Un param`etre est ´egalement ajout´e aux op´erations : l’ensemble des valeurs prises par ces variables libres (i.e. ensemble des valeurs du vecteur d’it´eration). Dans la suite, on d´esignera cet ensemble sous le nom de domaine.
Des am´eliorations peuvent ´egalement ˆetre mises en oeuvre apr`es application du sch´ema (optimis´e ou non). Elles consistent essentiellement `a d´eplacer et regrouper les op´erations de la machine abstraite apparaissant dans le code interm´ediaire, apr`es une analyse de flots de donn´ees et d’´eventuelles transformations de boucles. Ces derni`eres sont des manipulations de restructuration de codes (( classiques)) issues des vectoriseurs et parall´eliseurs pour machine `a m´emoire partag´ee telles que la distribution, la fusion ou le partitionnement de boucles [2, 99, 102].
D´efinition des op´erations des machines abstraites
Les d´efinitions donn´ees ici permettent de prendre en compte un gros grain d’application du sch´ema de compilation (elles manipulent des domaines) et d’´eventuels regroupements (elles poss`edent des ensembles de param`etres) : par exemple regrouper des Refresh consistera `a produire un seul Refresh auquel on passe en param`etre l’union des param`etres des Refresh consid´er´es.
L’op´eration Refresh prend en param`etre un ensemble (non ordonn´e) de triplets :
Refresh(T1, T2, . . . ))
Chaque Tk est de la forme (R(I), RP (I), D(I)) o`u
• I est un ensemble de variables libres ;
• R(I) et RP (I) sont des ensembles de r´ef´erences `a des variables distribu´ees param´etr´es par I ;
• D(I) est un ensemble de valeurs prises par I.
Pour chaque triplet Tk, l’op´eration Refresh rend disponible sur les processus poss´edant une variable r´ef´erenc´ee dans RP (I), une copie des variables r´ef´erenc´ees dans R(I) pour toutes les valeurs de I d´ecrites dans D(I). Les processus fournissant les copies attendent que les copies soit constitu´ees et les processus b´en´eficiant des copies attendent que les copies soient effectu´ees. Par exemple, Refresh(({A[i],B[i]}, {C[i],D[i]}, {i = 0, 2, 4}), ({A[j]}, {C[j]}, {j = 1, 3, 5}) rafraˆıchit
A[0] et B[0] sur les processus qui poss`edent C[0] ou D[0] ;
A[2] et B[2] sur les processus qui poss`edent C[2] ou D[2] ;
A[4] et B[4] sur les processus qui poss`edent C[4] ou D[4] ;
A[1] sur les processus qui poss`edent C[1] ;
A[3] sur les processus qui poss`edent C[3] ;
A[5] sur les processus qui poss`edent C[5].
L’op´eration Exec
L’op´eration Exec prend ´egalement en param`etre un ensemble de triplets o`u figurent un ensemble de r´ef´erences param´etr´e RP (I) et un domaine D(I) :
Exec((RP (I), S(I), D(I)), . . . )
Pour chaque triplet, on pr´ecise en plus un param`etre S(I) : un ensemble d’instructions ´el´ementaires param´etr´ees par I. L’op´eration Exec fait en sorte que seuls les processus poss´edant une variable r´ef´erenc´ee dans RP (I) ex´ecutent les instructions de S(I), ceci pour toutes les valeurs de I d´ecrites dans D(I).
Aucun ordre n’est impos´e dans l’ex´ecution des diff´erentes instructions de S(I) sur un processus donn´e. Ceci est justifi´e par le fait que l’op´eration Exec est utilis´ee dans un contexte particulier o`u les instructions de S(I) sur un processus donn´e peuvent commuter. La d´efinition d’une op´eration Exec plus g´en´erale o`u il pourrait exister des d´ependances entre les instructions de S(I) pour un processus donn´e n´ecessiterait l’ajout d’un param`etre suppl´ementaire `a l’op´eration. Ce param`etre d´ecrirait les d´ependances entre les instructions des ensembles S(I) sous la forme d’un graphe par exemple.
La d´efinition des composantes RP (I) et D(I) est la mˆeme que pour les op´erations Refresh ou Exec. L’op´eration Sync effectue une seule synchronisation d’un ensemble de processus. Un processus participe `a la synchronisation si, pour un ou plusieurs des couples pass´es en param`etre, il poss`ede une des variables r´ef´erenc´ees dans RP (I) pour une des valeurs appartenant `a D(I).
L’op´eration Get
L’op´eration Get prend les mˆemes param`etres que l’op´eration Refresh. Sa fonction est similaire mis `a part les synchronisations : aucune attente n’est effectu´ee dans le Get.
L’op´eration Exec
Il s’agit de la mˆeme op´eration que l’op´eration Exec pour la machine `a messages.
Points cl´es de mise en oeuvre
On pourrait envisager de consid´erer les op´erations de la machine abstraite comme des primitives de l’ex´ecutif mais cela obligerait `a effectuer la totalit´e du travail support´e par ces op´erations `a l’ex´ecution et donc empˆecherait bon nombre d’optimisations, allant de ce fait `a l’encontre des objectifs vis´e lors de l’´elargissement du grain d’application du sch´ema de compilation.
C’est pourquoi on consid`ere que les op´erations de la machine abstraite constituent un langage interm´ediaire dans le compilateur et que l’interpr´etation de la machine abstraite est faite en partie par un travail statique (i.e. par le compilateur) et en partie par un travail dynamique (i.e. par l’ex´ecutif).
On distingue deux parties (haute et basse) dans le compilateur :
• La partie haute agit en deux temps, elle effectue :
– l’analyse du source et l’application du sch´ema de compilation pour produire un code interm´ediaire spmd faisant appel aux op´erations Refresh, Exec, Sync et Get ;
– l’analyse et la transformation du code interm´ediaire qui d´eplace et regroupe les op´erations Refresh, Exec, Sync et Get.
• La partie basse traduit ces op´erations en code de plus bas niveau, comprenant notamment des appels aux primitives de l’ex´ecutif.
Nous d´eveloppons dans la suite les points cl´es de la mise en oeuvre de la machine abstraite, en pr´ecisant ce qui peut ˆetre effectu´e `a la compilation. L’efficacit´e de cette mise en oeuvre d´epend en effet de facteurs qui n’ont pas ´et´e abord´es lors de sa d´efinition : l’acc`es aux donn´ees doit ˆetre d´etermin´e, des domaines d’it´eration et de donn´ees sont pris en compte, et des communications doivent ˆetre mises en place pour les copies de donn´ees distantes.
Gestion des donn´ees distribu´ees
Repr´esentation des donn´ees et acc`es
Une des tˆaches principales de la machine abstraite est la repr´esentation et l’acc`es aux donn´ees distribu´ees. Le probl`eme se pose principalement pour les tableaux distribu´es. On passe d’une entit´e unique `a une collection d’entit´e : les blocs poss´ed´es par les processus.
Les tableaux manipul´es dans le programme source et dont des r´ef´erences aux ´el´ements apparaissent en param`etre des op´erations de la machine abstraite sont de vrais tableaux multi-dimensionnels. Aucune hypoth`ese n’est faite `a ce niveau sur leur repr´esentation. Une r´ef´erence `a un ´el´ement de tableau est repr´esent´ee par un nom de variable et un vecteur d’indices. Or les machines d’ex´ecution ne permettent en fait que la manipulation d’une m´emoire lin´eaire.
La machine abstraite doit donc :
• stocker les ´el´ements des tableaux distribu´es dans la m´emoire de la machine d’ex´ecution (m´emoires priv´ees ou m´emoire virtuellement partag´ee).
• permettre l’acc`es aux donn´ees, c’est-`a-dire fournir l’adresse m´emoire correspondant `a un ´el´ement de tableau rep´er´e par un nom de variable et un vecteur d’indices.
Occupation m´emoire et rapidit´e d’acc`es
Un compromis doit ˆetre r´ealis´e entre le coˆut m´emoire induit par la repr´esentation des tableaux et la rapidit´e des acc`es aux ´el´ements. La solution extrˆeme consistant `a allouer le tableau entier sur tous les processus n’est ´evidemment pas applicable en g´en´eral : si aucune transformation n’est `a op´erer en ce qui concerne les acc`es, le surcoˆut m´emoire est prohibitif. Cette m´ethode ne peut donc ˆetre utilis´ee que pour les tableaux de petite taille. Inversement, une repr´esentation m´emoire peu coˆuteuse (typiquement r´ealis´ee en transformant la d´eclaration d’un tableau A(N) en une d´eclaration locale A(N/P) o`u P est le nombre de processus) associ´ee `a des transformations d’indices utilisant plusieurs op´erations coˆuteuses telles que la division enti`ere ou le modulo est `a ´eviter.
Uniformité
Deux types de donn´ees sont `a consid´erer sur un processus donn´e : les ´el´ements locaux (attribu´es `a ce processus par la distribution) et les ´el´ements re¸cus, copies temporaires d’´el´ements distants. On qualifie d’uniforme une gestion des tableaux distribu´es dans laquelle la repr´esentation et l’acc`es sont identiques qu’il s’agisse des ´el´ements de la partition locale ou des ´el´ements re¸cus.
En dehors de la simplicit´e ´evidente, l’avantage d’une gestion de tableaux uniforme r´eside dans le fait qu’il n’y a pas besoin de s´eparer les calculs purement locaux (n’utilisant que des donn´ees locales) des calculs requ´erant des donn´ees distantes.
En effet, la plupart des optimisations appliqu´ees `a des boucles s´eparent le code produit en une phase de communication et une phase de calcul durant laquelle on acc`ede aux ´el´ements locaux et aux ´el´ements pr´ec´edemment re¸cus (voir par exemple [67, 81]). Si le compilateur n’est pas capable de d´ecouper la phase de calcul en une partie n’acc´edant en lecture qu’aux ´el´ements locaux et une partie n’acc´edant qu’aux ´el´ements re¸cus, le calcul du possesseur de chaque ´el´ement est `a effectuer `a l’ex´ecution `a chaque r´ef´erence afin de s´electionner le m´ecanisme d’acc`es appropri´e.
La s´eparation des calculs purement locaux des calculs n´ecessitant des donn´ees distantes est possible dans certains cas simples mais peut s’av´erer tr`es complexe (`a la fois en ce qui concerne la compilation et le code g´en´er´e) dans le cas g´en´eral. Il est donc pr´ef´erable de ne pas faire l’hypoth`ese de cette s´eparation lors de la d´efinition de la gestion des tableaux distribu´es.
Ind´ependance vis `a vis des instructions
Dans le programme source soumis au compilateur, on distingue les sp´ecifications de distribution des donn´ees des instructions manipulant ces donn´ees. On dira qu’une gestion des tableaux distribu´es est ind´ependante vis `a vis des instructions si elle est enti`erement d´efinie `a partir de la d´eclaration du tableau original et de la sp´ecification de sa distribution.
Ce n’est pas le cas lorsque la repr´esentation distribu´ee d’un tableau et son mode d’acc`es est sujette ´egalement `a l’analyse des boucles o`u les r´ef´erences `a ce tableau apparaissent ou du type des acc`es `a ce tableau dans le code s´equentiel. Consid´erons par exemple deux nids de boucles successifs impliquant un mˆeme tableau distribu´e.
Pour chaque nid de boucle, `a partir des bornes et des r´ef´erences aux tableaux, on d´etermine une gestion de tableau optimale diff´erente. Pour pallier cette diff´erence, deux solutions sont envisageables :
• Remettre en cause les d´efinitions id´eales de chaque gestion et trouver une gestion commune. Ce compromis est difficile `a d´eterminer et risque d’ˆetre fortement pr´ejudiciable.
• Effectuer un changement de repr´esentation et/ou d’acc`es entre les deux nids de boucles. Cela peut occasionner `a l’ex´ecution un r´earrangement des donn´ees ou un recalcul de m´ecanisme d’acc`es.
Dans les deux cas, on risque d’aboutir `a un surcoˆut en temps ou en m´emoire, surcoˆut qui n’existe pas avec une gestion de tableaux ind´ependante.
Conservation de la contigu¨ıt´e
Une propri´et´e int´eressante d’une repr´esentation des tableaux distribu´es est la conservation de la contigu¨ıt´e des ´el´ements. En effet, le fait que des ´el´ements contigus dans la repr´esentation s´equentielle du tableau soit aussi contigus dans la repr´esentation distribu´ee pr´esente plusieurs avantages :
• L’exploitation de processeurs vectoriels est possible.
• Il est plus facile d’utiliser des communications directes — c’est-`a-dire des communications dans lesquelles on n’effectue pas d’empaquetage/d´epaquetage entre les m´emoires locales et les tampons de communication —, les ensembles d’´el´ements `a communiquer ´etant g´en´eralement contigus dans la repr´esentation s´equentielle (e.g. lignes ou colonnes d’un tableau bi-dimensionnel).
• L’optimisation du code g´en´er´e (par le compilateur de la machine cible) est facilit´ee.
• Les d´efauts de cache lors des acc`es successifs aux ´el´ements sont moins probables (il est fr´equent que les ´el´ements soient acc´ed´es suivant leur repr´esentation s´equentielle).
Possession des donn´ees
Pour pouvoir appliquer la r`egle des ´ecritures locales via l’utilisation de la fonction owner, la machine abstraite doit ˆetre capable de mettre en oeuvre la relation de possession entre les donn´ees du programme et les processus de la machine d’ex´ecution, conform´ement aux indications du programmeur.
La d´etermination de possesseurs de donn´ees `a l’ex´ecution est une fonctionnalit´e centrale de la machine abstraite qui apparaˆıt dans toutes ses op´erations, elle doit ˆetre mise en oeuvre efficacement. Il s’agit d’associer `a un ´el´ement de tableau donn´e un ou plusieurs identificateurs de processus de la machine d’ex´ecution.
Par ailleurs, on peut mettre en oeuvre des fonctionnalit´es annexes :
• La distribution des tableaux se faisant en deux temps (partitionnement en blocs du tableau puis attribution des blocs aux processus), on doit permettre de d´eterminer le ou les possesseurs d’un bloc de donn´ees.
• La relation de possession inverse peut aussi ˆetre n´ecessaire, la machine abstraite doit permettre de d´ecrire l’ensemble des donn´ees poss´ed´ees par un processus donn´e.
|
Table des matières
Introduction
1 Contexte de l’´etude
Contexte de l’´etude
1.1 Programmation des APMD
1.1.1 Difficult´e de programmation des APMD
1.1.2 Supports de programmation
1.1.2.1 Biblioth`eque de communication
1.1.2.2 M´emoire virtuelle partag´ee
1.1.3 Distribution de programmes s´equentiels
1.2 Approche de la compilation par distribution de donn´ees
1.3 Environnements de compilation par distribution de donn´ees
1.3.1 Langage
1.3.2 Compilateur
1.3.3 Ex´ecutif
1.3.4 Machines d’ex´ecution cibles
1.3.5 Performances
2 Machine abstraite pour la compilation dirigée par les données
2.1 Sch´ema de compilation de base
2.2 Introduction des machines abstraites
2.2.1 Application du sch´ema sur machine `a messages
2.2.2 Application du sch´ema sur machine `a MVP
2.3 Optimisation du sch´ema de compilation
2.4 D´efinition des op´erations des machines abstraites
2.5 Points cl´es de mise en oeuvre
2.5.1 Gestion des donn´ees distribu´ees
2.5.1.1 Repr´esentation des donn´ees et acc`es
2.5.1.2 Possession des donn´ees
2.5.2 Restriction des domaines
2.5.2.1 Restriction statique
2.5.2.2 Restriction dynamique
2.5.3 Communications
2.6 ´ Etat de l’art
2.6.1 Vienna Fortran
2.6.1.1 Analyse de recouvrement
2.6.1.2 Inspecteur / Ex´ecuteur
2.6.2 Fortran D
2.6.3 Gestion des donn´ees distribu´ees
2.6.3.1 Repr´esentation des tableaux
2.6.3.2 Acc`es
3 La machine abstraite Pandore
3.1 L’environnement Pandore II
3.1.1 Structure
3.1.2 Le langage
3.1.2.1 G´en´eralit´es
3.1.2.2 La phase distribu´ee
3.1.3 Le compilateur
3.1.3.1 Mod`ele de programme parall`ele
3.1.3.2 Le distributeur
3.1.3.3 Partie terminale du compilateur
3.1.4 L’ex´ecutif
3.2 Mise en oeuvre sur machine `a messages
3.2.1 La POM
3.2.1.1 Mod`ele de machine
3.2.1.2 Interface
3.2.2 Gestion des tableaux distribu´es
3.2.2.1 Principe
3.2.2.2 Pagination des tableaux distribu´es
3.2.2.3 R´eglage des param`etres
3.2.2.4 Optimisations
3.2.2.5 Calcul des possesseurs
3.2.2.6 Mise en oeuvre
3.2.2.7 Performances
3.2.2.8 Discussion
3.2.3 Op´erations Refresh / Exec
3.2.3.1 Le sch´ema de base
3.2.3.2 Le sch´ema optimis´e
3.3 Mise en oeuvre sur une m´emoire virtuelle partag´ee
3.3.1 La m´emoire virtuelle partag´ee Koan
3.3.1.1 Protocoles de gestion de coh´erence
3.3.1.2 R´egions partag´ees
3.3.1.3 Autres services
3.3.1.4 Interface de programmation
3.3.2 Utilisation pour la machine abstraite Pandore
3.3.3 Gestion des tableaux distribu´es
3.3.3.1 Principe
3.3.3.2 Prise en compte du placement
3.3.3.3 D´efinition de L
3.3.3.4 Mise en oeuvre de l’allocation et de l’acc`es
3.3.3.5 Calcul de possesseur
3.3.3.6 Initialisation des donn´ees
3.3.4 Sch´emas de compilation
3.3.4.1 Le sch´ema de base
3.3.4.2 Le sch´ema optimis´e
3.4 Comparaison des mises en oeuvre
4 Exp´erimentation et ´evaluation de performance
4.1 Probl´ematique
4.2 Exp´erimentation
4.2.1 Exp´erimentation sur machine `a messages
4.2.1.1 Noyaux
4.2.1.2 Application de propagation d’ondes
4.2.2 Exp´erimentation sur machine `a MVP
4.3 ´ Evaluation de performance et compilation par distribution de donn´ees
4.3.1 Performances des programmes parall`eles compil´es par distribution de donn´ees
4.3.1.1 Influence du programmeur
4.3.1.2 Influence du compilateur et de l’ex´ecutif
4.3.1.3 Buts de l’´evaluation
4.3.1.4 M´ethodes d’´evaluation
4.3.2 Outils g´en´eraux
4.3.2.1 Picl/ParaGraph
4.3.2.2 Topsys
4.3.2.3 Alpes
4.3.3 Outils associ´es `a des compilateurs dirig´es par les donn´ees
4.3.3.1 Estimateur de performance de Fortran D
4.3.3.2 PPPT
4.3.3.3 D´ebogueur de performance d’EPPP
4.3.4 Outils d’´evaluation dans Pandore
4.3.4.1 Motivations
4.3.4.2 Profiler
4.3.4.3 G´en´eration et analyse de traces
5 Bilan et perspectives
5.1 Bilan
5.2 Perspectives
Télécharger le rapport complet
