2 · Architecture et mémoire¶

Ce chapitre est le programme de rattrapage de l'architecture matérielle, qui n'a aucune UE dans la maquette FISA. C'est aussi le socle de tout ce qui suit : on n'optimise pas un code sans savoir sur quoi il tourne.

Difficulté : ★★★ · ⏱ 35 h

Intuition¶

Un processeur moderne peut exécuter une dizaine d'opérations par cycle d'horloge. Un accès à la mémoire principale coûte de l'ordre de deux à trois cents cycles. Le rapport est donc d'environ deux mille à un.

Tout le matériel — caches, préchargement, exécution dans le désordre, hyper-threading — existe pour masquer ce rapport. Et toute l'optimisation mono-nœud consiste à aider ce matériel à faire son travail, principalement en organisant les données pour qu'elles soient lues dans le bon ordre.

C'est la raison pour laquelle, en HPC, la disposition des données compte plus que l'algorithme dans un très grand nombre de cas.

La hiérarchie mémoire¶

Les ordres de grandeur¶

Les valeurs exactes dépendent de la machine ; ce sont les ordres de grandeur et les rapports qui importent.

Niveau	Taille typique	Latence (cycles)	Bande passante relative
Registres	quelques centaines d'octets	0 à 1	—
Cache L1 données	32 à 64 Ko par cœur	4 à 5	très élevée
Cache L2	512 Ko à 2 Mo par cœur	12 à 20	élevée
Cache L3	16 à 256 Mo partagé	40 à 80	moyenne
Mémoire principale locale	dizaines à centaines de Go	200 à 300	faible
Mémoire d'un autre domaine NUMA	—	300 à 500	très faible
Stockage NVMe	To	~ 10⁵	négligeable

Le nombre à retenir : la mémoire principale est deux ordres de grandeur plus lente que le L1, et son coût par octet transféré est le facteur limitant de la majorité des codes de calcul.

La ligne de cache¶

L'unité de transfert entre les niveaux est la ligne de cache, de 64 octets sur la plupart des architectures actuelles (parfois 128). Conséquences directes, et ce sont les plus importantes du chapitre :

Lire un octet coûte le même prix que lire 64 octets consécutifs. D'où la valeur de la contiguïté.
Un parcours avec un pas supérieur à 64 octets gaspille la majeure partie de chaque ligne chargée. Un parcours de tableau avec un pas de 16 double (128 octets) transfère deux lignes pour utiliser 8 octets : 94 % de gaspillage.
Deux threads qui écrivent dans la même ligne de cache se battent pour elle, même s'ils touchent des octets différents. C'est le faux partage (false sharing), déjà rencontré en ICPA24.

Le préchargeur¶

Le matériel détecte les motifs d'accès réguliers et charge les lignes à l'avance. Il est très efficace sur un parcours séquentiel ou à pas constant, et complètement inopérant sur un parcours aléatoire ou par indirection.

D'où la règle : un parcours séquentiel peut être dix fois plus rapide qu'un parcours aléatoire sur les mêmes données, à nombre d'accès identique. Ce n'est pas de la complexité algorithmique, c'est du matériel.

NUMA¶

Un nœud de calcul a plusieurs domaines NUMA (Non-Uniform Memory Access), typiquement un par socket, parfois plusieurs par socket sur les architectures récentes. Chaque domaine a sa mémoire locale, et l'accès à la mémoire d'un autre domaine passe par l'interconnexion entre processeurs : latence supérieure, bande passante inférieure.

La règle de la première touche (first touch) : sous Linux, une page virtuelle n'est associée à une page physique qu'au premier accès en écriture, et elle est allouée dans le domaine NUMA du cœur qui y accède. Conséquence, contre- intuitive et coûteuse :

// MAUVAIS : tout le tableau est alloué dans le domaine du thread maître
double *a = malloc(N * sizeof(double));
for (size_t i = 0; i < N; i++) a[i] = 0.0;     // séquentiel
#pragma omp parallel for
for (size_t i = 0; i < N; i++) a[i] = f(i);    // la moitié des threads
                                               // accèdent à distance

