Fonctionnement d'un ordinateur/Le renommage de registres

Pour améliorer l'exécution dans le désordre, les concepteurs de processeurs ont étudié des méthodes pour éliminer la grosse majorité des dépendances de données lors de l’exécution. Dans ce que j'ai dit précédemment, j'ai évoqué trois types de dépendances de données. Les dépendances RAW (Read After Write) sont des dépendances contre lesquelles on ne peut rien faire : ce sont de « vraies » dépendances de données. Elles imposent un certain ordre d’exécution de nos instructions. Mais les dépendances WAW (write after write) et WAR (write after read) sont de fausses dépendances, nées du fait qu'un emplacement mémoire est réutilisé, pour stocker des données différentes à des instants différents. Bien évidemment, l’imagination débridée des concepteurs de processeur a trouvé une solution pour supprimer ces dépendances : le renommage de registres.

Avant toute chose, précisons que ce chapitre abordera uniquement les techniques compatibles avec les exceptions précises. En clair, seulement les techniques utilisées sur les processeurs modernes. Il existe deux autres techniques de renommage de registre utilisées sur les processeurs sans exceptions précises : l'algorithme de Tomasulo et le scoreboarding. Contrairement à ce que vous avez pu lire ailleurs, il y a une forme de renommage de registre dans le scoreboarding, mais nous verrons cela dans quelques chapitres. Toujours est-il que ces deux techniques historiques étaient utilisées sur d'anciens ordinateurs, qui n'implémentaient pas la prédiction de branchement. Leurs techniques de renommage de registres étaient particulières, aussi nous les verrons dans un chapitre à part.

Le renommage de registres : généralités

Les dépendances WAR et WAW sont souvent opposées aux dépendances vraies (true dependency), à savoir les dépendances RAW. Les dépendances WAR et WAW viennent du fait qu'un même registre nommé est réutilisé plusieurs fois pour des données différentes. Un même nom de registre identifie une donnée différente à des instants différents du programme, ce qui force à exécuter les isntructions qui utilisent ce registre dans l'ordre. D'où le fait que les dépendances WAR et WAW sont souvent appelées des dépendances de nom (naming dependency). Si on change l'ordre de deux instructions ayant une dépendance de données WAW ou WAR, on peut se retrouver dans une situation où les deux instructions veulent stocker des données différentes en même temps dans le même registre, ce qui n'est pas possible. Mais elles n'existeraient pas si on utilisait un registre pour chaque donnée, qui est écrit une fois, lu une ou plusieurs fois, mais jamais écrasé. Un même nom de registre correspond alors à une donnée.

Une solution simple vient alors à l'esprit : conserver chaque donnée dans son propre registre et choisir le registre adéquat à l'utilisation. Un registre architectural correspond alors à plusieurs registres, chacun contenant une donnée bien précise. L'idée est qu'au lieu d'avoir un registre qui contient des données différentes à des instants différents, on a autant de registres que de données, ce qui améliore les possibilités de réorganisation des instructions. Il faut ainsi faire la distinction entre :

• registres architecturaux, définis par le jeu d'instructions ;
• registres physiques, physiquement présents dans l'ordinateur.
• registres virtuels utilisés pour le renommage de registre mais invisibles pour le programmeur.

Les registres physiques regroupent l'ensemble des registres, à savoir les registres architecturaux et virtuels.

Pour illustrer l'idée, prenons l'exemple suivant, où un registre architectural nommé R6 est utilisé pour stocker trois données consécutives. Il mémorise d'abord le nombre 255, puis le nombre 2567763, puis zéro. On suppose que ces trois valeurs sont indépendantes, dans le sens où elles sont utilisées par des instructions sans dépendances RAW. En théorie, on pourrait exécuter ces instructions séparément, mais ce n'est pas possible. Le fait est que l'on doit d'abord faire les calculs avec l'opérande 255, puis ceux avec l'opérande 2567763, puis ceux avec l'opérande zéro. La raison est que pour que le calcul démarre, il faut que l'opérande soit disponible. Et l’usage d'un seul registre pour stocker des opérandes différentes à des temps différents limite les possibilités d’exécution en parallèle.

Avec le renommage de registres, ces trois données sont enregistrées dans des registres physiques séparés, dès qu'elles sont disponibles. Le processeur garde évidemment trace du fait que ces trois registres physiques correspondent au registre architectural R6. Si les trois valeurs n'ont pas de dépendances entre elles, les instructions liées peuvent être exécutées dans le désordre et s’exécuter en même temps. Ce qui est le cas dans le schéma suivant, où certaines instructions sont exécutées en avance, ce qui réserve les registres physiques en avance.

Exemple où un registre architectural est utilisé pour contenir trois données successives.

Pour les connaisseurs, le renommage de registres réécrit le programme exécuté dans une représentation appelée SSA, utilisée par les compilateurs lors de la compilation. Et cette réécriture se fait un peu de la même manière avec un compilateur. Là où le compilateur change le nom des variables pour passer en forme SSA, le processeur change les noms de registres pour obtenir de l'assembleur SSA interne au processeur.

La durée de vie des registres virtuels

La plupart des processeurs disposent d'un banc de registre physique unique, qui regroupe registres physiques et virtuels. Mais il existe quelques processeurs qui font autrement. Ils ont un banc de registre pour les registres architecturaux, et les registres virtuels sont placés ailleurs dans le processeur, typiquement dans le tampon de ré-ordonnancement (ROB) ou la fenêtre d'instruction. Pour simplifier, considérons qu'ils sont dans un banc de registre spécialisé qui regroupe les registres virtuels. C'est un peu faux en soi, mais faisons comme si. Dans le reste de cette section, nous allons partir du principe que les registres virtuels et architecturaux sont séparés pour simplifier les explications, nous verrons les autres formes de renommage de registre plus tard.

