PDSP35 · Performance des systèmes parallèles¶

L'UE qui formalise ce que vous avez mesuré à tâtons depuis deux ans. Elle fournit le vocabulaire, les modèles et la méthode — et son évaluation par lecture d'article scientifique est une occasion à saisir.

Fiche signalétique¶


Code	PDSP35
Crédits	5 ECTS
Semestre	5, spécialisation — lundi matin
Responsable	HONORE Valentin
Concurrentes sur le créneau	OPTU35
Choix	Une des trois UE de spécialisation, en accord avec l'entreprise
Prérequis	Notions de base en complexité algorithmique ; programmation système, C (C++ idéalement) et compilation ; programmation Python
Effectif max	30

Ce que dit la brochure¶

Objectifs cités, dans une présentation qui situe le domaine :

« Le calcul parallèle s'est beaucoup développé ces dernières années du fait des besoins en calcul de plus en plus importants de nombreux domaines scientifiques, allant de la biologie à l'astrophysique en passant par la dynamique moléculaire. Ces besoins ont poussé à la construction de clusters, et l'apparition de nombreuses plates-formes plus ou moins spécialisées suivant les besoins (CPU, GPU, accélérateurs etc). […] Ces technologies de réseau avancées ont aussi démocratisé l'agrégation de plates-formes de calcul au travers de réseaux déployés à grande échelle appelées "grilles". Enfin, les services de Cloud Computing, utilisant la virtualisation, sont un moyen supplémentaire d'acquérir des ressources de calcul à la demande.

Dans tous ces services, l'exploitation efficace des plates-formes est un enjeu fondamental. Leur coût d'exploitation rend nécessaire l'optimisation de l'exploitation des ressources de calcul. L'objectif de ce cours est de fournir des outils de modélisation et d'analyse de performance de ces systèmes, allant du niveau applicatif jusqu'au niveau de la machine elle-même. Ce cours couvrira des aspects fondamentaux (algorithmique parallèle, modèles de performance) mais aussi des travaux pratiques mettant en œuvre ces notions. »

Modalité d'évaluation citée :

« L'évaluation se fera sous la forme de la lecture d'un article scientifique à choisir sur des thématiques abordées pendant le cours. D'autres évaluations seront envisagées en fonction de la répartition des séances de l'UE (projet etc) »

Contenu cité :