// BON : chaque thread initialise la part qu'il calculera ensuite
double *a = malloc(N * sizeof(double));
#pragma omp parallel for
for (size_t i = 0; i < N; i++) a[i] = 0.0;     // même découpage
#pragma omp parallel for
for (size_t i = 0; i < N; i++) a[i] = f(i);

Le gain typique sur une machine à deux domaines est un facteur 1,5 à 2 sur un code limité par la mémoire. C'est l'une des optimisations les plus rentables du HPC, et l'une des moins connues.

La disposition des données : AoS contre SoA¶

La question la plus fréquente et la plus déterminante.

Tableau de structures (Array of Structures, AoS) :

struct Particule { double x, y, z, vx, vy, vz, masse; };
struct Particule p[N];
// Mettre à jour toutes les positions x :
for (int i = 0; i < N; i++) p[i].x += p[i].vx * dt;

Chaque itération touche deux double séparés de 24 octets, dans une structure de 56 octets. Une ligne de cache de 64 octets contient un peu plus d'une particule, dont on utilise 16 octets sur 56. Et les accès ne sont pas contigus, donc la vectorisation est impossible sans instructions de rassemblement coûteuses.

Structure de tableaux (Structure of Arrays, SoA) :

struct Particules {
    double *x, *y, *z, *vx, *vy, *vz, *masse;
};
// Même mise à jour :
for (int i = 0; i < N; i++) p.x[i] += p.vx[i] * dt;

Deux parcours parfaitement séquentiels de tableaux contigus. Chaque ligne de cache est utilisée à 100 %, et la boucle se vectorise immédiatement.

Le gain : typiquement un facteur 2 à 6 sur ce type de noyau.

Quand l'AoS est préférable

Ce n'est pas une règle absolue. L'AoS gagne quand on accède à tous les champs d'un même élément : dans ce cas la structure entière est dans une ou deux lignes de cache, alors que la SoA nécessite sept accès dispersés.

En pratique, beaucoup de codes utilisent un compromis, l'AoSoA ou tiled AoS : un tableau de structures dont chaque champ est un petit tableau de la largeur d'un registre vectoriel. On obtient la vectorisation de la SoA et une partie de la localité de l'AoS. C'est ce que font les codes de dynamique moléculaire les plus optimisés.

Le pipeline et le parallélisme d'instructions¶

Un processeur exécute les instructions en plusieurs étages (lecture, décodage, exécution, écriture), et plusieurs instructions sont en cours simultanément. Il peut aussi les réordonner (out-of-order) et en exécuter plusieurs par cycle (superscalaire).

Trois conséquences pratiques.

1. Les dépendances tuent le débit. Cette boucle a une chaîne de dépendance : chaque addition attend la précédente.

double s = 0.0;
for (int i = 0; i < N; i++) s += a[i];   // latence de l'addition en série

Si une addition flottante a une latence de 4 cycles et un débit de 2 par cycle, cette boucle tourne à un huitième du débit possible. La solution est le déroulement avec plusieurs accumulateurs :

double s0=0, s1=0, s2=0, s3=0;
for (int i = 0; i < N; i += 4) {
    s0 += a[i]; s1 += a[i+1]; s2 += a[i+2]; s3 += a[i+3];
}
double s = (s0 + s1) + (s2 + s3);

Les quatre chaînes sont indépendantes, le pipeline se remplit. Attention : le résultat n'est pas identique au bit près, l'addition flottante n'étant pas associative. C'est pour cela que le compilateur ne le fait pas sans -ffast-math ou #pragma omp simd reduction.

2. Les branchements mal prédits coûtent cher. Une prédiction erronée vide le pipeline : de l'ordre de quinze à vingt cycles perdus. Un if imprévisible dans une boucle chaude est très coûteux. Remèdes : rendre le branchement prévisible (trier les données), le supprimer (calcul sans branche, branchless), ou le remplacer par une opération masquée vectorielle.

3. La latence des opérations diffère fortement.

Opération	Latence typique (cycles)
Addition, multiplication entière	1 à 3
Addition, multiplication flottante, FMA	4 à 5
Division flottante	13 à 20
Racine carrée	12 à 20
Fonctions transcendantes (`exp`, `sin`)	20 à 100

