ICPA24 · Introduction au calcul parallèle¶

La seule UE de calcul parallèle que tout apprenti suit obligatoirement. Elle est dans le tronc commun, elle ne se négocie pas, et elle dure vingt-et-une heures.

Fiche signalétique¶


Code	ICPA24
Statut	Module de l'UE INFO24 (10 ECTS), tronc commun du semestre 4
Responsable de l'UE	BUREL Guillaume
Découpage	10 séances de cours/TP intégrés + 2 séances de TP noté — soit 21 heures
Évaluation	TP noté, en première comme en seconde session
Choix	Aucun : tout le monde le suit

Ce que dit la brochure¶

Objectifs cités :

« L'objectif du module est de donner une introduction au calcul parallèle à travers une évocation rapide des fondements théoriques du parallélisme jusqu'à la programmation parallèle. Le cours sera donné sous la forme de cours intégrés mixant cours et TP pour que les étudiant.e.s manipulent le plus possible les techniques vues dans ce module. »

Contenu cité, en quatre points :

Généralités autour du calcul parallèle (contexte, architecture, modèles de programmation parallèle)

Parallélisme à base de threads

Programmation parallèle en mémoire partagée (intra-nœud) : OpenMP

Programmation parallèle par échange de messages : MPI (si le temps le permet, sinon une brève introduction)

Ce que ça vaut pour le HPC¶

Élevé par son statut, limité par son volume. Il faut tenir les deux bouts.

Ce qui est remarquable : que le calcul parallèle figure au tronc commun d'une formation généraliste par apprentissage. Tout diplômé FISA de l'ENSIIE sait ce qu'est un thread, une région parallèle OpenMP et, probablement, un MPI_Send. Beaucoup d'écoles n'en donnent pas autant à leurs spécialistes.

Ce qui limite : vingt-et-une heures pour couvrir le contexte, les threads, OpenMP et MPI. Cela fait environ cinq heures par thème. La brochure l'assume en écrivant que MPI passera « si le temps le permet ».

Ce que le contenu cité ne contient pas

Relisez la liste des quatre points. Elle ne mentionne ni la mesure, ni la performance. Ni faux partage, ni règle de la première touche, ni saturation de bande passante, ni roofline.

Ce n'est pas un reproche : c'est une introduction, et une introduction qui parlerait de false sharing avant d'avoir montré une région parallèle serait mal construite.

Mais cela signifie qu'à la sortie d'ICPA24, vous saurez écrire du code parallèle sans savoir s'il est rapide. Les cinq causes qui font qu'une parallélisation ne donne rien sont dans OpenMP et threads, et elles tiennent en un arbre de diagnostic d'une page.

Comment en tirer trois fois plus¶

C'est une UE courte, en cours intégrés, avec un enseignant disponible pendant les TP. C'est un format idéal pour poser des questions — à condition d'arriver avec les questions.

Arriver avec une mesure, pas avec une page blanche

Avant la première séance, faites P1 · le produit matriciel au moins jusqu'à l'étape 3, et P3 · le stencil 2D. Comptez quinze heures.

Vous arriverez alors avec trois questions que personne d'autre ne posera :

« Ma somme parallèle est plus lente que la séquentielle. Pourquoi ? » — c'est le faux partage, et vous ne l'oublierez jamais après l'avoir vu sur votre propre code.
« Mon accélération plafonne à six threads sur seize cœurs. » — c'est la saturation de bande passante mémoire, et c'est le comportement normal d'un noyau à faible intensité arithmétique.
« Comment je sais si 40 GFLOPS c'est bien ? » — c'est le modèle roofline, et c'est la question la plus importante du domaine.

Un enseignant à qui l'on pose ces trois questions pendant un TP y répond volontiers, et la réponse vaut le double d'un cours magistral.

Ressources¶

Priorité 1 — pour accompagner les vingt-et-une heures :

Les supports OpenMP de l'IDRIS, idris.fr/formations/openmp/, en français, gratuits, avec exercices. Le complément naturel du module 3.
Les supports MPI de l'IDRIS, pour le module 4 — surtout si le temps ne permet pas de le traiter en cours.
Timothy Mattson, Yun He, Alice Koniges, The OpenMP Common Core, MIT Press, 2019. La thèse du livre : on utilise une vingtaine de constructions OpenMP sur les trois cents du standard. C'est exactement le bon niveau ici.

Priorité 2 — pour la partie que le module ne traitera pas :

