1 · Modèles de performance

Le chapitre le plus important du socle. Un modèle de performance répond à la question qui précède toute optimisation : combien peut-on espérer gagner ? Sans réponse à cette question, on optimise à l'aveugle et on ne sait pas quand s'arrêter.

Difficulté : ★★★ · ⏱ 30 h

Intuition

Vous avez un code qui tourne en dix secondes. Vous passez une semaine à l'optimiser et vous arrivez à huit secondes. Avez-vous réussi ?

La question n'a pas de réponse sans savoir ce que la machine peut faire. Si la borne physique est neuf secondes, vous avez fait un travail remarquable. Si elle est d'une seconde, vous avez perdu une semaine.

Un modèle de performance est une estimation de cette borne, obtenue par un calcul simple à partir des caractéristiques de la machine et du code. Il n'est jamais exact — c'est un modèle. Il est utile parce qu'il donne un ordre de grandeur de ce qui est atteignable, ce qui suffit à décider où investir son temps.

Les grandeurs de base

Avant les modèles, le vocabulaire. Quatre grandeurs, avec leurs unités.

Grandeur	Symbole	Unité	Signification
Performance de calcul	\(P\)	FLOP/s	Opérations flottantes par seconde
Pic de calcul de la machine	\(P_{\max}\)	FLOP/s	Le maximum théorique atteignable
Bande passante mémoire	\(B\)	octet/s	Débit maximal vers la mémoire principale
Intensité arithmétique	\(I\)	FLOP/octet	Opérations effectuées par octet transféré

Le pic de calcul se calcule à partir des caractéristiques du processeur :

\[ P_{\max} = f \times n_{\text{cœurs}} \times w \times n_{\text{FMA}} \times 2 \]

où \(f\) est la fréquence en hertz, \(n_{\text{cœurs}}\) le nombre de cœurs, \(w\) le nombre d'éléments par registre vectoriel (8 pour AVX-512 en double précision, 4 pour AVX2), \(n_{\text{FMA}}\) le nombre d'unités de multiplication-addition fusionnée par cœur (souvent 2), et le facteur 2 vient du fait qu'une FMA compte pour deux opérations (une multiplication et une addition).

Exemple numérique. Un processeur à 32 cœurs, 2,5 GHz, AVX-512 (8 doubles par registre), 2 unités FMA :

\[ P_{\max} = 2{,}5 \times 10^9 \times 32 \times 8 \times 2 \times 2 = 2{,}56 \times 10^{12}\ \text{FLOP/s} \]

soit 2,56 TFLOP/s en double précision. Attention : cette valeur suppose que la fréquence reste à 2,5 GHz avec tous les cœurs en AVX-512, ce qui n'est presque jamais le cas — la fréquence baisse sous charge vectorielle. Le pic mesuré est typiquement 10 à 30 % inférieur au pic théorique.

L'intensité arithmétique est la propriété du code, pas de la machine. Elle se calcule en comptant les opérations flottantes et les octets qui doivent nécessairement traverser la frontière entre le cache et la mémoire principale.

Exemple. Le produit scalaire \(s = \sum_i x_i y_i\) sur des vecteurs de double trop grands pour tenir en cache : par élément, 2 opérations (une multiplication, une addition) et 16 octets lus (deux double). Donc \(I = 2/16 = 0{,}125\) FLOP/octet. C'est très faible.

Exemple. Le produit matrice-matrice \(C = AB\) de matrices \(n \times n\) : \(2n^3\) opérations et, si l'algorithme est bien bloqué, environ \(3n^2 \times 8\) octets transférés. Donc \(I \approx n/12\), qui croît avec \(n\). C'est pour cela que le GEMM peut approcher le pic de calcul alors que le produit scalaire ne peut pas.

Le modèle roofline

Le modèle le plus utile du domaine. Publié par Williams, Waterman et Patterson dans Communications of the ACM en 2009, il tient en une formule :

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

La performance atteignable est le minimum entre le pic de calcul et ce que la bande passante permet d'alimenter. Tracé sur un graphique log-log avec \(I\) en abscisse et \(P\) en ordonnée, cela donne deux droites : une pente de coefficient \(B\) à gauche, un plateau à \(P_{\max}\) à droite. D'où le nom : le profil ressemble à un toit.

Le point d'intersection, l'intensité arithmétique de bascule, vaut :

\[ I_{\text{bascule}} = \frac{P_{\max}}{B} \]

Exemple numérique. Avec \(P_{\max} = 2{,}56\) TFLOP/s et une bande passante mesurée \(B = 200\) Go/s :

\[ I_{\text{bascule}} = \frac{2{,}56 \times 10^{12}}{200 \times 10^9} = 12{,}8\ \text{FLOP/octet} \]