Une division dans une boucle chaude est souvent le goulot. Remplacer a[i] / b par a[i] * inv_b où inv_b = 1.0/b est calculé une fois : facteur trois ou plus. Le compilateur ne le fait pas sans autorisation, parce que ce n'est pas exactement équivalent en flottant.

Le SIMD¶

Les registres vectoriels permettent d'appliquer une opération à plusieurs éléments simultanément.

Extension	Largeur	`double` par registre	`float` par registre
SSE2	128 bits	2	4
AVX, AVX2	256 bits	4	8
AVX-512	512 bits	8	16
ARM NEON	128 bits	2	4
ARM SVE	variable (128 à 2048)	variable	variable

Trois voies pour vectoriser, par ordre de préférence :

Laisser le compilateur faire, en levant les obstacles : restrict, alignement, boucles simples, disposition SoA. C'est de loin la meilleure voie : portable, maintenable, et souvent aussi bonne que le code manuel.
Guider le compilateur par des directives : #pragma omp simd, #pragma omp simd reduction(+:s), #pragma GCC ivdep. On lui promet l'absence de dépendance.
Écrire les intrinsics à la main : _mm256_fmadd_pd, etc. Non portable, verbeux, et rarement nécessaire. À réserver aux noyaux critiques après avoir épuisé les deux premières voies, et en gardant toujours une version scalaire de référence.

Le SIMD et la fréquence

Sur certaines architectures, l'utilisation soutenue des registres 512 bits fait baisser la fréquence du processeur (AVX offset), parfois de 20 à 30 %. Une version AVX-512 peut donc être moins rapide qu'une version AVX2 si le gain de largeur ne compense pas la perte de fréquence. Cela se mesure, et cela dépend du modèle de processeur. Ne présumez rien.

Le blocking de cache¶

La technique d'optimisation la plus rentable sur les codes d'algèbre linéaire dense. Le principe : découper le calcul en blocs suffisamment petits pour que les données tiennent dans le cache, afin de les réutiliser avant qu'elles ne soient évincées.

Sur un produit matriciel naïf \(C = AB\) de matrices \(n \times n\) avec \(n = 4096\), chaque matrice fait 128 Mo : rien ne tient en cache, et chaque élément de \(A\) et de \(B\) est relu \(n\) fois depuis la mémoire. Le code est massivement limité par la bande passante.

Avec un blocage en tuiles de taille \(b\) telle que trois tuiles \(b \times b\) tiennent dans le L2, chaque tuile est chargée une fois et réutilisée \(b\) fois. L'intensité arithmétique passe de \(O(1)\) à \(O(b)\), ce qui fait basculer le noyau du régime memory bound au régime compute bound.

Le gain typique : un facteur 3 à 10 selon la taille et la machine. C'est le sujet de l'article de référence de Goto & van de Geijn, Anatomy of High-Performance Matrix Multiplication, qui décrit précisément comment les bibliothèques BLAS optimisées structurent ce blocage sur plusieurs niveaux de hiérarchie.

Le programme de rattrapage, en quatre étapes¶

Quatre étapes, 25 heures

Étape 1 · Lire, 8 h.