introduction au calcul et aux systèmes parallèles ;
notions de performance pour l'algorithmique parallèle : accélération et efficacité, loi d'Amdahl, pipelining, granularité, parties séquentielles et parallèles ;
performance au niveau machine : introduction à l'ordonnancement — définition, problèmes et algorithmes classiques ;
performance au niveau applicatif : parallélisme, contention, memory bound et *compute bound, outils d'aide à la performance, traçage d'applications* ;
ouverture : défis du calcul haute performance (énergie, gestion de données à l'échelle).

Ce que ça vaut pour le HPC¶

Très élevé, d'une manière différente des autres UE.

Les autres UE du parcours vous apprennent à faire : écrire du MPI, du CUDA, administrer un cluster. PDSP35 vous apprend à raisonner : prédire avant de mesurer, expliquer un écart, savoir quand s'arrêter d'optimiser.

C'est la compétence qui distingue un ingénieur d'un bricoleur habile. En compétition, elle a une valeur très concrète : quand il reste six heures et trois applications à optimiser, celui qui sait prédire lesquelles peuvent encore gagner un facteur deux et lesquelles sont déjà à la borne gagne la course.

Les modèles à maîtriser¶

L'UE en cite explicitement deux ; il faut en connaître quatre.

La loi d'Amdahl. Si une fraction \(s\) du temps d'exécution est irréductiblement séquentielle, l'accélération maximale sur \(p\) processeurs est :

\[ S(p) = \frac{1}{s + \dfrac{1-s}{p}} \]

où \(S\) est l'accélération (temps séquentiel divisé par temps parallèle), \(s\) la fraction séquentielle entre 0 et 1, et \(p\) le nombre de processeurs. Quand \(p \to \infty\), \(S \to 1/s\) : avec 5 % de code séquentiel, on ne dépassera jamais un facteur 20, quel que soit le nombre de cœurs. C'est la loi la plus citée et la plus mal comprise du domaine.

La loi de Gustafson, qui est la réponse à Amdahl. Si l'on augmente la taille du problème avec le nombre de processeurs — ce qui est ce qu'on fait réellement en HPC — l'accélération à charge proportionnelle devient :

\[ S(p) = s + p\,(1-s) \]

qui croît linéairement en \(p\). Amdahl décrit le strong scaling (taille fixe), Gustafson le weak scaling (taille proportionnelle). Ce sont deux expériences différentes et il faut toujours dire laquelle on rapporte.

Le modèle roofline, qui n'est pas cité mais qui est aujourd'hui le modèle de référence. La performance atteignable d'un noyau est bornée par :

\[ P = \min\left(P_{\max},\; B \times I\right) \]

où \(P\) est la performance en FLOP/s, \(P_{\max}\) le pic de calcul de la machine en FLOP/s, \(B\) la bande passante mémoire en octets par seconde, et \(I\) l'intensité arithmétique du noyau en FLOP par octet. Le point où \(B \times I = P_{\max}\) est le coude du diagramme : à gauche on est memory bound, à droite compute bound. C'est précisément la distinction citée au programme de l'UE.

Le modèle de Hockney pour les communications, déjà vu en PRPA23 : \(T(n) = \alpha + \beta n\).

Détail complet et exercices : Modèles de performance.

L'évaluation par lecture d'article : comment en profiter¶

C'est l'occasion la plus intéressante du semestre. Le choix de l'article est le vôtre. Choisissez-en un qui vous serve deux fois : pour l'UE, et pour votre projet ou votre compétition.

Comment choisir votre article

Critères : un article de conférence de premier rang (SC, IPDPS, ICS, PPoPP, Euro-Par, ISC), de dix à quinze pages, avec une méthodologie de mesure explicite, et sur un sujet qui recoupe votre projet personnel.

Familles d'articles particulièrement formateurs :

Thème	Article de référence
Le modèle roofline	Williams, Waterman, Patterson, « Roofline: An Insightful Visual Performance Model for Multicore Architectures » (Communications of the ACM, 2009)
Le bruit système	Petrini, Kerbyson, Pakin, « The Case of the Missing Supercomputer Performance » (SC 2003) — une enquête de détective, très plaisant à lire
Le bruit système, version quantitative	Hoefler, Schneider, Lumsdaine, « Characterizing the Influence of System Noise on Large-Scale Applications by Simulation » (SC 2010)
La méthodologie de mesure	Hoefler & Belli, « Scientific Benchmarking of Parallel Computing Systems » (SC 2015) — à lire absolument, quelle que soit votre thèse : douze règles pour mesurer honnêtement
L'optimisation GEMM	Goto & van de Geijn, « Anatomy of High-Performance Matrix Multiplication » (ACM TOMS, 2008)
Le vol de travail	Blumofe & Leiserson, « Scheduling Multithreaded Computations by Work Stealing » (JACM, 1999)
Les modèles de coût	Valiant, « A Bridging Model for Parallel Computation » (CACM, 1990), le modèle BSP ; et Culler et al., « LogP » (PPoPP 1993)
Le modèle ECM	Hofmann, Hager, Fey, et les articles du groupe d'Erlangen sur le modèle Execution-Cache-Memory, plus fin que le roofline
L'énergie	Les articles sur le power capping et sur le compromis performance-énergie, et les rapports du Green500

Le plus rentable : Hoefler & Belli, Scientific Benchmarking of Parallel Computing Systems. Il énonce douze règles de mesure — sur le nombre de répétitions, le choix entre moyenne, médiane et minimum, la présentation des intervalles de confiance, le rapport des versions logicielles. Ces règles amélioreront tout ce que vous mesurerez ensuite, y compris en compétition, et vous permettront de critiquer n'importe quel autre article.

Comment lire un article de performance, en trois passes :

Titre, résumé, figures, conclusion. Dix minutes. Quelle est la thèse ?
Introduction, méthodologie, résultats. Une heure. La méthodologie est-elle suffisante pour soutenir la thèse ? Quelle machine, quel compilateur, combien de répétitions, quelle variance ?
Les détails, les références, et la reproduction d'une figure si possible.

La question à toujours poser : quelle est la référence ? Un article qui annonce une accélération sans dire par rapport à quoi, ou par rapport à une version volontairement naïve, ne démontre rien. C'est plus courant qu'on ne l'imagine, même dans les bonnes conférences.

Arriver prêt¶

⏱ 12 h :

Avoir mesuré des choses. Si vous arrivez à PDSP35 avec un carnet de mesures des deux années précédentes, tout le cours prendra sens. Sinon, il restera abstrait.
Savoir tracer proprement. Matplotlib, échelles logarithmiques, barres d'erreur, courbes d'accélération avec la ligne idéale en pointillés. ⏱ 4 h.
Réviser la complexité algorithmique, prérequis cité. ⏱ 2 h.
Lire Hager & Wellein, chapitres 1 à 5. ⏱ 6 h. C'est le meilleur préambule possible.

Ressources¶

Priorité 1¶

Georg Hager, Gerhard Wellein, Introduction to High Performance Computing for Scientists and Engineers, CRC Press. Les chapitres sur les modèles simples de performance sont exactement le cœur de cette UE, traités avec une rigueur exemplaire.
Hoefler & Belli, « Scientific Benchmarking of Parallel Computing Systems » (SC 2015). Voir ci-dessus. Douze pages qui changent la manière de mesurer.
Le cours CS267 Applications of Parallel Computers de Berkeley (Jim Demmel), notes et vidéos gratuites. Les premières leçons sur les modèles de machine parallèle et les bornes de communication sont excellentes.

Priorité 2 — l'ordonnancement, qui est la spécialité du responsable¶

Peter Brucker, Scheduling Algorithms, Springer. La référence classique sur la théorie de l'ordonnancement.
Michael Pinedo, Scheduling: Theory, Algorithms, and Systems. L'alternative, plus orientée applications.
Pour l'ordonnancement en HPC spécifiquement : les articles sur le backfilling (Mu'alem & Feitelson), sur l'ordonnancement de tâches sur machines hétérogènes, et les travaux d'Inria Bordeaux et de l'IRIT sur le sujet. La bibliographie du responsable de l'UE est le meilleur guide.
La documentation de Slurm sur les algorithmes d'ordonnancement, pour le versant pratique. Lien : LOCL24.