Les registres virtuels ont une certaine durée de vie. On veut dire par là qu'une donnée écrite dans un registre virtuel y reste durant un certain temps, mais pas indéfiniment. Un registre virtuel est utilisé par une instruction en cours d'exécution dans le pipeline. Il nait lors du renommage de registre et meurt une fois l'instruction terminée. En clair, un registre virtuel dure durant toutes les étapes du pipeline qui suivent le renommage de registres. Une fois que l'instruction quitte le pipeline, qu'elle sort du ROB, le registre virtuel est inutile et doit laisser la place au registre architectural non-renommé.

Le résultat de l'instruction doit être transféré dans le registre architectural adéquat, le registre de destination de l'instruction. Si les registres virtuels et architecturaux sont séparés, il faut copier la donnée des registres virtuels vers les registres architecturaux. Utiliser un banc de registre unique résout le problème, mais n'allons pas trop vite, nous verrons cela en détail dans la suite. Toujours est-il qu'un registre virtuel est libéré quand l'instruction associée quitte le ROB.

Il est théoriquement possible de libérer un registre virtuel en avance, si on est certain qu'aucune instruction n'ira lire ce registre. Pour cela, le mieux est d'attribuer un compteur de lectures pour chaque registre. À noter que pour maintenir des exceptions précises, on est obligé d'attendre que la dernière instruction qui lit le registre ait validé. Le jeu n'en vaut clairement pas la chandelle. Le seul intérêt d'une telle optimisation est économiser des registres virtuels, d'avoir un banc de registres virtuels plus petits, mais cela se fait au prix de l'ajout de circuits qui consomment tout autant, si ce n'est plus de circuits, pour un résultat en termes de performances limité, voire nul.

Après avoir vu la mort des registres virtuels, voyons leur naissance. Le renommage de registre a lieu après le décodage, donc juste avant le passage dans le scoreboard, la fenêtre d’instruction, la file d'instruction ou toute autre structure dédiée à l'émission. En clair : les registres virtuels sont attribués juste avant émission et ne sont utiles qu'après. Les instructions susceptibles d'utiliser un registre virtuel sont donc les instructions émises ou prêtes à l'être, mais pas encore terminées. Les instructions en question sont soit en attente dans la fenêtre d’instruction, soit en cours d'exécution dans le chemin de données, soit en attente dans le ROB. Ces dernières attendent que les instructions précédentes se terminent.

Il faut noter que toutes les instructions émises ou en passe de l'être ont été ajoutées dans le ROB juste après le renommage. Même les instructions en attente dans la fenêtre d'instruction sont dans le ROB. Pour résumer, le ROB garde la trace de ces instructions prêtes à être émises ou déjà émises.

Le nombre idéal de registres virtuels

Mine de rien, le contenu de la section précédente nous donne une seconde borne maximale sur le nombre de registres virtuels utiles. Supposons que chaque instruction fournit un résultat, stocké dans un registre virtuel rien que pour lui. Le nombre maximal d'instructions chargées dans le pipeline après émission est égal au nombre d'entrée dans le ROB. Il peut y avoir moins d'instructions, ce qui fait que des entrées du ROB sont inutilisées, mais supposons que nous soyons dans le meilleur des cas. Dans ce cas, on doit avoir un registre virtuel par instruction, ce qui fait au maximum un registre virtuel par entrée du ROB. Rien ne sert d'avoir plus de registres virtuels que d'entrées dans le ROB, il n'y aura pas assez d’instructions dans le pipeline pour tous les utiliser.

Après avoir vu une borne maximale, voyons une limite minimale. Non pas qu'il faille absolument plus de registres virtuels que cette limite, simplement qu'il est préférable d'en avoir que cette limite. Partons du principe que les instructions pouvant utiliser un registre virtuel sont celles qui sont soit déjà émises, soit en attente de l'être. Si on néglige les instructions en attente dans le ROB, alors les instructions émises sont dans les ALUs. Le nombre d'instruction est donc égal à la somme de : la taille de la fenêtre d'instruction (instructions en attente), du nombre d'unités de calcul (instruction en cours d'exécution), unités d'accès mémoire inclues. Mieux vaut ne pas passer sous la somme taille de la fenêtre d'instruction + nombre d'unités de calcul.

Un bon compromis est d'avoir un nombre de registre virtuel compris entre ces deux bornes. Le nombre réel de registre virtuels est très souvent inférieur au nombre d'entrées du ROB, car toutes les instructions ne fournissent pas de résultat à enregistrer dans les registres. C'est le cas pour les instructions de branchement, par exemple, ou les écritures en mémoire RAM. Par contre, il vaut mieux avoir plus de registres que d'entrées dans la fenêtre d'instructions. La majorité es processeurs respectent ces deux limites basse et hautes, avec un nombre de registres réels entre les deux.

Les quelques rares exceptions étaient des processeurs qui implémentaient le renommage de registre pour la première fois, et où ce genre de détails n'étaient pas bien compris. Par exemple, on peut citer le PowerPC 604, qui avait 20 registres virtuels, alors que le ROB avait seulement 16 entrées. Les 4 registres virtuels en trop n'étaient pas utilisés. Le processeur qui a immédiatement suivi, le PowerPC 604, n'a pas fait cette erreur et a réduit le nombre de registres virtuels à seulement 16. Un autre exemple est le MIPS R10000, avec son ROB à 32 entrées, sa fenêtre d'instruction à 48 entrées et ses 64 registres virtuels. Le processeur suivant, le R12000, corrigea partiellement le problème en augmentant le ROB à 48 entrées, ce qui était insuffisant, mais bienvenu.

Le renommage de registre total et partiel

