Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
L'exécution dans le désordre (« out of order execution » en anglais, ou OoO) consiste à réorganiser l'ordre dans lequel les instructions vont s'exécuter dans le processeur. Ces instructions ne sont alors pas forcément exécutées dans l'ordre dans lequel elles apparaissent dans le programme[1].
Cela permet de mieux exploiter les ressources d'un processeur et ainsi de gagner du temps de calcul par rapport à l'exécution dans l'ordre (« in-order ») qui consiste à exécuter les instructions dans l'ordre prévu par le compilateur. Cette dernière permet cependant de diminuer les coûts et la consommation d'énergie en simplifiant le processeur. C'est par exemple le cas dans les processeurs Intel Atom (excepté depuis fin 2013) et une partie des ARM.
Dépendances de données
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 les instructions. Il existe trois types de dépendances de données.
Dépendances de données
Type
Effets
Read after write
La première instruction va écrire son résultat dans un registre ou dans la RAM, et un peu plus tard, la seconde va lire ce résultat et effectuer une opération dessus.
Write after Read
La première instruction va lire un registre ou le contenu d'une adresse en RAM, et la seconde va écrire son résultat au même endroit un peu plus tard.
Write after Write
Les deux instructions effectuent des écritures au même endroit : registre ou adresse mémoire.
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.
Exécution dans le désordre, Issue dans l'ordre
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 (émission), d’envoi des instructions aux unités fonctionnelles ne change 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.
Algorithme de Tomasulo
L'algorithme de Tomasulo est un algorithme d'exécution dans le désordre qui incorpore des techniques de renommage de registres pour supprimer les dépendances inutiles entre instructions et améliorer l’efficacité de l'exécution dans le désordre, ainsi qu'un réseau de bypass permettant de diminuer l'effet de certaines dépendances Read After Write sur les performances.
Exécution dans le désordre, Issue dans le désordre
Issue dans le désordre (mémoire tampon en jaune).
Certains algorithmes un peu plus évolués sont capables non seulement d’exécuter les instructions dans le désordre, mais aussi de les émettre (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.
