Exécution dans le désordre, renommage de registres et spéculation

Un pipeline dans l’ordre s’arrête à la première instruction qui n’est pas prête. Si un chargement prend quatre cycles, tout ce qui le suit attend, même les instructions qui n’ont rien à voir avec lui. Les autres unités du pipeline restent inactives alors qu’il y a du travail utile quelques instructions plus loin.

Un cœur dans le désordre (out of order) n’attend pas. Il regarde plus loin dans le programme, prend les instructions dont les entrées sont prêtes et les exécute : une instruction lente ne bloque plus celles qui n’en dépendent pas. Pour le programme, rien ne change : les résultats sont toujours validés comme si chaque instruction s’exécutait l’une après l’autre, dans l’ordre.

L’idée est ancienne. Le CDC 6600 (1964) utilisait un tableau de bord (scoreboard) pour suivre les registres en cours de calcul et laisser avancer les instructions indépendantes. L’IBM System/360 Model 91 (1967) a introduit l’algorithme de Tomasulo, avec renommage de registres et diffusion des résultats vers les instructions en attente. Il s’est imposé dans les CPU de bureau avec le Pentium Pro en 1995.

Une chaîne lente ne doit pas bloquer les autres

Les démos de ce chapitre exécutent un programme dans l’émulateur, puis ordonnancent les instructions exécutées sur deux cœurs aux ressources identiques : 2 instructions par cycle, chargements en 4 cycles (un succès dans le L1), multiplications en 3, divisions en 20, tout le reste en 1. L’un des cœurs démarre les instructions dans l’ordre du programme ; l’autre non.

Chaque ligne est une instruction : D quand elle entre dans le cœur, · pendant qu’elle attend, L pour un chargement, E pour l’exécution, R quand elle est retirée. Sur le cœur in order, le programme prend 26 cycles. Le chargement de ebx ne peut pas démarrer avant que la chaîne de eax qui le précède ait lancé sa dernière multiplication, et la chaîne de ecx attend à son tour. Les trois chaînes s’exécutent l’une après l’autre, alors qu’elles ne partagent aucune valeur.

Passez en out of order : 15 cycles. Les trois chargements démarrent presque ensemble, et les multiplications de chaque chaîne suivent dès que leurs propres entrées arrivent. Le seul ordre qui reste est celui qu’imposent les données.

L’organisation d’un cœur dans le désordre

Le cœur se découpe en une partie dans l’ordre, une partie dans le désordre, puis de nouveau une partie dans l’ordre :

1. Front end, dans l’ordre. Lire, prédire les branchements, décoder en µops, renommer les registres (voir plus bas), et envoyer chaque µop dans le tampon de réordonnancement (ROB, reorder buffer) et dans un ordonnanceur (aussi appelé stations de réservation).
2. Exécution, dans le désordre. À chaque cycle, l’ordonnanceur choisit des µops dont les opérandes sont prêts et les envoie aux unités d’exécution libres. Quand une µop se termine, elle diffuse son résultat aux µops qui l’attendent.
3. Retrait, dans l’ordre. Le ROB liste les µops dans l’ordre du programme. La plus ancienne est retirée — son résultat devient officiel — seulement quand elle est terminée et que tout ce qui la précède a été retiré.

Le ROB, c’est la fenêtre d’instructions : jusqu’où, au-delà de la plus ancienne instruction non terminée, le cœur peut chercher du travail. Les cœurs actuels en ont de grandes : 512 entrées dans le Golden Cove d’Intel, 320 dans le Zen 4 d’AMD.

Pourquoi le retrait reste dans l’ordre

L’exemple d’exécution dans le désordre de Tanenbaum laisse aussi les instructions se terminer dans le désordre, pour rester simple. Les vrais cœurs ne le font pas, à cause des exceptions précises. Quand une instruction provoque une faute — défaut de page, division par zéro — le système d’exploitation doit voir un état propre : toutes les instructions précédentes terminées, aucune des suivantes. C’est ce qui permet de traiter la faute puis de reprendre.

