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.

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. 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. On a besoin non seulement de nos registres architecturaux, mais aussi de registres supplémentaires cachés, adressables. Il faut ainsi faire la distinction entre :

• registres architecturaux, définis par l'architecture extérieure du processeur, mais fictifs avec le renommage de registres ;
• registres physiques, réellement présents dans notre processeur, bien plus nombreux que les registres architecturaux.

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.

L’unité de renommage

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. Vu qu'il y a plus de registres physiques que de registres architecturaux, le tag d'un registre physique est plus grand que le nom d'un registre architectural. Pour attribuer un registre architectural à un registre physique, il suffit de remplacer le nom du registre architectural par le tag du registre physique attribué. Ce remplacement est effectué dans un étage supplémentaire du pipeline, intercalé entre le décodage et l'émission.

Renommage de registres.

La table de correspondances de registres

Le remplacement "nom de registre -> tag" est effectué par un circuit spécialisé, la table de correspondance de registres (register map table). Il existe deux façons pour l'implémenter. 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).

Le renommage de registres permet à plusieurs registres physiques de devenir le même registre architectural. Chaque donnée présente dans un registre étant forcément le résultat d'une écriture dans un registre, il suffit de rediriger les écritures dans un nouveau registre à chaque fois. Il faut aussi faire la correspondance entre chaque registre physique et le registre architectural associé. Cela fait donc deux fonctions distinctes : rediriger les écritures dans un registre physique vide, et faire la correspondance entre registres physiques et architectural. Les deux fonctions sont prises en charge par deux circuits distincts. Le premier renomme les registres de destination, ceux dans lesquels on enregistre les résultats des instructions. Le second renomme les registres sources, qui contiennent les opérandes. Il se peut que les deux circuits soient fusionnés en un seul, mais ils sont conceptuellement distincts.

Pour renommer un registre de destination, il suffit de lui attribuer un registre virtuel inutilisé. La liste des registres vides est mémorisée dans une petite mémoire : la liste de disponibilités (free list). Lorsqu'un registre virtuel n'est plus utilisé par les prochaines instructions, il passe dans la liste de disponibilités. Lorsqu'un registre est attribué, il quitte la liste de disponibilités. Détecter les registres réutilisables est assez complexe et peut se faire de plusieurs façons, suivant le nombre d'instructions démarrées simultanément. Une solution attribue un compteur à chaque registre, qui est incrémenté/décrémenté quand une instruction entre/quitte le tampon de réordonnancement avec ce registre comme opérande.

Renommer les registres sources 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. Cette correspondance est mise à jour à chaque fois qu'un registre vide est réquisitionné pour servir de registre de destination pour une instruction. À ce moment, la table d’alias de registres est mise à jour. 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. Cependant, le résultat ne sera disponible qu'après avoir été calculé. C'est seulement à ce moment-là que le registre virtuel contiendra une donnée valide et sera utilisable par d'autres instructions. Pour savoir si un registre 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.

Unité de renommage de registres.

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.

On peut 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 une copie valide de la table d’alias de registres dans une mémoire à part, pour la restaurer au besoin. Par exemple, si jamais notre table d’alias de registres détecte un branchement, son contenu est sauvegardé 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.

Les différentes implémentations du renommage de registres

Dans l'implémentation la plus simple du renommage de registres, tous les registres virtuels sont stockés dans un seul gros banc de registres et il n'y a pas de registres architecturaux proprement dit. Cette méthode n'est ni plus ni moins que la technique du scoreboarding, vue au chapitre précédent, améliorée sur deux points : on ajoute un étage de renommage des registres et on augmente la taille du banc de registres. D'autres techniques utilisent des registres virtuels et architecturaux séparés. Chaque registre virtuel contiendra une valeur temporaire, destinée à être recopiée dans un registre architectural après un certain temps. Pour faire simple, une fois qu'un registre virtuel devient inutile, une fois les dépendances résolues, on copie le registre architectural correspondant.

Le renommage avec un banc de registres renommés