Priorité 3 — le traçage¶

Score-P avec Cube, Scalasca et Vampir : la chaîne européenne d'instrumentation et d'analyse. Score-P instrumente, Cube analyse, Vampir visualise la chronologie.
Extrae et Paraver (Barcelona Supercomputing Center) : l'alternative, avec la meilleure visualisation de traces du domaine et une méthodologie documentée (les BSC Performance Tools ont un guide de méthode remarquable).
HPCToolkit (Rice University), TAU (Oregon), MAQAO (UVSQ, français).
Brendan Gregg, pour la méthodologie générale de diagnostic de performance.

Priorité 4 — la simulation de systèmes parallèles¶

Sujet connexe, et bien français :

SimGrid (simgrid.org), développé en France, permet de simuler l'exécution d'applications parallèles sur des plateformes virtuelles. Utile pour étudier le passage à l'échelle sans avoir la machine, et pour tester des politiques d'ordonnancement.
Batsim, construit sur SimGrid, pour simuler des ordonnanceurs de travaux.

Exercices¶

E1 · ★ ⏱ 2 h — Amdahl et Gustafson. Écrire un programme dont la fraction séquentielle est connue et réglable (par exemple, une boucle parallèle et une boucle séquentielle dont on ajuste les longueurs). Mesurer l'accélération pour \(p\) de 1 à 32 et pour trois valeurs de \(s\). Superposer les courbes mesurées et les courbes théoriques d'Amdahl. Puis refaire en weak scaling et comparer à Gustafson.

