Multicœurs, multithreading et cohérence de cache

Jusqu’au milieu des années 2000, un nouveau processeur voulait dire un processeur plus rapide : une horloge plus haute, un pipeline plus profond, davantage de mécanique d’exécution dans le désordre. Puis l’horloge a cessé de grimper, et les fondeurs ont dépensé leurs transistors autrement : en cœurs supplémentaires. L’Apple M2 Ultra sur lequel ce chapitre a été mesuré en compte 24.

Plusieurs cœurs sur une puce posent trois questions nouvelles. Comment des cœurs qui ont chacun un cache privé se mettent-ils d’accord sur le contenu de la mémoire ? Que devient la performance quand deux cœurs touchent la même ligne de cache ? Et de combien un programme accélère-t-il vraiment avec 24 cœurs ? Ce chapitre y répond, mesures à l’appui.

Pourquoi les cœurs se sont multipliés

Le chapitre de physique sur les limites raconte l’histoire vue d’en bas. Pendant trente ans, la loi d’échelle de Dennard (Dennard scaling) a permis à chaque génération de transistors plus petits de tourner plus vite à puissance égale par millimètre carré. Vers 2005, la tension d’alimentation a cessé de baisser, et le repas gratuit s’est arrêté : monter encore l’horloge voulait dire plus de chaleur par millimètre carré qu’une puce ne peut en évacuer. C’est le mur de la puissance (power wall).

La loi de Moore continuait pourtant de livrer des transistors. Un cœur unique ne savait pas bien les employer : la largeur et la profondeur supplémentaires d’un cœur dans le désordre rapportent de moins en moins, parce que le code ordinaire n’a pas assez d’instructions indépendantes pour l’alimenter. Restait une option : construire plusieurs cœurs complets et laisser le logiciel exécuter plusieurs threads à la fois. IBM a mis deux cœurs sur une même puce avec le POWER4 en 2001. Intel et AMD ont livré leurs premières puces x86 double cœur en 2005. Les téléphones actuels ont de six à dix cœurs, les puces de serveur plus d’une centaine.

Le revers : un deuxième cœur n’apporte rien à un programme qui n’a qu’un thread. La vitesse doit désormais venir du logiciel, découpé en threads ou en processus.

Le multithreading matériel

Avant de dupliquer des cœurs entiers, il existe une façon moins chère d’exécuter plusieurs threads : laisser un seul cœur conserver l’état de plusieurs. Un cœur passe une bonne partie de son temps à attendre : un défaut de cache, un branchement mal prédit, une longue division. S’il a un second thread prêt, il peut combler ces trous.

Le multithreading matériel donne à chaque thread sa propre copie de l’état architectural (registres, compteur de programme, drapeaux), tandis que les threads partagent les unités d’exécution et les caches. Trois variantes :

Le grain fin cache bien la latence mais exige beaucoup de threads, et un thread seul avance lentement. Le gros grain garde un thread rapide mais paie un remplissage du pipeline à chaque bascule. Le multithreading simultané s’intègre naturellement à un cœur dans le désordre : son ordonnanceur choisit déjà des instructions prêtes dans une grande fenêtre, et peu lui importe de quel thread elles viennent. Intel l’a introduit sous le nom d’Hyper-Threading en 2002, avec deux threads par cœur. Le POWER8 d’IBM est monté jusqu’à huit.

Le SMT coûte peu de silicium, mais les deux threads se disputent tout : ports d’exécution, cache L1, prédicteur de branchement, TLB. Deux threads sur un cœur font en général plus de travail ensemble qu’un seul, mais bien moins que deux cœurs. Ils peuvent aussi s’espionner à travers les structures partagées, ce qui pousse certains systèmes sensibles à désactiver le SMT. Les cœurs d’Apple n’en ont pas, et Intel a retiré l’Hyper-Threading des cœurs performance de ses puces pour portables et ordinateurs de bureau de 2024. Sur le M2 Ultra, les nombres de processeurs logiques et physiques sont égaux :

$ sysctl hw.physicalcpu hw.logicalcpu
hw.physicalcpu: 24
hw.logicalcpu: 24

Les GPU poussent le multithreading à grain fin à l’extrême, en alternant entre des dizaines de groupes de threads pour masquer la latence mémoire ; le chapitre SIMD et GPU les décrit.

Cœurs performance et cœurs efficacité

Les 24 cœurs du M2 Ultra ne sont pas tous identiques :

$ sysctl hw.nperflevels hw.perflevel0.name hw.perflevel0.logicalcpu \
         hw.perflevel1.name hw.perflevel1.logicalcpu
hw.nperflevels: 2
hw.perflevel0.name: Performance
hw.perflevel0.logicalcpu: 16
hw.perflevel1.name: Efficiency
hw.perflevel1.logicalcpu: 8