Hennessy & Patterson, Computer Architecture: A Quantitative Approach, chapitre 2 (hiérarchie mémoire) et chapitre 3 (parallélisme d'instructions).
Ulrich Drepper, What Every Programmer Should Know About Memory (2007, gratuit), en entier.

Étape 2 · Mesurer, 5 h. Les exercices E1 à E3 ci-dessous : courbe de hiérarchie mémoire, coût de NUMA, effet du pas d'accès.

Étape 3 · Optimiser un GEMM, 8 h. L'exercice E6, par étapes mesurées. C'est l'exercice initiatique du domaine.

Étape 4 · Les intrinsics, 4 h. Les manuels d'Agner Fog et l'Intel Intrinsics Guide, avec l'exercice E5.

Ce que le rattrapage ne donnera pas : la conception d'un mini-processeur dans un simulateur. C'est formateur mais non nécessaire. Si le sujet vous attire, Nand2Tetris ou Harris & Harris, Digital Design and Computer Architecture, le couvrent.

Exercices¶

E1 · ★★ ⏱ 3 h — La courbe de la hiérarchie. Allouer un tableau de taille \(S\) croissante de 1 Ko à 1 Go, le parcourir en boucle avec un pas de 64 octets (une ligne de cache), et mesurer le temps moyen par accès. Tracer en log-log. Identifier les paliers L1, L2, L3, RAM, et comparer les tailles observées aux valeurs de lscpu. Puis refaire avec un parcours par liste chaînée aléatoire (pour désactiver le préchargeur) et comparer : l'écart mesure l'efficacité du préchargement.

E2 · ★★ ⏱ 2 h — Le coût du pas. Parcourir un tableau de 1 Go avec des pas de 1, 2, 4, 8, 16, 32, 64, 128 éléments de type double. Tracer le débit effectif (octets utiles par seconde) en fonction du pas. Le débit doit s'effondrer dès que le pas dépasse une ligne de cache, puis se stabiliser, puis remonter légèrement quand le pas dépasse la taille d'une page.

E3 · ★★ ⏱ 3 h — NUMA. Sur une machine à au moins deux domaines, mesurer la bande passante de STREAM dans quatre configurations : local, distant, entrelacé, laissé au système. Puis reproduire la démonstration de la première touche avec un code OpenMP. Vérifier la répartition physique avec numastat.

E4 · ★★ ⏱ 2 h — Les dépendances et le déroulement. Mesurer une somme de tableau avec 1, 2, 4, 8 et 16 accumulateurs indépendants. Tracer les GFLOPS. Identifier le point de saturation, et le rapprocher du rapport latence/débit de l'addition flottante sur votre processeur (les tables d'Agner Fog le donnent). Vérifier ce que fait le compilateur avec -O3 seul, puis avec -O3 -ffast-math.

E5 · ★★★ ⏱ 4 h — Trois niveaux de SIMD. Écrire un AXPY (\(y \leftarrow \alpha x + y\)) en quatre versions : scalaire, avec #pragma omp simd, avec intrinsics AVX2, et avec intrinsics AVX-512 si la machine le permet. Mesurer les quatre, vérifier l'assembleur généré pour la version omp simd, et surveiller la fréquence du processeur pendant les mesures. Conclusion attendue : la version guidée par directive est aussi bonne que les intrinsics, ce qui justifie de ne presque jamais écrire d'intrinsics.

E6 · ★★★★ ⏱ 8 h — Le GEMM par étapes. Le grand exercice. Implémenter un produit matriciel \(C \mathrel{+}= AB\) en double précision, et le faire progresser en mesurant les GFLOPS à chaque étape :

Étape	Attente réaliste (en % du pic)
1. Trois boucles imbriquées naïves (`i`, `j`, `k`)	1 à 3 %
2. Réordonnancement des boucles (`i`, `k`, `j`)	5 à 10 %
3. Blocage à un niveau (tuiles pour le L2)	15 à 25 %
4. Blocage à deux niveaux (L2 et L1)	25 à 35 %
5. Micro-noyau déroulé avec accumulateurs en registres	40 à 55 %
6. Vectorisation explicite du micro-noyau	55 à 70 %
7. Parallélisation OpenMP	60 à 80 % du pic multicœur
Référence : OpenBLAS ou MKL	85 à 95 %

Les valeurs dépendent de la machine et de votre persévérance ; ce sont les rapports entre étapes qui comptent. Ressources : la série How to Optimize GEMM et l'article de Goto & van de Geijn.

E7 · ★★★ ⏱ 3 h — Le faux partage, quantifié. Reprendre l'exercice de ICPA24 sur le faux partage, et le diagnostiquer avec perf c2c. Lire le rapport : il identifie la ligne de cache contestée et les adresses en cause. C'est l'outil qui transforme un mystère en diagnostic.

E8 · ★★★ ⏱ 4 h — Le TLB. Mesurer les défauts de TLB avec perf stat -e dTLB-load-misses,dTLB-loads sur un parcours aléatoire d'un tableau de plusieurs gigaoctets, en pages de 4 Ko puis en huge pages de 2 Mo. Rapporter le taux de défauts et le temps, et vérifier la cohérence quantitative entre les deux. Lien : ARSE23.

