Exécution dans le désordre

L'exécution dans le désordre évite l'insertion de bulles dans le pipeline lorsque deux instructions ayant une dépendance de données sont chargées dans le pipeline. Par dépendances de données, on veut dire qu'une des instructions va aller lire ou écrire à la même adresse, ou dans le même registre d'une façon qui impose un ordre d’exécution strict pour nos instructions. Il existe trois types de dépendances de données.

Ces dépendances imposent un certain ordre d’exécution pour les instructions. L'ordre d’exécution des lectures et des écritures ne doit pas changer, sous peine de modifier le résultat du programme. Or, sur les processeurs dotés de pipeline, il se peut que les lectures et écritures changent d'ordre : les lectures et écritures dans les registres ne se font pas aux mêmes étages, et une instruction peut donc lire une donnée pas encore écrite, etc. Cela arrive lors de l’exécution d'instructions multicycles, ou en l'absence de réseau de forwarding. Dans ces conditions, le processeur insère des bulles dans le pipeline pour maintenir l'ordre des lectures/écritures tel que spécifié par le programmeur. L'exécution dans le désordre consiste à remplacer ces bulles par les instructions suivant l'instruction bloquée.

Les algorithmes d’exécution dans le désordre les plus simples changent uniquement l'ordre d’exécution des instructions, ainsi que l'ordre dans lequel les résultats sont disponibles en sortie de l'unité de calcul. Par contre, l'ordre d'Issue, d’envoi des instructions aux unités fonctionnelles ne changent pas : les instructions sont fetchées, décodées, et issues dans l'ordre imposé par le programme. Deux algorithmes de ce type existent : le scoreboarding, et l'algorithme de Tomasulo. Tous les processeurs implémentant l’exécution dans le désordre possèdent plusieurs unités fonctionnelles, comme des unités de calcul.

Scoreboarding

Scoreboarding

L'algorithme de scoreboarding utilise une détection et une gestion des dépendances centralisée : un seul circuit s’occupe de détecter et de gérer toutes les dépendances entre instructions. Ce circuit s'appelle le scoreboard.

Celui est basé sur 4 grandes étapes : l'issue, la lecture des opérandes, l’exécution, et l'écriture des résultats. Ces 4 étages de pipeline sont parfois présents dans d'autres processeurs qui ne gèrent pas l'exécution dans le désordre. Mais ceux-ci ne fonctionnent pas de la même façon dans l'algorithme de scoreboarding.

• L'étage Issue sert à vérifier que l'instruction présente dans l'étage n'a pas de dépendances structurelles ou Write after Write avec une instruction présente dans les étages suivants du pipeline.
• L'étage Read Operand va lire les opérandes de l'instruction, depuis les registres ou la mémoire.
• Une fois ces opérandes disponibles, l'instruction s’exécute.
• Ensuite, le résultat de l'instruction est écrit dans les registres à l'étage Writeback. Dans cet étage, l'instruction est mise en attente (elle n'enregistre pas son résultat dans les registres ou la mémoire) tant qu'elle a une dépendance WAR (Write after Read) avec une autre instruction dans le pipeline.

C'est le scoreboard qui pilote le passage de chaque instruction d'un étage à un autre. Pour cela, il doit détecter les dépendances entre instructions en fonction des informations que lui envoient les autres circuits du processeur. Pour ce faire il mémorise, pour chaque instruction :

• le registre dans lequel sera enregistré le résultat de l'instruction ;
• l'état courant de l'instruction (l'étage du pipeline dans lequel elle est).

Le scoreboard doit aussi mémoriser l'état courant de chaque unité fonctionnelle du processeur, afin de détecter les dépendances structurelles et certaines dépendances Read after Write. Ainsi, le scoreboard peut décider quand une instruction en attente dans l'étage Read Operand peut passer à l'étape d'exécution dans l'unité fonctionnelle qui lui a été réservée. Ce scoreboard doit pour cela mémoriser :

• si l'unité est en cours d'utilisation ;
• l'opération qu'elle exécute ;
• le registre de destination du résultat ;
• les registres des opérandes de l'instruction en cours d’exécution dans l'unité fonctionnelle ;
• les unités qui fournissent ces opérandes ;
• des bits qui indiquent si ces opérandes sont disponibles ou pas.

OOO Issue

Certains algorithmes un peu plus évolués sont capables non seulement d’exécuter les instructions dans le désordre, mais aussi de les Issue dans le désordre. Ces algorithmes peuvent être vus comme des variations du scoreboarding ou de l'algorithme de Tomasulo, mais auxquels un circuit a été ajouté : l'Instruction Window, aussi appelée Issue Queue. Ce circuit est une mémoire tampon, intercalée entre l'étage d'Issue et l'étage précédent (décodage ou renommage de registres). Cette mémoire tampon va servir à stocker des instructions tant que celles-ci ne sont pas prêtes à être exécutées. Ainsi, si une instruction ne peut être exécutée, pour cause de dépendance structurelle ou de dépendance non-résoluble, elle ne bloquera pas le reste du pipeline. À la place, de nouvelles instructions pourront être chargées et être envoyées aux unités de calcul si elles le peuvent.