E2 · ★★ ⏱ 3 h — Le roofline de votre machine. Construire le diagramme roofline complet d'une machine : pic de calcul mesuré (par un micro-noyau de FMA saturant), bande passante mesurée (STREAM), et les plafonds intermédiaires correspondant aux niveaux de cache. Puis y positionner cinq noyaux mesurés : DAXPY, DGEMV, DGEMM, un stencil, un SpMV. Comparer la position prédite par l'intensité arithmétique à la performance effectivement mesurée.

E3 · ★★ ⏱ 3 h — Compute bound ou memory bound, en trois méthodes. Pour un noyau donné, déterminer le régime par trois voies indépendantes : le calcul analytique de l'intensité arithmétique, la mesure des compteurs matériels avec LIKWID ou perf, et l'expérience de la variation de fréquence (réduire la fréquence du processeur : un code compute bound ralentit proportionnellement, un code memory bound presque pas). Les trois doivent concorder. Si ce n'est pas le cas, comprendre pourquoi est l'exercice.

E4 · ★★★ ⏱ 4 h — La trace et le chemin critique. Instrumenter une application MPI+OpenMP avec Score-P ou Extrae, produire une trace, et l'analyser : où est le déséquilibre de charge, quel rang attend, quelle collective domine, quel est le chemin critique. Produire une figure de chronologie annotée.

E5 · ★★★ ⏱ 4 h — Les douze règles appliquées. Reprendre une mesure que vous avez faite dans une UE antérieure et la refaire en appliquant strictement les douze règles de Hoefler & Belli : nombre de répétitions justifié, statistique appropriée, intervalles de confiance, rapport complet de l'environnement. Comparer la conclusion initiale et la conclusion révisée. Dans un cas sur deux, la première conclusion ne survit pas.

E6 · ★★★★ ⏱ 6 h — L'ordonnancement, en simulation. Avec SimGrid ou un simulateur maison, comparer trois politiques d'ordonnancement de travaux (FCFS, FCFS avec backfilling, et une politique par priorité) sur une trace de charge réaliste. Mesurer le temps d'attente moyen, le slowdown pondéré et le taux d'utilisation de la machine. Vous découvrirez qu'améliorer une métrique dégrade souvent une autre, ce qui est le fond du problème de l'ordonnancement.

Projet¶

Projet PDSP35 · L'étude de performance publiable

⏱ 40 h · ★★★★

Sujet. Produire une étude de performance conforme aux standards d'un article de conférence : question de recherche, méthodologie explicite, résultats reproductibles, limites honnêtement énoncées.

Choisir une question, formulée de sorte qu'une mesure puisse y répondre. Exemples :

« Jusqu'à quelle échelle le solveur X passe-t-il à l'échelle sur la machine Y, et quel mécanisme précis limite son efficacité au-delà ? »
« Le modèle roofline prédit-il correctement la performance de N noyaux de la suite Z sur trois machines différentes ? Où échoue-t-il, et pourquoi ? »
« Quel est le compromis performance-énergie de l'application A en fonction du nombre de cœurs actifs et de la fréquence, et existe-t-il un point de fonctionnement meilleur que le défaut ? »
« Quelle est la sensibilité du temps d'exécution de l'application B au placement des processus sur la topologie, et quelle amélioration un placement optimisé apporte-t-il ? »