Les cœurs performance sont de larges cœurs dans le désordre, ceux mesurés dans le chapitre sur les cœurs réels. Les cœurs efficacité sont plus petits et plus lents, mais font le même travail avec beaucoup moins d’énergie. Les deux exécutent le même jeu d’instructions ARM64 : le système d’exploitation peut donc placer n’importe quel thread sur l’un ou l’autre. ARM a lancé l’idée sous le nom de big.LITTLE en 2011, Apple l’utilise dans tous ses Mac à puce M depuis 2020, et les P-cores et E-cores d’Intel ont suivi en 2021.

L’écart se mesure facilement. Une boucle de 4,8 milliards de multiplications-additions dépendantes a pris 4,6 s sur un cœur performance, et 9,1 à 9,8 s sur un cœur efficacité (forcé avec taskpolicy -b, qui abaisse aussi sa fréquence). Répartie entre plusieurs threads, chacun faisant une part égale :

Jusqu’à 16 threads, chacun obtient un cœur performance et l’accélération suit le nombre de threads. Les 8 derniers atterrissent sur des cœurs efficacité, qui valent à peu près quatre cœurs performance : 24 cœurs, mais une accélération d’environ 19 au mieux. Faire prendre aux threads de petits morceaux de travail dans un compteur partagé, plutôt que des parts égales fixées d’avance, a donné le meilleur résultat, 0,24 s, parce que les cœurs rapides prennent simplement plus de morceaux. Le système aide aussi en déplaçant les threads d’un type de cœur à l’autre pendant l’exécution.

Caches privés, mémoire partagée

Chaque cœur a ses propres caches L1, et en général son propre L2 ou un L2 partagé par un petit groupe. Sur le M2 Ultra, chaque groupe de quatre cœurs performance partage un L2 de 16 Mo, et chaque groupe de quatre cœurs efficacité un L2 de 4 Mo :

hw.perflevel0.cpusperl2: 4
hw.perflevel0.l2cachesize: 16777216
hw.perflevel1.cpusperl2: 4
hw.perflevel1.l2cachesize: 4194304

Les caches privés sont rapides parce qu’ils sont proches et que personne d’autre ne s’en sert. Mais ils créent un problème que le chapitre sur les caches pouvait ignorer. Supposons que les cœurs 0 et 1 aient tous deux lu la variable x dans leur L1. Le cœur 0 écrit x = 1 dans son cache à écriture différée (write-back). Le cœur 1 relit x, trouve sa propre copie, et obtient l’ancienne valeur. Deux copies d’une même adresse sont désormais en désaccord.

Le matériel l’empêche grâce à un protocole de cohérence de cache. Sa promesse est simple : pour chaque emplacement mémoire pris isolément, tous les cœurs voient les écritures dans le même ordre, et une lecture renvoie la dernière écriture. Le moyen habituel de le garantir est la règle un seul écrivain ou plusieurs lecteurs : à tout instant, une ligne est soit modifiable par un seul cache, soit lisible par un nombre quelconque de caches, jamais les deux.

MESI

Le protocole classique, MESI, marque chaque ligne de chaque cache d’un état parmi quatre :

Les caches surveillent les requêtes des autres, à l’origine en espionnant (snooping) un bus partagé, où chaque cache voit chaque transaction. Les transitions principales :

• Défaut en lecture. Le cache demande la ligne. Si personne d’autre ne l’a, elle arrive en E ; si d’autres caches l’ont, tout le monde finit en S. Si un cache la détient en M, c’est lui qui fournit les données (et elles sont réécrites en mémoire), et les deux finissent en S.
• Écriture dans une ligne S. Le cache diffuse d’abord une invalidation : toutes les autres copies passent en I. Ensuite seulement, sa propre copie devient M. C’est la règle de l’écrivain unique en action.
• Écriture dans une ligne E. Personne d’autre ne l’a : le cache passe en M sans bruit, sans aucun trafic sur le bus. C’est tout l’intérêt de l’état E : un thread qui lit puis écrit des données privées ne paie aucune diffusion.
• Défaut en écriture. Le cache demande la ligne avec intention de la modifier : il obtient les données et invalide toutes les autres copies en une seule transaction.

La démo ci-dessous applique exactement ces règles à deux cœurs. Lisez x depuis le cœur 0 et la ligne arrive E ; lisez-la depuis le cœur 1 et les deux copies passent S ; incrémentez-la sur le cœur 1 et la copie du cœur 0 est invalidée ; relisez-la sur le cœur 0 et le cœur 1 fournit la ligne modifiée et la réécrit en mémoire.