De nombreux processeurs ont des registres architecturaux séparés pour les nombres flottants et entiers. Dans ce cas, leur renommage est indépendant : on peut renommer les registres flottants à part des registres entiers. Mais les deux types de registres sont renommés à part. Sauf sur certains processeurs, qui ne renomment qu'un seul type de registres, pas l'autre !

Microarchitecture Zen 1 des CPU d'AMD.

Le renommage de registre peut être total ou partiel. Avec le renommage total, toutes les instructions voient leurs registres renommés. Il s'agit de la méthode la plus utilisée à ce jour, par simplicité de conception. Mais des processeurs assez anciens utilisaient un renommage partiel, qui ne s’appliquaient qu'à certains types d'instruction bien précis. Par exemple, seulement les instructions flottantes étaient renommées, seuls les registres flottants étaient renommés.

Comme exemple, on pourrait citer les processeurs Power1, Power2 et PowerPC 601. Sur le premier, seuls les registres flottants étaient renommés, et seulement pour les instructions de lecture flottante. La raison est que le processeur n'a qu'une seule FPU et ne peut donc pas exécuter des opérations flottantes dans le désordre sur celle-ci, ce qui fait que renommer les registres ne sert à rien. Le processeur Power 2 dispose lui de plusieurs FPU et le renommage de registres touche aussi les instructions flottantes arithmétiques. Dans un autre registre, le processeur Nx586 ne renommait que les registres entiers, pour les instructions entières.

Les processeur qui utilisaient le renommage partiel étaient des processeurs assez anciens, qui faisaient avec un budget en transistors limité. De plus, la technique n'était pas très bien maitrisée, et était encore balbutiante. La technique a pourtant été proposée dès 1970 dans divers articles académiques, et raffinée pendant les années 70. Mais le budget en transistors du renommage de registre a fait qu'elle n'a pas été utilisée avant que la loi de Moore fasse son œuvre.

Les différentes implémentations du renommage de registres

Dans l'implémentation la plus simple du renommage de registres, tous les registres physiques sont stockés dans un seul gros banc de registres, qui regroupe registres virtuels et architecturaux. Mais d'autres implémentations font totalement autrement, et séparent les registres virtuels et registres architecturaux. Voyons maintenant les différentes implémentations possibles du renommage de registres.

Mais avant toute chose, parlons du réseau de contournement. Pour simplifier les explications, appelons instruction productrice l'instruction qui fournit un résultat, et instruction consommatrice celle qui l'utilise comme opérande. Si une instruction consommatrice est chargée dans le pipeline quelques cycles après l'instruction productrice, les deux sont dans le pipeline en même temps. Dans ce cas, on pourrait penser que c'est le réseau de contournement qui gérerait le transfert du résultat de l'instruction productrice à l’instruction consommatrice. Et effectivement, c'est souvent le cas.

Mais les registres virtuels sont pris en compte dans le système de contournement. Si le résultat est écrit dans un registre virtuel, il peut aussi être lu dans ce registre virtuel. Lire un résultat dans les registres virtuels permet d'implémenter une forme de contournement. Tout cela pour dire qu'il peut y avoir un lien entre contournement et renommage de registres, les deux doivent être conçu de manière à communiquer entre eux. Typiquement, il y a toujours un réseau de contournement pour connecter la sortie d'une ALU aux entrées des autres. Ce dernier gère le cas où un résultat d’instruction est réutilisé comme opérande au cycle suivant. Mais pour réutiliser un résultat deux cycles après ou plus tard, c'est le système de renommage de registres qui s'en charge.

Le renommage à banc de registres physiques

Les processeurs modernes utilisent un seul banc de registres pour les registres architecturaux et virtuels, appelé banc de registres physiques (physical register file). Le tampon de réordonnancement et la fenêtre d'instruction contiennent des numéros de registres virtuels, des pointeurs vers les registres. Il y a toujours un réseau de contournement pour connecter la sortie d'une ALU aux entrées des autres, qui gère le cas où la sortie de l'ALU est utilisé comme opérande au cycle suivant. Mais pour réutiliser un résultat deux cycles après ou plus tard, c'est le banc de registres physiques qui s'en charge. Les opérandes viennent donc soit du banc de registres physique, soit du réseau de contournement.

Renommage à banc de registres physiques.

Avec ce système, un registre physique peut être dans quatre états.

• Le premier état est celui d'un registre disponible, près à servir de registre de destination. Par disponible, on veut dire que ce registre peut être réservé par l'unité de renommage, mais qu'il n'a pas encore été réservé. Ce n'est ni un registre virtuel, ni un registre architectural, juste un registre inutilisé.
• Le second état est l'état réservé, celui d'un registre virtuel qui attend qu'une instruction écrive son résultat dedans. L'état réservé réserve un registre en écriture, mais interdit les lectures dedans.
• Le troisième état est celui d'un registre virtuel dans lequel une instruction a écrit son résultat, mais l'instruction n'a pas encore quitté le ROB. Le registre est alors appelé un registre écrit.
• Enfin, le quatrième est celui d'un registre architectural, qui contient une donnée valide, dans le sens où il n'est associé à aucune instruction dans le ROB.

Un registre passe normalement par ces quatre états dans l'ordre disponible, virtuel réservé, virtuel écrit, architectural. Une fois que l'instruction attribuée quitte le ROB, le registre virtuel devient un registre architectural. Cependant, cela suppose que l'instruction quitte le ROB normalement, ce qui n'est pas le cas suite à une mauvaise prédiction de branchement ou autre. Dans ce cas, il repasse immédiatement à l'état disponible. L'unité de renommage des registre mémorise l'état de chaque registre pour savoir dans quel état il est.

Avec ce système, les données ne sont pas déplacées, ce qui a un avantage en termes de performance, de consommation énergétique et de simplification des circuits du processeur. Une fois enregistrées dans un registre, les données ne se déplacent plus. Avec un banc de registre virtuel séparé, elles sont recopiées d'un banc de registre virtuel vers un banc de registre architectural. Et les autres techniques que nous allons voir ont le même problème.

