Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Architecture des ordinateurs

Exécution dans le désordre : Tomasulo, tampon de réordonnancement et spéculation

Émission, exécution et validation, stations de réservation et bus de données commun, tampon de réordonnancement et exceptions précises avec démonstration, exécution spéculative et Spectre, désambiguïsation de la mémoire.

https://www.electronics-engineering.com/fr/execution-dans-le-desordre-tomasulo-tampon-de-reordonnancement/

Pas encore de vote : soyez le premier à noter cette page.

Un pipeline dans l’ordre s’arrête quand une instruction attend des données, et avec elle toutes les suivantes, même indépendantes. Un processeur dans le désordre laisse passer devant les instructions prêtes, et réordonne les résultats à la fin. C’est l’idée de l’algorithme de Tomasulo (IBM 360/91, 1967), qui, avec l’ajout du tampon de réordonnancement, est le cœur de tout processeur haute performance actuel. Dans cette leçon, nous regardons les stations de réservation, le bus de données commun, le tampon de réordonnancement avec la démonstration qu’il garantit des exceptions précises, l’exécution spéculative et la désambiguïsation de la mémoire.

L’idée

Un chargement qui manque le cache peut coûter des centaines de cycles. Dans un pipeline dans l’ordre, le processeur reste inactif pendant tout ce temps. Pourtant, derrière le chargement, il y a souvent des dizaines d’instructions qui n’ont rien à voir avec la donnée attendue. L’exécution dans le désordre sépare trois moments qui coïncident dans le pipeline simple :

  1. l’émission, dans l’ordre : l’instruction est décodée, ses registres renommés, et elle est mise en attente ;
  2. l’exécution, dans le désordre : elle démarre dès que ses opérandes sont disponibles ;
  3. la validation (commit), de nouveau dans l’ordre : le résultat devient définitif, visible pour l’architecture.
Schéma d'un processeur dans le désordre avec stations de réservation, bus de données commun et tampon de réordonnancement
Les instructions vont de la file IQ à la table d’alias des registres RAT, puis aux stations de réservation RS, une par type d’unité. Quand les opérandes sont prêts, l’instruction va à l’unité fonctionnelle ; le résultat est diffusé sur le bus de données commun CDB aux stations qui l’attendent et au tampon de réordonnancement ROB, qui met à jour les registres RF dans l’ordre.

Stations de réservation et bus de données commun

Chaque unité fonctionnelle a devant elle un groupe de stations de réservation : des registres qui contiennent une instruction en attente, avec ses opérandes. Pour chaque opérande, la station contient la valeur, si elle est déjà disponible, ou l’étiquette de l’instruction qui la produira. Les étiquettes sont en pratique les registres physiques de la leçon précédente : le renommage se fait ici, et les dépendances WAR et WAW disparaissent.

Quand une unité termine, elle met le résultat et son étiquette sur le bus de données commun (CDB). Toutes les stations qui attendent cette étiquette la capturent dans le même cycle ; une instruction dont tous les opérandes sont prêts est envoyée à son unité à la première occasion, sans égard pour l’ordre du programme. Les vraies dépendances sont respectées par construction, parce qu’aucune instruction ne démarre sans ses opérandes.

Le tampon de réordonnancement

Dans l’algorithme original, les résultats écrivaient directement dans les registres, dans le désordre. Cela crée un problème : si une instruction provoque une exception (une division par zéro, un défaut de page), certaines instructions suivantes pourraient avoir déjà modifié l’état, et le système d’exploitation ne saurait pas où reprendre. La solution est le tampon de réordonnancement (ROB) : une file circulaire où chaque instruction prend une place, dans l’ordre du programme, à l’émission. Les résultats s’écrivent dans le ROB ; une instruction est validée (commit), c’est-à-dire qu’elle écrit dans les registres architecturaux ou en mémoire, seulement quand elle est en tête de file et terminée.

Théorème. Avec une validation dans l’ordre depuis le ROB, les exceptions sont précises : quand l’exception de l’instruction I_k est traitée, l’état architectural contient les résultats de toutes les instructions qui précèdent I_k et d’aucune de celles qui suivent.

Démonstration. L’état architectural (registres et mémoire) ne change qu’à la validation, et les instructions sont validées dans l’ordre du programme, l’une après l’autre depuis la tête du ROB. L’exception de I_k est enregistrée dans sa place du ROB et traitée quand I_k arrive en tête : à ce moment toutes les instructions précédentes ont été validées, parce qu’elles étaient devant dans la file, et aucune des suivantes ne l’a été, parce qu’elles sont derrière. Le processeur jette le contenu du ROB à partir de I_k et saute au gestionnaire. ∎

L’exécution spéculative

Le même mécanisme permet d’exécuter des instructions avant de savoir si elles doivent l’être. Quand on rencontre un branchement conditionnel, le processeur prédit sa direction (leçon sur la prédiction) et continue d’émettre des instructions sur ce chemin. Si la prédiction était juste, ces instructions sont validées normalement ; si elle était fausse, quand le branchement arrive en tête du ROB, toutes les instructions suivantes sont jetées et l’exécution repart de la bonne adresse. Rien de ce qui a été fait par erreur n’a touché l’état architectural.

L’état micro-architectural, lui, a été touché : les instructions exécutées par erreur peuvent avoir chargé des données dans les caches. C’est le principe des attaques Spectre (2018), qui déduisent des données secrètes en mesurant les temps d’accès au cache après une exécution spéculative. Les contre-mesures (barrières, isolation, modifications des compilateurs) coûtent quelques pour cent de performance.

La mémoire

Les dépendances à travers la mémoire sont les plus délicates : un chargement peut lire l’adresse qu’une écriture précédente est sur le point d’écrire, mais l’adresse n’est connue qu’après avoir été calculée. Les écritures attendent la validation dans une file d’écritures ; un chargement compare son adresse à celles de la file et, s’il trouve une écriture à la même adresse, en prend directement la valeur (store-to-load forwarding). Les processeurs modernes osent plus : ils exécutent le chargement même avant de connaître les adresses des écritures précédentes, en prédisant qu’il n’y a pas de conflit, et s’ils se trompent, ils annulent et ré-exécutent.

Les tailles

Un processeur haute performance de 2025 a un ROB de 500-600 entrées, quelques centaines de registres physiques, une dizaine d’unités fonctionnelles et peut avoir des centaines d’instructions « en vol ». La grande fenêtre sert surtout à cacher la latence de la mémoire : pendant qu’un chargement attend la DRAM, le processeur trouve du travail utile plusieurs instructions plus loin.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x