Cours Parallélisme et distribution en PDF (Avancé)

Parallélisme et Distribution. Discipline qui étudie les méthodes et algorithmes permettant d'exécuter des calculs en parallèle sur plusieurs unités de traitement et d'organiser la coopération entre machines distantes, en combinant aspects théoriques (modèles PRAM, preuves de correction) et pragmatiques (implémentation en Java, RMI). Sujet central pour le calcul haute performance, les systèmes distribués et la tolérance aux pannes, il lie optimisation du débit, minimisation de la latence et garanties de cohérence entre processus. Téléchargez le PDF pour accéder au texte complet et aux exemples fournis.

🎯 Ce que vous allez apprendre

• Programmation concurrente avec threads Java

  Description des primitives de création et de gestion de threads, cycle de vie et ordonnancement pour maîtriser la mémoire partagée sur la JVM. L'étudiant saura écrire et déboguer sections critiques en utilisant synchronized, analyser le comportement de la JVM vis‑à‑vis des accès concurrents et éviter races et deadlocks.

• Primitives de synchronisation et modèles de coordination

  Étude des moniteurs, sémaphores (binaires et à compteur), barrières et du protocole 2PL. Indispensable pour concevoir protocoles de cohérence et transformer spécifications concurrentes en implémentations sûres et performantes.

• Modèle PRAM et techniques algorithmiques parallèles

  Compréhension du modèle PRAM (CRCW/CREW) et des techniques (saut de pointeur, théorèmes de simulation). Analyse de la complexité parallèle (accélération, efficacité, bisection) et transposition d'algorithmes séquentiels en versions PRAM adaptées aux machines réelles.

• Transformations de boucles et ordonnancement

  Dépendances de données, calcul et approximation des dépendances, puis transformations (distribution, fusion, échange, déroulement, skewing) et algorithme d'Allen & Kennedy pour extraire parallélisme et préparer le code à l'optimisation automatique ou manuelle.

• Topologies et routage pour architectures parallèles

  Principes de routage, algorithmes sur anneau et hypercube, diffusion et échange total, pipelines et plongements de grilles. Discussion sur le clustering de processeurs, l'allocation de tâches et l'optimisation des communications (échange de messages, MPI) pour minimiser congestion et latence.

• Algèbre linéaire parallèle et tolérance aux pannes

  Méthodes de produit matrice‑vecteur, factorisation LU parallèle (Cannon, Fox, Snyder), allocations cycliques et recouvrement communication/calcul. Introduction aux espaces simpliciaux et protocoles de décision pour assurer terminaison correcte malgré défaillances.

📑 Sommaire du document

• Avant-propos
• Introduction
• Threads Java
• Modèle PRAM
• Coordination de processus
• Algorithmes d’exclusion mutuelle (mémoire partagée)
• Problèmes d’ordonnancement
• Communications et routage

💡 Pourquoi choisir ce cours ?

Rédigé par Eric Goubault (Commissariat à l'Energie Atomique), ce document combine fondements théoriques et mises en œuvre pratiques : modèles abstraits (PRAM), preuves d'algorithmes et code d'illustration en Java. L'approche alterne démonstrations mathématiques, études d'algorithmes classiques (Dekker, Peterson, 2PL) et exemples applicatifs (RMI, exemple de "lampe"), facilitant le passage de la théorie à l'implémentation. Le texte couvre aussi des aspects souvent négligés comme le recouvrement communication/calcul et la géométrisation des tâches pour la tolérance aux pannes.

Le cours introduit la nécessité du parallélisme face aux limites physiques de la Loi de Moore : l'augmentation du nombre de cœurs et l'évolution des architectures rendent indispensable l'optimisation simultanée du débit et de la latence. Ce contexte matériel oriente les choix algorithmiques et les stratégies d'implémentation présentées dans le texte.

Métriques de performance

• Accélération (Speedup)
• Efficacité
• Extensibilité (Scalability)
• Loi d'Amdahl

Concepts de performance : Accélération et Efficacité

Mesurer le comportement d'un algorithme parallèle nécessite de distinguer la latence, le débit et l'efficacité de l'utilisation des ressources. La latence correspond au temps de réponse d'une opération, le débit au nombre d'opérations traitées par unité de temps. L'efficacité compare la speedup observée au nombre de ressources utilisées en tenant compte des coûts de synchronisation et communication. La Loi d'Amdahl sert de borne théorique pour l'accélération maximale donnée une fraction séquentielle du calcul.

• Latence : temps nécessaire pour compléter une opération individuelle, affectée par synchronisation et dépendances.
• Débit : nombre d'opérations complétées par unité de temps, indicateur de la scalabilité pratique.
• Efficacité : speedup normalisé par le nombre de processeurs, met en évidence les pertes dues à la communication et à l'ordonnancement.

👤 À qui s'adresse ce cours ?

• Public cible : étudiants en master, ingénieurs en calcul scientifique et systèmes distribués, développeurs d'applications parallèles et chercheurs souhaitant un panorama mêlant théorie et pratique.
• Prérequis : bonne maîtrise d'un langage impératif (idéalement Java), notions d'algorithmique et complexité, bases d'algèbre linéaire (produit matrice‑vecteur, LU) et familiarité avec mémoire partagée et passage de messages.

❓ Foire Aux Questions (FAQ)

Comment le document compare-t-it les modèles PRAM CRCW et CREW pour la JVM ? Le texte précise que la JVM n'implémente pas un CRCW complet mais ressemble plutôt à un modèle CREW : les lectures concurrentes sont autorisées tandis que les écritures concurrentes doivent être ordonnancées via des verrous ou sémaphores; les théorèmes de simulation présentent des méthodes pour mapper algorithmes PRAM sur machines réelles en tenant compte des coûts de communication et synchronisation.

Quand préférer des algorithmes de type Cannon/Fox pour la LU parallèle ? Les algorithmes de grille 2D (Cannon, Fox) sont recommandés pour matrices denses réparties sur une grille de processeurs afin d'optimiser le recouvrement communication/calcul et réduire le coût de synchronisation; le cours détaille aussi l'allocation cyclique et les stratégies pour architectures hétérogènes.