Modèles de performance — le roofline, Amdahl, Gustafson. Vingt heures, et c'est ce qui donne un sens aux mesures du TP noté.
OpenMP et threads — les cinq causes d'échec d'une parallélisation.
Les cartes de référence OpenMP, openmp.org : quatre pages, le document le plus utile du site.

Exercices¶

Ces exercices supposent le module suivi ; ils prolongent chacun de ses points.

E1 · ★ ⏱ 2 h — La réduction, quatre fois. Sommer un tableau de cent millions de double : séquentiellement, avec atomic, avec critical, avec reduction(+:s). Les versions 2 et 3 seront plus lentes que la séquentielle. Expliquer pourquoi, et pourquoi reduction ne l'est pas.

E2 · ★★ ⏱ 2 h — Le faux partage, mesuré. Un tableau de compteurs, un par thread, incrémentés un million de fois. Version 1 : compteurs adjacents. Version 2 : chaque compteur aligné sur 64 octets. Le facteur entre les deux est typiquement de 5 à 20. Confirmer le diagnostic avec perf c2c.

E3 · ★★ ⏱ 3 h — La courbe d'accélération, et son plafond. Prendre un noyau limité par la mémoire (un stencil, un AXPY) et un noyau limité par le calcul (un produit matriciel bloqué). Tracer l'accélération de 1 à N threads pour les deux. Le premier plafonne vers quatre à huit threads, le second monte presque linéairement. C'est la démonstration la plus parlante du modèle roofline, et elle tient en trois heures.

E4 · ★★ ⏱ 2 h — Le placement. Reprendre E3 en jouant sur OMP_PROC_BIND et OMP_PLACES, et en affichant OMP_DISPLAY_AFFINITY=true. Constater que le placement change le résultat, et vérifier sur quels cœurs les threads ont réellement été posés.

E5 · ★★★ ⏱ 4 h — MPI, si le cours ne le traite pas. Écrire un échange en anneau puis un ping-pong, mesurer la courbe latence/bande passante, et en extraire les deux paramètres du modèle de Hockney, \(T(n) = \alpha + \beta n\). Vingt lignes de code, et cela donne la caractérisation du réseau de votre machine.

Le TP noté¶

L'évaluation est un TP noté, en première comme en seconde session.

Comment le préparer

Un TP noté de calcul parallèle demande presque toujours de paralléliser un noyau et de montrer que ça marche. Les deux points où l'on perd des points, et qui ne sont pas techniques :

1. Ne pas valider le résultat. Un code parallèle rapide et faux ne vaut rien. Prévoyez systématiquement une comparaison avec la version séquentielle, avec une tolérance justifiée — l'ordre des additions change, donc l'égalité exacte n'est pas le bon critère.

2. Ne pas mesurer proprement. Une seule exécution, pas de préchauffage, pas de médiane. Les cinq règles du chronométrage sont dans Outils de mesure et elles prennent vingt minutes à appliquer.

Comment le module s'articule avec le reste¶

UE ou chapitre	Lien
SYEX11 (S1, tronc commun)	Les bases système : processus, threads
PRPA23 (S3, option)	Si vous l'avez prise, ICPA24 sera une révision sur MPI — et une découverte sur OpenMP
PRCV24 (S4, option)	Le module MPPT24 approfondit les threads que ICPA24 introduit
PGPU35 (S5)	ICPA24 satisfait le prérequis « Programmation Parallèle »
Modèles de performance	Ce qui manque : comment savoir si c'est rapide
OpenMP et threads	Ce qui manque : pourquoi ça n'accélère pas

Le point de passage vers le semestre 5

Fait. La fiche de PGPU35 donne comme prérequis « Programmation Parallèle » et « C/C++ ».

ICPA24 étant au tronc commun, tout apprenti satisfait ce prérequis, même sans avoir pris PRPA23 au semestre 3. C'est une bonne nouvelle : la porte du GPU n'est fermée à personne.

À retenir¶

ICPA24 en trois phrases

C'est la seule UE de calcul parallèle que tout apprenti suit, elle est au tronc commun du semestre 4, et elle dure vingt-et-une heures — threads, OpenMP, et MPI si le temps le permet.

Son contenu ne comporte aucune notion de mesure ni de performance : à sa sortie, vous saurez écrire du code parallèle sans savoir s'il est rapide. C'est le rôle de Modèles de performance et d'OpenMP et threads.

Le meilleur usage du module est d'y arriver avec une mesure qui vous intrigue : un code parallèle plus lent que le séquentiel, ou une accélération qui plafonne. Le format en cours intégrés permet de poser la question, et la réponse vaut le double du cours.

Fiche suivante : PRCV24 · Programmation concurrente et vérification.