Parallélisme et Distribution - Optimiser les Performances

Objectifs d'apprentissage

• Comprendre les concepts fondamentaux du parallélisme et de la distribution dans les systèmes informatiques.
• Maîtriser la programmation multithread en Java et les mécanismes de synchronisation.
• Appliquer le modèle PRAM (Parallel Random Access Machine) pour analyser des algorithmes parallèles.
• Étudier les techniques de coordination de processus et les algorithmes d'exclusion mutuelle en mémoire partagée.
• Résoudre des problèmes d'ordonnancement dans des environnements parallèles et distribués.
• Explorer les protocoles de communication et de routage dans les réseaux distribués.
• Utiliser la technologie RMI (Remote Method Invocation) pour développer des applications distribuées.
• Appliquer des méthodes d'algèbre linéaire parallèle pour résoudre des problèmes à grande échelle.
• Concevoir des systèmes tolérants aux pannes pour assurer la robustesse des applications distribuées.

Public cible

Ce cours s'adresse aux étudiants en informatique de niveau avancé (licence 3 ou master), ainsi qu'aux professionnels souhaitant approfondir leurs connaissances en calcul parallèle et systèmes distribués. Une maîtrise des bases de la programmation (notamment en Java) et des concepts fondamentaux d'algorithmique est requise. Le cours convient également aux ingénieurs en informatique désireux de se spécialiser dans l'optimisation des performances ou le développement d'applications haute disponibilité.

Contenu détaillé

Avant-Propos

Introduction générale aux enjeux du parallélisme et de la distribution, avec un aperçu historique de l'évolution des architectures multi-cœurs et des réseaux distribués. Présentation des défis actuels en termes de scalabilité et de performance.

Introduction

Différences entre parallélisme (traitement simultané sur une même machine) et distribution (traitement réparti sur plusieurs machines). Métriques de performance : speedup, efficacité, surcoût de communication. Exemples concrets d'applications parallèles et distribuées.

Threads Java

Détail de l'API java.lang.Thread, états d'un thread (new, runnable, blocked, terminated). Synchronisation via synchronized, wait/notify, et les locks du package java.util.concurrent. Étude des problèmes classiques (interblocages, starvation) et bonnes pratiques.

Modèle PRAM

Présentation du modèle théorique PRAM (EREW, CREW, CRCW) et son utilisation pour l'analyse d'algorithmes parallèles. Exemples d'algorithmes (somme préfixée, tri) et complexité en temps/logique.

Coordination de processus

Algorithmes de rendez-vous et d'élection (ex : algorithme de Peterson). Problèmes classiques (producteur-consommateur, lecteurs-rédacteurs) et solutions utilisant des sémaphores ou des moniteurs.

Algorithmes d'exclusion mutuelle

Implémentations matérielles (test-and-set, compare-and-swap) et logicielles (algorithmes de Dekker, Bakery). Preuves de correction (sûreté, vivacité). Impact sur les performances des caches (faux partage).

Problèmes d'ordonnancement

Ordonnancement statique vs dynamique. Algorithmes pour systèmes homogènes/hétérogènes (round-robin, work stealing). Théorie de l'ordonnancement (graphes de tâches, NP-complétude).

Communications et routage

Protocoles de message passing (MPI, PVM). Routage dans les réseaux maillés (dimension ordering). Modèles de performance (latence, bande passante, modèle LogP).

Remote Method Invocation

Architecture RMI : stub, skeleton, registry. Sérialisation d'objets et gestion des exceptions distantes. Sécurité (politiques RMISecurityManager). Alternatives modernes (gRPC, REST).

Algèbre linéaire

Décomposition matricielle parallèle (LU, QR). Produit matriciel en blocs. Bibliothèques standards (BLAS, ScaLAPACK). Applications en machine learning distribué.

Systèmes tolérants aux pannes

Techniques de réplication (état-machine, quorums). Consensus distribué (Paxos, Raft). Vérification formelle (model checking). Études de cas (bases de données distribuées, blockchains).

Méthodologie

Le cours combine théorie (30%) et pratique (70%) via des TP sur machines multicœurs et clusters. Un projet final implémente une application distribuée réelle avec benchmarking. Évaluation par contrôle continu (projets) et examen final (analyse d'algorithmes).