1  Parallélisme

2  Pourquoi le parallélisme?

• Les microprocesseurs, les machines ne sont presque plus ``séquentielles''
• Les systèmes d'exploitation (UNIX...) font tourner en permanence des dizaines de tâches au moins
• Pour des raisons d'efficacité de calcul en temps et en mémoire, de plus en plus de programmes sont parallélisés (historiquement, chez les numériciens)
• Certains problèmes sont intrinsèquement parallèles ou distribués (grandes bases de données: transactions simultanées! etc.)

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

7  Mais subtil à programmer...

• Nouvelles primitives (® programmation)
• Nouveaux types de bugs, dans la coordination des tâches (® sémantique mathématique); exemple académique (trois philosophes qui dînent):
  
  
  
  
  
  
• Difficulté d'atteindre les performances crêtes (® algorithmique)

8  Programme

• Les ``threads'' en JAVA (rappel, et simulation modèles PRAM etc.)
• Les ``nouveaux'' problèmes liés au parallélisme (problème de coordination, exclusion mutuelle, points morts etc.)
• L'algorithmique parallèle de base (PRAM, complexité, réseaux de tri, algorithmes sur anneau etc.)
• L'ordonnancement de tâches
• Au delà du multitâche (``clusters'' de stations, distribution, RMI, JavaParty etc.)

9  Organisation

• Complémentaire du cours système, faisant suite au cours d'informatique fondamentale (avec quelques rappels)
• Cours suivis de TPs et de TDs (utilisation des threads JAVA)
• Ecrit
• Voir par exemple le cours de l'année dernière:
  
  http://www.enseignement.polytechnique.fr/profs/informatique/
  
  Eric.Goubault/ParaI.html et http://www.enseignement.polytechnique.fr/profs/informatique/
  
  Eric.Goubault/pvm.html

10  Plan de ce cours en particulier

• Introduction
• Modèles du parallélisme, une première approche
• Threads JAVA (rappels)

11  Introduction

12  Taxonomie de Tanenbaum:

13  Taxonomie de Tanenbaum (1):

14  Exemple

int A[100];
...
for (i=1;100>i;i++)
   A[i]=A[i]+A[i+1];

15  Taxonomie de Tanenbaum (2):

• (1) Parallèle (Connection Machine)
  
• (2) Systolique

16  Exemple

       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))

17  Exemple

18  Taxonomie de Tanenbaum (3):

19  Exemple

FOR  i:=1 to n DO
   R(a+b*i):=A(a'+b'*i)+B(a''+b''*i);

20  Exemple

21  Taxonomie de Tanenbaum (4):

• (1) Mémoire partagée (Sequent)
  
