Previous Next Contents

Chapter 1    Introduction au parallélisme

1.1  Une classification des machines parallèles

Une machine parallèle est essentiellement un ensemble de processeurs qui coopèrent et communiquent.

Historiquement, les premières machines parallèles sont des réseaux d'ordinateurs, et des machines vectorielles et faiblement parallèles (années 70 - IBM 360-90 vectoriel, IRIS 80 triprocesseurs, CRAY 1 vectoriel...).

On distingue classiquement quatre types principaux de parallélisme (Taxonomie de Tanenbaum): SISD, SIMD, MISD et MIMD. De nos jours cette classification peut paraître un peu artificielle car le moindre micro-processeur courant inclut lui-même plusieurs formes de micro-parallélisme. Elle permet néanmoins d'expliquer les bases de l'architectures des ordinateurs, séquentiels et parallèles. Cette classification est basée sur les notions de flot de contrôle (deux premières lettres, I voulant dire ``Instruction'') et flot de données (deux dernières lettres, D voulant dire ``Data'').

1.1.1  Machine SISD

Une machine SISD (Single Instruction Single Data) est ce que l'on appelle d'habitude une machine de Von Neuman. Une seule instruction est exécutée et une seule donnée (simple, non-structurée) est traitée à tout instant.

Le code suivant,

int A[100];
...
for (i=1;100>i;i++)
   A[i]=A[i]+A[i+1];
s'exécute sur une machine séquentielle en faisant les additions A[1]+A[2], A[2]

+A[3], etc., A[99]+A[100] à la suite les unes des autres.

1.1.2  Machine SIMD

Une machine SIMD (Single Instruction Multiple Data) peut être de plusieurs types, parallèle ou systolique. En général l'exécution en parallèle de la même instruction se fait en même temps sur des processeurs différents (parallélisme de donnée synchrone). Examinons par exemple le code suivant écrit en CM-Fortran sur la Connection Machine-5 avec 32 processeurs,

       INTEGER I,A(32,1000)
CMF$   LAYOUT A(:NEWS,:SERIAL)
       ...
       FORALL (I=1:32,J=1:1000) 
     $    A(I:I,J:J)=A(I:I,J:J)+A(I:I,(J+1):(J+1))
Chaque processeur i, 1 £ i £ 32 a en sa mémoire locale une tranche du tableau A: A(i,1), A(i,2), ..., A(i,1000). Il n'y a pas d'interférence dans le calcul de la boucle entre les différentes tranches: tous les processeurs exécutent la même boucle sur leur propre tranche en même temps (cf. figure 1.1).


Figure 1.1: Répartion d'un tableau sur les processeurs d'une machine SIMD typique

1.1.3  Machine MISD

Une machine MISD (Multiple Instruction Single Data) peut exécuter plusieurs instructions en même temps sur la même donnée. Cela peut paraître paradoxal mais cela recouvre en fait un type très ordinaire de micro-parallélisme dans les micro-processeurs modernes: les processeurs vectoriels et les architectures pipelines.

Un exemple de ``pipelinage'' d'une addition vectorielle est le suivant. Considérons le code:

FOR  i:=1 to n DO
   R(a+b*i):=A(a'+b'*i)+B(a''+b''*i);
A, B et R sont placés dans des registres vectoriels qui se remplissent au fur et à mesure du calcul,

Temps A ( i ) B ( i ) R ( i )
1 1 . . . 1 . . . . . . .
2 2 1 . . 2 1 . . . . . .
3 3 2 1 . 3 2 1 . . . . .
4 4 3 2 1 4 3 2 1 . . . .
5 5 4 3 2 5 4 3 2 1 . . .
6 6 5 4 3 6 5 4 3 2 1 . .
etc.

En ce sens, quand le pipeline est rempli, plusieurs instructions sont exécutées sur la même donnée.

1.1.4  Machine MIMD

Le cas des machines MIMD (Multiple Instruction Multiple Data) est le plus intuitif et est celui qui va nous intéresser le plus dans ce cours. On a plusieurs types d'architecture possibles:

C'est le cas (2) que l'on va voir plus particulièrement avec PVM. On pourra également simuler le cas (1)1 .

