Exécution dans le désordre

L'exécution dans le désordre permet à un processeur d'exécuter les instructions dès que leurs opérandes sont prêts, plutôt que de suivre strictement l'ordre du programme. Elle utilise le renommage de registres et la mise en tampon pour exposer le parallélisme tout en produisant des résultats dans l'ordre.

Definition

L'exécution dans le désordre est une technique microarchitecturale par laquelle un processeur réorganise dynamiquement l'exécution des instructions pour lancer les instructions indépendantes dès que leurs opérandes sont disponibles, tout en utilisant la mise en tampon et le renommage pour préserver l'apparence d'une exécution séquentielle et d'une complétion dans l'ordre.

Scope

Ce sujet couvre l'ordonnancement dynamique : les stations de réservation, le renommage de registres pour éliminer les fausses dépendances, le tampon de réorganisation (reorder buffer) qui assure la validation dans l'ordre (in-order commit), et la récupération de l'exécution spéculative. Il s'appuie directement sur l'algorithme de Tomasulo. Il exclut la prédiction de direction de branche (branch prediction) et la notion plus large de l'étendue du parallélisme (instruction-level parallelism), se concentrant sur le mécanisme de réorganisation lui-même.

Core questions

• Comment un processeur peut-il exécuter des instructions dans le désordre du programme tout en produisant des résultats corrects et dans l'ordre ?
• Comment le renommage de registres élimine-t-il les dépendances d'écriture après lecture (write-after-read) et d'écriture après écriture (write-after-write) ?
• Quelle est la contribution des stations de réservation et du tampon de réorganisation ?
• Comment les exceptions et les mauvaises prédictions sont-elles récupérées précisément dans un cœur à exécution dans le désordre ?

Key concepts

• ordonnancement dynamique
• stations de réservation
• renommage de registres
• bus de données commun
• tampon de réorganisation
• validation dans l'ordre
• exceptions précises
• récupération de l'exécution spéculative

Key theories

Algorithme de Tomasulo

Le schéma de Tomasulo utilise des stations de réservation et un bus de données commun pour renommer les registres et distribuer les instructions aux unités fonctionnelles dès que leurs opérandes deviennent disponibles, permettant une exécution dans le désordre qui ne respecte que les vraies dépendances de données.

Exceptions précises via la validation dans l'ordre

Un tampon de réorganisation (reorder buffer) conserve les résultats des instructions exécutées dans le désordre et les valide dans l'ordre du programme, de sorte que les exceptions et les mauvaises prédictions peuvent être gérées précisément comme si l'exécution avait été strictement séquentielle.

Mechanisms

Les instructions décodées sont renommées en registres physiques et placées dans des stations de réservation ou une file d'attente d'émission (issue queue), où elles attendent les opérandes diffusés sur un bus de résultats. Une fois prêtes, elles s'exécutent sur les unités fonctionnelles disponibles dans n'importe quel ordre. Un tampon de réorganisation suit l'ordre original du programme et valide les résultats séquentiellement, rejetant les résultats spéculatifs en cas de mauvaise prédiction ou d'exception afin que l'état architectural soit toujours précis.

Clinical relevance

L'exécution dans le désordre est le moteur principal des processeurs haute performance, masquant les latences de mémoire et d'exécution en trouvant des tâches indépendantes à effectuer. Elle a également des implications en matière de sécurité : étant donné que le travail spéculatif et désordonné peut accéder transitoirement à des données avant d'être annulé, elle a permis les classes d'attaques par canal auxiliaire microarchitectural de type Spectre et Meltdown.

History

Tomasulo a introduit l'ordonnancement dynamique dans l'IBM System/360 Model 91 en 1967. La combinaison avec le tampon de réorganisation (reorder buffer) pour les exceptions précises, développée dans les années 1980, a rendu l'exécution dans le désordre pratique pour les processeurs à usage général, et elle est devenue la norme dans les conceptions haute performance à partir du milieu des années 1990.

Debates

Performance versus complexité, consommation d'énergie et sécurité

L'exécution dans le désordre offre de solides performances en mode mono-thread, mais à un coût significatif en termes de complexité matérielle et de consommation d'énergie, et sa spéculation s'est avérée exploitable ; cela alimente le débat sur l'agressivité de la spéculation par rapport à la préférence pour des conceptions plus simples, plus efficaces ou plus sécurisées.

Key figures

• Robert Tomasulo
• Yale Patt
• James E. Smith
• John L. Hennessy

Seminal works

• tomasulo1967
• hennessy2019

Frequently asked questions

Si les instructions s'exécutent dans le désordre, comment le programme reste-t-il correct ?

Le processeur réorganise uniquement l'exécution, pas les résultats. Le renommage de registres garantit qu'il respecte les vraies dépendances de données, et un tampon de réorganisation (reorder buffer) valide les résultats dans l'ordre original du programme, de sorte que l'état architectural visible est exactement celui que produirait une exécution séquentielle.

Qu'est-ce que le renommage de registres ?

Le renommage de registres mappe les registres architecturaux nommés dans les instructions sur un pool plus large de registres physiques. Cela élimine les fausses dépendances (de nom) qui découlent de la réutilisation des noms de registres, permettant à davantage d'instructions indépendantes de s'exécuter en parallèle sans conflit pour le stockage des registres.