Un autre avantage est que les opérandes proviennent toutes du même endroit : le banc de registre unique. Avec un banc de registre séparés, les opérandes peuvent provenir soit des registres architecturaux, soit des registres virtuels. Les opérandes peuvent donc provenir du banc de registre architectural, mais aussi du banc de registre renommés. La conséquence est que la gestion des interconnexions est beaucoup plus compliquée, notamment quand on veut implémenter le contournement. Pas de problèmes de ce genre avec un banc de registre unique.

Le renommage dans le tampon de réordonnancement

Il est possible de faire le renommage dans le tampon de réordonnancement (ROB, pour ReOrder Buffer)). Cela veut dire que les résultats des instructions sont mémorisés dans le tampon de réordonnancement. Les entrées du ROB se voient ajouter un champ pour mémoriser le résultat d'une instruction, et ce champ sert de registre virtuel. Les entrées du ROB deviennent ainsi adressables, elle ont un numéro, qui sert de numéro/nom de registre virtuel.

Avec cette technique, les registres architecturaux sont séparés des registres virtuels inclus dans le ROB. Les registres architecturaux sont regroupés dans un banc de registres spécialisé, appelé le retirement register file. La fenêtre d'instruction mémorise soit un nom de registre architectural, soit l'adresse de l'entrée du ROB qui contient le résultat voulu. Quand une instruction a tous ses opérandes de prêts, ceux-ci sont lus depuis le ROB ou les registres architecturaux. Pour cela, le ROB mémorise l'état de chaque entrée, de chaque registre virtuel : vide, réservée pour un résultat, écrite avec un résultat.

Renommage dans le tampon de réordonnancement.

Un défaut est que cela complexifie l'implémentation des interconnexions par rapport à un banc de registre physique. Il y a toujours un réseau de contournement pour réutiliser un résultat un cycle plus tard. Mais pour réutiliser un résultat deux cycles après ou plus tard, c'est le ROB qui s'en charge. Les opérandes peuvent être lues depuis trois sources : le ROB, le banc de registre architectural, et le réseau de contournement. Soit une source de plus qu'avec la technique précédente, ce qui complexifie les multiplexeurs de contournement. Et cela a un effet sur la latence des opérations, le temps de traversée de ces multiplexeurs n'est pas gratuit, sans compter le temps mis pour les signaux de commande pour les configurer.

Le renommage de registre est aussi plus compliqué. Au lieu de simplement remplacer un numéro de registre architectural par un numéro de registre physique, on doit faire la différence entre numéro de registre et adresse dans le ROB, pour savoir où lire les opérandes. Sans quoi ne sait pas configurer les multiplexeurs et choisir la bonne source pour les opérandes.

Un autre défaut est que les registres virtuels doivent être copiés dans les registres architecturaux quand une instruction quitte le ROB. La copie se fait ici du ROB vers le banc de registre architectural. Et copier la donnée a un cout en énergie que l'usage d'un banc de registre unique n'a pas.

Un dernier défaut est que le nombre de registres virtuel est égal au nombre d'entrées dans le ROB. Or, on a vu plus haut que c'est un peu du gâchis, car beaucoup d'instructions ne produisent aucun résultat. Le hardware ajouté pour les entrées est donc sous-utilisé, il ne sert que si l'instruction fournit un résultat, mais ne sert à rien sinon.

Le renommage avec un tampon de renommage

Le dernier défaut évoqué dit que beaucoup d'entrées du ROB sont inutilisées et que les registres virtuels associés sont gâchés. Pour éviter cela, il est possible de sortir les résultats d'instruction du ROB et de les placer dans une mémoire FIFO complémentaire du ROB, appelée le tampon de renommage. Pour le dire autrement, le ROB amélioré est scindé en deux, avec le ROB proprement dit d'un côté, et un pseudo-ROB pour le renommage de registres et le contournement. Pour information, cette technique de renommage était utilisée dans d'anciens processeurs commerciaux, comme les Pentium Pro, le Pentium II, ou encore le Pentium III, ainsi que dans le Core 2 Duo.

La technique est souvent expliquée en décrivant le tampon de renommage comme un banc de registre séparé pour les registres virtuels, appelé le banc de registres renommés (rename register file). Il est séparé du banc de registres architecturaux, avec lequel il communique. La raison à cela est que le tampon de renommage est adressable alors que le ROB ne l'est pas. Il faut dire que le tampon de renommage a tout d'un banc de registre : il contient les registres virtuels et seulement ceux-ci, on peut l'adresser, lire des opérandes dedans, écrire des résultats dedans, etc. Par contre, il y a une différence avec un banc de registre normal : il est traité comme une mémoire FIFO. Nous avons déjà vu comment implémenter une FIFO avec un banc de registre et quelques registres, aussi je ne fais pas de rappels sur ce point.

S'il s'agissait d'un véritable banc de registre isolé, sans rien de plus, le ROB et la fenêtre d'instruction contiendraient des numéros de registres virtuels, qui adressent directement le banc de registre renommé. Une telle implémentation est possible, mais aucun processeur commercial n'a utilisé une telle implémentation. A la place, le banc de registre est en réalité une mémoire FIFO, dont les entrées sont adressables, avec de plus un système de cache utilisé pour faire la correspondance entre nom de registre architectural et nom de registre virtuel. Nous détaillerons ce dernier point dans la section qui explique comment fonctionne l'unité de renommage.

Une fois que l'instruction attribuée quitte le ROB, le registre virtuel est libéré, à savoir qu'il repasse en état disponible. C'est à ce moment qu'à lieu la copie de la donnée dans le registre architectural adéquat. Il faut noter que le registre virtuel n'est pas effacé, il contient toujours l'ancienne donnée. Mais ce n'est pas un problème. S'il est réservé par une instruction, elle écrira dedans, ce qui écrasera cette donnée. Et de manière générale, il est impossible de lire cette donnée, que ce soit si le registre est disponible ou réservé.