Certains processeurs utilisent un banc de registres pour les registres architecturaux, et un autre pour les registres virtuels : ce dernier est appelé le banc de registres renommés (rename register file), tandis que le premier est appelé le banc de registres architecturaux (retirement register file). Quand le tampon de réordonnancement veut écrire une donnée dans les registres architecturaux, il doit lire le résultat à écrire depuis le banc de registres renommés. Pareil pour le chargement d'une donnée dans les stations de réservation, qui a lieu depuis ce dernier.

Renommage à banc de registres renommés.

Le renommage dans le tampon de réordonnancement

Certains processeurs font le renommage dans le tampon de réordonnancement. Vu que le résultat de l’opération est mémorisé dans le tampon de réordonnancement, l'entrée correspondante peut servir de registre virtuel. Chaque entrée devient ainsi adressable. Avec cette technique, les stations de réservation ne mémorisent pas un nom de registre architectural, mais l'adresse de l'entrée du tampon de réordonnancement qui contient le résultat voulu. Quand une instruction a tous ses opérandes de prêts, ceux-ci sont lus depuis le tampon de réordonnancement (ou depuis la mémoire, en cas de mauvaise prédiction de branchement).

Renommage dans le tampon de réordonnancement.

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. Il arrive que certains processeurs fusionnent le tampon de réordonnancement et les stations de réservation dans un seul circuit.

Le renommage dans les stations de réservation

Certains processeurs renomment les registres dans les stations de réservation, chaque champ opérande d'une entrée servant de registre virtuel. Les noms de registre de l'entrée sont modifiés de manière à mémoriser des noms de registres virtuels, des tags.

Entrée d'une station de réservation.

La sortie des unités de calcul est reliée aux entrées des stations de réservation via un bus, le bus commun d’ordonnancement de la mémoire (common memory-ordering bus). Ce bus transmet à la fois la donnée aux entrées, mais aussi le nom du registre de destination, histoire de détecter les dépendances RAW.

Algorithme de Tomasulo.

Pour faciliter l'arbitrage de ce bus, une seule unité de calcul peut envoyer des données sur ce bus. Les autres doivent mettre en attente leurs résultats dans une mémoire tampon, soit un registre, soit une FIFO. Cette mémoire est appelée un producteur (producer).

Producteurs en sortie d'une ALU.

Le renommage dans la fenêtre d’instruction

Certains processeurs renomment les registres dans la fenêtre d'instruction, chaque entrée de celle-ci servant de registre virtuel. Les entrées doivent toutefois être adaptées, afin de stocker les opérandes de l'instruction à stocker, en plus de l'opcode, des noms de registres, des bits de présence, etc. Le mécanisme de détection des dépendances doit aussi être adapté afin de relier les entrées au bus commun d’ordonnancement de la mémoire : sans cela, les résultats d'un calcul ne peuvent pas être contournés jusqu'aux entrées dans la fenêtre d'instruction.

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). Les raisons à cela sont multiples. Premièrement, cette méthode ne fait pas de copies entre un banc de registres renommés et un banc de registres architecturaux, ce qui a un avantage en termes de performance, de consommation énergétique et de simplification des circuits du processeur. Et c'est sans compter que le tampon de réordonnancement et les stations de réservation contiennent des pointeurs vers nos registres, ce qui prend moins de place que stocker directement les données.

Libérer un registre est cependant plus complexe : on ne peut le faire que lorsqu'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é.

Renommage à banc de registres physiques.

Un autre avantage est certaines opérations deviennent inutiles grâce à certaines optimisations. Il s'agit des instructions de copie d'un registre dans un autre (les MOV) ou d’échange entre deux registres (XCHG). Après une copie, le contenu des deux registres 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.

Le même genre d'optimisation peut être effectué avec des instructions inutiles, dont le résultat vaut soit zéro, soit un des opérandes. On pourrait citer comme exemples les décalages par 0, les additions et soustractions avec 0, la multiplication par 0 ou 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. S 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 instruction, 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.

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.