• (2) Mémoire locale + réseau de communication (Transputer, Connection Machine, local, par réseau d'interconnexion) - Système réparti

22  Mémoire Partagée

23  Mémoire Partagée

• Barrières de synchronisation,
• Sémaphores : deux opérations P et V.
• Verrou (mutex lock) : sémaphore binaire qui sert à protéger une section critique.
• Moniteurs : construction de haut niveau, verrou implicite.

24  Machine distribuée

25  Machine distribuée

• Appel de procédure distribuée (RPC ou RMI en ce qui nous concernera) :
  • réponse synchrone
  • réponse asynchrone
• Envoi/Réception de message asynchrone (tampon de taille limitée ou non); active polling ou gestion à l'arrivée par une procédure handler.
• Envoi/Réception de message synchrone : rendez-vous.
• Mélange des deux derniers cas.

26  Exemple -- Clients/Serveurs

27  Remarques

28  Programmation parallèle:

• (1) Language séquentiel: le compilateur parallélise (Fortran...), voir fin du poly d'Y. Robert
  
• (2) Constructions parallèles explicites (Parallel C, Occam...)

29  Constructions parallèles explicites

• Création de parallélisme,
  • Itération simultanée sur tous les processeurs (FOR parallèle de Fortran),
  • Définition d'un ensemble de processus (COBEGIN),
  • Création de processus (FORK de Unix)
• Contrôle du parallélisme,
  • Synchronisation (Rendez-vous d'Ada),
  • Passage de messages (synchrones/asynchrones, broadcast,...),
  • Section critiques (gestion de la mémoire partagée),
  • Stopper une exécution parallèle (COEND, WAIT d'Unix)

30  Processus (MIMD)

• sa propre pile de données,
• son compteur ordinal,
• éventuellement sa mémoire locale

31  Constructions parallèles explicites (suite):

32  Constructions parallèles explicites (suite):

• X dit à Y: ``Donne moi ton nom et je te dirai le mien''. Y dit la même chose à X. Ceci est une situation d'interblocage.
• X et Y veulent tous deux utiliser un objet. X est plus rapide qu'Y et obtient régulièrement l'utilisation de cet objet avant Y qui ne l'obtient jamais. On dit que Y est en situation de famine.

33  Constructions parallèles explicites (suite):

34  Réseaux de stations

35  Architectures hybrides

36  Threads JAVA

• Concept répandu mais annexe dans d'autres langages de programmation (C ou C++ par exemple),
• Concept intégré dans JAVA (mais aussi ADA)
• Thread = ``Thread of Control'', processus léger etc.
• un Thread est un programme séquentiel, avec sa propre mémoire locale, s'exécutant en même temps, et sur la même machine virtuelle JAVA, que d'autres threads
• communication à travers une mémoire partagée (ainsi que des méthodes de synchronisations)

37  Utilité des threads

• Plus grande facilité d'écriture de certains programmes (extension de la notion de fonction)
• Systèmes d'exploitation
• Interfaces graphiques
• Ordinateurs multi-processeurs (bi-pentium etc.)

38  Création

• on peut configurer Proc, par exemple lui associer une priorité,
• on peut l'exécuter en invoquant la méthode start du thread,

39  Exécution

• start() va à son tour invoquer la méthode run du thread (qui ne fait rien par défaut)
• C'est possible par exemple si on définit Proc comme une instance d'une sous-classe de Thread, dans laquelle on redéfinit la méthode run.
• Les variables locales sont des champs de cette sous-classe.

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

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

43  Remarques

• Les entiers valeur sont distincts dans les deux threads qui s'exécutent. C'est une variable locale au thread.
• Si on avait déclaré static int valeur, cette variable aurait été partagée par ces deux threads (durée de vie=celle des threads).
• Si on avait déclaré Integer valeur (``classe enveloppante'' de int), cette classe aurait été partagée par tous les threads et aurait une durée de vie éventuellement supérieure à celle des threads

44  Arrêt

• méthode stop() (dangereux et n'existe plus en JAVA 2),
• méthode sleep(long) (suspension du thread pendant un certain nombre de nanosecondes)

45  Mais...

• Pas d'héritage multiple en JAVA, donc on ne peut pas hériter de Thread et d'une autre classe en même temps,
• Il est alors préférable d'utiliser l'interface Runnable.

46  L'interface Runnable

• L'interface Runnable représente du code exécutable,
• Elle ne possède qu'une méthode, public void run();
• Par exemple la classe Thread implémente l'interface Runnable.
• Mieux encore, on peut construire une instance de Thread à partir d'un objet qui implémente l'interface Runnable par le constructeur: public Thread(Runnable target);

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

• isAlive() renvoie un booléen indiquant si un thread est encore vivant (après que start() se soit exécuté, et avant la fin normale ou imposée par stop()),

50  Déterminer la terminaison d'un thread

• void join() (comme sous Unix) attend la terminaison d'un thread.
• Egalement: void join(long timeout) attend au maximum timeout millisecondes.
• Par exemple:

  public class ... extends Thread {
     ...
     public void stop() {
        t.shouldRun=false;
        try {
           t.join();
        } catch (InterruptedException e) {}   } }
  

51  Nommer les threads

• void setName(String name) nomme un thread: utile essentiellement pour le debugging (toString() renvoie ce nom)
• String getName() renvoie le nom du thread.

52  Informations sur les threads

• static Thread currentThread() renvoie la référence au Thread courant c'est-à-dire celui qui exécute currentThread(),
• static int enumerate(Thread[] threadArray) place tous les threads existant (y compris le main() mais pas le thread ramasse-miettes) dans le tableau threadArray et renvoie leur nombre.
• static int activeCount() renvoie le nombre de 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 L^AT_EX by H^EV^EA.