Renommage à banc de registres renommés.

La technique partage tous les défauts du renommage dans le ROB. Le réseau de contournement est plus compliqué car les opérandes peuvent venir de trois sources : les deux bancs de registres et le réseau de contournement. De plus, les registres virtuels doivent être copiés dans les registres architecturaux, avec tout ce que cela implique. Déjà, déplacer des données implique un cout en énergie et en consommation d'électricité, qu'il vaut mieux éviter. De plus, il faut ajouter un port de lecture sur le banc de registre renommés, pour copier un registre sans nuire aux performances. Le banc de registres physiques n'a pas à être modifié : le port d'écriture existant suffit pour la copie, vu qu'on n'écrit dedans que pour copier des résultats d'instructions validées/terminées.

Par contre, le cout en transistors est plus faible qu'avec le renommage dans le ROB, vu que le banc de registre a moins de registres virtuels que le ROB. La technique n'impose pas d'avoir autant de registres virtuels que d'entrées dans le ROB, ce qui permet d'en réduire le nombre. Par contre, comparé à l'usage d'un banc de registres unique, le cout en transistors est plus élevé. La différence se fait surtout au niveau des ports de lecture/écriture du banc de registres. La raison est que l'on doit ajouter un port de lecture pour copier les résultats dans les registres architecturaux. Du moins, dans le cas le plus simple. C'est le cas sur un processeur qui permet de compléter l'exécution d'une instruction par cycle. Mais certains processeurs peuvent terminer l'exécution de plusieurs instructions par cycle. C'est notamment le cas des processeurs dits superscalaires, qui sont capables de charger, exécuter et terminer plusieurs instructions par cycle. Ils auront droit à leur chapitre dédié, mais passons. Toujours est-il que si plusieurs instructions peuvent se terminer en même temps, il faut ajouter autant de ports de lecture sur le banc de registre pour copier leurs résultats.

Le renommage physique-virtuel

Les méthodes mentionnées au-dessus ont un léger problème : beaucoup de registres physiques sont gâchés, car attribués à une instruction dès l'étage de renommage et libérés lorsque on est certain qu'aucune instruction ne lira le registre physique attribué. Et parfois, les registres sont alloués trop tôt, alors qu'ils auraient pu rester libres durant encore quelques cycles. C'est notamment le cas quand l'instruction renommée attend un opérande dans la fenêtre d'instruction, ou quand le résultat est en cours de calcul dans l'unité de calcul. Ces situations ont toutes la même origine : le renommage a lieu tôt dans le pipeline, pour garder les dépendances entre instructions. Mais dans les faits, rien n'oblige à utiliser les registres architecturaux pour conserver les dépendances. On peut tout simplement attribuer un tag à chaque résultat d'instruction, tag qui ne correspond pas à un registre architectural. Et ce tag sera alloué à un registre architectural le plus tard possible, quand l'instruction fournira son résultat. Ce genre de méthodes a été formalisée avec ce qu'on appelle la technique du banc de registres physiques-virtuels (physical-virtual register file).

Cette méthode demande d'ajouter une seconde table de correspondance, qui fait le lien entre le tag et le registre physique. De plus, la table d’alias de registres doit être modifiée : elle ne doit pas seulement faire la correspondance entre le nom de registre et le tag, mais aussi avec le registre physique s'il est déjà attribué. Ainsi, lors du renommage en sortie du décodeur, on peut renommer l'instruction avec les registres physiques si ceux-ci sont connus lors du renommage, et renommer avec des tags dans le cas contraire. Il faut noter que cette méthode a un léger problème : quand une instruction termine et que le résultat doit se voir attribuer un tag, il se peut parfaitement qu'il n'y ait plus de registre physique de libre. Les solutions pour régler ce problème sont assez complexes, aussi je n'en parlerai pas ici.

L’unité de renommage

Pour commencer, sachez qu'il existe deux méthodes pour implémenter l'unité de renommage. La première utilise une unité à part, séparées, qui contient de nombreuses mémoires caches/FIFO pour stocker des informations nécessaires pour le renommage de registres. La seconde mémorise les informations de renommage dans le ROB ou le tampon de renommage, voir ailleurs. Les deux types d'unités de renommage sont assez différentes. Pour les désigner, je vais parler d'implémentation par tag et d'implémentation associative.

De plus, les deux types d'unités ne sont pas utilisées sur les mêmes implémentations. Par exemple, avec un banc de registre physique, il est naturel d'utiliser une implémentation par tag, l'autre implémentation n'est pas pratique. Aussi, tous les processeurs avec un banc de registre physique utilisent une unité de renommage pat tag. Mais pour le renommage dans le ROB, c'est l'inverse : les deux implémentations sont possibles, mais il est préférable d'utiliser une implémentation associative. Pour simplifier les explications, je vais commencer par décrire le premier type, avec un banc de registre physique.

	Implémentation par tag	Implémentation associative
Banc de registre physique	Seule implémentation possible
Renommage dans le ROB	Possible, certains processeurs utilisent la technique	Possible, certains processeurs utilisent la technique
Renommage dans un tampon de renommage	Possible, tous les processeurs utilisent la technique	Possible, aucun processeur connu

Les unités de renommage par tag

Les registres architecturaux sont identifiés par des noms de registre, tout comme les registres physiques. Les noms de registre des registres physiques sont appelés des tags. Les registres physiques sont bien plus nombreux que les registres architecturaux, sans quoi le renommage de registre n'a aucun intérêt. La conséquence est que les numéros de registres physiques sont plus grands que les numéros de registres architecturaux. Le renommage de registres remplace les noms/numéros de registres architecturaux par des numéros de registres physiques, par des tags. D'où le terme de renommage de registre. Ce remplacement est effectué dans un étage supplémentaire du pipeline, intercalé entre le décodage et l'émission.