Mémoire Partagée:


Figure 1.2: Architecture simplifiée d'une machine à mémoire partagée
Une machine MIMD à mémoire partagée2 est principalement constituée de processeurs avec des horloges indépendantes, donc évoluant de façon asynchrone, et communiquant en écrivant et lisant des valeurs dans une seule et même mémoire (la mémoire partagée). Une difficulté supplémentaire, que l'on ne décrira pas plus ici, est que chaque processeur a en général au moins un cache de données (voir figure 1.2), tous ces caches devant avoir des informations cohérentes aux moments cruciaux.

La synchronisation des exécutions des processeurs (ou processus, qui en est une ``abstraction logique'') est nécessaire dans certains cas. Si elle n'était pas faite, il y aurait un risque d'incohérence des données. Partant de x=0, exécutons x:=x+x en parallèle avec x:=1. On a alors essentiellement trois exécutions possibles (en supposant chacune des affectations compilées en instructions élémentaires insécables, ou ``atomiques'', comme suit):

LOAD x,R1 WRITE x,1 LOAD x,R1
LOAD x,R2 LOAD x,R1 WRITE x,1
WRITE x,1 LOAD x,R2 LOAD x,R2
WRITE x,R1+R2 WRITE x,R1+R2 WRITE x,R1+R2
Résultat x=0 Résultat x=2 Résultat x=1

Cela n'est évidemment pas très satisfaisant; il faut rajouter des synchronisations pour choisir tel ou tel comportement, et en tout cas éviter le troisième comportement en général. Les deux premiers sont acceptables en un certain sens, ils sont deux possibles séquentialisations des processus parallèles.

La synchronisation peut se faire par différents mécanismes:

Les opérations P et V sur les sémaphores sont parmi les plus classiques et élémentaires. On peut considérer qu'à chaque variable partagée x dans la mémoire est associé un ``verrou'' (du même nom) indiquant si un processus est en train de manipuler la variable, en interdisant son accès. L'opération Px exécutée par un processus verrouille ainsi son accès exclusif à x. L'opération Vx ouvre le verrou et permet à d'autres processus de manipuler x à leur tour.

La encore des erreurs sont possibles, en voulant trop synchroniser par exemple. Il peut y avoir des cas d'interblocage (deadlock, livelock) en particulier.

Supposons qu'un processus T1 ait besoin (pour effectuer un calcul donné) de verrouiller puis déverrouiller deux variables x et y dans l'ordre suivant: P x puis P y puis Vx puis Vy alors qu'un autre processus, en parallèle, désire faire la séquence P y, P x puis V y et enfin Vx. En fait les deux processus peuvent s'interbloquer l'un l'autre si T1 acquiert x (respectivement T2 acquiert y) puis attend y (respectivement x).

Machine distribuée

En général, l'emploi d'autres mécanismes de communication que la mémoire partagée pour une machine MIMD est due au fait que les processeurs sont physiquement trop éloignés pour qu'un partage de petites informations soit raisonnable. Par exemple, le réseau Internet permet de considérer en un certain sens, tous les ordinateurs reliés comme étant un seul et même ordinateur distribué, où les processeurs travaillent de façon asynchrone et où les informations transitent par passage de message. Un certain nombre de super-calculateurs travaillent par échange de messages également.

De façon générale, la synchronisation et l'échange d'information peuvent se faire par,

Le protocole RPC (``Remote Procedure Call'') entre machines UNIX avec réseau Ethernet est un exemple de programmation MIMD (cf. figure 1.3).


Figure 1.3: Architecture Client/Serveur (RPC)

1.1.5  Conclusion

Les architectures sont plus ou moins bien adaptées à certains problèmes. En fait, le gain de temps espéré, qui est d'au plus N (nombre de processeurs)3 est rarement atteint et, en pratique, parallélisme difficile à contrôler. Enfin, pour revenir à notre première remarque sur la taxonomie de Tanenbaum, il y a de plus en plus rarement une distinction tranchée entre le modèle mémoire partagée et celui par passage de messages; dans la realité, la situation est très hybride.

