Aller au contenu

PRPA23 · Programmation parallèle distribuée

L'UE la plus importante que puisse choisir un apprenti. C'est le seul enseignement de MPI de tout le cursus FISA, et il n'y a pas de rattrapage plus tard : aucune UE des semestres suivants ne reprend le sujet.

Fiche signalétique
Code PRPA23 (modules IMPI23 et PMPI23)
Crédits 4 ECTS, 42 h
Semestre 3, option — mardi après-midi
Responsable JAEGER Julien
Concurrentes sur le créneau PRFO23, PRST23
Choix Une seule option au S3, avec l'accord de l'entreprise
Prérequis Programmation C/C++ nécessaire
Effectif max 30

Ce que dit la brochure

Objectifs cités :

« Les thèmes et compétences abordés dans cette UE sont la programmation parallèle en mémoire distribuée pour le calcul haute performance à l'aide du modèle de programmation MPI. Dans cette UE, nous aborderons tous les aspects de la programmation parallèle par passage de message, que ce soit l'utilisation de l'API, les algorithmes sous-jacents présents dans les implémentations de cette API, et les détails à prendre en compte pour réaliser un code MPI efficace. »

Module 1 · IMPI23, introduction à MPI :

  • introduction à l'API MPI ;
  • échanges de messages par communications en point à point ;
  • échanges de messages par communications collectives ;
  • échanges de messages par communications collectives avancées ;
  • description et utilisation des types dérivés ;
  • travaux dirigés de mise en œuvre.

Module 2 · PMPI23, programmation MPI avancée :

  • lectures et écritures parallèles de fichiers avec MPI-IO ;
  • échanges de messages par communications unidirectionnelles (RMA) ;
  • introduction aux réseaux rapides ;
  • description des topologies réseaux ;
  • astuces pour produire un programme MPI efficace ;
  • travaux dirigés.

Sur les grilles de compétences

La brochure FISA ne publie pas de grille de compétences par UE, contrairement à la brochure de la formation sous statut étudiant. Les cotations « Expert / Maîtrise / Intermédiaire » citées dans les éditions précédentes de ce document n'ont donc pas d'équivalent ici.

Ce que ça vaut pour le HPC

Décisif, sans réserve. Trois éléments du programme sont particulièrement remarquables pour une UE de deuxième année.

1. « Les algorithmes sous-jacents présents dans les implémentations de cette API ». La plupart des cours de MPI enseignent l'API et s'arrêtent là. Savoir comment un MPI_Bcast est implémenté — en arbre binomial, en scatter suivi d'un allgather, en chaîne pipelinée selon la taille du message — change la manière dont on écrit le code. On cesse de considérer les collectives comme des boîtes noires, et on comprend pourquoi la même collective coûte différemment selon la taille et le nombre de rangs.

2. Les types dérivés. Sous-estimés et sous-enseignés. Ils permettent d'échanger une colonne d'une matrice stockée en lignes en un seul appel, sans tampon intermédiaire. C'est la différence entre un code de décomposition de domaine élégant et un enfer de recopies manuelles.

3. Les RMA et MPI-IO. Les communications unidirectionnelles (MPI_Put, MPI_Get, MPI_Win) sont le modèle de programmation qui monte, parce qu'il s'appose mieux aux réseaux modernes qui font du RDMA en matériel. MPI-IO est la seule manière correcte d'écrire un gros fichier depuis mille processus. Les deux sujets sont rarement abordés au niveau licence ou master 1.

La partie « réseaux rapides et topologies » est celle qui manque le plus souvent ailleurs. Comprendre la différence entre un fat-tree, un dragonfly et un tore, et savoir que le placement des rangs sur les nœuds change les performances d'un facteur deux, est une compétence de compétiteur.

Arriver prêt

Avant le premier cours, ⏱ 8 h :

  1. Installer une implémentation MPI sur votre machine — OpenMPI ou MPICH — et faire tourner un « hello world » sur quatre processus. Le seul fait de comprendre mpicc, mpirun -np 4 et la différence entre rank et size vous fera gagner la première séance.
  2. Réviser les pointeurs et la mémoire en C. MPI est une API C, elle passe des adresses et des tailles en octets. Si void*, sizeof et l'arithmétique de pointeurs vous gênent, réglez cela d'abord.
  3. Lire le chapitre 1 de Using MPI (Gropp, Lusk, Skjellum), qui pose le modèle de passage de messages en une vingtaine de pages.