Les puces réelles ajoutent des états. AMD utilise MOESI, dont l’état O (Owned) permet de partager une ligne modifiée sans la réécrire d’abord en mémoire. Le MESIF d’Intel ajoute un état F (Forward) qui désigne le seul détenteur chargé de répondre, pour que plusieurs caches ne répondent pas à la fois. Une puce de dizaines de cœurs ne peut pas non plus diffuser chaque requête à tout le monde : elle tient un filtre d’espionnage (snoop filter) ou un répertoire (directory) qui note quels cœurs détiennent chaque ligne, et n’interroge que ceux-là. Le chapitre sur les multiprocesseurs revient sur les répertoires, qui y deviennent indispensables.

La cohérence est aussi ce qui fait fonctionner les instructions atomiques sur une puce multicœur : un cœur qui exécute lock add ou ldadd prend la ligne en état M, fait la lecture et l’écriture dans son propre cache, et fait patienter les requêtes des autres cœurs jusqu’à ce qu’il ait fini. Le verrouillage du bus des machines anciennes n’est plus nécessaire, comme l’explique le chapitre sur l’arbitrage de bus.

Une ligne qui voyage entre cœurs

La cohérence n’est pas gratuite. Quand un cœur écrit une ligne qu’un autre cœur détient, la ligne doit se déplacer. Deux threads qui jouent au ping-pong à travers une variable partagée (chacun attend la valeur de l’autre, puis écrit la sienne) le mesurent directement. Sur le M2 Ultra, sur plusieurs centaines d’exécutions de 20 000 allers-retours, un aller-retour a pris 66 à 70 ns au mieux, environ 110 ns pour l’exécution médiane, et jusqu’à environ 400 ns pour la plus lente.

macOS ne laisse pas un programme choisir les cœurs de ses threads, donc chaque exécution tombe sur une paire différente. L’écart est cohérent avec l’organisation de la puce : deux cœurs d’un même groupe partagent un L2, deux cœurs de groupes différents non, et sur le M2 Ultra certaines paires sont sur des puces (dies) différentes. Dans tous les cas, un passage par le protocole de cohérence coûte des dizaines à des centaines de nanosecondes, contre environ 1 ns pour un succès en L1.

Le faux partage

La cohérence travaille sur des lignes entières, pas sur des variables. Deux threads qui écrivent des variables différentes situées dans la même ligne se la disputent quand même : chaque écriture invalide la copie de l’autre cœur, et la ligne fait des allers-retours exactement comme si les données étaient partagées. C’est le faux partage (false sharing).

La démo de cohérence ci-dessus le montre à l’échelle d’une seule ligne. Appuyez sur Lecture avec x et y dans la même ligne : deux threads incrémentent chacun leur compteur 8 fois, et chacun des 16 incréments échoue : 16 transactions de bus et 15 invalidations, la ligne faisant des allers-retours entre les deux caches. Passez à lignes séparées et relancez : chaque thread échoue une fois, puis réussit 7 fois : 2 transactions de bus, aucune invalidation.

Le test : chaque thread incrémente son propre compteur 100 millions de fois, avec un chargement, une addition et un rangement volatile. Les compteurs sont soit voisins (à 8 octets d’écart, dans une même ligne de 128 octets), soit à 128 octets l’un de l’autre (une ligne chacun) :

static void *work(void *arg) {
    volatile long *c = arg;          // each thread gets its own counter
    for (long i = 0; i < 100000000; i++)
        (*c)++;
    return NULL;
}

Temps sur le M2 Ultra, trois exécutions chacun, chaque thread faisant les mêmes 100 millions d’incréments :

Espacés, 8 threads font 8 fois le travail dans le même temps qu’un seul, et 16 threads à peine plus : un passage à l’échelle quasi parfait, puisque rien n’est partagé. Serrés, deux threads sont déjà 5 fois plus lents qu’un seul, alors qu’aucun ne lit jamais le compteur de l’autre. Avec des incréments atomiques (atomic_fetch_add, relâché) au lieu d’incréments ordinaires, deux threads ont pris 12,9 à 14,1 ns par incrément serrés et 2,1 ns espacés, un facteur 6 à 7.

Il y a une subtilité sur cette machine. sysctl hw.cachelinesize indique 128 octets, deux fois la taille x86. Des compteurs à 64 octets d’écart, sans danger sur une puce x86, partagent encore une ligne ici : avec des atomiques, deux threads ont pris 3,9 à 4,2 ns par incrément à 64 octets de distance, deux fois le temps des compteurs espacés. Un code qui aligne sur 64 octets « parce que les lignes de cache font 64 octets » reste en faux partage sur les puces d’Apple. std::hardware_destructive_interference_size en C++17, et ____cacheline_aligned dans le noyau Linux, existent pour obtenir la bonne valeur sur chaque plateforme.

Le remède est dans la disposition des données : donner aux données chaudes de chaque thread leur propre ligne, avec alignas(128) ou du remplissage, ou garder les données de chaque thread dans des structures à lui et les combiner à la fin. Le faux partage est invisible dans le code source et difficile à trouver sans les compteurs de performance matériels ; c’est une cause classique de programmes qui ralentissent quand on ajoute des threads.

