Previous Up Next

Chapter 2  Introduction

Ce chapitre est bien sûr loin d'être exhaustif. On n'y parle pratiquement pas de micro-parallélisme, c'est-à-dire du parallélisme au niveau des microprocesseurs. En effet la plupart des microprocesseurs modernes sont à eux seuls de véritables machines parallèles. Par exemple il n'est pas rare (Pentium, PowerPC etc.) d'avoir plusieurs unités de calcul arithmétique (dans le cas du Pentium, d'unités de calcul flottant, ou dans le cas des processeurs MIPS, plusieurs additionneurs, multiplieurs etc.) pouvant fonctionner en parallèle. On parle un peu plus loin du calcul en pipeline qui est courant dans ce genre d'architectures.

A l'autre bout du spectre, les projets les plus en vogue à l'heure actuelle, sont les immenses réseaux d'ordinateurs hétérogènes distribués à l'échelle d'internet, qui posent un certain nombre de problèmes théoriques et pratiques. On pourra se reporter aux divers projets de ``metacomputing'', voir par exemple
http://www.metacomputing.org/
et le projet ``GRID'', voir par exemple http://www.gridforum.org/. Il existe un projet de grille national (GRID'5000) pour lequel vous pouvez trouver des documents sur le web. Il est coordonné par Franck Cappello au LRI (à l'Université d'Orsay).

2.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 Flynn-Tanenbaum): SISD, SIMD, MISD et MIMD. 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'').

2.1.1  Machine SISD

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

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.

2.1.2  Machine SIMD

Une machine SIMD (Single Instruction Multiple Data) est une machine qui exécute à tout instant une seule instruction, mais qui agit en parallèle sur plusieurs données, on parle en général de ``parallélisme de données''. Les machines SIMD peuvent être de plusieurs types, par exemple, parallèles ou systoliques.

Les machines systoliques sont des machines SIMD particulières dans lesquelles le calcul se déplace sur une topologie de processeurs, comme un front d'onde, et acquiert des données locales différentes à chaque déplacement du front d'onde (comportant plusieurs processeurs, mais pas tous en général comme dans le cas (1)).

En général dans les deux cas, 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 (cas (1)) écrit en CM-Fortran sur la Connection Machine-5 avec 32 processeurs, 
       INTEGER I,J,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 dans 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 2.1). Ceci grâce à la directive LAYOUT qui indique à CM-Fortran que les calculs concernant la deuxième dimension de A s'effectueront en séquentiel tandis que ceux concernant la première dimension se feront en parallèle.

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

2.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 ``pipeline'' 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. Par contre, certaines instructions comme les branchements conditionnels forcent généralement à vider le pipeline, avant d'être exécutées. L'efficacité s'en trouve alors fortement diminuée.

2.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. Ici, chaque processeur peut exécuter un programme différent sur des données différentes. On a plusieurs types d'architecture possibles: C'est le cas (1) que l'on va voir plus particulièrement avec JAVA. On pourra également simuler le cas (2). Pour le cas (2) (en PVM et MPI) et en particulier pour des applications au calcul scientifique, on pourra se reporter par exemple au cours [GNS00].

Parce qu'il n'est en général pas nécessaire d'utiliser des programmes différents pour chaque processeur, on exécute souvent le même code sur tous les noeuds d'une machine MIMD mais ceux-ci ne sont pas forcément synchronisés. On parle alors de modèle SPMD (Single Program Multiple Data).

Mémoire Partagée:


Figure 2.2: Architecture simplifiée d'une machine à mémoire partagée.

Une machine MIMD à mémoire partagée est principalement constituée de processeurs avec des horloges indépendantes, donc évoluant de façon asynchrone, et communicant 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 2.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 quatre 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,R1
LOAD x,R2 LOAD x,R1 WRITE x,1 LOAD x,R2
WRITE x,1 LOAD x,R2 LOAD x,R2 WRITE x,R1+R2
WRITE x,R1+R2 WRITE x,R1+R2 WRITE x,R1+R2 WRITE x,1
Résultat x=0 Résultat x=2 Résultat x=1 Résultat x=1

Cela n'est évidemment pas très satisfaisant; il faut rajouter des synchronisations pour choisir tel ou tel comportement. Cela est en particulier traité à la section 5.6.

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 les verra par la suite en long, en large et en travers, en particulier à la section 5.4). 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 la manipuler, et ainsi en interdisant l'accès pendant ce temps. 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). Tout cela sera encore traité à la section 5.4.2.

Mémoire distribuée

L'emploi d'autres mécanismes de communication que la mémoire partagée pour une machine MIMD est dû à plusieurs choses: par exemple, les processeurs peuvent être physiquement trop éloignés pour qu'un partage de petites quantités d'information 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 car il n'est techniquement pas possible de connecter un très grand nombre de processeurs directement à une même mémoire.

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 2.3). On verra au chapitre 9.3 la programmation correspondante en JAVA (à travers les RMI).
2cm
Figure 2.3: Architecture Client/Serveur (RPC).

2.1.5  Gain d'efficacité

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) est rarement atteint et, en pratique, le parallélisme est 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 réalité, la situation est très hybride.

2.2  Contrôle d'une machine parallèle

Il y a deux méthodes principales, On pourra se reporter à [Rob00] et [GNS00] pour les techniques utilisées par les compilateurs dans le cas (1). On en traitera un petit aspect au chapitre 7. On se concentre ici principalement sur le deuxième cas. Il faut alors disposer de primitives (ou instructions) pour:
Previous Up Next