Ressources

Priorité 1 — à lire absolument

  • William Gropp, Ewing Lusk, Anthony Skjellum, Using MPI: Portable Parallel Programming with the Message-Passing Interface, 3ᵉ éd., MIT Press, 2014. Le livre de référence, écrit par les auteurs de MPICH et co-auteurs du standard. Couvre tout IMPI23 et une partie de PMPI23.
  • Les supports de cours MPI de l'IDRIS, en français, librement téléchargeables sur idris.fr/formations/mpi/. C'est de loin la meilleure documentation francophone sur MPI : plusieurs centaines de diapositives avec schémas de communication et exercices corrigés. Fait, consulté le 17 septembre 2026.
  • Le standard MPI lui-même, sur mpi-forum.org. Contre-intuitivement, c'est très lisible : chaque fonction est spécifiée avec ses arguments, ses conditions d'erreur et des exemples. Prenez l'habitude d'y vérifier une sémantique plutôt que de deviner.

Priorité 2 — pour PMPI23

  • William Gropp, Torsten Hoefler, Rajeev Thakur, Ewing Lusk, Using Advanced MPI: Modern Features of the Message-Passing Interface, MIT Press, 2014. Le volume qui traite RMA, MPI-IO, les communicateurs, les topologies et les types dérivés avancés. C'est exactement le programme de PMPI23.
  • Les documentations d'OpenMPI (open-mpi.org/doc) et de MPICH, notamment les pages sur le réglage des composants de transport (btl, mtl, pml sous OpenMPI). C'est là qu'on apprend à changer d'algorithme de collective par variable d'environnement.
  • Les OSU Micro-Benchmarks (mvapich.cse.ohio-state.edu) : la suite de référence pour mesurer latence et bande passante MPI, point à point et collectives. Indispensable en compétition.

Priorité 3 — pour aller plus loin

  • Peter Pacheco, Matthew Malensek, An Introduction to Parallel Programming, 2ᵉ éd., Morgan Kaufmann, 2021. Plus pédagogique que Gropp, couvre MPI, OpenMP et CUDA dans un même volume.
  • Victor Eijkhout, Parallel Programming for Science and Engineering, volume 2 de The Art of HPC, PDF gratuit sur theartofhpc.com. Excellent, avec des exercices, et gratuit.
  • Thomas Rauber, Gudula Rünger, Parallel Programming for Multicore and Cluster Systems, Springer. Plus formel, bon sur les modèles de coût.
  • Pour les topologies réseau : la littérature sur dragonfly commence à l'article de Kim, Dally, Scott, Abts, « Technology-Driven, Highly-Scalable Dragonfly Topology » (ISCA 2008).

Outils à maîtriser

Outil Usage
mpirun, srun Lancement ; savoir passer du premier au second sous Slurm
OSU Micro-Benchmarks Mesure de latence et de bande passante
mpiP Profilage MPI léger, par fonction et par rang
Score-P + Scalasca + Vampir ou Cube Instrumentation et trace détaillée
Extrae + Paraver (BSC) Alternative à Score-P, excellente visualisation
hwloc / lstopo Voir la topologie du nœud, pour placer les rangs
--map-by, --bind-to (OpenMPI) Placement des processus sur les cœurs
ThreadSanitizer, MUST Détection d'erreurs MPI et de courses

MUST, l'outil que personne ne connaît

MUST est un vérificateur d'exécution pour MPI, développé à Aix-la-Chapelle et à Dresde. Il détecte les erreurs d'utilisation de l'API — types incohérents entre l'envoi et la réception, communicateurs mal appariés, interblocages — que MPI ne signale pas et qui se manifestent par un plantage incompréhensible à 512 rangs. Si votre code MPI se comporte mal à grande échelle et bien à 4 rangs, c'est le premier outil à sortir.

Exercices

E1 · ★ ⏱ 2 h — Ping-pong. Écrire un ping-pong entre deux rangs, mesurer le temps d'aller-retour pour des messages de 1 octet à 16 Mo par puissances de deux. Tracer la latence et la bande passante. Identifier :

  • la latence à vide \(\alpha\) (l'ordonnée à l'origine) ;
  • la bande passante asymptotique \(1/\beta\) (la pente inverse) ;
  • la taille de message où la bande passante atteint la moitié du maximum, notée \(N_{1/2}\).