Renommage de registres.

Le remplacement se fait cependant différemment pour le registre de destination et les registres d'opérandes. Le registre de destination est associé à un registre virtuel disponible. L'allocation du registre de destination prend un registre disponible et le place en état réservé. Une nouvelle correspondance entre registre architectural et virtuel est alors crée. Mais pour les opérandes, c'est autre chose. Les opérandes sont soit dans un registre architectural, soit dans un registre virtuel en état écrit. Les noms de registres architecturaux pour les opérandes doivent être remplacé par le nom de registre adéquat, déjà attribué. Une sacrée différence : on attribue un registre virtuel pour le résultat, les opérandes ont déjà un registre virtuel attribué.

Un autre point est que l'unité de renommage ne fait pas que modifier les registres opérande/de destination. Elle gère aussi la disponibilité des opérandes. Plus haut, on a dit qu'un registre virtuel pouvait être dans quatre états. Soit il est disponible, soit il est réservé, soit il est écrit, soit la donnée est dans un registre architectural. L'unité de renommage est au courant de l'état de chaque registre. Les quatre états possibles sont utilisés pour diverses raisons.

Et il y a deux manières pour mémoriser la correspondance entre un registre physique et un registre architectural. La première est d'utiliser un circuit à part, qui fait partie de l'unité de renommage, l'autre est d'intégrer les correspondances dans le ROB ou toute autre structure dédiée. Pr exemple, on peut ajouter la correspondance dans le ROB, dans la fenêtre d'instruction, éventuellement dans le banc de registres renommés ! Dans ce qui suit, nous allons parler du cas où on utilise une mémoire à part, partie intégrante de l'unité de renommage de registre. Nous verrons l'intégration dans le ROB après, de même que la relation avec les quatre techniques précédentes.

Renommer le registre de destination : la liste de disponibilité

Renommer le registre de destination de l'instruction demande juste de de lister tous les registres disponibles. Pour renommer un registre de destination, il suffit de lui attribuer un registre virtuel inutilisé. Pour cela, certaines techniques de renommage de registres mémorisent la liste des registres disponibles dans une petite mémoire : la liste de disponibilités (free list). L'implémentation de la liste de disponibilité varie grandement d'un processeur à l'autre. Avec certaines méthodes de renommage de registre, qui impliquent un ROB, on peut même s'en passer totalement.

Dans sa version la plus simple, elle contient un bit pour chaque registre, qui indique s'il est disponible ou non. Le bit en question est mis à jour quand une instruction entre/quitte le tampon de réordonnancement avec ce registre comme opérande. Lorsqu'un registre est attribué, il quitte la liste de disponibilités. Lorsque son instruction quitte le ROB, le bit de disponibilité est mis à jour. Une version plus évoluée utilise une mémoire FIFO qui contient des noms de registres. Le renommage du registre de destination utilise cette FIFO pour sortir le numéro de registre virtuel adéquat. Dans la suite, nous partirons du principe que c'est cette méthode qui est utilisée.

Il faut noter que si le renommage est fait dans le ROB, la liste de disponibilité est inutile. La raison est que le ROB est déjà une mémoire FIFO, comme la liste de disponibilité. De plus, les registres virtuels sont dans le ROB. Attribuer un registre virtuel consiste simplement à mobiliser une entrée vide du ROB, en enfilant l'instruction dedans. Le ROB sait quelle est la prochaine entrée à allouer à une instruction émise, du fait de son caractère FIFO.

La table de correspondances de registres

Le renommage du registre de destination attribue un registre virtuel pour un résultat d'instruction. Reste qu'il faut maintenir cette attribution tant que l'instruction ne s'est pas terminée. Pendant toute la durée de vie de l'instruction, il faut se souvenir que tel registre virtuel correspond à tel résultat d'instruction, mais aussi à tel registre architectural. En effet, les instructions suivantes vont lire ce résultat pour l'utiliser comme opérande. Elle encoderont ce résultat/opérande avec le registre architectural censé contenir l'opérande. Le renommage de registre devra alors remplacer les registres opérande par le registre virtuel adéquat, qui contient l'opérande.

Le renommage des registres opérande est le rôle de la table d’alias de registres (register alias table), une mémoire qui contient le registre virtuel associé à chaque registre architectural. Elle mémorise précisément une table de correspondance entre registre architectural et registre virtuel/physique. La table d'alias contient une correspondance par registre architectural, qui change au gré du renommage des instruction. De plus, elle contient un bit qui indique si le registre a été renommé ou non. S'il n'a pas été renommé, alors l'opérande est disponible dans les registres architecturaux, pas dans un registre virtuel. C'est très utile sur les processeurs avec un banc de registre séparés pour les registres architecturaux. Cela permet de savoir où lire les opérandes.

La correspondance en question est mise à jour quand une instruction est émise, et quand elle termine. Premièrement, elle est mise à jour à chaque fois qu'un registre de destination est renommé. En clair, la table d’alias de registres est mise à jour à chaque lecture dans la table de disponibilité. Le registre virtuel choisi dans la liste de disponibilités est attribué au registre architectural de destination du résultat. Il suffira de réutiliser cette correspondance par la suite.

Deuxièmement, elle est mise à jour quand une instruction termine, quand elle quitte le ROB. Le ROB envoie alors le numéro du registre virtuel qui contenait le résultat enregistré dans les registres architecturaux. Le numéro est alors enregistré dans la table de disponibilité. De plus, la correspondance associée dans la table d'alias est effacée.

Unité de renommage de registres.