Le retrait dans l’ordre l’offre gratuitement. Une instruction fautive est seulement marquée dans le ROB. Quand elle arrive en tête, tout ce qui est plus ancien a été retiré et rien de plus récent : le cœur jette le travail plus récent et lève l’exception exactement là. Les interruptions sont traitées de la même façon.

Fausses dépendances et renommage de registres

Seule la lecture après écriture (RAW) est une vraie dépendance : la seconde instruction a besoin de la valeur que produit la première. Deux autres ordres n’existent que parce que le programme réutilise un nom de registre :

• Écriture après lecture (WAR) : une instruction veut écraser un registre qu’une instruction plus ancienne n’a pas encore lu.
• Écriture après écriture (WAW) : deux instructions écrivent le même registre, et c’est la valeur la plus récente qui doit rester.

Voici deux calculs sans rapport qui utilisent tous deux eax, comme le fait sans cesse le code compilé avec seulement 16 registres :

Avec renaming off, le second chargement doit attendre : il écraserait eax avant que la première chaîne en ait fini. Le programme prend 17 cycles, dans l’ordre ou non.

Passez renaming sur on : 11 cycles dans le désordre. Le cœur dans l’ordre reste à 17. Le renommage de registres donne à chaque résultat son propre registre physique. Les 16 noms de l’ISA — rax, rbx, … — ne sont que des entrées d’une table d’alias de registres qui indique quel registre physique contient actuellement chaque nom. Un cœur possède quelques centaines de registres physiques derrière ces 16 noms. Quand le second mov eax, … est renommé, eax pointe simplement vers un nouveau registre physique, et les deux chaînes s’exécutent côte à côte. WAR et WAW disparaissent ; seules les vraies dépendances restent.

Les drapeaux sont renommés eux aussi. Dans la première démo, désactivez le renommage : les trois chaînes ralentissent à 24 cycles, car chaque imul écrit aussi le registre des drapeaux. Les chaînes entrent donc en collision sur lui, même si leurs registres de données sont différents.

Le renommage permet aussi à certaines instructions de se terminer sans s’exécuter. xor eax, eax est reconnu comme « mettre à zéro, sans dépendre de l’ancienne valeur », et sur beaucoup de cœurs un mov de registre à registre se contente de recopier une entrée de la table d’alias.

Voir plus loin : la fenêtre

Plus la fenêtre est grande, plus le cœur peut trouver loin du travail indépendant — en particulier des chargements, qui peuvent prendre des centaines de cycles s’ils ratent les caches. En lancer plusieurs à la fois s’appelle le parallélisme au niveau mémoire (memory-level parallelism).

add eax, [m] est découpée en deux µops : le chargement, qui n’a besoin que de l’adresse, et l’addition, qui a besoin de la valeur chargée et de eax. Avec une fenêtre de 4, le cœur ne contient qu’une itération et la boucle prend 115 cycles. Passez-la à 32 : 52 cycles. Les chargements des itérations suivantes démarrent pendant que les précédents sont encore en cours, et seules les additions d’un cycle forment une chaîne. Réglez aussi width sur 4 : 29 cycles, plus de deux instructions par cycle. Le cœur dans l’ordre met 100 à 116 cycles dans les trois réglages.

Chargements et rangements demandent un soin particulier, car leurs adresses ne sont connues qu’à l’exécution. Les files de chargement et de rangement suivent toutes les µops mémoire en cours. Un chargement qui lit une adresse qu’un rangement plus ancien, pas encore retiré, est en train d’écrire obtient la valeur directement depuis la file de rangement (store-to-load forwarding). Un chargement peut aussi s’exécuter avant des rangements plus anciens dont l’adresse n’est pas encore connue, en pariant qu’ils ne se chevauchent pas ; si c’est le cas, il est rejoué.

La spéculation