Le modèle à ajuster est le modèle de Hockney :

\[ T(n) = \alpha + \beta n \]

où \(T\) est le temps en secondes, \(n\) la taille du message en octets, \(\alpha\) la latence en secondes et \(\beta\) l'inverse de la bande passante en secondes par octet. Comparer vos valeurs à celles des OSU Micro-Benchmarks sur la même machine, et expliquer tout écart.

E2 · ★★ ⏱ 3 h — Réimplémenter les collectives. Écrire à la main, avec uniquement MPI_Send et MPI_Recv :

  1. un MPI_Bcast naïf (le rang 0 envoie à tous, en boucle) ;
  2. un MPI_Bcast en arbre binomial ;
  3. un MPI_Reduce en arbre ;
  4. un MPI_Allreduce par reduce puis broadcast, et un MPI_Allreduce par l'algorithme papillon (recursive doubling).

Mesurer les quatre contre la version native de la bibliothèque. Vous découvrirez que la bibliothèque est meilleure — et pourquoi.

E3 · ★★ ⏱ 2 h — Types dérivés. Une matrice \(N \times N\) de double stockée en lignes. Envoyer la colonne \(j\) au rang voisin :

  1. par recopie manuelle dans un tampon contigu ;
  2. avec un MPI_Type_vector.

Mesurer les deux. Puis faire la même chose pour un sous-bloc \(k \times k\) avec MPI_Type_create_subarray.

E4 · ★★★ ⏱ 6 h — Stencil 2D avec cellules fantômes. Résoudre l'équation de la chaleur 2D par un schéma explicite à cinq points sur une grille distribuée en damier. Points à traiter :

  • décomposition cartésienne avec MPI_Cart_create et MPI_Cart_shift ;
  • échange des quatre bords avec des types dérivés (les bords verticaux ne sont pas contigus) ;
  • version bloquante avec MPI_Sendrecv, puis version non bloquante avec MPI_Isend/MPI_Irecv/MPI_Waitall ;
  • version avec recouvrement calcul-communication : lancer les communications, calculer l'intérieur du domaine, attendre, calculer les bords.

Mesurer l'accélération de 1 à N nœuds, à taille de problème fixe (strong scaling) puis à taille par processus fixe (weak scaling). Tracer les deux courbes. C'est le projet de référence de tout cours de MPI, et il est demandé sous une forme ou une autre dans la plupart des entretiens en HPC.

