Présentation de la parallélisation automatique

Chapter 4

Présentation de la parallélisation automatique

Plus une année ne se passe sans qu'un constructeur propose une nouvelle machine parallèle. Pour l'instant aucune architecture ne semble pouvoir s'imposer (bien que les Cray classiques basés sur quelques processeurs vectoriels restent une valeur sûre). Le bouillonnement qui agite en ce moment le marché des machines parallèles est révélateur de l'intérêt porté à ce nouveau type d'ordinateurs. Même les machines personnelles suivent la mode ; il est désormais possible d'acquérir une plaque mère de PC comportant deux processeurs Pentium. Si le matériel ne cesse de se perfectionner, le logiciel a (comme d'habitude) du mal à suivre. Ce chapitre dresse un bref bilan de la situation actuelle.

4.1

Langage parallèle versus parallélisation automatique

Pour tirer pleinement parti des machines parallèles existantes, il existe deux solutions :

définir des langages parallèles efficaces et portables ;
extraire le parallélisme des programmes écrits dans un langage séquentiel.

La première solution est attirante ; chaque domaine d'étude a créé son langage de programmation : Pascal pour l'enseignement, Cobol pour la gestion, Prolog et Lisp pour l'intelligence artificielle, C pour les systèmes d'exploitation, etc. Alors pourquoi pas un langage pour la programmation parallèle ? De nombreuses tentatives ont été menées, surtout autour de Fortran (il existe quelques compilateurs basés sur C et sur Lisp, principalement pour les CM-2 et CM-5). Les compilateurs Fortran sont nombreux ; citons le CM-Fortran pour les machines de TMC, le Cray-Fortran et le MP-Fortran pour la société MasPar. Ces compilateurs s'inspirent des standards comme Fortran-77 ou Fortran-90 mais sont largement incompatibles entre eux. Cela explique certainement qu'aucun langage ou idiome n'ait réussi à s'imposer. Des efforts de normalisation sont faits, par exemple pour les communications inter-processeurs (la bibliothèque PVM [1] est de facto un standard) et pour un nouveau Fortran parallèle : HPF [43]. Pour l'instant aucun compilateur HPF n'est vraiment disponible.

Une alternative est la parallélisation automatique de programmes écrits dans un langage séquentiel. Ce procédé présente, lui aussi, plusieurs avantages.

Un argument souvent mis en avant est la réutilisation des codes existants. Il est vrai que la récriture d'un programme coûte cher en temps et en hommes. C'est d'ailleurs un travail sans fin car dès que le programme est opérationnel, la machine parallèle est obsolète. Comme de plus les langages parallèles ne sont pas portables (ou inefficaces sur une autre machine), quasiment tout le programme doit être repris.
La parallélisation automatique évite au programmeur de programmer à un trop bas niveau (comme par exemple avec C* de la CM-2, qui n'est rien d'autre qu'un assembleur, avec une coloration de langage C) ; il n'a pas non plus à se soucier de l'architecture de la machine cible. C'est particulièrement vrai au niveau des processeurs modernes (e.g. le Pentium d'Intel) ; ces processeurs possèdent plusieurs unités de traitement qui ne sont correctement utilisées que si le code machine est étudié pour.
Enfin, pour peu que le paralléliseur soit prévu pour plusieurs machines cibles, la portabilité est assurée sans perte de performances (le paralléliseur extrait le parallélisme le mieux adapté à une machine cible donnée).

4.2

Analyse des dépendances

Une notion importante dans le domaine de la parallélisation automatique est la notion de dépendance entre les opérations d'un programme. Dans un programme séquentiel l'ordre < d'exécution des opérations est complètement déterminé. Il s'agit donc d'un ordre total ; pour chaque couple d'opérations l'une s'exécute avant l'autre. Or cet ordre est parfois factice. En effet les structures de contrôle (les boucles, les alternatives, etc.) des langages de programmation classiques (Pascal, Fortran, C, etc.) sont basées sur une sémantique séquentielle (e.g. les itérations d'une boucle sont exécutées les unes après les autres). Cette sémantique est parfois inutile. Le but de la parallélisation automatique est d'extraire un ordre partiel <_// de <. Cet ordre doit être le moins contraignant possible (i.e. permettre d'exécuter le plus grand nombre possible d'opérations en parallèle). Mais il faut aussi que l'exécution des opérations suivant l'ordre <_// donne les même résultats que lorsqu'elles sont exécutées suivant <. L'analyse des dépendances s'attache à trouver les opérations qui entrent en conflit, c'est-à-dire qui doivent être exécutées suivant un ordre prédéterminé. Deux opérations sont en conflit lorsqu'elles utilisent une même ressource pour laquelle l'ordre d'accès est important. Ce peut être un enregistrement d'un disque, un modem, une fenêtre graphique, etc. Mais plus généralement il s'agit d'une cellule mémoire. En fait tout accès à une ressource peut être vue comme un accès mémoire ; les périphériques sont le plus souvent commandés via des adresses mémoire fictives ; l'image d'une fenêtre graphique est stockée dans une mémoire, etc. Bernstein [10] a remarqué que les conflits entre opérations d'affectation à une cellule mémoire sont de trois types :

les dépendances producteur-consommateur (PC), une opération écrit dans une cellule mémoire ultérieurement utilisée par une seconde opération ;
les dépendances consommateur-producteur (CP), ici une opération lit la valeur d'une cellule mémoire avant qu'elle ne soit écrasée par autre opération ;
enfin les dépendances producteur-producteur (PP), deux opérations écrivent successivement dans la même cellule mémoire.

Ces dépendances peuvent être représentées dans un graphe, le graphe des dépendances.

4.3

Historique de la parallélisation automatique

Il existe plusieurs méthodes pour paralléliser les programmes séquentiels. La méthode historique consiste à appliquer des transformations sur le programme source. Les transformations susceptibles de mettre en relief du parallélisme sont nombreuses [65].

Par exemple l'inversion de boucles peut amener une boucle parallèle externe en position interne. C'est indispensable pour qu'une machine vectorielle puisse exploiter le parallélisme. Ainsi, dans le nid de boucle
DO i=1,n
  DO j=1,n
    s(i,j)=s(i,j-1)+a(i,j)
  END DO
END DO
la boucle externe est parallèle alors que la boucle interne ne l'est pas. Pour un processeur vectoriel mieux vaut inverser les boucles (c'est valide pour cet exemple) et vectoriser la boucle interne :
DO j=1,n
  DO ALL i=1,n
    s(i,j)=s(i,j-1)+a(i,j)
  END DO
END DO

La méthode de parallélisation de programmes par transformations successives présente un inconvénient majeur : l'ordre optimal d'application des transformations n'a toujours pas été trouvé. Il est d'ailleurs probable qu'il n'en existe pas et que la seule méthode optimale consiste à essayer toutes les combinaisons possibles. C'est pourquoi des méthodes plus systématiques ont été mises au point. La méthode de Kennedy et Allen [3] permet de traiter un programme entier. L'idée de base est que les composantes fortement connexes du graphe de dépendances du programme représentent des opérations contenues dans le même nid de boucles ¹. Le nouveau programme généré par la méthode de Kennedy et Allen est tel que :

les corps des boucles du nouveau programme sont les plus petits possibles ;
les nouvelles boucles sont parallélisées quand c'est possible.

Cette méthode combine donc, de manière automatique, deux transformations classiques : l'éclatement de boucles et la parallélisation de boucles. Un inconvénient de cette méthode est, puisque seulement deux transformations sont prises en compte, que tout le parallélisme du programme n'est pas extrait. La méthode des fronts (ou des vagues ou des hyper-plans) travaille au niveau des nids de boucles. Elle partitionne l'espace d'itération d'un nid suivant des hyper-plans de telle manière que toutes les opérations liées à un hyper-plan puissent s'exécuter en parallèle. Les premiers travaux sur cette méthode sont dus à Y. Muraoka et à L. Lamport ; une description plus précise se trouve dans [65].

La méthode géométrique est la dernière née des méthodes de parallélisation automatique. Elle s'appuie sur la méthode des fronts et sur les recherches menées dans le domaine de la conception des circuits systoliques [50]. Cette méthode est utilisée par exemple dans le paralléliseur PAF du laboratoire PRiSM, dans le paralléliseur PIPS de l'ENSMP [34] ou au laboratoire LIP de l'ENS de Lyon ([20]). La méthode géométrique consiste à effectuer un changement de base sur l'espace d'itération des nids de boucles du programme. L'idée est que le nouveau nid, correspondant à la nouvelle base, soit tel que ses boucles les plus externes représentent le ``temps'' et les plus internes l'``espace''. Toutes les opérations d'une itération des boucles sur le temps peuvent s'exécuter au même moment ; les boucles sur l'espace décident des processeurs sur lesquels s'effectuent ces opérations. Les boucles sur le temps sont donc des boucles séquentielles et celles sur l'espace des boucles parallèles. Un exemple de parallélisation par la méthode géométrique est donnée en 5.5.

4.4

Les modèles de machines parallèles

Il existe un grand nombre de modèles de machines parallèles différentes. En toute théorie, le modèle d'une machine est défini :

par le type et le nombre de ses processeurs généraux (e.g. quelques processeurs vectoriels pour un Cray Y-MP, de nombreux SPARC pour la CM-5) et la présence ou non de processeurs dédiés au calcul flottant (e.g. aucun pour un Cray Y-MP, 4 par SPARC pour la CM-5) ;
par le type de son réseau de contrôle (e.g. les processeurs 4 bits de la MasPar sont synchronisés, les iPSC/860 de l'Intel Paragon peuvent exécuter chacun un programme différent, enfin les SPARC de la CM-5 peuvent fonctionner dans les deux modes) ;
par le type d'accès à la mémoire dont elle dispose (la plupart des machines massivement parallèles proposent une mémoire globale, par contre la mémoire d'un réseau de stations est distribuée) ;
et par la topologie de son réseau d'interconnexion (e.g. un tore à 3 dimensions pour le Cray T3D ou un fat-tree pour la CM-5).

Pour compliquer le tableau, l'architecture de la machine virtuelle impliquée par les langages de programmation disponibles sur une machine peuvent différer de l'architecture réelle de la machine. Heureusement tous ces paramètres ne sont pas à prendre en compte dans le contexte de la parallélisation automatique. Les points importants pour ce domaine d'étude sont présentés par Paul Feautrier dans [30]. Il s'agit :

du type du réseau de contrôle ;
du type d'accès à la mémoire par les processeurs.

Cette classification définit quatre grandes classes de machines :

les machines synchrones à mémoire globale, il s'agit de machines exotiques ; les ASICs peuvent trouver une place dans cette catégorie ;
les machines SIMD telles la MasPar ;
les machines asynchrones à mémoire distribuée : les réseaux de stations en sont l'archétype ;
les machines asynchrones à mémoire globale : la plupart des machines massivement parallèles modernes font partie de cette catégorie (la CM-5, le Cray T3D, la KSR-1, etc.).

Dans cette thèse il est supposé implicitement que la machine cible est une machine à mémoire globale. Nous ne considérons donc que la catégorie des machines SIMD et celle des machines asynchrones à mémoire globale (puisqu'il n'y pas ici de confusion possible nous appellerons MIMD les machines de cette catégorie).

1: Un nid de boucles est un ensemble de boucles emboîtées.