Tout noyau dont l'intensité est inférieure à 12,8 est limité par la mémoire (memory bound) et ne pourra jamais approcher le pic de calcul, quelle que soit la qualité de son implémentation. Tout noyau au-dessus est limité par le calcul (compute bound).

Le produit scalaire, à \(I = 0{,}125\), est limité par la mémoire d'un facteur cent. Sa performance maximale est \(200 \times 10^9 \times 0{,}125 = 25\) GFLOP/s, soit 1 % du pic. Un produit scalaire à 25 GFLOP/s sur cette machine est donc parfait, et quelqu'un qui s'en plaindrait n'aurait rien compris.

L'usage pratique du roofline, en cinq étapes

1. Mesurer \(P_{\max}\) par un micro-noyau de FMA saturant, pas par la formule théorique.
2. Mesurer \(B\) par STREAM, pas par la fiche technique.
3. Calculer \(I\) de votre noyau, à la main, par comptage.
4. En déduire la borne \(\min(P_{\max}, B \times I)\).
5. Mesurer votre performance réelle et calculer le rapport. Au-dessus de 70 % de la borne, il est temps de s'arrêter ou de changer d'algorithme. En dessous de 30 %, il y a un problème identifiable.

Les quatre limites du roofline

1. Il ignore la latence. Un code avec des dépendances longues et peu de parallélisme d'instructions n'atteindra pas la borne même s'il est compute bound.
2. Il suppose un seul niveau de mémoire. En réalité il y a L1, L2, L3 et la RAM, chacun avec sa bande passante. D'où les rooflines « hiérarchiques » à plusieurs plafonds.
3. Il ne distingue pas les types d'opérations. Une division flottante coûte dix à vingt fois une addition. Un code plein de divisions n'atteindra pas le pic FMA.
4. Il ignore les communications. Sur plusieurs nœuds, il faut ajouter un terme de communication. C'est l'objet du modèle de Hockney ci-dessous.

Le modèle ECM (Execution-Cache-Memory), développé par le groupe de Hager et Wellein à Erlangen, corrige les deux premiers points en modélisant explicitement les transferts entre niveaux de cache et le recouvrement partiel. Il est plus précis et plus coûteux à appliquer. À connaître, à utiliser quand le roofline ne suffit plus à expliquer un écart.

La loi d'Amdahl

Si une fraction \(s\) du temps d'exécution séquentiel ne peut pas être parallélisée, l'accélération sur \(p\) processeurs est bornée par :

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

et quand \(p \to \infty\), \(S \to 1/s\).

Exemple numérique. Avec 5 % de code séquentiel, l'accélération maximale est \(1/0{,}05 = 20\), atteinte asymptotiquement. Sur 64 cœurs on obtient \(1/(0{,}05 + 0{,}95/64) = 15{,}4\), soit une efficacité de 24 %. Sur 1 024 cœurs, \(19{,}6\), soit une efficacité de 1,9 %.

La conclusion pratique est brutale : à grande échelle, la seule chose qui compte est la fraction séquentielle. Et la fraction séquentielle inclut des choses qu'on oublie : la lecture du fichier d'entrée, l'initialisation, les écritures de résultats, les barrières de synchronisation, et le déséquilibre de charge.

La loi de Gustafson

La réponse à Amdahl, formulée en 1988. Elle observe qu'en HPC, on n'utilise pas mille processeurs pour résoudre plus vite le même problème : on les utilise pour résoudre un problème mille fois plus gros. À charge proportionnelle :

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

qui croît linéairement en \(p\).

Les deux lois ne se contredisent pas : elles décrivent deux expériences différentes.

	Strong scaling (Amdahl)	Weak scaling (Gustafson)
Taille du problème	Fixe	Proportionnelle à \(p\)
Question posée	Combien plus vite ?	Combien plus gros ?
Comportement	Plafonne à \(1/s\)	Croît linéairement
Usage typique	Réduire un temps de restitution	Augmenter la résolution ou la précision

L'erreur de méthode la plus fréquente

Annoncer une accélération sans dire lequel des deux on mesure. C'est systématiquement relevé par un relecteur d'article ou un jury de compétition. Toujours préciser, et idéalement présenter les deux courbes.

Et pour le weak scaling, préciser aussi la métrique : on ne peut pas comparer des temps, puisque le problème change. On rapporte soit le temps par unité de travail, soit l'efficacité \(E = T_1 / T_p\) (qui devrait rester proche de 1).

Le modèle de Hockney pour les communications

Pour un message de \(n\) octets entre deux processus :

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

où \(\alpha\) est la latence en secondes (le coût fixe, indépendant de la taille) et \(\beta\) l'inverse de la bande passante en secondes par octet.

