Parallélisme et distribution

Parallélisme et distribution

Publié le 21 févr. 2011 - Donne ton avis

Le but de ce cours est de donner une idee de la programmation, algorithmique et semantique de systemes paralleles et distribues. Pour y arriver, on utilise un biais dans un premier temps, qui nous permettra d'aborder les principaux themes du domaine. On va utiliser le systeme de \threads" de JAVA pour simuler des processus paralleles et distribues. Plus tard, on utilisera d'autres fonctionnalites de JAVA, comme les RMI, pour e ectuer veritablement des calculs en parallele sur plusieurs machines. Les \threads" en tant que tels sont une premiere approche du parallelisme qui peut m^eme aller jusqu'au \vrai parallelisme" sur une machine multi-processeurs
Photo de profil de hallouma21
Fiche rédigée par
hallouma21
3 téléchargements

Ce document est-il utile ?

-- / 20

Contenu de ce document de Informatique > Programmation

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 di usion . . . . . . . . . . . . . . . . . . . . . . . 85 8.3.3 Di usion personnalisee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8.3.4 Echange total . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 8.3.5 Di usion 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 Di usion 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Il faut être inscrit pour télécharger un document

Crée un compte gratuit pour télécharger ce document

Je m'inscrisOU

J'ai déjà un compte

Je me connecte