Fonctionnement d'un ordinateur/Le renommage de registres

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

Pour améliorer l'exécution dans le désordre, les concepteurs d'ordinateurs 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 sont des dépendances contre lesquelles on ne peut rien faire : ce sont de « vraies » dépendances de données. Quelle que soit la situation, ces dépendances imposent un certain ordre d’exécution de nos instructions. Mais les dépendances write after write et write after read sont de fausses dépendances. Elles proviennent du fait que deux instructions doivent se partager le même registre ou la même adresse mémoire, 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, les deux instructions utilisent le même registre pour stocker des données différentes en même temps. Manque de chance, un registre ne peut contenir qu'une seule donnée, et l'une des deux sera perdue. Une solution simple vient alors à l'esprit : conserver les différentes versions d'un même registre dans plusieurs registres séparés, et choisir le registre adéquat à l'utilisation. À chaque fois qu'on veut écrire, l'écriture est redirigée vers un autre registre. Et toutes les lectures vers cette version du registre sont redirigées vers ce registre supplémentaire. Une fois qu'une donnée, une version d'un registre, devient inutile, le registre devient réutilisable. On voit bien qu'un seul registre architectural correspondra en réalité à plusieurs registres, chacun contenant le résultat d'une écriture. 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.

Le renommage de registres permet à deux registres physiques de devenir le même registre architectural. Le scoreboarding vu au chapitre précédent ne gère pas le renommage de registres. On peut toutefois adapter celui-ci, en augmentant la taille du banc de registres, et en ajoutant un étage chargé d'effectuer le renommage des registres après les unités de décodage. Avec cette technique, tous les registres virtuels sont stockés dans un seul gros banc de registres, et il n'y a pas de registres architecturaux. Les 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.

L’unité de renommage[modifier | modifier le wikicode]

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. Pour attribuer un registre architectural à un registre physique, il suffit de remplacer le nom du registre architectural par le tag du registre physique attribué : le registre architectural est renommé. 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. Ce remplacement est effectué dans un étage supplémentaire du pipeline, intercalé entre le décodage et l'émission.

Renommage de registres.

Table de correspondances de registres[modifier | modifier le wikicode]

Ce remplacement 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). Ce circuit est conceptuellement divisé en deux gros sous-circuits, qui sont parfois fusionnés en un seul, mais on fera comme si dans les explications qui vont suivre.

Lorsqu'on attribue un nouveau registre virtuel pour un registre architectural, on doit prendre un registre virtuel inutilisé. La table de correspondances de registres doit donc connaitre la liste des registres vides dans une petite mémoire : la liste de disponibilités (free list). Lorsqu'un registre virtuel n'est plus utilisé par les prochaines instructions, on peut réutiliser le registre comme bon nous semble : il passe alors 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 consiste à attribuer un compteur à chaque registre : ce compteur est incrémenté/décrémenté quand une instruction entre/quitte le tampon de réordonnancement avec ce registre comme opérande.

Maintenant que l'on a réussit à renommer les registres de destination de notre instruction avec la liste de disponibilités, on doit renommer les registres sources, qui contiennent les opérandes. C'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 pas immédiatement disponible pour notre instruction. Il ne le sera qu'après avoir été calculé. C'est seulement à ce moment-là que notre registre virtuel contiendra une donnée valide et sera utilisable par d'autres instructions. Pour savoir si notre registre contient une donnée valide, la table d’alias de registres contient un bit de validité pour chaque registre architectural. Ce bit de validité est mis à jour lors de l'écriture du résultat dans le registre virtuel correspondant.

Récupération après une prédiction[modifier | modifier le wikicode]

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 : on n'a strictement aucune correspondance entre le registre architectural et un registre virtuel invalidé par la prédiction de branchement. 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.

Fichier de registres renommés[modifier | modifier le wikicode]

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). Tampons de réordonnancement et stations de réservation contiennent des noms de registres virtuels ou réels qui contiennent la donnée. 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.

Tampon de réordonnancement[modifier | modifier le wikicode]

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). 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.

Renommage dans le tampon de réordonnancement.

Renommage dans les stations de réservation[modifier | modifier le wikicode]

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.

Fenêtres d’instruction[modifier | modifier le wikicode]

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.

Banc de registres physiques[modifier | modifier le wikicode]

On peut aussi utiliser un seul banc de registres pour les registres architecturaux et virtuels : c'est un banc de registres physiques (physical register file). Aujourd'hui, presque tous les processeurs utilisent ce genre de structure pour faire du renommage de registres, pour plusieurs raisons. Premièrement, cette méthode est économe en énergie. Il faut dire qu'elle ne demande pas de copier des registres entre un banc de registres renommés et un banc de registres architecturaux, ce qui a en outre un avantage en terme de performance ou 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 si le renommage de registres implémente 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 la copie de notre registre dans un autre, le contenu des deux registres est identique tant qu'aucun des deux registre ne subit d'écriture. On peut alors utiliser un seul registre physique pour la valeur recopiée et l'original, toute lecture de ces deux valeurs lisant celui-ci. Lors d'une écriture dans un de ces deux registres, il suffira d'utiliser un registre physique vide pour stocker la donnée à écrire et l'associer avec le nom de ce registre.

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 peut remarquer que ces calculs correspondent dans la plupart des cas à des calculs dont un opérande vaut 0 ou 1 : des 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, on peut faire en sorte que ces calculs ne soient 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.

Renommage physique-virtuel[modifier | modifier le wikicode]

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.