1.2  Contrôle d'une machine parallèle

Il y a deux méthodes principales,

On verra brièvement les techniques pour le cas (1) à la section 7.2. On se concentre ici principalement sur le deuxième cas. Il faut alors disposer de primitives (ou instructions) pour:


Figure 1.4: Représentation simplifiée du flot d'exécution dans le cas d'un COBEGIN/COEND

1.3  Quelques exemples de machines parallèles

Dans cette section, l'objectif est de donner une idée des super-calculateurs utilisés dans le monde industriel et du calcul scientifique.

1.3.1  La Connection Machine-5

Elle est composée de, Plusieurs modèles (voir figure 1.5) ont été installés en France, dont un à l'ETCA (32 noeuds, 2 processeurs de contrôle, 1 Go de RAM, 16 Go de disques, 4 Gflops crête, mai 1993).


Figure 1.5: Une Connection-Machine 5
Elle peut fonctionner en,

1.3.2  Cray T3E

La machine la plus puissante chez CRAY, deux types de modèles, refroidissement à air (pas plus de 128 processeurs) ou par un liquide (jusqu'à 2048 processeurs). Pour les deux types de modèles on peut avoir des configurations (voir figures 1.6 et 1.6):

Performance de crête de 9.6 GFlops à 1.2 TFlops, jusqu'à 4 To de mémoire vive.


Figure 1.6: Deux Cray T3E
Il peut être utilisé,

1.3.3  IBM SP2

L'IBM RISC/6000 Scalable POWERparallel System (SP) est constitué de (voir figure 1.7):

Figure 1.7: Un IBM SP2

1.3.4  Réseaux de stations

Un réseau de stations fonctionne en mode MIMD avec une communication par passage de messages (typiquement gérés par PVM) sur un réseau local ou d'interconnexion.

En fait, un réseau de stations est souvent une architecture hybride dans le sens où il peut y avoir combinaison sur un réseau local de stations et de machines multiprocesseurs (elles-même gérant leur parallélisme interne par mémoire partagée ou par bus ou réseau). PVM peut également gérer ce genre d'architecture.

1.3.5  Top 500

Il est établi régulièrement une liste des 500 machines les plus puissantes, voir à ce propos http://www.top500.org. La puissance est mesurée par un benchmark d'algèbre linéaire, indiquée ci-dessous par le nombre Rmax, qui est la performance en Gflop/s pour le problème le plus gros programmé sur l'ordinateur. En novembre 1999 on trouvait:

Rang Constructeur Ordinateur Rmax
1 Intel ASCI Red 2379.6
2 IBM ASCI Blue-Pacific SST, IBM SP 604e 2144
3 SGI ASCI Blue Mountain 1608
4 Cray/SGI T3E1200 891.5
5 Hitachi SR8000/128 873.6
... ... ... ...
9 Cray/SGI T3E1200 671.2
... ... ... ...
32 Fujitsu VPP5000/31 286.9

Et les domaines d'applications et sites d'installation correspondants:

Rang Site Domaine
1 Sandia National Labs, USA Recherche
2 Lawrence Livermore National Laboratory, USA Recherche, Energie
3 Los Alamos National Laboratory, USA Recherche
4 Gouvernement, USA Secret
5 Université de Tokyo, Japon Académique
... ... ...
9 Deutscher Wetterdienst, Germany Recherche, Météo
... ... ...
32 Météo-France, France Recherche, Météo

Pour avoir une idée des puissances requises selon les domaines d'application, on pourra se reporter à [CS98]. En quelques mots, il faut savoir que la prévision météorologique à deux jours demande environ 100 Mégaoctets de mémoire et 100 Mégaflops, pour 3 jours il faut compter environ 1 Gigaoctet pour environ 10 Gigaflops. Le design d'une molécule pharmaceutique nécessite à l'heure actuelle environ 10 Gigaoctets pour 100 Gigaflops.

1
On se reportera à ce propos à la section 7.1.3.
2
C'est ce qui est simulé par exemple par les threads JAVA, sur un seul processeur.
3
Il existe néanmoins des problèmes avec gains moyens supérieurs (recherche distribuée).
Previous Next Contents