La fenêtre ne s’arrête pas aux branchements. Grâce à la prédiction de branchement, le front end continue d’envoyer des µops le long du chemin prédit : une grande partie de la fenêtre est donc en général spéculative, faite d’instructions qui se révéleront peut-être sur le mauvais chemin. C’est sans danger grâce au retrait dans l’ordre. Quand un branchement s’avère mal prédit, toutes les µops plus récentes que lui sont vidées du ROB, la table d’alias est restaurée dans son état au moment du branchement, et la lecture repart de la bonne adresse. Aucun résultat du mauvais chemin n’a jamais été retiré.

Tanenbaum décrit aussi une spéculation faite par le compilateur : remonter un chargement au-dessus d’un branchement, avec des instructions spéciales et des bits de poison, pour qu’un chargement spéculatif fautif ne déclenche l’erreur que si sa valeur est réellement utilisée. Le bit NaT de l’Itanium fonctionnait ainsi. Les cœurs modernes dans le désordre font la même chose en matériel, dynamiquement, sur du code ordinaire.

Quand la spéculation fuit : Spectre et Meltdown

Vider le mauvais chemin annule ses effets sur les registres et la mémoire, mais pas sur les caches. Un chargement spéculatif amène quand même sa ligne dans le cache, et le chapitre sur les caches a montré à quel point un succès et un défaut diffèrent en temps. En 2018, des chercheurs en ont fait des attaques :

• Spectre (variante 1, contournement de vérification de bornes) : l’attaquant entraîne un branchement comme if (i < size) à être prédit pris, puis l’appelle avec un i hors limites. Le cœur lit spéculativement l’octet secret à array[i] et s’en sert comme indice dans un autre tableau, ce qui charge une ligne qui dépend du secret. Les résultats sont vidés, mais en mesurant quelle ligne est maintenant en cache, l’attaquant retrouve l’octet.
• Meltdown : sur beaucoup de cœurs Intel de l’époque, un chargement de mémoire noyau depuis le mode utilisateur n’était bloqué qu’au moment de son retrait. Spéculativement, il renvoyait les données, qui pouvaient fuir de la même façon.

Les parades touchent tous les niveaux : l’isolation des tables de pages du noyau (KPTI), qui garde la mémoire du noyau non mappée pendant que le code utilisateur s’exécute ; des barrières de spéculation comme lfence et le masquage d’indices insérés par les compilateurs ; des mises à jour de microcode ; et du nouveau silicium. Ce sont des attaques par exécution transitoire : elles lisent ce que la machine a fait sur un chemin qui, officiellement, n’a jamais eu lieu.

Les limites

L’exécution dans le désordre trouve le parallélisme qui existe déjà dans le programme ; elle ne peut pas le créer. Une seule chaîne d’opérations dépendantes — comme la somme courante eax ci-dessus — avance à la vitesse de cette chaîne, quelle que soit la taille de la fenêtre. Des fenêtres plus grandes, plus de registres physiques et des ordonnanceurs plus larges coûtent aussi de la surface et de l’énergie, et doivent être parcourus à chaque cycle. C’est l’une des raisons pour lesquelles les cœurs n’ont grandi que lentement en largeur et en profondeur, et pour lesquelles l’étape suivante a été de multiplier les cœurs — le sujet des chapitres sur les multicœurs.

À retenir

• Un cœur dans le désordre exécute les µops dès que leurs opérandes sont prêts, pas dans l’ordre du programme, mais les retire toujours dans l’ordre.
• Le tampon de réordonnancement est la fenêtre d’instructions, et le retrait dans l’ordre garantit des exceptions précises.
• Seules les dépendances RAW sont réelles. Le renommage vers des registres physiques supprime WAR et WAW, drapeaux compris.
• Une grande fenêtre offre du parallélisme au niveau mémoire. Les files de chargement et de rangement gèrent l’ordre mémoire, avec le store-to-load forwarding.
• Tout ce qui suit un branchement prédit est spéculatif et vidé en cas d’erreur. Ses effets de bord sur les caches sont ce qu’exploitent Spectre et Meltdown.