Architectures multiprocesseurs¶

SMP, NUMA, cohérence de cache — les problèmes qui emergent quand plusieurs processeurs partagent la mémoire.

Pourquoi plusieurs processeurs¶

La fréquence des processeurs a plafonne autour de 4-5 GHz au milieu des années 2000 — le "mur de la puissance" (power wall). Doubler la fréquence quadruple la consommation électrique. L'industrie a donc bifurque vers le multicoeur : au lieu d'un processeur plus rapide, on met plusieurs processeurs en parallèle.

Ce choix a des conséquences profondes pour le logiciel. Un programme séquentiel ne beneficie pas de cœurs supplémentaires. La performance ne vient plus gratuitement de l'évolution du matériel — il faut concevoir pour le parallélisme. Hennessy et Patterson appellent cela la fin du "free lunch" pour les développeurs.

Trois murs ont stoppe l'augmentation de la fréquence :

• Le power wall : la puissance dissipee augmente cubiquement avec la fréquence (P = C x V^2 x f, et V augmente avec f)
• Le memory wall : la latence mémoire n'a pas baisse aussi vite que les processeurs ont accéléré — le ratio s'est dégradé
• L'ILP wall : le parallélisme d'instructions exploitable dans un flux séquentiel est limite — on ne peut pas indéfiniment trouver plus d'instructions indépendantes

SMP : Symmetric Multiprocessing¶

Dans une architecture SMP, tous les processeurs partagent un accès uniforme à la mémoire principale. Chaque cœur à la même latence pour accéder à n'importe quelle zone mémoire. C'est le modèle le plus simple et le plus ancien pour le multiprocesseur.

graph TB
    C1["Coeur 1<br>+ Cache L1/L2"] --> BUS["Bus memoire partage"]
    C2["Coeur 2<br>+ Cache L1/L2"] --> BUS
    C3["Coeur 3<br>+ Cache L1/L2"] --> BUS
    C4["Coeur 4<br>+ Cache L1/L2"] --> BUS
    BUS --> MEM["Memoire partagee"]

Avantages du SMP¶

• Simplicité de programmation : pas besoin de se soucier de la topologie mémoire. Tout thread peut accéder à toute la mémoire avec la même latence.
• Migration de threads : l'OS peut déplacer un thread d'un cœur à l'autre sans pénalité de performance liee à la localité mémoire.
• Équilibrage de charge : tous les cœurs sont équivalents, donc l'ordonnanceur OS peut répartir equitablement la charge.

Limites du SMP¶

Le bus mémoire est partage. Quand le nombre de cœurs augmente, la contention sur le bus devient le goulot. Au-delà de 8 a 16 cœurs, un SMP pur ne passe plus à l'échelle — la bande passante mémoire par cœur s'effondre.

Pour comprendre : si un bus mémoire offre 50 GB/s de bande passante et qu'on y connecte 4 cœurs, chacun dispose de ~12.5 GB/s. Avec 16 cœurs, chacun n'a plus que ~3 GB/s. Avec 64 cœurs, ~0.8 GB/s par cœur — insuffisant pour alimenter un processeur moderne.

SMT : Simultaneous Multithreading¶

Le SMT (appelé Hyper-Threading chez Intel) est une technique qui permet à un seul cœur physique de présenter deux threads logiques. Le cœur partage ses unites d'exécution entre les deux threads : quand un thread attend un cache miss, l'autre peut utiliser les unites libres.