Ordres de grandeur typiques sur un réseau HPC moderne : \(\alpha\) de l'ordre de 1 à 2 microsecondes, et une bande passante de plusieurs dizaines à quelques centaines de gigabits par seconde selon la technologie.

La grandeur dérivée la plus utile est \(N_{1/2} = \alpha/\beta\), la taille de message à laquelle le coût de latence égale le coût de transfert. En dessous, on paie surtout la latence : il faut agréger les messages. Au-dessus, on paie surtout le volume : il faut réduire les données ou recouvrir.

Pour les collectives, les coûts dépendent de l'algorithme. Pour un Allreduce sur \(p\) processus par doublement récursif, le coût est de l'ordre de :

\[ T \approx \log_2(p) \times (\alpha + \beta n) \]

Le terme en \(\log p\) est la raison pour laquelle un gradient conjugué, qui fait un Allreduce par itération, finit par être limité par les communications à grande échelle. C'est le résultat central du projet de PRPA23.

Les modèles plus complets, pour culture

• BSP (Bulk Synchronous Parallel), de Valiant (1990) : un calcul est une suite de super-étapes, chacune composée d'un calcul local, d'une communication et d'une barrière. Le coût d'une super-étape est \(w + g\,h + \ell\) où \(w\) est le travail local, \(h\) le volume communiqué, \(g\) le coût unitaire de communication et \(\ell\) le coût de la barrière. Élégant, pédagogique, et c'est le modèle sur lequel repose la conception de nombreux algorithmes distribués.
• LogP, de Culler et al. (1993) : quatre paramètres — latence \(L\), surcoût processeur \(o\), écart minimal entre messages \(g\), nombre de processeurs \(P\). Plus fin que Hockney, notamment pour les messages courts en rafale.
• Les bornes de communication : il existe des résultats démontrant qu'un algorithme donné doit nécessairement communiquer au moins un certain volume. Pour la multiplication matricielle, la borne de Hong et Kung, puis les travaux de Ballard, Demmel, Holtz et Schwartz, établissent une borne inférieure en \(\Omega(n^3/\sqrt{M})\) où \(M\) est la taille de la mémoire rapide. Cela a donné naissance à toute une famille d'algorithmes dits communication-avoiding, qui atteignent la borne. C'est le sujet de recherche le plus élégant du domaine, et il est enseigné dans CS267 à Berkeley.

Exercices

E1 · ★ ⏱ 2 h — Le pic, théorique et mesuré. Calculer le pic théorique de votre machine par la formule ci-dessus. Puis l'approcher par la mesure : écrire une boucle de FMA indépendantes (assez de variables d'accumulation pour masquer la latence, typiquement 8 à 16) et mesurer les GFLOPS obtenus. Comparer. Puis refaire en surveillant la fréquence réelle (turbostat ou /proc/cpuinfo en boucle) et expliquer l'écart par l'AVX offset.