La loi d’Amdahl

Supposons qu’un programme passe une fraction p de son temps dans un travail qu’on peut répartir sur n cœurs, et le reste, 1 − p, dans un travail qu’on ne peut pas répartir : lecture des entrées, une phase séquentielle, un verrou devant lequel tout le monde fait la queue. La meilleure accélération possible est :

accélération = 1 / ((1 − p) + p / n)

Gene Amdahl a formulé cet argument en 1967, et il fait réfléchir. Quand n grandit, p / n s’évanouit, et l’accélération ne peut jamais dépasser 1 / (1 − p). Un programme parallèle à 95 % ne pourra jamais aller plus de 20 fois plus vite, quel que soit le nombre de cœurs. Changez p ci-dessous et lancez :

1// Amdahl's law: speedup = 1 / ((1 - p) + p / n)
2// p is the parallel fraction, in thousandths (950 = 95%).
3long speedup_x100(long p, long n) {
4    return 100 * 1000 * n / ((1000 - p) * n + p);
5}
6 
7int main() {
8    long p = 950;                       // try 500, 900, 990...
9    long cores[6] = {1, 2, 8, 24, 100, 1000};
10    printf("parallel part: %ld.%ld%%\n", p / 10, p % 10);
11    for (int i = 0; i < 6; i++) {
12        long s = speedup_x100(p, cores[i]);
13        printf("%4ld cores: %ld.%02ld x\n", cores[i], s / 100, s % 100);
14    }
15    return 0;
16}

À 95 %, 24 cœurs donnent 11,16× et 1 000 cœurs seulement 19,62×. À 99 %, 24 cœurs donnent 19,51× et 1 000 cœurs 90,99×. (La démo calcule en entiers : elle tronque au lieu d’arrondir.) La fraction séquentielle domine vite : ce sont les derniers 5 % qui décident de ce que valent 1 000 cœurs.

Le passage à l’échelle mesuré plus haut colle à ce tableau. La boucle de calcul est presque 100 % parallèle : les 16 cœurs performance du M2 Ultra ont donc donné environ 14,5×, et ce qui a limité le résultat à 24 cœurs à 19× était la lenteur des cœurs efficacité, pas une partie séquentielle. Un vrai programme a aussi des surcoûts qui grandissent avec n (verrous disputés, lignes qui rebondissent d’un cache à l’autre, comme les compteurs partagés du chapitre sur les threads) et peut même ralentir au-delà d’un certain nombre de cœurs.

La loi d’Amdahl suppose un problème de taille fixe. En pratique, on utilise les grosses machines pour de plus gros problèmes, et la partie parallèle grandit en général avec le problème, pas la partie séquentielle. John Gustafson l’a fait remarquer en 1988 : vue ainsi, l’accélération atteignable continue de croître avec n. Les deux points de vue sont justes ; ils répondent à des questions différentes : « de combien mon calcul va-t-il plus vite ? » contre « quel calcul plus gros puis-je faire dans le même temps ? ».

À retenir

• Quand la loi d’échelle de Dennard a pris fin vers 2005, les fréquences ont buté sur le mur de la puissance, et les transistors supplémentaires sont allés à davantage de cœurs. La performance doit désormais venir d’un logiciel parallèle.
• Le multithreading matériel garde l’état de plusieurs threads dans un cœur. Le SMT (Hyper-Threading) émet les instructions de plusieurs threads dans le même cycle ; les cœurs d’Apple n’en ont pas : 24 processeurs physiques = 24 logiques sur le M2 Ultra.
• Le M2 Ultra a 16 cœurs performance et 8 cœurs efficacité. Une boucle de calcul a accéléré d’environ 14,5× sur 16 threads et de 17 à 19× sur 24, un cœur efficacité l’exécutant environ deux fois moins vite.
• Un protocole de cohérence garde les caches privés cohérents : un seul écrivain ou plusieurs lecteurs par ligne. MESI suit chaque ligne comme Modifiée, Exclusive, Partagée ou Invalide ; les grandes puces suivent les détenteurs avec des filtres d’espionnage ou des répertoires.
• Déplacer une ligne entre deux cœurs du M2 Ultra a pris de 66 à 400 ns par aller-retour, selon l’endroit où tournaient les threads.
• Faux partage : des compteurs indépendants dans une même ligne de 128 octets ont rendu deux threads 5× plus lents qu’un seul (6 à 7× avec des atomiques) ; les espacer de 128 octets a donné un passage à l’échelle quasi parfait. Sur les puces d’Apple, aligner sur 64 octets ne suffit pas.
• Loi d’Amdahl : avec une fraction parallèle p, l’accélération plafonne à 1 / (1 − p) : 20× pour un programme parallèle à 95 %, quel que soit le nombre de cœurs.