Les sept sections du rapport, dans le format d'un article :

Introduction et question — une page, avec la contribution annoncée.
Contexte et travaux antérieurs — au moins cinq articles cités et réellement lus, avec ce que chacun apporte et ce qui manque.
Méthodologie — machine, compilateur et version, options, jeux de données, nombre de répétitions, statistique utilisée, procédure exacte. Quelqu'un doit pouvoir refaire l'expérience.
Modèle — la prédiction analytique, posée avant les mesures.
Résultats — figures propres, avec barres d'erreur, et confrontation au modèle.
Discussion — l'explication des écarts, qui est la partie scientifique.
Limites et menaces à la validité — honnêtement. Une seule machine ? Un seul compilateur ? Un jeu de données non représentatif ? C'est la section qui distingue un travail sérieux.

Livrable annexe : un dépôt contenant les scripts, les données brutes et les notebooks de figures, de sorte qu'un lecteur puisse tout régénérer.

Pourquoi ce projet. Parce que c'est exactement la forme attendue par l'évaluation de l'UE, parce que c'est réutilisable pour RDEV36, et parce que savoir produire une étude de performance défendable est la compétence la plus transférable de tout le parcours — en recherche, en industrie, et devant un jury de compétition.

Erreurs fréquentes¶

Sept fautes de mesure, toutes courantes dans la littérature

Rapporter une moyenne sur une distribution asymétrique. Les temps d'exécution ont une queue à droite (une exécution ralentie par un voisin). La moyenne est tirée vers le haut par les valeurs aberrantes. Rapporter la médiane pour caractériser le comportement typique, et le minimum pour caractériser la capacité de la machine.
Une seule répétition. Sans variance mesurée, aucune conclusion n'est valide. Trois au minimum, dix si la variance est forte.
Ne pas dire quel scaling on mesure. Strong ou weak : ce sont deux expériences différentes, et les confondre invalide tout.
L'accélération super-linéaire non expliquée. Obtenir 40× sur 32 cœurs est possible — le problème découpé tient dans les caches — mais cela doit être expliqué, pas présenté comme un succès.
Comparer des choses incomparables. Deux machines, deux compilateurs, deux tailles de problème : on ne peut changer qu'une variable à la fois.
Tronquer l'axe des ordonnées. Un graphique dont l'axe commence à 90 % fait paraître énorme une différence de 2 %. C'est une faute de présentation, et un jury la voit.
Ne pas rapporter les échecs. Une optimisation qui n'a rien apporté est un résultat. L'omettre biaise la littérature et prive le lecteur de l'information la plus utile.

Comment l'UE s'articule avec le reste¶

UE ou chapitre	Lien
PRPA23, ICPA24, PGPU35	Les trois modèles de programmation dont PDSP35 modélise la performance
PRSA24 (S4)	La pratique du profiling ; PDSP35 en donne la théorie
ARSE23 (S3)	Le bruit système, l'ordonnanceur, la contention
LOCL24 (S4)	L'ordonnancement de travaux, côté Slurm
GIIG35 (S5)	L'énergie, citée dans l'ouverture du cours
Modèles de performance	Le complément : roofline détaillé, ECM, LogP, bornes de communication
Outils de mesure	Le catalogue des outils de traçage

À retenir¶

PDSP35 en trois phrases

C'est l'UE qui transforme la mesure en science : Amdahl, Gustafson, roofline, memory bound contre compute bound, ordonnancement, traçage. L'évaluation par lecture d'article est une occasion — choisissez Hoefler & Belli, Scientific Benchmarking of Parallel Computing Systems (SC 2015), dont les douze règles amélioreront toutes vos mesures futures. La compétence à acquérir est de prédire avant de mesurer, ce qui permet de savoir quand il reste quelque chose à gagner et quand il faut s'arrêter.

Fiche suivante : COAV35 · Compilation avancée.