E5 · ★★★ ⏱ 4 h — MPI-IO. Reprendre le stencil et écrire la grille complète dans un fichier unique à chaque pas de sauvegarde, de trois manières :

  1. chaque rang écrit son propre fichier (N fichiers) ;
  2. tous les rangs envoient au rang 0, qui écrit (goulot d'étranglement) ;
  3. MPI_File_write_all avec une vue définie par MPI_Type_create_subarray.

Mesurer les trois pour 4, 16 et 64 rangs. La troisième doit gagner largement, et comprendre pourquoi est le cœur du sujet des entrées-sorties parallèles. Lien : Entrées-sorties et stockage.

E6 · ★★★★ ⏱ 8 h — RMA. Implémenter un compteur global partagé avec MPI_Win_create et MPI_Fetch_and_op, puis un vol de tâches (work stealing) entre rangs à partir de ce compteur. Comparer à une version maître-esclave classique par messages. Sujet difficile : la sémantique de synchronisation des fenêtres RMA (MPI_Win_fence contre MPI_Win_lock contre MPI_Win_flush) est subtile. Lire le chapitre correspondant de Using Advanced MPI avant de commencer.

Projet

Projet PRPA23 · Un solveur de Poisson distribué, mesuré et documenté

⏱ 30 à 40 h · ★★★★

Sujet. Résoudre \(-\Delta u = f\) sur un carré avec conditions de Dirichlet, par la méthode du gradient conjugué, en MPI, sur une grille distribuée.

Livrables :

  1. Le code, dans un dépôt Git avec CMake et intégration continue.
  2. Une validation numérique : convergence vers la solution analytique pour un \(f\) choisi, avec une courbe d'erreur en fonction du raffinement.
  3. Une étude de passage à l'échelle forte et faible, jusqu'au nombre maximal de nœuds auquel vous avez accès.
  4. Un modèle de coût analytique du temps par itération, de la forme \(T = T_{\text{calcul}} + T_{\text{communication}}\), comparé aux mesures. Le produit scalaire global impose un MPI_Allreduce par itération : son coût en \(\log P\) doit apparaître dans vos courbes.
  5. Une trace Score-P ou Extrae du programme à 16 rangs, avec identification du chemin critique.
  6. Un rapport de huit pages maximum.

Pourquoi ce projet. C'est, à peu de choses près, ce que fait le benchmark HPCG — celui qui sert de second classement officiel aux supercalculateurs, précisément parce qu'il est représentatif des codes réels, contrairement à HPL. En le construisant vous-même, vous comprendrez HPCG de l'intérieur, ce qui est un avantage considérable en compétition.

Extension possible (⏱ +15 h) : ajouter un préconditionneur de Jacobi, puis un Gauss-Seidel symétrique par blocs. Mesurer le compromis entre le nombre d'itérations (qui baisse) et le coût par itération (qui monte). C'est l'arbitrage fondamental des méthodes itératives.

Erreurs fréquentes

Les sept pièges de MPI

  1. Croire qu'un MPI_Send est asynchrone. MPI_Send est bloquant au sens du standard : il rend la main quand le tampon est réutilisable, ce qui peut être immédiat (petit message, copie dans un tampon interne) ou nécessiter que le destinataire poste sa réception (gros message, protocole rendezvous). Deux rangs qui font MPI_Send l'un vers l'autre avant de faire MPI_Recv fonctionnent pour 8 octets et s'interbloquent pour 8 mégaoctets. C'est le bug numéro un, et il est indétectable en test à petite taille.
  2. Modifier le tampon d'un MPI_Isend avant le MPI_Wait. Le standard l'interdit ; la plupart des implémentations ne s'en plaignent pas et renvoient des données fausses de façon intermittente.
  3. Oublier que les collectives sont bloquantes et collectives. Tous les rangs du communicateur doivent les appeler, dans le même ordre. Un MPI_Barrier dans un if (rank == 0) interbloque.
  4. Mesurer avec MPI_Wtime sans barrière. Le temps mesuré au rang 0 inclut le déséquilibre de charge des autres. Pour mesurer une phase, encadrez-la de MPI_Barrier — et sachez que la barrière coûte elle-même quelque chose.
  5. Confondre strong et weak scaling. À taille fixe, l'accélération plafonne (Amdahl). À taille proportionnelle, elle peut rester linéaire (Gustafson). Annoncer une accélération sans préciser lequel des deux on mesure est une faute de méthode, et un jury la relèvera.
  6. Ignorer le placement. Deux rangs sur le même socket communiquent par la mémoire partagée ; deux rangs sur des nœuds différents passent par le réseau. Un facteur dix. Utilisez --map-by, --bind-to, ou les options Slurm équivalentes, et vérifiez avec lstopo.
  7. Ne pas vérifier les codes de retour. MPI renvoie des erreurs qu'on peut consulter. Par défaut, l'erreur fait avorter le programme, mais les messages sont souvent obscurs. Activez MUST une fois dans le semestre : vous trouverez des bugs dormants.

Comment l'UE s'articule avec le reste

UE Lien
ICPA24 (S4) MPI + OpenMP = programmation hybride, le modèle dominant en production
SYFP24 (S4) MPI-IO s'appuie sur Lustre ou GPFS ; comprendre les deux ensemble
LOCL24 (S4) Lancer du MPI sous Slurm avec le bon placement
PGPU35 (S5) MPI + CUDA, avec le GPU-aware MPI
PDSP35 (S5) Les modèles de coût que PRPA23 utilise sans les formaliser
MPI en profondeur Le complément hors programme

À retenir

PRPA23 en trois phrases

C'est l'UE qui définit le parcours : sans MPI, il n'y a pas de HPC distribué. Son originalité est d'entrer dans les algorithmes des implémentations et d'aborder RMA, MPI-IO et les topologies réseau, trois sujets rarement enseignés à ce niveau. Le projet à faire absolument est le stencil 2D avec recouvrement calcul-communication, mesuré en strong et weak scaling.

Fiche suivante : ARSE23 · Architecture d'un système d'exploitation.