Projets fondateurs¶

Cinq projets à faire avant ou au début du semestre 3. Ils sont conçus pour tenir sur un ordinateur portable et ne nécessitent aucun accès à un cluster. Ils construisent les réflexes sur lesquels tout le reste repose.

Charge totale : environ 60 heures.

P1 · Le produit matriciel, du naïf à OpenBLAS¶

⏱ 15 h · ★★★ · À faire en premier, sans exception.

Pourquoi celui-là¶

C'est l'exercice initiatique du calcul haute performance. Il enseigne, sur un seul noyau de vingt lignes, tout ce qui compte : hiérarchie mémoire, blocage de cache, vectorisation, parallélisme, et l'humilité nécessaire face aux bibliothèques optimisées.

C'est aussi l'exercice dont on parle en entretien, et celui qui permet de comprendre HPL de l'intérieur.

Le sujet¶

Implémenter \(C \mathrel{+}= A B\) pour des matrices carrées de double, et la faire progresser par étapes mesurées.

Étape	Ce qu'on fait	Attente (% du pic)
0	Mesurer le pic de la machine et la bande passante STREAM	—
1	Trois boucles `i`, `j`, `k` naïves	1 à 3 %
2	Réordonner en `i`, `k`, `j`	5 à 10 %
3	Bloquer pour le L2	15 à 25 %
4	Bloquer pour le L2 et le L1	25 à 35 %
5	Micro-noyau déroulé, accumulateurs en registres	40 à 55 %
6	Vectoriser le micro-noyau (`omp simd` puis intrinsics)	55 à 70 %
7	Paralléliser en OpenMP	60 à 80 % du pic multicœur
8	Comparer à OpenBLAS ou MKL	référence : 85 à 95 %

Les valeurs dépendent de la machine et de votre persévérance. Ce sont les rapports entre étapes qui importent.

Livrables¶

Le code, avec une fonction par étape et un mode de mesure intégré.
Un test qui vérifie que toutes les versions donnent le même résultat à une tolérance justifiée (l'ordre des additions change, donc pas d'égalité binaire).
Un tableau des huit étapes : GFLOPS, pourcentage du pic, facteur cumulé.
Un graphique GFLOPS en fonction de la taille \(n\), pour trois ou quatre versions.
Trois paragraphes expliquant pourquoi chaque étape a apporté ce qu'elle a apporté.

Le piège¶

Après l'étape 3, les gains deviennent difficiles et il faut lire. Les ressources sont l'article de Goto & van de Geijn, Anatomy of High-Performance Matrix Multiplication, et la série de tutoriels How to Optimize GEMM.

Extension¶

Refaire les étapes 1 à 3 en float et comparer : on attend un facteur deux du fait de la largeur vectorielle doublée et de la moitié du trafic mémoire. Si vous ne l'obtenez pas, comprendre pourquoi.

Liens : Architecture et mémoire, Solveurs.

P2 · La caractérisation complète d'une machine¶

⏱ 12 h · ★★

Pourquoi celui-là¶

Parce qu'on n'optimise pas sur une machine qu'on ne connaît pas, et parce que c'est la première chose à faire quand une équipe de compétition reçoit un accès.

Ce projet produit un document réutilisable. Refaites-le sur chaque machine nouvelle que vous rencontrez : en trois ans vous aurez une collection qui vaut de l'or.

Le sujet¶

Produire la fiche technique mesurée d'une machine.

Contenu attendu :

Topologie : sortie de lstopo commentée, nombre de sockets, cœurs, fils par cœur, tailles de L1, L2, L3, nombre de domaines NUMA, matrice des distances.
Pic de calcul mesuré en FP64 et FP32, par un micro-noyau de FMA saturant, comparé au pic théorique calculé. Expliquer l'écart (fréquence sous charge vectorielle).
Bande passante mémoire mesurée par STREAM : 1 thread, tous les threads, et les quatre configurations NUMA.
Bandes passantes par niveau de cache, par likwid-bench ou un micro-banc maison.
Latences et tailles de cache mesurées par la courbe de pas croissant.
Taux de défauts de TLB avec et sans huge pages.
Bruit système : la distribution des temps d'une boucle de calcul fixe répétée mille fois. Histogramme, médiane, 99ᵉ centile, maximum.
Le roofline de la machine, avec l'intensité de bascule.
La puissance : puissance au repos et sous charge, par RAPL.

Livrable¶

Un document de six à huit pages, avec toutes les commandes utilisées, de sorte qu'un lecteur puisse le refaire sur sa machine.

Liens : ARSE23, Modèles de performance, Outils de mesure.

P3 · Le stencil 2D, séquentiel puis OpenMP¶

⏱ 10 h · ★★

Pourquoi celui-là¶

Le stencil est le second noyau canonique du HPC, après le GEMM, et il est son opposé exact : limité par la mémoire et non par le calcul. Le contraste est pédagogiquement précieux.

C'est aussi la base du projet MPI P6 et de la moitié des codes de simulation réels.

Le sujet¶

Résoudre l'équation de la chaleur 2D par un schéma explicite à cinq points, sur une grille de \(N \times N\) points, pendant \(T\) pas de temps.

Étapes :

Version séquentielle correcte, validée contre une solution analytique.
Calculer l'intensité arithmétique et prédire la performance par le roofline. Le stencil à cinq points fait environ 5 opérations par point pour 2 accès mémoire incompressibles de 8 octets (la lecture de la grille et l'écriture du résultat, la réutilisation des voisins étant assurée par le cache), soit une intensité proche de \(5/24 \approx 0{,}2\) FLOP/octet. C'est très faible : le noyau est massivement memory bound.
Mesurer, en mises à jour de points par seconde (une métrique plus parlante que les GFLOPS pour un stencil), et comparer à la borne.
Optimiser : deux tampons alternés plutôt qu'une recopie, disposition mémoire linéaire, échange de boucles, blocking spatial.
Le blocage temporel (temporal blocking) : traiter plusieurs pas de temps sur un même bloc spatial avant de passer au suivant, pour réutiliser le cache. C'est l'optimisation la plus puissante et la plus difficile. Elle augmente réellement l'intensité arithmétique.
Paralléliser en OpenMP, avec attention à la première touche.

Livrables¶

Le code, la validation, le tableau des étapes, et une comparaison de la performance obtenue à la bande passante STREAM. Un stencil bien optimisé atteint 70 à 90 % de la valeur STREAM ; c'est là qu'il faut s'arrêter, et le savoir évite de perdre des jours.

Liens : Modèles de performance, OpenMP et threads.

P4 · Le chronomètre et le carnet de mesures¶

⏱ 8 h · ★★

Pourquoi celui-là¶

Parce que c'est l'infrastructure de tout le reste, et que personne ne la construit avant d'en avoir douloureusement besoin.

Le sujet¶

Construire l'outillage de mesure que vous utiliserez pendant trois ans.

Trois composants :

1. Une bibliothèque de chronométrage (C++ ou C), qui fournit :

un chronomètre à horloge monotone, avec une résolution mesurée ;
un mécanisme de phases nommées (timer.start("calcul"), timer.stop("calcul")), avec rapport final ;
la répétition automatique avec préchauffage, et le calcul de la médiane, du minimum et de l'écart-type ;
une protection contre l'élimination du calcul par le compilateur.

2. Un collecteur de métadonnées : un script qui capture automatiquement le nom de la machine, le modèle de processeur, le compilateur et sa version, les options de compilation, les modules chargés, les variables d'environnement pertinentes (OMP_*), le hash Git, et la date.

3. Une base de mesures : un CSV ou une base SQLite avec une ligne par expérience, alimentée automatiquement, plus un script d'interrogation qui produit les courbes classiques (accélération, performance en fonction de la taille, comparaison de configurations).

Le test de validation¶

Lancer la même mesure trois fois à des heures différentes, et vérifier que les trois lignes de la base sont complètes et que la variance est cohérente. Puis donner le dépôt à un camarade et vérifier qu'il peut alimenter la même base depuis sa machine.

Liens : Outils de mesure, ITIC23.

P5 · La chaîne de développement scientifique complète¶

⏱ 15 h · ★★★

Pourquoi celui-là¶

C'est la préparation directe d'INPS23, et le projet qui sera le plus réutilisé : il sert de socle à P6, P8, P13 et au projet d'UE.

Le sujet¶

Choisir un problème physique simple et construire toute la chaîne autour.

Choix du problème : diffusion de la chaleur 3D, équation des ondes 2D, dynamique moléculaire de type Lennard-Jones sur quelques milliers de particules, ou un automate de Lattice-Boltzmann pour un écoulement 2D. Le dernier est particulièrement intéressant : il est simple à écrire, visuellement satisfaisant, et c'est un vrai noyau de mécanique des fluides.

Les six maillons :

Le code : C++ moderne, CMake, structure claire, testé, avec un test de validation physique (conservation d'une quantité, solution analytique, symétrie) et non un simple test de non-plantage.
La configuration : un fichier TOML, YAML ou JSON. Aucune constante physique codée en dur. Le programme refuse de démarrer sur une configuration invalide, avec un message utile.
La production : un script de campagne qui balaie des paramètres, écrit des points de reprise et reprend après interruption sans recalculer.
Les données : sortie HDF5 avec métadonnées complètes, dont le hash Git, les options de compilation, la machine et la date.
Le post-traitement : script Python qui produit toutes les figures, et une visualisation 3D avec ParaView ou VisIt.
La restitution : un rapport de six pages et une présentation de dix minutes.

Les trois ajouts qui font la différence, et que l'énoncé d'une UE ne demandera peut-être pas :

un chiffre de performance comparé à une borne ;
un profil (perf record) avec identification du point chaud ;
une courbe d'effet des options de compilation.

Critère de réussite¶

Donner le dépôt à quelqu'un d'extérieur et qu'il puisse, sans vous poser de question et en moins d'une heure, construire le code et reproduire une de vos figures.

Liens : INPS23, Build et environnement, Entrées-sorties.

Le bilan des fondateurs¶

Après ces cinq projets, vous savez

calculer une borne de performance et vous y comparer ;
mesurer proprement, avec répétitions, métadonnées et carnet ;
reconnaître un noyau compute bound d'un noyau memory bound, et savoir ce que chacun peut espérer ;
optimiser un noyau par blocage, vectorisation et parallélisation ;
caractériser une machine avant de l'utiliser ;
construire une chaîne scientifique reproductible de bout en bout.

C'est le socle. Tout le reste s'appuie dessus, y compris les UE : vous aborderez ICPA24 et PRPA23 en sachant déjà mesurer, ce qui change complètement ce que vous en tirerez.

Chapitre suivant : Projets intermédiaires.