E2 · ★ ⏱ 2 h — STREAM. Compiler et exécuter STREAM (le banc d'essai de John McCalpin, référence du domaine), en 1 thread puis en tous les threads. Comparer les quatre noyaux (Copy, Scale, Add, Triad) et expliquer pourquoi ils ne donnent pas le même débit. Comparer la valeur obtenue à la bande passante théorique (nombre de canaux mémoire × fréquence × largeur).

E3 · ★★ ⏱ 3 h — Le roofline complet. Avec les résultats de E1 et E2, tracer le roofline de votre machine. Ajouter les plafonds correspondant aux bandes passantes de L1, L2 et L3, mesurées par likwid-bench ou un micro-banc maison. Puis y positionner six noyaux mesurés : DAXPY, DDOT, DGEMV, DGEMM, un stencil 3D à 7 points, un SpMV en CSR.

E4 · ★★ ⏱ 2 h — Amdahl en pratique. Construire un programme dont on contrôle la fraction séquentielle, et vérifier expérimentalement la loi d'Amdahl pour \(s \in \{0{,}01; 0{,}05; 0{,}20\}\) et \(p\) de 1 à 32. Superposer mesures et théorie. Puis mesurer la fraction séquentielle réelle d'un code existant par régression sur la courbe d'accélération, et comparer à ce que vous croyiez.

E5 · ★★★ ⏱ 4 h — Le modèle de Hockney ajusté. Mesurer une courbe de ping-pong MPI, ajuster \(\alpha\) et \(\beta\) par régression linéaire, calculer \(N_{1/2}\), et vérifier la prédiction du modèle sur des tailles non utilisées pour l'ajustement. Puis constater que le modèle échoue à une taille particulière : la transition entre le protocole eager (envoi immédiat dans un tampon) et le protocole rendezvous (négociation avant transfert). Localiser le seuil, et le retrouver dans la documentation de votre implémentation MPI.

E6 · ★★★ ⏱ 4 h — Prédire avant de mesurer. Choisir un noyau que vous n'avez jamais mesuré. Écrire d'abord la prédiction complète : intensité arithmétique, régime, borne, performance attendue. Puis mesurer. Calculer l'écart. Si l'écart dépasse 30 %, trouver l'explication. C'est l'exercice le plus formateur du chapitre, et il est à refaire chaque fois que vous rencontrez un nouveau noyau.

E7 · ★★★★ ⏱ 6 h — Le modèle ECM. Appliquer le modèle ECM à un stencil 3D, en suivant la méthodologie des articles du groupe d'Erlangen. Comparer la précision de la prédiction à celle du roofline. Vous devriez constater que l'ECM est nettement plus précis, au prix d'un travail bien supérieur — ce qui est la leçon du chapitre sur le compromis entre simplicité et précision d'un modèle.

Erreurs fréquentes

Sept fautes de modélisation

1. Utiliser le pic théorique comme référence. Le pic théorique n'est jamais atteignable : fréquence réduite sous charge vectorielle, unités partagées entre fils logiques. Mesurez-le.
2. Utiliser la bande passante de la fiche technique. Elle est typiquement 20 à 40 % supérieure à ce que STREAM mesure. Mesurez-la.
3. Compter les octets au lieu des octets nécessaires. L'intensité arithmétique se calcule sur le trafic incompressible entre le cache et la mémoire, en supposant une réutilisation parfaite dans le cache. Compter tous les accès du code donne une intensité fausse et trop faible.
4. Oublier les écritures avec allocation. Une écriture dans une ligne de cache non présente provoque d'abord une lecture de cette ligne (write-allocate). Un a[i] = b[i] + c[i] transfère donc 32 octets par élément et non 24. Cela change l'intensité de 33 %. Les instructions d'écriture non temporelles (non-temporal stores) évitent ce coût.
5. Croire qu'un modèle qui se trompe est inutile. Un modèle qui prédit à 30 % près suffit à décider où investir. Un modèle qui se trompe d'un facteur trois signale au contraire une découverte à faire.
6. Confondre efficacité et accélération. L'efficacité est \(E = S(p)/p\). Une accélération de 50 sur 64 cœurs paraît bonne mais correspond à 78 % d'efficacité ; sur 1 024 cœurs, une accélération de 50 correspond à 5 %.
7. Modéliser après avoir optimisé. Le modèle sert à décider quoi optimiser. Le faire après, c'est de la justification a posteriori.

Ressources

Priorité 1 :

• Williams, Waterman, Patterson, « Roofline: An Insightful Visual Performance Model for Multicore Architectures », Communications of the ACM, 2009. L'article fondateur, huit pages, très lisible.
• Georg Hager, Gerhard Wellein, Introduction to High Performance Computing for Scientists and Engineers, CRC Press, chapitres sur les modèles de performance. Le meilleur traitement pédagogique.
• Hoefler & Belli, « Scientific Benchmarking of Parallel Computing Systems », SC 2015. Les douze règles de mesure. À lire absolument.

Priorité 2 :

• STREAM (cs.virginia.edu/stream/) : le banc d'essai et sa documentation.
• Intel Advisor, qui produit un roofline automatiquement avec les boucles positionnées dessus. Le plus pédagogique des outils commerciaux, gratuit dans oneAPI.
• Les articles sur le modèle ECM du groupe de Hager et Wellein (Erlangen).
• Amdahl, « Validity of the single processor approach… » (1967) et Gustafson, « Reevaluating Amdahl's Law », CACM, 1988. Deux articles de deux pages chacun, à lire pour la culture.

Priorité 3 :

• Valiant, « A Bridging Model for Parallel Computation », CACM, 1990 (BSP).
• Culler et al., « LogP: Towards a Realistic Model of Parallel Computation », PPoPP 1993.
• Ballard, Demmel, Holtz, Schwartz, « Minimizing Communication in Numerical Linear Algebra », 2011, et le cours CS267 de Berkeley sur les algorithmes communication-avoiding.

---

À retenir

Les quatre formules à connaître par cœur

Roofline : \(P = \min(P_{\max}, B \times I)\)

Intensité de bascule : \(I_{\text{bascule}} = P_{\max}/B\)

Amdahl : \(S(p) = 1/(s + (1-s)/p)\), plafond \(1/s\)

Hockney : \(T(n) = \alpha + \beta n\), seuil \(N_{1/2} = \alpha/\beta\)

Et la méthode

Mesurer la borne, calculer l'intensité, prédire, mesurer, expliquer l'écart. Dans cet ordre. C'est tout le chapitre.

Chapitre suivant : Architecture et mémoire.