Il existe deux façons pour implémenter la table d'alias. La plus ancienne consiste à utiliser une mémoire associative dont le tag contient le nom du registre architectural et la donnée le nom du registre physique. Sur les processeurs plus récents, on utilise une mémoire RAM, dont les adresses correspondent aux noms de registres architecturaux, et dont le contenu d'une adresse correspond au nom du registre physique associé. On n'a alors qu'une seule correspondance entre registre physique et registre architectural, mais cela ne pose pas de problème si on renomme les instructions dans l'ordre d'émission (ce qui est toujours fait). Notons que la table l'alias doit avoir deux ports de lecture : un pour chaque opérande. Et cela vaut peu importe son implémentation : le cache comme la RAM doivent avoir deux ports.

L'interaction entre renommage de registres et autres optimisations

L'unité de renommage de registre ne fait pas que du renommage de registre, mais joue aussi un rôle dans l'exécution dans le désordre, et prend en charge des rôles annexes à son rôle principal. Par exemple, elle est impliquée pour corriger les mauvaises prédiction de branchement, les exceptions matérielle ou toute situation qui demande de vider le pipeline. En dehors de ces situations, un registre passe normalement par ces quatre état dans l'ordre disponible, réservé, écrit, architectural. Mais ce n'est pas le cas lors d'une mauvaise prédiction de branchement ou autre. Dans ce cas, tous les registres passent immédiatement à l'état disponible, sauf les registres architecturaux.

La récupération après une prédiction invalide

Quand une exception ou une mauvaise prédiction de branchement a lieu, les registres virtuels contiennent des données potentiellement invalides, contrairement aux registres architecturaux. En cas de mauvaise prédiction de branchement, la table d’alias de registres est partiellement vidée. Par vidée, on veut dire qu'on élimine les correspondances avec les registres virtuels invalidés. De plus, on doit remettre la table d’alias de registres et la table de disponibilités dans l'état antérieur au chargement de l'instruction qui a déclenché la mauvaise prédiction de branchement ou l'exception matérielle. Et cela peut se faire de différentes manières.

La première solution s'applique au renommage dans le ROB. Il suffit de stocker dans le tampon de réordonnancement ce qui a été modifié dans l'unité de renommage de registres par l'instruction correspondante. Ainsi, lorsqu'une instruction sera prête à valider, et qu'une exception ou mauvaise prédiction de branchement aura eu lieu, les modifications effectuées dans l'unité de renommage de registres seront annulées les unes après les autres.

Une autre solution consiste à garder un historique des changements fait dans la table d'alias. Lorsqu'une mauvais prédiction est détectée, le processeur traverse l'historique et annule les changements faits un par un. Le tout est assez lent, vu que la traversée se fait un renommage à la fois. Une optimisation utilise une copie valide de la table d’alias de registres dans une mémoire à part, pour la restaurer au besoin. Si jamais le processeur détecte un branchement, la table d’alias de registres est sauvegardée dans une mémoire intégrée au processeur. On peut utiliser plusieurs mémoires de sauvegarde de ce type, pour gérer une succession de branchements.

La gestion des opérandes disponibles : "lecture avant émission" et "lecture après émission"

Passons maintenant à un détail d'implémentation de l'exécution dans le désordre. La lecture après émission utilise des fenêtres d'instruction proprement dit, alors que la lecture avant émission utilise des stations de réservation. Rappelons que la différence est que les premières émettent les instruction puis lisent les registres, alors que la seconde lit les opérandes depuis les registres juste après le renommage de registre, pour les stocker dans la fenêtre d'instruction. La différence est donc que les étages sont répartis différemment. Avec la "lecture avant émission", l'étage de lecture des opérandes est placé entre l'étage de renommage de registres et l'étage d'émission. Avec la "lecture après émission", l'étage de lecture des registres est situé après l'étage d'émission/select/wakeup.

Les deux méthodes de lecture avant ou après émission montrent une grande différence pour ce qui est de déterminer la disponibilité des opérandes. Pour la lecture après émission, le renommage de registre n'est pas impliqué. Mais avec la lecture avant émission, les opérandes sont lues dans les registres entre le renommage des registres et l'entrée dans la station de réservation. Ce qui implique qu'on sait quelles sont les opérandes disponibles lors du renommage de registres. Pour cela, l'unité de renommage de registre contient, pour chaque registre virtuel, un bit ready qui indique que le registre renommé contient une opérande est disponible. S'il est à 0, l'instruction est placée dans la fenêtre d'instruction, et attend que ses opérandes soient disponibles. S'il est à 1, les opérandes sont soit lues dans le registre et placées dans la fenêtre d'instruction, soit lues au moment d'exécuter l'instruction.

L'ensemble de ces bits est en plus des bits de disponibilité de la station de réservation, dans l'implémentation la plus simple. Les deux sont alors mis à jour en même temps. Une autre solution regroupe les bits de disponibilité dans une structure matérielle appelée la table de disponibilité, qui est consultée à la fois par les stations de réservation et l'unité de renommage de registres. L'avantage de cette solution est que les signaux de réveil sont envoyés à une seule structure matérielle, pas plus. De plus, il n'y a pas de duplication des bits de disponibilité. Non pas que quelques bits fassent une grosse différence, mais tout est bon à prendre.

Notons qu'avec un banc de registres physique, le bit de disponibilité se déduit des quatre états que peut prendre un registre physique. L'unité de renommage de registre doit sait déjà quelles sont les opérandes indisponibles, celles qui ont déjà été calculées, et celles enregistrées dans un registre architectural. Notons qu'un registre virtuel, une fois attribué, peut être en état réservé ou écrit. Seul l'état écrit correspond à une opérande disponible, l'unité de renommage doit donc pouvoir faire la différence. Pour savoir si un registre virtuel contient une donnée valide, la table d’alias de registres lui associe un bit de validité qui est mis à jour lors de l'écriture du résultat dans le registre virtuel correspondant. Elle doit aussi mémoriser quels registres architecturaux ont une donnée valide.

