Parallélisme et distribution

Plan :

1 Avant-Propos 7 2 Introduction 9 2.1 Une classication des machines paralleles . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.1 Machine SISD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.2 Machine SIMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.3 Machine MISD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.4 Machine MIMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.5 Gain d'ecacite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Contr^ole d'une machine parallele . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3 Threads Java 15 3.1 Introduction aux threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Les threads en JAVA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2.1 Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2.2 Partage des variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.3 Quelques fonctions elementaires sur les threads . . . . . . . . . . . . . . . . 18 3.3 Elements avances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.1 Priorites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.2 Ordonnancement des t^aches JAVA . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.3 Les groupes de processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4 Modele PRAM 23 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 Technique de saut de pointeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Circuit Eulerien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4 Theoremes de simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.5 Tris et reseaux de tris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5 Coordination de processus 33 5.1 Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.2 Une solution : synchronized . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3 Moniteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.4 Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.4.1 Semaphores binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.4.2 Un peu de semantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.4.3 Un complement sur la JVM . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.4.4 Quelques grands classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.4.5 Semaphores a compteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.5 Barrieres de synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.6 Un exemple d'ordonnancement : sequentialisation . . . . . . . . . . . . . . . . . . . 52 3 4 TABLE DES MATI ERES 6 Algorithmes d'exclusion mutuelle (memoire partagee) 59 6.1 Peut-on se passer de synchronized? . . . . . . . . . . . . . . . . . . . . . . . . . . 59 6.2 Premiers algorithmes ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.3 Algorithme de Dekker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 6.4 Algorithme de Peterson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7 Problemes d'ordonnancement 73 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.2 Nids de boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.3 Dependance des donnees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.3.1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.3.2 Calcul des dependances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.3.3 Approximation des dependances . . . . . . . . . . . . . . . . . . . . . . . . 75 7.4 Transformations de boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 7.4.1 Distribution de boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 7.4.2 Fusion de boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 7.4.3 Composition de boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 7.4.4 Echange de boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 7.4.5 Deroulement de boucle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7.4.6 Rotation de boucle [skewing] . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7.4.7 Exemple de parallelisation de code . . . . . . . . . . . . . . . . . . . . . . . 79 7.5 Algorithme d'Allen et Kennedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 8 Communications et routage 83 8.1 Generalites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 8.2 Routage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 8.3 Algorithmique sur anneau de processeurs . . . . . . . . . . . . . . . . . . . . . . . 84 8.3.1 Hypotheses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 8.3.2 Probleme elementaire : la diusion . . . . . . . . . . . . . . . . . . . . . . . 85 8.3.3 Diusion personnalisee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8.3.4 Echange total . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 8.3.5 Diusion pipelinee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 8.4 Election dans un anneau bidirectionnel . . . . . . . . . . . . . . . . . . . . . . . . . 90 8.4.1 Algorithme de Le Lann, Chang et Roberts (LCR) . . . . . . . . . . . . . . 91 8.4.2 Algorithme de Hirschberg et Sinclair (HS) . . . . . . . . . . . . . . . . . . . 91 8.5 Communications dans un hypercube . . . . . . . . . . . . . . . . . . . . . . . . . . 94 8.5.1 Chemins dans un hypercube . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 8.5.2 Plongements d'anneaux et de grilles . . . . . . . . . . . . . . . . . . . . . . 94 8.5.3 Diusion simple dans l'hypercube . . . . . . . . . . . . . . . . . . . . . . . . 95 9 Remote Method Invocation 97 9.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 9.2 Exemple : RMI simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 9.3 RMI avec Callback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 9.4 RMI avec reveil de serveur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 9.4.1 Exemple d'une \lampe" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 9.4.2 Complement : politiques de securite . . . . . . . . . . . . . . . . . . . . . . 110 9.5 CORBA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .