Séance 4 — Architectures distribuées et NUMA
bleutitreSéance 4 : Architectures distribuées et NUMA
Limites de l’espionnage et passage au distribué
Une machine à bus ressemble à un petit bureau : tous les cœurs partagent un bus, comme un tableau blanc commun, et chacun surveille ce qui s’y écrit. Que se passe-t-il quand la machine grandit ? Cinquante personnes autour d’un seul tableau blanc ne peuvent plus travailler : les écritures se succèdent sans répit, chacun doit tout surveiller, et l’attente pour écrire s’allonge. La solution consiste à créer plusieurs bureaux, chacun avec son tableau, reliés par une messagerie, et à tenir dans chaque bureau un répertoire qui sait qui possède quoi : c’est l’architecture NUMA avec cohérence par répertoire.
Pourquoi l’espionnage ne passe pas à l’échelle
Les protocoles MSI et MESI de la Séance 2 reposent sur l’espionnage du bus (snooping). Rappel du fonctionnement :
- tous les caches surveillent un bus partagé ;
- chaque transaction est diffusée à tous ;
- le mécanisme est direct, mais il ne passe pas à l’échelle.
Problèmes de l’espionnage avec beaucoup de cœurs :
Contention du bus : un seul bus partagé devient un goulot d’étranglement.
- avec 2 à 4 cœurs : le bus tient la charge ;
- avec 8 à 16 cœurs : le bus sature ;
- au-delà de 32 cœurs : un bus unique n’est plus réaliste.
Bande passante limitée : chaque transaction consomme de la bande passante.
- chaque cache doit examiner toutes les transactions ;
- une transaction est examinée par les \(n-1\) autres caches : un travail en \(O(n)\) par transaction.
Consommation d’énergie : tous les caches doivent rester actifs en permanence.
- surveillance continue, donc énergie dépensée sans utilité quand le cache n’a pas la donnée ;
- une contrainte forte pour les serveurs et les centres de données.
Le problème de passage à l’échelle de l’espionnage : le trafic sur le bus croît linéairement avec le nombre de cœurs, mais la bande passante du bus reste fixe. Il existe donc un nombre maximal de cœurs au-delà duquel le système ne peut plus fonctionner efficacement.
Limite pratique : environ 8 à 16 cœurs avec espionnage sur un bus unique.
Le premier état montre une écriture de P0 sur une donnée que seul C2 possède : P0 diffuse un BusRdX, les trois autres caches examinent la transaction (cadres orange) et seul C2 a une copie, qu’il invalide (S\(\rightarrow\)I) ; C0 passe de I à M. Avec seize cœurs, la même écriture fait travailler quinze caches pour une seule copie utile. Le second état chiffre la charge du bus, avec des valeurs d’illustration : chaque cœur émet \(20\) millions de transactions par seconde et le bus en écoule \(200\) millions. La demande vaut \(40\) % de la capacité avec 4 cœurs, \(80\) % avec 8, \(160\) % avec 16 et \(320\) % avec 32 : au-delà de \(10\) cœurs, les requêtes attendent leur tour et chaque cœur ralentit.
4 cœurs : 3 caches examinent la transaction
16 cœurs et charge du bus selon le nombre de cœurs
Architectures NUMA (Non-Uniform Memory Access)
Principe de base
Une architecture NUMA (Non-Uniform Memory Access) est un système multiprocesseur où la latence d’accès à la mémoire dépend de la localisation physique de la mémoire par rapport au processeur.
Caractéristiques :
- plusieurs nœuds, chacun avec des processeurs et une mémoire locale ;
- accès local rapide, accès distant plus lent ;
- interconnexion entre les nœuds (liens point à point, réseau, crossbar).
NUMA, c’est comme des bibliothèques municipales dans différents quartiers.
Architecture UMA (Uniform Memory Access) :
- une seule bibliothèque centrale ;
- tout le monde met le même temps pour y accéder ;
- mais si elle est loin, c’est lent pour tout le monde.
Architecture NUMA :
- plusieurs bibliothèques de quartier ;
- on va vite à la bibliothèque de son quartier (mémoire locale) ;
- mais si le livre est dans un autre quartier, c’est plus long (mémoire distante) ;
- avantage : chacun a une bibliothèque proche ;
- défi : savoir où se trouve chaque livre.
Organisation d’un système NUMA
Un système NUMA à quatre nœuds se décrit nœud par nœud : chaque nœud a ses cœurs, son cache de dernier niveau (L3) et sa mémoire locale ; les nœuds sont reliés par des liens. Dans la figure, les liens forment un anneau : N0 est voisin de N1 et de N2, mais pas de N3, qu’il n’atteint qu’en deux sauts. C’est cette distance, et non la seule séparation local/distant, qui donne les trois latences du tableau suivant.
Le cœur c0 de N0 lit successivement une adresse de sa mémoire locale, une adresse de la mémoire de N1, puis une adresse de la mémoire de N3. Pour l’accès local, la requête manque dans le L3 (cadre orange) et va en mémoire 0 : \(80\) ns, soit \(240\) cycles à \(3\) GHz. Pour la mémoire de N1, la requête et la donnée traversent un lien (en rouge) : \(140\) ns, \(1{,}75\) fois l’accès local. Pour la mémoire de N3, il faut deux liens, par N1 : \(200\) ns, \(2{,}5\) fois l’accès local.
Accès local : défaut dans le L3, lecture en mémoire 0
Après les trois accès : 0, 1 et 2 sauts
Latences typiques d’accès à la mémoire (ordres de grandeur ; cycles à \(3\) GHz, \(1\) ns \(=3\) cycles, comme à la Séance 1) :
| Type d’accès | Latence | Cycles | Rapport |
|---|---|---|---|
| Cache L1 | 1 ns | 3 | 1\(\times\) |
| Cache L2 | 4 ns | 12 | 4\(\times\) |
| Cache L3 | 12 ns | 36 | 12\(\times\) |
| Mémoire locale | 80 ns | 240 | 80\(\times\) |
| Mémoire distante (1 saut) | 140 ns | 420 | 140\(\times\) |
| Mémoire distante (2 sauts) | 200 ns | 600 | 200\(\times\) |
La mesure de référence d’un serveur bi-socket récent (Cascade Lake) donne \(80{,}8\) ns en local et \(140{,}4\) ns vers l’autre socket : le rapport \(140{,}4/80{,}8 \approx 1{,}74\) correspond aux \(140/80=1{,}75\) du tableau.
Latences du tableau, à la même échelle : l’accès distant à deux sauts coûte 200 fois un succès en L1.
Un programme accède à un tableau de 1 million d’entiers (4 Mo, soit environ \(3{,}81\) Mio). Sur un système NUMA à 4 nœuds :
- 60 % des accès sont locaux (80 ns chacun) ;
- 30 % sont distants à 1 saut (140 ns) ;
- 10 % sont distants à 2 sauts (200 ns).
On suppose que chaque accès va en mémoire (aucun succès en cache) et que les accès ne se recouvrent pas.
a) Calculer la latence moyenne par accès.
b) Si l’on obtenait 90 % d’accès locaux, quel serait le gain ?
c) Combien de temps faut-il pour accéder à tous les éléments, dans chaque cas ?
Afficher la correction
Méthode. La latence moyenne est une moyenne pondérée : chaque latence compte pour la part des accès qui la subissent. Les parts doivent faire \(100\) %.
a) Latence moyenne (cas actuel) :
\[L_{\text{moyenne}} = 0{,}6 \times 80 + 0{,}3 \times 140 + 0{,}1 \times 200 = 48 + 42 + 20 = 110 \text{ ns}\]
b) Cas optimisé (90 % local) :
En supposant que les 10 % restants sont à 1 saut : \[L_{\text{optimisée}} = 0{,}9 \times 80 + 0{,}1 \times 140 = 72 + 14 = 86 \text{ ns}\]
Accélération : \[S = \frac{110}{86} \approx 1{,}28\] Le programme va \(1{,}28\) fois plus vite ; son temps baisse de \((110-86)/110 \approx 21{,}8\) %. Une accélération de \(1{,}28\) ne signifie pas \(28\) % de temps en moins.
c) Temps total :
Cas actuel : \[T_{\text{actuel}} = 1\,000\,000 \times 110 \text{ ns} = 110\,000\,000 \text{ ns} = 0{,}11 \text{ seconde}\]
Cas optimisé : \[T_{\text{optimisé}} = 1\,000\,000 \times 86 \text{ ns} = 86\,000\,000 \text{ ns} = 0{,}086 \text{ seconde}\]
Différence : 24 millisecondes économisées sur un seul parcours du tableau.
Erreur fréquente : faire la moyenne des trois latences sans les pondérer, \((80+140+200)/3 = 140\) ns, comme si chaque type d’accès était aussi fréquent.
Cohérence par répertoire (directory-based)
Principe du répertoire
L’espionnage ne fonctionnant plus avec beaucoup de cœurs, un autre mécanisme est nécessaire : le répertoire (directory).
Un protocole de cohérence à répertoire (directory-based) maintient, pour chaque bloc de mémoire, des informations centralisées :
- quel(s) cache(s) possède(nt) une copie du bloc ;
- l’état du bloc (propre ou modifié) ;
- le nœud home qui gère le bloc.
Avantage principal : des communications point à point au lieu d’une diffusion.
Le répertoire, c’est comme le système de suivi des colis.
Sans répertoire (espionnage) :
- pour trouver un colis, on crie dans toutes les directions ;
- tous les livreurs doivent écouter tous les cris ;
- c’est inefficace avec beaucoup de livreurs.
Avec répertoire :
- un bureau central sait où est chaque colis ;
- on le lui demande, il indique exactement où aller ;
- les communications sont ciblées ;
- le système passe beaucoup mieux à l’échelle.
Structure du répertoire
Chaque entrée du répertoire contient :
l’état du bloc :
Uncached(U) : aucun cache ne possède le bloc ;Shared(S) : un ou plusieurs caches ont une copie en lecture seule ;Modified(M) : un seul cache a le bloc, et il l’a modifié (dirty).
le vecteur de présence (presence vector) :
- un bit par nœud, qui indique si ce nœud a une copie ;
- exemple avec 4 nœuds : \([1, 0, 1, 0]\) = les nœuds 0 et 2 ont le bloc.
le bit dirty :
- il indique si le bloc a été modifié ; il équivaut donc à l’état M ;
- le nœud qui a la copie modifiée est alors le seul dont le bit de présence vaut 1.
Structure d’un répertoire de cohérence : trois blocs consécutifs de 64 octets.
Ce vecteur a un prix : avec \(p\) nœuds, chaque bloc de \(64\) octets (\(512\) bits) porte \(p\) bits de présence, soit \(16/512 \approx 3{,}1\) % de la mémoire pour \(16\) nœuds et \(64/512 = 12{,}5\) % pour \(64\) nœuds. Au-delà, les machines remplacent le vecteur complet par des représentations plus compactes.
Concepts clés : nœud home, demandeur et propriétaire
Dans un système à répertoire :
- Nœud home : le nœud qui possède physiquement l’adresse mémoire et tient l’entrée de répertoire de ce bloc. Il est responsable de la cohérence de ce bloc.
- Nœud demandeur (requestor) : le nœud qui lance une demande d’accès (lecture ou écriture) à un bloc mémoire.
- Nœud propriétaire (owner) : le nœud qui possède actuellement la seule copie valide d’un bloc modifié.
Principe de fonctionnement :
Le demandeur envoie une demande au nœud home.
Le home consulte son répertoire.
Le home coordonne les actions nécessaires :
- si le bloc est en mémoire (propre) \(\rightarrow\) il l’envoie au demandeur ;
- si le bloc est modifié ailleurs \(\rightarrow\) il demande un write-back, puis envoie le bloc ;
- si le bloc est partagé et que le demandeur veut écrire \(\rightarrow\) il invalide toutes les copies.
Protocoles à répertoire : cas d’usage
Les trois cas qui suivent ont lieu sur une machine à 4 nœuds ; le bloc X a son home en N0 et vaut \(3\) en mémoire au départ. Chaque figure montre, à gauche, les caches des nœuds (état MSI de la copie de X et sa valeur) et la mémoire du home ; à droite, l’entrée du répertoire et le tableau des actions déjà faites, avec le temps écoulé depuis la demande. Rouge : modifié à l’étape ; orange : consulté sans changement ; flèches bleues : requêtes et messages de contrôle ; vertes : données ; violettes : write-back ; grises : étapes passées.
Cas 2 : défaut de lecture sur un bloc sale (Modified)
Scénario : le nœud 1 veut lire un bloc, mais le nœud 2 l’a modifié.
Demandeur (N1) \(\rightarrow\) home (N0) : « Read Request ».
Home : consulte le répertoire :
- état = Modified ;
- propriétaire = nœud 2.
Home \(\rightarrow\) propriétaire (N2) : « Fetch » (demande d’intervention).
Propriétaire \(\rightarrow\) home : « Data Write-Back » et les données.
Home \(\rightarrow\) demandeur : « Data Reply » et les données.
Home : met à jour le répertoire :
- état = Shared ;
- vecteur = \([0, 1, 1, 0]\) (N1 et N2 ont une copie).
Le bit de N0 reste à 0 : le vecteur de présence décrit les caches qui ont une copie ; la mémoire du home, remise à jour par le write-back, n’y figure pas.
Messages échangés : 4 messages.
Latence : 4 \(\times\) latence réseau + temps mémoire, soit \(4\times50+80=280\) ns.
Au départ, la mémoire du home contient X \(=3\), valeur périmée (en gris) : N2 a écrit \(8\) et détient la seule copie valide, en M. La consultation du répertoire révèle l’état M et le propriétaire N2 : la mémoire ne peut pas répondre. Le home envoie un Fetch ; N2 renvoie le bloc (write-back), passe de M à S, et le home écrit \(8\) en mémoire (\(230\) ns). La réponse arrive à N1 à \(280\) ns.
Étape 4 : write-back de N2, mémoire remise à jour
Étape 6 : répertoire en S, présence 0110
Sur un système NUMA à 4 nœuds, la latence réseau vaut 50 ns par message et un accès mémoire 80 ns.
Le nœud 2 veut lire un bloc dont le home est le nœud 0 :
a) Calculer la latence si le bloc est propre en mémoire.
b) Calculer la latence si le bloc est modifié par le nœud 3.
c) Comparer avec un accès local (80 ns). Quel est le surcoût du NUMA ?
Afficher la correction
Méthode. Identifier le cas d’après l’état du bloc (propre : cas 1 ; modifié : cas 2), écrire la suite des messages, puis additionner les temps qui se succèdent : chaque message coûte une latence réseau, chaque accès à la mémoire du home un temps mémoire.
a) Bloc propre :
Séquence : N2 \(\rightarrow\) N0 (request), N0 lit la mémoire, N0 \(\rightarrow\) N2 (reply).
\[\text{Latence} = 50 + 80 + 50 = 180 \text{ ns}\]
b) Bloc modifié par N3 :
Séquence :
- N2 \(\rightarrow\) N0 : request (50 ns) ;
- N0 \(\rightarrow\) N3 : fetch (50 ns) ;
- N3 \(\rightarrow\) N0 : write-back (50 ns) ;
- N0 écrit en mémoire (80 ns) ;
- N0 \(\rightarrow\) N2 : reply (50 ns).
\[\text{Latence} = 50 + 50 + 50 + 80 + 50 = 280 \text{ ns}\]
c) Comparaison avec l’accès local :
- accès local : 80 ns ;
- accès distant (propre) : 180 ns \(\rightarrow\) \(180/80 = 2{,}25\) fois plus lent ;
- accès distant (sale) : 280 ns \(\rightarrow\) \(280/80 = 3{,}5\) fois plus lent.
Conclusion : la localité des données est déterminante en NUMA. Dans ce modèle, un accès distant coûte \(2{,}25\) à \(3{,}5\) fois un accès local.
Erreur fréquente : oublier, dans le cas modifié, l’écriture en mémoire du home, ou compter le fetch et le write-back comme un seul message. Autre confusion : ce modèle compte \(50\) ns par message ; il ne se compare pas terme à terme aux \(140\) ns mesurées d’un accès distant, qui ne passe pas par trois nœuds.
Cas 3 : défaut d’écriture (lecture exclusive)
Scénario : le nœud 1 veut écrire dans un bloc partagé par les nœuds 2 et 3.
Demandeur (N1) \(\rightarrow\) home (N0) : « Write Request ».
Home : consulte le répertoire :
- état = Shared ;
- vecteur = \([0, 0, 1, 1]\) (N2 et N3 ont des copies).
Home \(\rightarrow\) N2, N3 : « Invalidation » (messages envoyés en parallèle).
N2, N3 \(\rightarrow\) home : « Invalidation Ack ».
Home \(\rightarrow\) demandeur : « Write Permission » et les données.
Home : met à jour le répertoire :
- état = Modified ;
- propriétaire = N1 ;
- vecteur = \([0, 1, 0, 0]\).
Messages échangés : 6 messages (1 requête, 2 invalidations, 2 accusés de réception, 1 réponse) ; avec \(k\) copies à invalider, \(2+2k\) messages.
Optimisation possible : les invalidations sont envoyées en parallèle, et le home lit la mémoire pendant ce temps. La latence vaut alors \(50 + \max(50+50, 80) + 50 = 200\) ns ; envoyées l’une après l’autre, les deux invalidations coûteraient \(50 + 2\times(50+50) + 50 = 300\) ns.
Le répertoire indique S et la présence \(0011\) : le home sait qu’il faut prévenir N2 et N3, et eux seuls. Les deux invalidations partent ensemble (\(100\) ns) ; les copies de N2 et N3 passent de S à I ; les accusés reviennent à \(150\) ns. La réponse donne à N1 la donnée et la permission d’écrire : son cache passe de I à M, X \(=9\). La mémoire garde \(3\), valeur périmée que le répertoire signale par l’état M.
Étape 3 : invalidations ciblées vers N2 et N3
Étape 6 : répertoire en M, propriétaire N1, 6 messages
Comparaison espionnage et répertoire
| Critère | Espionnage | Répertoire |
|---|---|---|
| Communication | Diffusion sur un bus partagé | Point à point par un réseau |
| Passage à l’échelle | Limité (8 à 16 cœurs) | Centaines à milliers de cœurs |
| Complexité | Mise en œuvre plus directe | Plus complexe (répertoire, messages) |
| Trafic d’une écriture | Atteint les \(n-1\) autres caches | Atteint les seuls nœuds qui ont une copie |
| Latence | Faible (bus rapide) | Plus élevée (passage par le home) |
| Surcoût mémoire | Aucun (pas de structure) | Répertoire (\(p\) bits par bloc : 3 % à 16 nœuds, 12,5 % à 64) |
| Énergie | Tous les caches actifs | Seuls les nœuds concernés actifs |
| Usage typique | Processeurs de bureau et portables | Serveurs multi-sockets, HPC |
| Exemples | Multiprocesseurs à bus, cœurs d’un même socket | SGI Origin et UV, liens entre sockets AMD EPYC et Intel Xeon |
Une grappe de machines (cluster) n’apparaît dans aucune des deux colonnes : ses nœuds n’ont pas de cohérence matérielle entre eux et communiquent par messages (section 6.3).
Hybridation : approche hiérarchique
De nombreux systèmes modernes utilisent une approche hybride :
- niveau intra-nœud : espionnage entre les cœurs d’un même socket (4 à 16 cœurs) ;
- niveau inter-nœuds : répertoire entre les sockets ou les nœuds.
Exemple : serveur bi-socket
- socket 0 : 8 cœurs avec espionnage local ;
- socket 1 : 8 cœurs avec espionnage local ;
- entre le socket 0 et le socket 1 : répertoire.
Avantage : la faible latence de l’espionnage local s’ajoute au passage à l’échelle du répertoire.
Le cœur c2 du socket 0 lit d’abord le bloc A, dont le home est le socket 0 et dont c5 a une copie : la demande reste dans le socket, ses sept autres caches l’examinent ; c5, en S, ne répond pas et la mémoire 0 fournit la donnée ; le socket 1 n’est pas dérangé. Il lit ensuite le bloc B, dont le home est le socket 1 : la demande traverse le lien vers le répertoire du socket 1, qui trouve B en U et fait répondre la mémoire 1, puis note la copie du socket 0. Aucun cœur du socket 1 n’a espionné cette lecture.
Bloc A : espionnage dans le socket 0
Bloc B : répertoire du socket 1 mis à jour
Optimisation de la localité en NUMA
Stratégies de placement des données
En NUMA, la performance dépend fortement du placement des données. Objectif : maximiser les accès locaux. Le système d’exploitation gère la mémoire par pages (\(4\) Kio) et ne choisit la page physique, donc le nœud, qu’au moment où la page est touchée pour la première fois, pas au moment de l’allocation.
Stratégies de placement NUMA (Linux) :
- Premier contact (first-touch) : la page mémoire est placée sur le nœud du cœur qui l’écrit ou la lit en premier.
- Entrelacement (interleaved) : les pages sont distribuées tour à tour sur tous les nœuds (
numactl --interleave). - Nœud préféré (preferred node) : allouer de préférence sur un nœud choisi, et sur un autre s’il est plein (
numactl --preferred) ;numactl --membindimpose au contraire le nœud et échoue s’il est plein. - Local : allouer sur le nœud du fil (thread) qui demande la page. C’est la politique par défaut de Linux ; comme la page n’est placée qu’à son premier accès, c’est elle qui produit le comportement de premier contact.
La topologie se lit dans /sys, et un processus se lie à des cœurs par os.sched_setaffinity, sans privilège particulier :
import os
import glob
# coeurs du systeme, coeurs autorises (Linux)
print("coeurs :", os.cpu_count())
print("autorises :", sorted(os.sched_getaffinity(0)))
# un dossier par noeud NUMA : coeurs et distances
motif = "/sys/devices/system/node/node[0-9]*"
for d in sorted(glob.glob(motif)):
coeurs = open(d + "/cpulist").read().strip()
dist = open(d + "/distance").read().strip()
nom = os.path.basename(d)
print(nom, ": coeurs", coeurs, " distances", dist)
# lier ce processus aux coeurs 0 et 1 (sans privilege)
os.sched_setaffinity(0, {0, 1})
print("lie a :", sorted(os.sched_getaffinity(0)))Sortie :
coeurs : 2
autorises : [0, 1]
node0 : coeurs 0-1 distances 10
lie a : [0, 1]La machine de l’exemple n’a qu’un nœud ; sur un serveur bi-socket, le programme afficherait deux dossiers node0 et node1 et les distances 10 21. Le module psutil, parfois proposé pour cet usage, donne la mémoire totale de la machine mais pas sa répartition par nœud. Pour lier à la fois les cœurs et la mémoire, numactl s’utilise en ligne de commande, par exemple numactl --cpunodebind=0 --membind=0 python3 mon_script.py.
Le tableau data occupe 8 pages. np.empty réserve les adresses sans écrire : aucune page n’est placée (hachures). Le fil 0, lié à un cœur de N0, écrit sa moitié : les pages p0 à p3 sont placées dans la mémoire de N0 au moment de cette première écriture. Le fil 1, sur N1, écrit l’autre moitié : p4 à p7 vont sur N1. Pendant le calcul, chaque fil ne lit que des pages locales.
Le fil 0 écrit sa moitié : p0 à p3 sur N0
Calcul : chaque fil lit ses pages locales
Trois placements se comparent sur ce tableau, avec \(80\) ns en local et \(140\) ns à distance. Si le fil principal (sur N0) initialise tout, les 8 pages vont sur N0 : le fil 1 ne fait que des accès distants, et la moyenne vaut \((80+140)/2=110\) ns. Avec l’entrelacement, chaque fil a une page sur deux en local : \(110\) ns aussi, mais la charge se partage entre les deux contrôleurs mémoire. Avec le premier contact par le fil qui calcule, tout est local : \(80\) ns, une latence moyenne \(110/80 = 1{,}375\) fois plus faible. La phase parallèle dure autant que le fil le plus lent : elle est \(140/80 = 1{,}75\) fois plus courte qu’avec un seul nœud et \(1{,}375\) fois plus courte qu’avec l’entrelacement.
Trois placements des 8 pages : un seul nœud, entrelacé, premier contact.
Algorithmes NUMA-aware
Un algorithme NUMA-aware (conscient de NUMA) est conçu pour maximiser la localité des données en tenant compte de la topologie NUMA du système.
Principes :
- partitionner les données selon les nœuds ;
- chaque fil travaille sur les données de son nœud local ;
- minimiser les communications entre nœuds ;
- utiliser des structures de données distribuées.
Mémoire partagée et mémoire distribuée
Les fils d’un processus partagent sa mémoire ; les processus de multiprocessing, eux, ont chacun la leur. Ces deux modèles se retrouvent à l’échelle des machines. En mémoire partagée, une donnée écrite par un cœur est lue par un autre sans aucune instruction de transfert : le matériel (bus, protocole de cohérence, répertoire) transporte la donnée. En mémoire distribuée, chaque nœud n’adresse que sa propre mémoire ; pour qu’une valeur passe d’un nœud à l’autre, le programme doit l’envoyer dans un message (q.put) et l’autre doit la recevoir (q.get). C’est le modèle des grappes de machines, programmées par échange de messages (bibliothèques MPI).
Mémoire partagée : P1 lit la valeur écrite par P0
Mémoire distribuée : la valeur arrive à B par un message
import os
import multiprocessing as mp
import numpy as np
def somme_locale(i, n_part, q):
"""processus i : se lie a un coeur, cree SA partition,
renvoie sa somme"""
if hasattr(os, "sched_setaffinity"):
# Linux : lier ce processus a un coeur
coeurs = sorted(os.sched_getaffinity(0))
os.sched_setaffinity(0, {coeurs[i % len(coeurs)]})
# graine de la partition i ; premier contact : pages locales
rng = np.random.default_rng(i)
part = rng.random(n_part)
# message : 2 nombres
q.put((i, part.sum()))
def somme_numa_aware(n, n_workers=4):
q = mp.Queue()
ps = [mp.Process(target=somme_locale, args=(i, n // n_workers, q))
for i in range(n_workers)]
for p in ps:
p.start()
# recevoir les messages
partielles = dict(q.get() for _ in ps)
for p in ps:
p.join()
total = sum(partielles[i] for i in range(n_workers))
return total, partielles
if __name__ == "__main__":
total, partielles = somme_numa_aware(10_000_000, n_workers=4)
for i in sorted(partielles):
print(f"partition {i} : {partielles[i]:.3f}")
print(f"somme : {total:.3f}")
ref = sum(np.random.default_rng(i).random(2_500_000).sum()
for i in range(4))
print("identique au calcul sequentiel :", total == ref)Sortie :
partition 0 : 1250334.250
partition 1 : 1249690.417
partition 2 : 1250445.842
partition 3 : 1250214.590
somme : 5000685.099
identique au calcul sequentiel : TrueCe programme reprend le schéma d’une somme parallèle, avec trois précautions. D’abord, chaque processus crée sa partition au lieu de la recevoir : si le parent créait tout le tableau, il en toucherait toutes les pages, qui seraient placées sur son nœud, et il faudrait en plus copier \(80\) Mo vers les processus (sous Windows et macOS, qui lancent les processus par spawn, les arguments sont transmis par copie). Ensuite, chaque processus se lie à un cœur avec os.sched_setaffinity, ce qui ne demande aucun privilège ; sur une machine NUMA, il faudrait choisir un cœur du nœud voulu (/sys/devices/system/node/node*/cpulist). Enfin, seuls les résultats circulent : chaque processus envoie un message de deux nombres, et le parent fait la réduction finale.
Le parent lance 4 processus en ne leur passant que (i, n // 4, q). Chaque processus se lie à un cœur, crée ses \(2{,}5\) millions de valeurs, calcule sa somme partielle et l’envoie dans la file. Le parent reçoit les 4 messages et les additionne : \(5\,000\,685{,}099\), exactement la somme séquentielle des mêmes partitions.
Réduction finale : 4 messages, 3 additions ; valeurs de l’exécution réelle.
Patron de parallélisation NUMA-aware
Mauvaise approche (NUMA-oblivious) :
- allouer et initialiser toutes les données sur un nœud ;
- lancer les fils sur tous les nœuds ;
- \(\rightarrow\) tous les fils des autres nœuds font des accès lents.
Bonne approche (NUMA-aware) :
- partitionner les données en \(N\) parts (\(N\) = nombre de nœuds) ;
- placer chaque partition sur son nœud (premier contact par le fil qui l’utilisera) ;
- lancer chaque fil sur le nœud de sa partition et l’y lier ;
- minimiser les accès entre partitions ;
- faire la réduction finale (coût faible).
Un système NUMA a 2 nœuds (8 cœurs chacun). Il faut multiplier deux matrices \(8000\times8000\).
Approche 1 (naïve) :
- matrices A et B stockées sur le nœud 0 ;
- 16 fils répartis sur les deux nœuds.
Approche 2 (NUMA-aware) :
- matrice A partitionnée : A1 sur le nœud 0, A2 sur le nœud 1 ;
- matrice B répliquée sur les deux nœuds ;
- 8 fils sur le nœud 0 calculent avec A1 ;
- 8 fils sur le nœud 1 calculent avec A2.
Questions :
a) Dans l’approche 1, quel pourcentage des accès est distant ?
b) Dans l’approche 2, quel pourcentage des accès est distant ?
c) Avec les latences du début du cours (local = 80 ns, distant = 140 ns), calculer le gain de l’approche 2.
Afficher la correction
Méthode. Pour chaque fil, chercher où sont les données qu’il lit ; la part des accès distants donne la latence moyenne (moyenne pondérée, comme au premier exercice).
a) Approche 1 :
Les 8 fils du nœud 0 font des accès locaux ; les 8 fils du nœud 1 font des accès distants (tout est sur le nœud 0). Les fils faisant le même travail, la moitié des accès est distante.
Pourcentage d’accès distants : 50 %.
b) Approche 2 :
Chaque fil accède :
- à sa partition de A : locale ;
- à sa copie de B : locale ;
- tout est local.
Pourcentage d’accès distants : 0 % (sauf la copie initiale de B, négligeable devant le calcul).
c) Calcul du gain :
Latence moyenne de l’approche 1 : \[L_1 = 0{,}5 \times 80 + 0{,}5 \times 140 = 40 + 70 = 110 \text{ ns}\]
Latence moyenne de l’approche 2 : \[L_2 = 1{,}0 \times 80 = 80 \text{ ns}\]
Accélération : \[S = \frac{110}{80} = 1{,}375\]
Gain : 1,375 fois plus rapide, soit \(30/110 \approx 27{,}3\) % de temps en moins, sans compter la contention réduite sur le contrôleur mémoire du nœud 0, qui servait à lui seul les 16 fils. Si les 16 fils doivent tous finir (fork-join), la durée est fixée par les fils du nœud 1 : \(140/80 = 1{,}75\).
Compromis : l’approche 2 occupe deux fois la mémoire de B (réplication) : \(8000^2 \times 8\) octets \(= 512\) Mo (environ \(488\) Mio) de plus en float64, mais le gain de performance le compense.
Erreur fréquente : compter les accès distants de l’approche 1 à \(100\) % (seuls les fils du nœud 1 sont pénalisés), ou oublier que la réplication de B n’a de sens que parce que B n’est que lue.
Mesure et profilage NUMA
Outils de diagnostic
# Afficher la topologie NUMA
numactl --hardware
# Resultat typique (serveur bi-socket) :
# available: 2 nodes (0-1)
# node 0 cpus: 0 1 2 3 4 5 6 7
# node 0 size: 32768 MB
# node 1 cpus: 8 9 10 11 12 13 14 15
# node 1 size: 32768 MB
# node distances:
# node 0 1
# 0: 10 21
# 1: 21 10
# Statistiques NUMA d'un processus
numastat -p <PID>
# Lancer un programme avec affinite NUMA
numactl --cpunodebind=0 --membind=0 ./mon_programme
# Migrer les pages d'un processus du noeud 0 vers le noeud 1
migratepages <PID> 0 1Les distances sont des valeurs relatives fournies par le micrologiciel : \(10\) pour un accès local, \(21\) pour l’autre socket, soit un coût annoncé \(2{,}1\) fois plus grand. La mesure (\(140{,}4/80{,}8 \approx 1{,}74\)) est plus fiable que ce chiffre, qui sert surtout à ordonner les nœuds du plus proche au plus lointain.
Mesurer l’effet de la localité en Python
Le programme suivant fait le même travail sur les mêmes données en ne changeant que l’ordre des lectures : dans l’ordre des indices, puis dans un ordre aléatoire. Les lectures data[indices] ont lieu pendant la mesure, pour les deux ordres ; chaque durée est la plus courte de sept essais.
import time
import numpy as np
from numpy.random import default_rng
def mesure(data, indices, n=7):
mini = float("inf")
for _ in range(n):
t0 = time.perf_counter()
np.sum(data[indices] ** 2) # lit data
mini = min(mini, time.perf_counter() - t0)
return mini
print(" taille ordre hasard rapport")
for taille in [100_000, 1_000_000, 10_000_000]:
data = default_rng(0).random(taille)
ordre = np.arange(taille)
hasard = default_rng(1).permutation(taille)
t_o = mesure(data, ordre)
t_h = mesure(data, hasard)
print(f"{taille:>10,} {t_o * 1e3:6.2f}",
f"{t_h * 1e3:6.2f} {t_h / t_o:8.1f}")Sortie :
taille ordre hasard rapport
100,000 0.51 0.58 1.1
1,000,000 2.93 5.66 1.9
10,000,000 59.37 113.43 1.9Durées en millisecondes. Avec \(100\,000\) valeurs (\(0{,}8\) Mo), le tableau tient dans les caches de la machine de mesure (\(2\) Mio de L2 par cœur, \(260\) Mio de L3) : l’ordre importe peu. Au-delà, lire au hasard coûte ici environ deux fois plus, et bien davantage sur une machine dont le L3 est plus petit que le tableau : chaque lecture tombe dans une autre ligne de cache. Ce programme mesure la localité dans la hiérarchie des caches ; lancé sous numactl --cpunodebind=0 --membind=1 sur une machine à deux nœuds, il mesure en plus le coût de la mémoire distante.
Une mesure qui ne mesure rien. Une version courante de ce test copie une fois le tableau dans le désordre, puis chronomètre le parcours de la copie :
import time
import numpy as np
from numpy.random import default_rng
def chrono(f, x, n=7):
mini = float("inf")
for _ in range(n):
t0 = time.perf_counter()
f(x)
mini = min(mini, time.perf_counter() - t0)
return mini
def travail(data):
return np.sum(data ** 2)
print(" taille rapport")
for taille in [100_000, 1_000_000, 10_000_000]:
data = default_rng(0).random(taille)
t_seq = chrono(travail, data)
indices = default_rng(1).permutation(taille)
data_alea = data[indices] # une seule copie
t_alea = chrono(travail, data_alea) # en ordre
print(f"{taille:>10,} {t_alea / t_seq:8.2f}")Sortie :
taille rapport
100,000 0.98
1,000,000 1.00
10,000,000 0.92La copie data[indices] est faite avant la mesure ; le tableau data_alea est ensuite lu dans l’ordre, comme data. Le rapport reste proche de \(1\) (entre \(0{,}92\) et \(1{,}00\)) quelle que soit la taille : le désordre n’est jamais mesuré.
Synthèse et recommandations
Quand utiliser le répertoire ou l’espionnage
| Critère | Espionnage | Répertoire |
|---|---|---|
| Nombre de cœurs | Moins de 16 cœurs | Plus de 16 cœurs |
| Type de système | Bureau, portable, petits serveurs | Serveurs multi-sockets, HPC, centres de données |
| Latence | Critique (un bus, peu de sauts) | Tolère le passage par le home |
| Coût | Limité | Élevé |
| Complexité | Réduite | Acceptable |
Checklist de la programmation NUMA-aware
Profiler d’abord : mesurer les accès locaux et distants :
- utiliser
numastat,perf; - repérer les zones du programme qui font le plus d’accès distants.
- utiliser
Partitionner les données :
- diviser selon le nombre de nœuds NUMA ;
- placer chaque partition sur son nœud.
Lier fils et données :
- le fil du nœud \(N\) traite les données du nœud \(N\) ;
- utiliser l’affinité des cœurs et de la mémoire.
Minimiser le partage :
- éviter les variables partagées souvent modifiées ;
- préférer les réductions locales suivies d’une réduction finale.
Répliquer si nécessaire :
- données en lecture seule : les répliquer sur chaque nœud ;
- compromis entre mémoire et performance.
Mesurer le gain :
- comparer la version NUMA-aware et la version qui ignore NUMA ;
- vérifier que le gain justifie le travail.
Pièges courants en NUMA
Erreurs fréquentes en programmation NUMA :
Initialisation centralisée
N = 10_000_000 # Mauvais : le fil principal ecrit toutes les pages data = np.ones(N) # Bon : reserver sans toucher les pages, # puis chaque fil initialise sa partition data = np.empty(N)Pour un grand tableau,
np.emptyetnp.zerosne touchent aucune page (le système fournit des pages nulles à la demande) : c’est la première écriture qui place les pages. Le conseil vaut pour des fils qui partagent un même tableau (C avec OpenMP, ou fils Python sur des opérations NumPy).Migration de fils
- un fil alloue sur le nœud 0, puis migre vers le nœud 1 ;
- \(\rightarrow\) tous ses accès deviennent distants ;
- solution : fixer l’affinité des cœurs dès le départ.
False sharing entre nœuds
- plus coûteux que le false sharing sur un même socket ;
- la ligne fait l’aller-retour par le réseau : latence 2 à 3 fois plus élevée ;
- solution : remplissage (padding) et alignement.
Ignorer la topologie
- certains nœuds sont plus proches que d’autres ;
- consulter les distances :
numactl --hardware; - organiser les communications selon la topologie.
Ce qu’il faut retenir
- L’espionnage ne passe pas à l’échelle au-delà de 8 à 16 cœurs (contention du bus).
- NUMA : accès mémoire non uniforme, la latence dépend de la localisation de la donnée.
- Répertoire : cohérence par répertoire, communications point à point.
- Nœud home : responsable de l’entrée de répertoire d’un bloc mémoire.
- Vecteur de présence : un bit par nœud, qui indique les nœuds ayant une copie.
- Défaut de lecture (bloc propre) : 2 messages ; défaut de lecture (bloc sale) : 4 messages.
- Défaut d’écriture : invalidations ciblées (pas de diffusion), \(2+2k\) messages pour \(k\) copies.
- Latences typiques : local 80 ns, distant 140 à 200 ns (1,75 à 2,5 fois plus lent).
- Optimisation NUMA : partitionner, lier fils et données, minimiser les accès distants.
- Premier contact : la page est placée sur le nœud qui y accède en premier.
- Mémoire distribuée : les données passent par des messages ; seules les sommes partielles circulent dans une réduction.
- Profilage : toujours mesurer avant et après une optimisation, et vérifier que la mesure mesure ce qu’elle annonce.
Synthèse du cours
Les quatre séances suivent une même question à des échelles croissantes : où sont les données, qui y accède, et combien coûte l’accès ? La Séance 1 a montré pourquoi le parallélisme s’est imposé et pourquoi la mémoire, plus que le calcul, fixe souvent le rythme : lignes de cache, hiérarchie en cycles, lois d’Amdahl et de Gustafson, granularité. La Séance 2 a ajouté plusieurs caches, donc plusieurs copies d’une même donnée, et les protocoles (MSI, MESI) qui les gardent cohérentes par espionnage du bus. La Séance 3 a placé plusieurs fils sur ces données partagées et les mécanismes qui ordonnent leurs accès. Cette séance a dépassé le bus : la mémoire se répartit entre des nœuds, la distance aux données se paie en nanosecondes, et la cohérence passe par un répertoire, jusqu’aux machines sans cohérence matérielle, qui échangent des messages.
Le cours en quatre séances : d’un cœur et sa mémoire à plusieurs nœuds.
Références
- J. L. Hennessy, D. A. Patterson, Computer Architecture: A Quantitative Approach, 6e éd., Morgan Kaufmann, 2019, § 5.4 (cohérence par répertoire).
- D. E. Culler, J. P. Singh, A. Gupta, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann, 1999, chap. 8.
- D. Lenoski et al., « The Stanford DASH Multiprocessor », IEEE Computer 25(3), 1992.
- J. Laudon, D. Lenoski, « The SGI Origin: A ccNUMA Highly Scalable Server », ISCA 1997.
- U. Drepper, What Every Programmer Should Know About Memory, 2007, § 5 (NUMA).
- G. Hager, G. Wellein, Introduction to High Performance Computing for Scientists and Engineers, CRC Press, 2010, chap. 8 (ccNUMA, premier contact).
- Mesures de latence : VSC (KU Leuven), « Memory bandwidth and latency measurements », nœuds Cascade Lake et Skylake (Intel MLC).
- Pages de manuel Linux :
numactl(8),numastat(8),set_mempolicy(2).
Pour cette séance
Les slides
À lire en ligne
- TD — Séance 4 — Architectures distribuées et NUMA
- Lab 5 — Mémoire distribuée et NUMA : placement, répertoire et messages
À télécharger
- Notebooks des labs de la séance 4 (ZIP, 49 Ko)