Erreurs fréquentes¶

Huit fautes d'optimisation mono-nœud

Optimiser la complexité algorithmique en ignorant la localité. Un algorithme en \(O(n \log n)\) avec des accès aléatoires peut être plus lent qu'un \(O(n^2)\) séquentiel pour des \(n\) modérés. La constante cachée contient la hiérarchie mémoire.
Utiliser des listes chaînées, des arbres de pointeurs, des std::map dans un code de calcul. Chaque déréférencement est un défaut de cache potentiel.
Garder une disposition AoS par habitude objet. C'est le réflexe naturel du programmeur C++ formé à l'objet, et c'est souvent la faute la plus coûteuse du code.
Oublier l'alignement. Une allocation non alignée sur la largeur du registre vectoriel force le compilateur à générer des chargements non alignés, plus lents, ou à ajouter un prologue de boucle. aligned_alloc ou posix_memalign sur 64 octets.
Écrire des intrinsics trop tôt. Toujours essayer les deux premières voies de vectorisation d'abord. Le code en intrinsics est non portable, et il sera probablement battu par le compilateur sur la génération suivante de processeurs.
Ne pas mesurer la fréquence. Voir l'AVX offset. Une conclusion sur le SIMD sans surveiller la fréquence peut être entièrement fausse.
Activer l'hyper-threading sans mesurer. Il aide sur les codes en attente de mémoire, il nuit sur les codes intensifs en calcul. Les deux sont vrais, il faut mesurer.
Croire que le compilateur va tout faire. Il fait beaucoup, et il ne fait presque jamais le blocage de cache, le changement de disposition des données, ni le choix de l'algorithme. Ces trois-là sont à vous.

Ressources¶

Priorité 1 :

John Hennessy, David Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann (6ᵉ édition, 2017 ; des éditions plus récentes peuvent exister). Chapitres 2 et 3 en priorité.
Ulrich Drepper, What Every Programmer Should Know About Memory, 2007. Gratuit, inégalé sur les caches et NUMA du point de vue du programmeur.
Randal Bryant, David O'Hallaron, Computer Systems: A Programmer's Perspective, 3ᵉ éd. Chapitres 3 (assembleur), 5 (optimisation) et 6 (hiérarchie mémoire). Le meilleur livre pour faire le lien entre le code et la machine.

Priorité 2 :

Les manuels d'Agner Fog (agner.org/optimize), quatre volumes gratuits, dont les tables d'instructions donnant latence et débit par microarchitecture. La référence des professionnels.
L'Intel 64 and IA-32 Architectures Optimization Reference Manual, et l'Intel Intrinsics Guide en ligne.
Le Arm Neoverse Software Optimization Guide et la documentation SVE, pour l'architecture ARM.
Compiler Explorer (godbolt.org), en permanence.

Priorité 3 :

Goto & van de Geijn, « Anatomy of High-Performance Matrix Multiplication », ACM TOMS, 2008. L'article qui explique comment on atteint le pic.
La série How to Optimize GEMM, un tutoriel pas à pas fondé sur ce travail.
Le projet BLIS et les articles de van Zee & van de Geijn (2015) sur le cadre qui a généralisé cette approche.
llvm-mca, OSACA, uiCA : analyseurs statiques de blocs d'assembleur, qui prédisent le débit en cycles.
MAQAO (maqao.org, UVSQ) : analyse de boucles sur binaire, avec diagnostic des limitations.

À retenir¶

Les six règles de l'optimisation mono-nœud

Contiguïté d'abord. Un parcours séquentiel de tableau contigu, toujours.
SoA plutôt qu'AoS dès qu'on traite un champ à la fois.
Première touche : initialiser en parallèle, avec le même découpage que le calcul.
Bloquer pour le cache sur les noyaux à réutilisation de données.
Casser les chaînes de dépendance par des accumulateurs multiples.
Laisser le compilateur vectoriser, en levant les obstacles plutôt qu'en écrivant des intrinsics.

Le nombre à retenir

Un accès à la mémoire principale coûte de l'ordre de deux cents cycles, contre un cycle pour une opération arithmétique. Tout découle de ce rapport.

Chapitre suivant : MPI en profondeur.