1  Parallélisme

Eric Goubault

Commissariat à l'Energie Atomique

Saclay

2  Pourquoi le parallélisme?

Le parallélisme, d'exotique il y a encore peu, est devenu indispensable:

3  Au niveau d'un microprocesseur (Athlon)...


4  Au niveau d'une machine...


5  Au niveau d'un réseau de machines...


6  Une des machines les plus puissantes au monde


(IBM ASCI White, Lawrence Livermore National Laboratory, 2000, 8192 processeurs Power3 à 375Mhz: 12.3 teraflops! - simulation des armes thermonucléaires)

7  Mais subtil à programmer...

8  Programme

9  Organisation

10  Plan de ce cours en particulier

11  Introduction












Machine parallèle = ensemble de processeurs qui coopèrent et communiquent






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

12  Taxonomie de Tanenbaum:






Quatre types: SISD, SIMD, MISD et MIMD.









Basée sur les notions de flot de contrôle et flot de données.

13  Taxonomie de Tanenbaum (1):












Machine SISD = Single Instruction Single Data
  = Machine Von Neuman

14  Exemple

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.

15  Taxonomie de Tanenbaum (2):






Machine SIMD = Single Instruction Multiple Data

En général exécution synchrone

16  Exemple

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 sa propre tranche en même temps.

17  Exemple



18  Taxonomie de Tanenbaum (3):









Machine MISD = Multiple Instruction Single Data






Processeurs vectoriels, architectures pipelines

19  Exemple

Pipelinage d'une addition vectorielle,
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,

20  Exemple

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.                        

21  Taxonomie de Tanenbaum (4):






Machine MIMD = Multiple Instruction Multiple Data

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

22  Mémoire Partagée



23  Mémoire Partagée

Synchronisation par,

24  Machine distribuée



25  Machine distribuée

Synchronisation et échange d'information par,

26  Exemple -- Clients/Serveurs

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



27  Remarques









Architectures plus ou moins adaptées à certains problèmes.









Gain de temps espéré: au plus N (nombre de processeurs).




En pratique, parallélisme difficile à contrôler

28  Programmation parallèle:

29  Constructions parallèles explicites

30  Processus (MIMD)

Un Processus est une unité de programme séquentielle (abstraction d'un processeur) avec,









31  Constructions parallèles explicites (suite):








32  Constructions parallèles explicites (suite):

Synchronisation: but = assurer qu'à un moment donné tous les processus ont suffisament avancés leurs calculs.




Erreurs possibles: Interblocage (deadlock, livelock), Famine,... (cours 2 et 3)




Exemples:

33  Constructions parallèles explicites (suite):

MIMD mémoire partagée,




Erreurs possibles: incohérence des données.




Partant de x=0, on exécute x:=x+x en parallèle avec x:=1. Par exemple, on a ces trois exécutions possibles:

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




Pour y remédier, sections critiques et exclusion mutuelle.

34  Réseaux de stations

Pas d'horloge globale, mode MIMD, communication par passage de messages (typiquement gérés par PVM, MPI dans le monde numérique, voir,

- http://www-unix.mcs.anl.gov/mpi/

- http://www.csm.ornl.gov/pvm/pvm_home.html

) sur un réseau local ou d'interconnexion.

35  Architectures hybrides



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). Par exemple threads JAVA+RMI.

36  Threads JAVA

37  Utilité des threads

38  Création

Pour créer un thread, on crée une instance de la classe Thread,

Thread Proc = new Thread();

39  Exécution

40  Exemple

class Compte extends Thread {
   int valeur;

   Compte(int val) {
      valeur = val;
   }

   public void run() {
      try {

41  

         for (;;) {
            System.out.print(valeur + " ");
            sleep(100);
         }
      } catch (InterruptedException e) {
           return;
        }   
   }

   public static void main(String[] args) {
      new Compte(1).start();
      new Compte(2000).start();
   }
}

42  Exécution

L'exécution du programme main donne quelque chose comme,

> java Compte
1 2000 2000 1 1 1 1
^C
>

43  Remarques

44  Arrêt

45  Mais...

46  L'interface Runnable

47  Exemple

class Compte implements Runnable {
   int valeur;

   Compte(int val) {
      valeur = val;
   }

   public void run() {
      try {
         for (;;) {
            System.out.print(valeur + " ");
            sleep(100);
         }

48  Exemple

      } catch (InterruptedException e) {
           return;
        }   
   }

   public static void main(String[] args) {
      Runnable compte1 = new Compte(1);
      Runnable compte2 = new Compte(2000);
      new Thread(compte1).start();
      new Thread(compte2).start();
   }
}

49  Déterminer la terminaison d'un thread

50  Déterminer la terminaison d'un thread

51  Nommer les threads

52  Informations sur les threads

53  Exemple

class Compte3 extends Thread {
   int valeur;

   Compte3(int val) {
      valeur = val;
   }

   public void run() {
      try {
         for (;;) {
            System.out.print(valeur + " ");
            sleep(100);
         }

54  

      } catch (InterruptedException e) {
           return; } }

   public static void printThreads() {
      Thread[] ta = new Thread[Thread.activeCount()];
      int n = Thread.enumerate(ta);
      for (int i=0; i<n; i++) {
         System.out.println("Le thread "+ i + " est 
                            " + ta[i].getName());
      } } 

   public static void main(String[] args) {
      new Compte3(1).start();
      new Compte3(2000).start();
      printThreads(); } }

55  Exécution

% java Compte3
1 2000 Le thread 0 est main
Le thread 1 est Thread-2
Le thread 2 est Thread-3
1 2000 1 2000 1 2000 1 2000 2000 
1 1 2000 2000 1 1 2000 2000 1 1 
2000 2000 1 1 2000 2000 1 1 2000 
2000 1 1 2000 2000 1 1 ^C
%

This document was translated from LATEX by HEVEA.