Le gain du SMT est typiquement de 20 a 30% de throughput supplémentaire — pas 100%, car les deux threads partagent les mêmes ressources physiques (cache L1, unites d'exécution, bande passante). Pour les charges sensibles à la latence, le SMT peut même dégrader les performances du fait de la contention sur les caches.

NUMA : Non-Uniform Memory Access¶

L'architecture NUMA résout le problème de scalabilité du SMP en donnant à chaque groupe de processeurs (nœud NUMA) sa propre mémoire locale. Un processeur accede rapidement a sa mémoire locale, mais plus lentement à la mémoire d'un autre nœud.

graph TB
    subgraph "Noeud NUMA 0"
        C1["Coeurs 0-7<br>+ Caches L1/L2/L3"] --> MC0["Controleur memoire 0"]
        MC0 --> MEM0["DIMM locale 0<br>128 GB"]
    end
    subgraph "Noeud NUMA 1"
        C2["Coeurs 8-15<br>+ Caches L1/L2/L3"] --> MC1["Controleur memoire 1"]
        MC1 --> MEM1["DIMM locale 1<br>128 GB"]
    end
    MC0 --interconnect QPI/UPI/IF--> MC1

L'interconnect entre les nœuds (Intel QPI/UPI, AMD Infinity Fabric) est un lien haute bande passante mais avec une latence supplémentaire par rapport à l'accès mémoire local.

Distance mémoire¶

Sur un serveur a 2 sockets, la pénalité NUMA est de ~1.7x. Sur un serveur a 4 ou 8 sockets, elle peut atteindre 3-4x pour les nœuds les plus eloignes. La commande numactl --hardware affiche la matrice de distances NUMA.

Comparaison SMP vs NUMA¶

Politiques d'allocation NUMA¶

Linux offre plusieurs politiques d'allocation mémoire NUMA via numactl et set_mempolicy() :

• local (défaut) : alloue sur le nœud ou tourne le thread. Optimal quand les threads accedent a leur propre mémoire.
• bind : force l'allocation sur un ou plusieurs nœuds spécifiques. Utile pour isoler une base de données sur un nœud.
• interleave : repartit les pages en round-robin entre les nœuds. Bon pour les structures partagees massivement (hash tables globales).
• preferred : préféré un nœud mais accepte les autres si nécessaire.

Cas concret : PostgreSQL sur NUMA¶

PostgreSQL utilise un modèle multi-processus avec mémoire partagee (shared_buffers). Sur un serveur 2 sockets, si les shared_buffers sont alloues sur le nœud 0, les processus PostgreSQL sur le nœud 1 accedent à la mémoire partagee avec une pénalité de 1.7x. La solution est de démarrer PostgreSQL avec numactl --interleave=all pour répartir les shared_buffers equitablement entre les nœuds.

Cohérence de cache¶

Quand plusieurs cœurs ont chacun leur cache L1/L2 et partagent la mémoire, un problème fondamental apparait : si le cœur 0 modifie une donnée en cache, le cœur 1 qui a une copie de cette donnée doit voir la modification. C'est le problème de cohérence de cache.

Sans mécanisme de cohérence, deux cœurs pourraient lire des valeurs différentes pour la même adresse mémoire — un comportement inacceptable pour la plupart des programmes.

Protocole MESI¶

Le protocole MESI est le plus repandu. Chaque ligne de cache est dans l'un de quatre états :

graph LR
    I["Invalid"] --lecture locale--> E["Exclusive"]
    I --lecture, autres ont copie--> S["Shared"]
    E --ecriture locale--> M["Modified"]
    S --ecriture locale--> M
    M --lecture par autre coeur--> S
    E --lecture par autre coeur--> S
    S --ecriture par autre coeur--> I
    M --ecriture par autre coeur--> I

Snooping vs directory¶

Deux mécanismes implementent la cohérence :

• Snooping : chaque cache surveille le bus et réagit quand il voit un accès a une ligne qu'il possédé. Simple mais ne passe pas à l'échelle (tous les caches doivent voir toutes les transactions). Utilisé dans les systèmes SMP a petit nombre de cœurs.
• Directory-based : un répertoire centralise (ou distribué) enregistre quels caches possèdent chaque ligne. Seuls les caches concernes sont contactes lors d'une invalidation. Passe à l'échelle mais ajoute de la latence. Utilisé dans les systèmes NUMA.

Les processeurs modernes combinent les deux : snooping au sein d'un nœud NUMA (entre les cœurs partageant un L3), directory-based entre nœuds NUMA.

MOESI et MESIF¶

Le protocole MOESI (AMD) ajoute un état O (Owner) : le cœur qui a modifie la donnée peut la fournir directement a un autre cœur demandeur sans écrire en mémoire d'abord. Cela réduit le trafic vers la mémoire principale.

Le protocole MESIF (Intel) ajoute un état F (Forward) : parmi les caches en état Shared, un est désigné comme responsable de répondre aux requêtes, evitant les réponses multiples.

Coût de la cohérence¶

La cohérence de cache n'est pas gratuite. Quand un cœur écrit une donnée partagee, il doit :

1. Envoyer un message d'invalidation a tous les caches qui ont une copie
2. Attendre l'acquittement de chaque cache
3. Obtenir la propriété exclusive de la ligne
4. Effectuer l'écriture

Ce processus prend 40 a 200 cycles selon la topologie. Sur un système NUMA, l'invalidation peut traverser l'interconnect, ajoutant 100+ cycles supplémentaires. C'est ce qui rend les locks contestes si coûteux : chaque acquisition de lock force un échange de cohérence entre les cœurs.

Memory ordering¶

Les processeurs modernes réordonnent les accès mémoire pour optimiser les performances. Un cœur peut exécuter une écriture après une lecture même si le code les spécifié dans l'ordre inverse, tant que le résultat final est correct du point de vue de ce cœur. Mais du point de vue d'un autre cœur, les opérations peuvent apparaître dans un ordre différent.

Modèles de consistance¶

Le modèle TSO de x86 est relativement fort : les lectures ne sont jamais reordonnees entre elles, les écritures ne sont jamais reordonnees entre elles, et une lecture ne peut pas passer devant une écriture précédente à la même adresse. Le seul reordonnement autorise est qu'une lecture peut passer devant une écriture a une adresse différente (store buffer forwarding).

Le modèle relaxed d'ARM autorise quasiment tous les reordoncements. Un programme correct sur x86 peut avoir des bugs de cohérence sur ARM si les barrieres mémoire appropriees ne sont pas presentes. C'est pourquoi la portabilité x86 → ARM est delicate pour le code concurrent bas-niveau.

Barrieres mémoire¶

Les barrieres mémoire (memory fences) forcent un ordre entre les opérations :

• Store barrier (sfence) : toutes les écritures avant la barriere sont visibles avant celles après
• Load barrier (lfence) : toutes les lectures avant la barriere sont completees avant celles après
• Full barrier (mfence) : combine les deux

En pratique, les langages de haut niveau exposent ces mécanismes via des abstractions :

Le programmeur n'écrit presque jamais de barrieres directement, mais il doit comprendre pourquoi elles existent pour utiliser correctement les primitives de synchronisation. Utiliser memory_order_relaxed quand memory_order_acquire est nécessaire cause des bugs subtils et non reproductibles — les pires a debugger.

False sharing¶

Le false sharing est un piege de performance insidieux. Il se produit quand deux cœurs modifient des variables différentes qui se trouvent sur la même ligne de cache (64 octets). La cohérence de cache ne fonctionne qu'au niveau de la ligne, pas de l'octet.

struct counters {
    long counter_thread_0;  // offset 0, 8 octets
    long counter_thread_1;  // offset 8, 8 octets
};
// Les deux compteurs sont sur la meme ligne de cache de 64 octets

Les deux compteurs sont sur la même ligne de cache. Quand le thread 0 incremente son compteur, la ligne est invalidee dans le cache du thread 1, et vice versa. Les deux threads se volent mutuellement la ligne de cache en permanence — la performance s'effondre même si les variables sont logiquement indépendantes.

L'impact peut être dramatique : un programme qui devrait scaler lineairement avec le nombre de cœurs peut devenir plus lent que la version single-thread à cause du trafic de cohérence.

Solution : padding¶

struct counters {
    long counter_thread_0;
    char padding[56];       // remplissage pour atteindre 64 octets
    long counter_thread_1;  // debut d'une nouvelle ligne de cache
};

Solutions par langage¶

Le framework LMAX Disruptor (Java) utilise cette technique massivement pour atteindre des performances de millions d'opérations par seconde avec un ring buffer partage entre threads.

Primitives de synchronisation et leur coût¶

Comprendre le coût des primitives de synchronisation aide à choisir la bonne approche :

Les algorithmes lock-free (bases sur CAS) évitent les locks mais n'évitent pas la cohérence de cache. Un CAS conteste sur une variable partagee entre cœurs NUMA distants coute autant qu'un lock conteste. La seule solution fondamentale est de réduire le partage — chaque thread travaille sur ses propres données, et la synchronisation est réduite au minimum.

Implications pour l'architecte¶

Les architectures multiprocesseurs préfigurent les problèmes des systèmes distribués. Les mêmes patterns se retrouvent a une échelle différente :

1. Cohérence vs performance : plus on garantit de cohérence, plus on paie en performance. Ce trade-off se retrouve dans les bases de données distribuées (strong consistency vs eventual consistency). MESI dans un processeur est l'équivalent de Raft/Paxos dans un cluster.

2. Localité des données : en NUMA, placer les données pres du processeur qui les traite est critique. En distribué, c'est le même principe : on envoie le calcul vers les données, pas l'inverse (MapReduce, Spark). La pénalité NUMA (2x) est une version miniature de la pénalité réseau (1000x).

3. Contention : un lock conteste sur un multiprocesseur ressemble a un lock distribué conteste — le coût est domine par la communication entre les participants, pas par l'opération protégée elle-même. La solution dans les deux cas est de partitionner pour éviter la contention.

4. False sharing et isolation : partitionner les données par thread/processeur pour éviter la contention est le même pattern que partitionner les données par nœud en distribué (sharding). Le thread-local storage est l'équivalent du shared-nothing.

5. Memory ordering : les garanties d'ordre faibles d'ARM ressemblent aux garanties faibles d'un système distribué. Dans les deux cas, il faut des barrieres ou des protocoles explicites pour garantir que les observations sont coherentes.

Chapitre suivant : Clusters et parallelisme — shared-nothing, loi d'Amdahl et calcul haute performance.