Rappelons que le processeur sait qu'une opérande est disponible parce qu'un signal de réveil est généré dans le pipeline, pour dire que telle opérande est disponible. Le signal transmet l'opérande avec le numéro de registre (virtuel ici). Le numéro de registre transmis est alors comparé avec tous les numéros de registre des opérandes, dans la fenêtre d'instruction et/ou les stations de réservation. Il est possible qu'une instruction soit dans l'étape de renommage alors que le signal de réveil est envoyé. Si rien n'est fait, l'instruction sera insérée dans la fenêtre d'instruction avec une opérande indisponible, alors qu'elle l'est. Elle restera alors indéfiniment dans la fenêtre d'instruction, vu que le signal de réveil n'est généré qu'une seule fois.

Pour éviter cela, le signal de réveil doit aussi être envoyé aux instructions dans l'unité de renommage de registre. Une solution pour éviter cela est d'enregistrer directement les noms de registres renommés dans la fenêtre d'instruction, dès la sortie de l'unité de renommage. Les noms de registres sautent un étage de pipeline, donc. La comparaison avec les signaux de réveil se fait alors dans la fenêtre d'instruction, pas besoin de rajouter un comparateur dans l'étage de lecture des registres. Une autre solution est d'utiliser une table de disponibilité unique. Les signaux de réveil ne sont alors pas perdus.

Les optimisations liées au renommage de registres

Le renommage de registre permet d'implémenter certaines optimisations annexes, qu'on ne croirait pas reliées au renommage de registre au premier abord. Par exemple, saviez-vous que le renommage de registre permet d'exécuter certaines instructions directement dans l'unité de renommage ? De nombreuses optimisations éliminent certaines instructions, en les remplaçant par des renommages de registres. Il existe plusieurs optimisations de ce genre, qui portent les noms barbabres d'élimination des MOV, de calcul trivial, et de remplacement d'idiomes.

L'élimination des MOV

La première optimisation de ce genre élimine les instructions de copie d'un registre dans un autre (les MOV) ou d’échange entre deux registres (XCHG). Ce qui explique pourquoi l'optimisation en question porte le nom d'élimination des MOV (MOV elimination), sous-entendu, des MOV inter-regsitres.

L'élimination des MOV est une technique implémenté sur les processeurs à banc de registre physique. En clair, il faut qu'il y ait un seul banc de registre. C'est important, car c'est la seule méthode qui fait que les registres virtuels n'ont pas à être copiés dans les registres architecturaux, ce qui facilite grandement l'implémentation d’une technique visant à éliminer des copies de registres. L'idée est qu'après une copie, le contenu des deux registres source et destination est identique tant qu'aucun des deux registres ne subit d'écriture. On peut alors utiliser un seul registre physique pour la valeur mémorisée, toute lecture des deux registres lisant celui-ci. Lors d'une écriture dans un de ces deux registres, le renommage attribuera un nouveau registre physique pour la nouvelle valeur écrite.

Formellement, il s'agit d'une optimisation de type copy-on-write.

Le remplacement d'idiomes

Le même genre d'optimisation peut être effectué avec des instructions inutiles, dont le résultat vaut zéro. En effet, il existe de nombreuses méthodes pour mettre un registre à zéro. Faire un XOR entre le registre et lui-même, le soustraire à lui-même ou le multiplier par zéro sont quelques exemples. Et de tels idiomes sont utilisés par les compilateurs, au lieu d'un simple MOV 0 -> registre, qui copie un 0 dans le registre. La raison est que les instructions MOV sont assez longues, vu qu'elles doivent intégrer une constante immédiate.

Le renommage de registres peut être utilisé pour éliminer ces opérations et les remplacer par une mise à zéro du registre. L'optimisation en question porte le nom de remplacement d'idiomes. Elle est implémentée depuis les processeurs Pentium de microarchitecture P6, et leurs équivalents AMD.

Un autre avantage de cette optimisation est que cela casse de fausses chaines de dépendances. Par exemple, une opération "reg XOR reg" faire croire au processeur qu'il y a une dépendance de donnée entre cette instruction, et les instructions précédente qui écrivent dans le registre. Le XOR est donc exécuté après ces instructions faussement dépendantes, alors que la mise à zéro du registre pourrait se faire en parallèle en utilisant un registre virtuel séparé. Les techniques précédentes permettent d'éliminer ces fausses dépendances.

Les optimisations de calculs triviaux

Il existe aussi des opérations dont le résultat est une des opérandes. On pourrait citer comme exemples les décalages par 0, les additions et soustractions avec 0, la multiplication par 1, et bien d'autres. En utilisant intelligemment le renommage de registres, ces calculs ne sont pas effectués. Les techniques qui permettent cela sont des techniques dites de calcul trivial (trivial computation).

La détection des calculs simplifiables demande de comparer les opérandes avec 0 ou 1, via un paquets de comparateurs regroupés dans une unité de détection des calculs triviaux. Leur simplification se fait dans la table de renommage de registres, le registre de destination de l'instruction simplifiée étant renommé pour pointer sur l'opérande/résultat. Si le résultat est nul, on considère que la correspondance est invalide et on met le registre physique à une valeur invalide, similaire au pointeur NULL du C. Si un calcul lit un registre physique invalide, celui-ci est automatiquement simplifié par l'unité de renommage, l'autre opérande étant alors attribué automatiquement comme registre de destination du résultat dans la table de renommage.

Mais cette technique a tendance à modifier la latence des instructions, qui est réduite après simplification. Cela pose problème au niveau des circuits d'émission et du planificateur, qui n'aiment pas les latences variables, comme on l'a vu il y a quelques chapitres.