Fonctionnement d'un ordinateur/Le scoreboarding et l'algorithme de Tomasulo

Dans ce chapitre, nous allons voir deux techniques d'exécution dans le désordre un peu à part. Il s'agit de deux techniques historiques appelées le scoreboarding et l'algorithme de Tomasulo. Les deux ne sont plus utilisés aujourd'hui, pour plusieurs raisons. La première est que ces technique ne gèrent pas les exceptions précises, ce qui fait qu'on ne peut pas les utiliser en même temps que la prédiction de branchement. Il est possible de les modifier pour leur adjoindre un ROB, mais le résultat est quelque peu complexes, surtout que le résultat ressemble beaucoup aux techniques de renommage dans le ROB.

L'algorithme de Tomasulo et les stations de réservation

L'algorithme de Tomasulo est un algorithme assez compliqué à expliquer, car il mélange exécution dans le désordre, contournement et renommage de registre implicite en un seul algorithme. L'algorithme de Tosmasulo a été implémenté une première fois sur les ordinateurs IBM 360/91, et quelques processeurs ont utilisé une variante de celui-ci. Beaucoup de processeurs modernes se sont sont inspiré de cet algorithme pour leur design. Il est antérieur au scoreboarding du CDC 6600, qui avait des fonctionnalités similaires, mais nous allons le voir avant, afin de mieux faire ressortir les ressemblances entre les deux algorithmes.

Avec l'algorithme de Tomasulo, le renommage de registre se fait dans des stations de réservation, des fenêtres d'instructions, associée chacune à une unité de calcul, modifiées de manière à faciliter le contournement. Dans son acceptation la plus stricte, le terme station de réservation est réservé au cas où il y a une station de réservation par unité de calcul. L'algorithme de Tomasulo initial a été décrit pour un processeur avec trois stations de réservation : une pour le circuit multiplieur/diviseur flottant, une pour l'additionneur flottant, et une pour l'unité LOAD/STORE. Précisons cependant que le terme de station de réservation a été élargit par la suite pour désigner toute fenêtre d'instruction capable de mémoriser les opérandes, peu importe qu'elle soit liée à une seule ou plusieurs ALUs, peu importe que la fenêtre d'instruction soit centralisée ou décentralisée. D'ailleurs, c'est l'usage que je fais de ce terme dans ce cours/wikilivre. Précisons aussi que le terme a été utilisé n'importe comment et beaucoup l'ont utilisé comme synonyme de fenêtre d'instruction, sans doute pour des raisons historiques.

Un autre point très important est que, dans le papier de Tomasulo, les stations de réservation ne conservent que les instructions en attente d'émission. L'algorithme original n'avait pas de ROB et ne gérait pas du tout les exceptions précises. Il ne peut donc pas être utilisé sur les architectures modernes, qui utilisent de la prédiction de branchement. Il est possible d'ajouter un ROB à l'algorithme, mais il doit être modifié et on retombe alors sur une forme de renommage dans le ROB.

Les stations de réservation et le contournement

Les stations de réservation mémorisent les instructions en attente d'exécution sur l'unité de calcul, tant qu'elles n'ont pas encore leurs opérandes prêtes. Par modifiées pour faciliter le contournement, je veux dire par là qu'elles mémorisent les opérandes d'une instruction à exécuter. Si les opérandes sont dans les registres, elles sont lues depuis les registres avant issue/dispatch, et mémorisées dans la station de réservation. Si elles ne sont pas encore disponibles au moment de l'issue, elles seront fournies plus tard par le système de contournement et seront alors enregistrées dans la station de réservation. Le fait que la fenêtre d'instruction incorpore les opérandes de l'instruction implique une forme de renommage d'instruction implicite, comme on le verra plus tard.

Il s'agit d'une technique dite de lecture avant émission, qui lit les registres d'une instruction avant de l'émettre. C'est la première fois dans ce cours que nous voyons une telle technique, qui n'est en rien une optimisation. Toutes les techniques d'exécution dans le désordre précédentes émettaient les instructions avant de lire les registres. Un désavantage de la lecture avant émission est qu'il faut stocker les opérandes après lecture, ici dans les stations de réservation. Mais un avantage est que le banc de registre a besoin de moins de ports de lecture, car une bonne partie des opérandes sont fournies par le système de contournement.

Pour gérer le contournement, les résultats d'une instruction sont non seulement envoyés vers le ROB et/ou les registres, mais ils sont aussi envoyés vers les stations de réservation, via un bus de contournement. La sortie de chaque unité de calcul est connectée à toutes les stations de réservation, dans le cas idéal. Pour cela, la sortie des unités de calcul est reliée aux stations de réservation via un bus, appelé le bus commun d’ordonnancement de la mémoire (common memory-ordering bus), que nous nommerons dorénavant bus de contournement.

L'idée derrière le bus de contournement est que les sorties des unités de calcul sont reliées à un bus, qui est lui connecté aux entrées des ALU. La contrainte est qu'une seule unité de calcul peut envoyer des données sur ce bus. Rien d'étonnant : c'est un bus, il ne peut transférer qu'une donnée à la fois. Si plusieurs unités de calcul veulent transmettre leurs résultats sur ce bus, l'une d'entre elle est choisie et les autres doivent mettre en attente leurs résultats dans une mémoire tampon, soit un registre, soit une FIFO. Dans les deux cas, le registre ou la FIFO sont appelés des producers. L'implémentation demande de bloquer des opérations dans l'ALU si le contournement doit être mis en attente, ce qui bloque tout le pipeline en cas de problème.

Le bus de contournement est assez spécifique à l'algorithme de Tomasulo, dans le sens où c'est un des rares articles académique à utiliser un tel bus de contournement.

Le renommage de registres dans les stations de réservation

L'unité d'émission attribue à chaque résultat d'instruction un identifiant de résultat. L'identifiant est une sorte de numéro de registre virtuel, qui est transmis sur le bus de contournement. L'identifiant est propagé comme tout signal de commande, il suit l'instruction sur son trajet dans le pipeline. Quand l'unité de calcul a fini son calcul, l'identifiant est envoyé avec le résultat sur le bus de contournement. Les stations de réservation contenant cet identifiant de résultat enregistrent alors le résultat dans le champ adéquat. De plus, le ROB a des entrées modifiées pour contenir l'identifiant de résultat, afin d'associer un identifiant de résultat à un registre de destination.

Les entrées des stations de réservation sont assez semblables à celle des fenêtres d'instruction, à un détail près : les opérandes sont enregistrées directement dans des champs séparés. Une entrée d'une station de réservation mémorise une instruction, à savoir toutes les informations nécessaires pour l'exécuter, y compris les opérandes. L'entrée est structurée en plusieurs champs. Le premier mémorise l'opcode de l'instruction. Il y a aussi un champ pour l'identifiant de résultat. Il y a aussi deux champs, un par opérande. Il peut contenir deux choses : soit l'opérande elle-même, soit l'identifiant de résultat associé. Pour faire la différence, les deux champs ont chacun un bit de présence, qui indique si l'opérande est présente dans le champ ou non (auquel cas, c'est un identifiant).

Vous vous demandez certainement où sont les registres virtuels avec cette organisation. Et bien il ne s'agit ni plus ni moins que des stations de réservation. Et plus précisément des champs pour les opérandes, qui contiennent soit l'opérande disponible, soit l’identifiant de résultat. L'identifiant de résultat est l'équivalent d'un nom de registre virtuel. D'ailleurs, une fois l'instruction émise, il n'y a pas de noms de registre physique dans les stations de réservation, pour les opérandes.

En somme, le renommage de registre est pris en charge par le système de contournement. Les registres virtuels sont des registres qui reçoivent des résultats en sortie de l'ALU, les mettent en attente, puis les envoient en entrée de l'ALU. Le tout fonctionne comme une sorte de contournement retardé. La technique de renommage via le ROB fonctionnait un peu sur le même principe, mais il n'était pas aussi explicite.

L'exécution d'une instruction avec l'algorithme de Tomasulo

L'exécution d'une instruction avec des stations de réservation se fait en plusieurs étapes. Premièrement, l'instruction est émise, dans le sens où elle est transmise de l'unité d'émission aux stations de réservation. Deuxièmement, l'instruction est exécutée ou attend son exécution. Enfin, son résultat est enregistré dans les registres et envoyé aux stations de réservation pour contournement.

L'émission se fait sous condition qu'une station de réservation pour l'unité de calcul voulue soit disponible. Si c'est le cas, l'unité d'émission vérifie si les opérandes sont disponibles dans le banc de registre architecturaux. Les opérandes disponibles sont alors traitées différemment des opérandes non-disponibles. Les opérandes non-disponibles, elles seront envoyées via contournement plus tard et le renommage de registre doit être utilisé. L'opérande est associée à l'identifiant de résultat qui permet de savoir quand elle sera calculée. A l'opposé, les opérandes disponibles sont lues depuis les registres et enregistrées dans la station de réservation, leur bit de présence est mis à 1. Il n'y a pas de renommage de registres, car il n'y en a pas besoin pour ces opérandes.

Reprenons maintenant après l'émission de l'instruction, qui a été envoyée dans les stations de réservation. Elle attend alors que ses opérandes soient disponibles dans la station de réservation. Les opérandes non-disponibles sont alors calculées par des instructions et sont envoyées sur le bus de contournement. La station de réservation reconnait alors l'identifiant et enregistre le résultat dans le champ adéquat. Une fois toutes les opérandes disponibles, l'instruction est exécutée. Une fois son résultat connu, il est envoyé sur le bus de contournement, mais aussi dans le banc de registres. Et le tout continue.

Le scoreboarding du CDC 6600

L'implémentation du scoreboard sur le CDC 6600/7600 est appelée dans la suite du cours : le scoreboarding. La description que je vais donner du scoreboard est très différente de celle disponible dans les livres d'architecture des ordinateurs. La plupart des manuels, surtout les textbooks américains, donnent une description très haut niveau, très algorithmique du scoreboarding, qui ne sera pas abordée. A la place, je vais donner une description alternative, différente autant sur l'approche que le fond.

Le CDC 6600 n'existe plus, tous les exemplaires ont depuis longtemps été démontés, aussi il ne reste que des sources historiques pour savoir comment fonctionnait son scoreboard. Heureusement, il existe un livre qui décrit dans les moindres détails cette architecture, écrit par un des concepteurs de l'ordinateur : Design of a computer : the CDC 6600. Ce qui va suivre est majoritairement ité de cette source.

Le chemin de données du CDC 6600 et sa relation avec le scoreboard

Le pipeline d'un processeur avec scoreboarding ressemble à celui du schéma suivant. Pour résumer, le chemin de donnée forme un pipeline à trois étages : lecture des registres, exécution dans l'ALU, écriture dans les registres. Les opérations à effectuer son envoyées aux ALUs, et elles attendent leurs opérandes dedans.

La séparation en trois étages fait qu'il y a des registres entre chaque étages. Les opérandes sont chargées dans des registres en amont de l'ALU, et le résultat est enregistré temporairement dans un registre en sortie de l'ALU. Nous les appellerons : registres opérandes et registre résultat. Entre les deux, l'ALU effectue une opération quand les opérandes sont disponibles dans les registres opérandes, et maintien le résultat dans le registre résultat si besoin. Il y a aussi un autre registre qui mémorise l'opcode de l'opération, lors de l'attente des opérandes, mais aussi lors de l'exécution. Nous l'omettrons dans ce qui suit, car il s'agit d'un registre de pipeline classique.

Les registres opérande et résultat n'ont pas besoin d'être très complexes vu qu'ils servent juste à maintenir une donnée. Les registres ne sont pas connectés à l'horloge, les bascules ne sont pas synchrones, ils sont fabriqués à partir de simples latches, de simples bascules D non-synchrones. Et il en est de même pour le registre d'opcode. Le scoreboard commande le signal Enable qui autorise les écritures dedans, rien de plus. Le pipeline est donc le suivant :

Les registres opérandes sont chacun associé à un bit READ FLAG qui précise si l'opérande du calcul est disponible. Les bits READ FLAG sont mis à jour par un mécanisme assez complexe, qui sera vu dans la suite. Le scoreboard gère les transferts entre les registres opérande/résultat et le reste du processeur. Il génère deux signaux de 1 bit nommés GO READ et GO STORE/GO WRITE. Le signal GO READ déclenche la copie d'un registre architectural dans un registre opérande. Le signal GO WRITE déclenche la copie du registre résultat dans le registre architectural adéquat.

Pour effectuer une lecture ou une écriture, les noms des registres adéquats sont mémorisés dans deux registres notés Fi, Fj, et Fk. Fi mémorise le registre de destination de l'opération, Fj et Fk mémorisent les noms/numéros des registres opérandes. Les deux registres Qj et Qk sont utilisés pour la détection des opérandes disponibles, nous en reparlerons plus tard. Les registres Fi, FJ et Fk sont dans le scoreboard, et ils sont envoyés sur les entrées d'adresse du banc de registre suivant les besoins, suivant qu'on fasse une lecture ou une écriture. La lecture et écriture des registres donc totalement le fait du scoreboard, qui commande le banc de registres, comme le ferait un séquenceur normal.

Notez que les registres opérandes, couplés au registre d'opcode, peuvent être vus comme une station de réservation simplifiée, sans gestion du contournement. La différence principale avec l'algorithme de Tomasulo est que les champs pour les identifiants de résultat ont disparus, et que les bits de disponibilité des opérandes READ FLAG sont en réalité intégré au scoreboard, comme on le verra plus tard, avec une gestion de la disponibilité des opérandes totalement différente. De plus, il n'y a qu'une seule station de réservation par ALU, donc un risque plus grand de dépendances structurelles. On ne peut mettre en attente qu'une seule instruction par ALU avec le scoreboard.

Les désignateurs utilisés par le scoreboard

Les registres opérandes et résultat ne sont pas des registres architecturaux, mais ce ne sont pas des registres de pipeline non plus. Il est possible de faire l'analogie avec une station de réservation, mais l'analogie est limitée pour une raison simple : le scoreboard attend que les deux opérandes sont disponibles pour déclencher la lecture avec le signal GO READ. En théorie, il est tout à fait possible de lire un registre opérande à la fois, dès que l'opérande est disponible, mais le scoreboard ne faisait pas comme ça. De plus, les opérandes ne sont pas vraiment transmises via un réseau de contournement depuis la sortie de l'ALU.

Cependant, une rumeur veut que le processeur implémente un système de contournement, qui passe...par l'intermédiaire des registres. Paradoxal, mais qui s'explique pourtant très bien quand on connait le fonctionnement des registres utilisés. Le processeur utilisait une ancienne technologie de transistors, appelée ECL. Beaucoup de bancs de registres fabriqués avec cette technologie avaient une propriété intéressante : toute donnée écrite sur le port d'écriture était immédiatement disponible sur le port de lecture. Plus précisément, l'écriture se faisait sur front montant et la lecture sur front descendant. En faisant cela, une opérande pouvait être écrite dans les registres architecturaux, mais pourtant copiée dans les registres opérandes au même cycle. Le tout fonctionne presque comme un système de contournement, avec cependant quelques limitations ! Avec un vrai système de contournement, l'implémentation est beaucoup plus puissante.

Quant à savoir si les registres opérandes sont nommés, c'est un peu compliqué et la réponse serait qu'ils sont nommés de manière implicite. Il est d'ailleurs débattable de savoir si le CDC 6600/7600 implémente le renommage de registres... Le point de discorde est lié au fait que le scoreboard attribue un numéro à chaque unité de calcul, appelé le désignateur Q. Et ces identifiants sont utilisés pour la lecture des opérandes et leur copie dans les registres, ils se comportent comme un nom de registre virtuel.

Pour simplifier les explications, nous allons partir du principe que les désignateurs sont encodés en représentation unaire. Pour rappel, la représentation unaire représente un nombre sur plusieurs bits, dont un seul est à 1. Un zéro est codé en mettant tous les bits du nombre à zéro, la valeur 1 est encodée avec la valeur 000...0001, le deux avec 000...0010, etc.

Désignateur d'ALU
ALU ADD	ALU MUL	ALU DIV	ALU SUB	ALU CMP	ALU MOV
0	0	1	0	0	0

La réalité est que les désignateurs sont présents à plusieurs endroits et sont soit codés en unaires, soit codés en binaire, avec des traductions fréquentes entre les deux. Ils sont par exemple traduits du binaire vers l'unaire lors de la génération des signaux READ FLAG. Les traductions inverses sont aussi fréquentes. Les traductions se basent sur des décodeurs/encodeurs un peu modifiés.

L'avantage de la représentation unaire est que les comparaisons sont légèrement plus simples, les comparateurs économisent quelques portes logiques. De plus, elle s'adapte assez bien avec le fait que chaque unité de calcul précise si elle est disponible ou non, ce qui deviendra plus clair dans la suite.

Les réservations et la table de réservation

Le scoreboard du CDC 6600 contient une table de réservation, qui permet de réserver une unité de calcul pour une instruction à émettre. La table de réservation est composée d'entrées, une par unité de calcul, qui peut mémoriser une instruction. Une entrée mémorise pour chaque unité de calcul :

l'opcode de l'instruction à exécuter dessus ;
les noms/numéros des registres opérandes et destination ;
les désignateurs Q des unités de calcul qui fourniront les opérandes en résultat ;
deux bits READ FLAG qui disent si l'opérande associé est disponible.

Dans le livre utilisé comme source, il n'est pas clair si les noms des registres opérandes/résultat sont placés dans l'unité de calcul ou dans le scoreboard. Les explications semblent indiquer que c'est juste à côté de l'ALU, mais les schémas se contredisent là-dessus. Dans la suite, je pars du principe qu'ils sont dans le scoreboard, ce qui aurait bien plus de sens.

Le scoreboard consulte la table de réservation pour émettre une instruction. Avant d’émettre une instruction, elle regarde si l'entrée est libre ou déjà occupée par une instruction. Pour cela, chaque entrée est associée à un bit BUSY qui indique si l'entrée est vide ou occupée. Vu qu'il y a une entrée par unité de calcul, attribuer une entrée à une instruction est asszz simple : chaque instruction va dans une entrée bien précise, il suffit de vérifier celle-ci. Le bit BUSY est mis à 1 quand une instruction est émise, ajoutée dans l'entrée, mis à zéro quand elle est terminée. La libération d'une entrée se fait quand le signal GO WRITE est émis, le signal RELEASE ne suffit pas.

La réservation permet de réserver une ALU pour une opération. L'instruction est alors envoyée à l'ALU, où elle attend que ses opérandes soient disponibles. Une instruction attend son tour et n'est émise qu'une fois que les deux bits READ FLAGS sont à 1. La conséquence est qu'une instruction/micro-opération reste dans l'unité de calcul tant qu'elle a des dépendances RAW. Et seules les dépendances RAW, où une instruction pour opérande le résultat d'une instruction précédente, impliquent un blocage du pipeline et des bulles de pipeline. Les dépendances WAW ou WAR sont traitées autrement.

La table de réservation ne stocke pas les opérandes, ce qui fait qu'on peut la voir comme une fenêtre d'instruction à une entrée, ou encore comme une station de réservation castrée. Un détail très important est que ce système de réservation met en attente une instruction par ALU. Vu que toutes les ALUs du CDC 6600 sont très différentes, l'attribution d'une instruction à une ALU est trivial. Par contre, si une instruction veut utiliser une ALU réservée, elle ne peut pas et il faut bloquer le pipeline. Le système de réservation est donc une cause de dépendances structurelles qui bloquent l'émission des instructions dans de nombreux cas. Ce ne serait pas le cas si on pouvait placer plusieurs réservations par unité de calcul, mais passons.

Pour une dépendance WAR, l'instruction est émise, elle s'exécute, mais son résultat est maintenu dans le registre résultat le temps que ces dépendances soient résolues. Pour le dire autrement, Les dépendances WAR font que les instructions sont retenues dans l'étage d'enregistrement des données, un peu comme sur un processeur à pipeline multicycle (de longueur fixe). Sauf que les pipeline multicycle, il y aurait plusieurs registres d'échelonnements qui se suivent, alors qu'on n'en a qu'un ici, ce qui fait que l'unité de calcul est bloquée si l'écriture est retardée. En théorie, les dépendances WAW devraient être traitées avec un mécanisme similaire, mais le processeur détectait ces dépendances à l'émission et bloquait l'émission si un registre lu était accédé en lecture.

La Q-table : l'unité de renommage de registres

Quand une instruction est décodée et émise, elle réserve une unité de calcul. Mais il faut pour cela remplir les champs pour les désignateurs d'ALU, même si on voit mal à quoi ils servent pour le moment. Il se trouve que les registres opérandes contiennent une valeur, qui est le résultat d'une instruction soit déjà passée par une ALU, soit en cours d'exécution dans une ALU. Le désignateur pour un opérande est donc le désignateur de cette ALU. Reste à faire la correspondance entre un résultat/registre et l'ALU qui va le calculer ou l'a déjà calculé. Pour cela, le scoreboard mémorise la correspondance entre un registre/résultat et une unité de calcul dans une mémoire cache appelée la Q-table. Pour comprendre à quoi elle sert, prenons deux instructions consécutives, dont la seconde utilise le résultat de la première.

La première instruction est lancée dans une unité de calcul enregistre son résultat dans un registre de destination. Le scoreboard mémorise alors dans la Q-table que le registre de destination est associé à telle unité de calcul, elle mémorise une correspondance entre le désignateur de l'ALU et le registre de destination. Par la suite, la seconde instruction est émise. Le scoreboard interroge la Q-table pour les deux opérandes de l'instruction, pour récupérer les deux désignateurs de l'ALU associés. Ils sont envoyés au banc de registres pour gérer la lecture des opérandes.

Pour résumer, le scoreboard effectue les actions suivantes lors de l'émission.

Premièrement, il détermine si l'unité de calcul est disponible ou non, en utilisant le bit de disponibilité BUSY.
Deuxièmement, il mémorise les numéros de registres opérande et résultat pour commander la lecture des opérandes.
Troisièmement, il traduit les numéros de registres opérande en identifiants d'ALU.
Quatrièmement, il mémorise dans une Q-table la relation entre le registre de destination et l'unité de calcul choisie à l'étape 1.

La troisième étape permet de faire le lien entre un résultat calculé mais pas encore enregistré dans les registres, et un registre opérande non-nommé. Le lien guide le chargement des opérandes et donc le système de contournement passant par des registres (ce qui est du renommage de registre implicite).

La gestion des résultats : les signaux RELEASE et GOWRITE

Une fois d'instruction exécutée, son résultat est enregistré dans le registre résultat. Une fois le résultat dans le registre résultat, l'unité de calcul envoie un signal REQUEST au scoreboard pour savoir si la donnée peut être enregistrée dans les registres architecturaux. L'ensemble des signaux REQUEST est regroupé dans un vecteur de bit, une sorte de nombre, dont chaque bit indique quelle unité veut écrire un résultat. L'ensemble des signaux RELEASE forment un nombre encodé en unaire qui indique quelle ALU a fournit le résultat. Là, le scoreboard effectue plusieurs opérations successives sur ce nombre, en appliquant plusieurs masques.

Le premier masque appliqué vérifie pour chaque ALU si elle a le droit d'écrire son résultat en mémoire, sur la base des dépendances WAW et WAR. En cas de dépendances WAR ou WAW, l'écriture du résultat est retardé, ce qui fait que l'unité de calcul n'est pas considérée, son signal RELEASE est ignoré, il est masqué. Le masque qui permet cela est appelé le masque READ PENDING.

Le second masque est un circuit de priorité qui sélectionne un bit seulement. Il est en effet possible que plusieurs unités de calcul fournissent un résultat en même temps. Ou encore que l'une ait son écriture retardée et ait un signal RELEASE à 1 depuis plusieurs cycles. Toujours est-il qu'on ne peut écrire qu'un résultat à la fois, ce qui fait qu'il faut sélectionner une unité de calcul. Pour cela, un circuit de priorité sélectionne un seul signal RELEASE à 1 et met les autres à zéro. C'est le second masque.

Traitement des signaux REQUEST
Signaux REQUEST en sortie des ALUs
0	1	0	1	1	1	0	0	0	0
Application du masque READ PENDING pour les dépendances WAW/WAR
0	0	0	1	1	0	0	0	0	0
Sélection par un circuit de priorité
0	0	0	1	0	0	0	0	0	0

Après l'application du second masque, il ne reste qu'un seul bit à un, qui indique quelle ALU a été sélectionnée pour l'écriture. Il se trouve que l'ensemble des bits forme un désignateur d'ALU, encodé en représentation unaire, en représentation one-hot. Pour rappel, cela veut dire que seul un bit dans le nombre est à 1 et ce bit indique la valeur encodée. Si le bit numéro X est à 1, alors la valeur encodée vaut X. L'usage d'une représentation unaire/one-hot fait que l'on a juste à concaténer les signaux REQUEST et appliquer des masques pour obtenir le désignateur adéquat, pas besoin d'encodeur compliqués, ni de circuits de sélection complexes. Le désignateur résultat est appelé désignateur d'ALU choisie.

Une fois ce désignateur calculé, le désignateur d'ALU choisie est envoyé à la table de réservation, afin de récupérer le nom/numéro du registre résultat associé. Le scoreboard commande le port d'écriture du banc de registre, avec un signal GOWRITE et le nom/numéro du registre de destination récupéré. Le signal RELEASE est alors remis à zéro. Reste à générer le signal GO WRITE et faire les actions adéquates.

Mais il reste deux opérations de maintenance pour terminer l'écriture. La première est de remettre en ordre la Q-table. L'entrée qui liait l'unité de calcul au registre de destination doit être remise à zéro. Le résultat ayant été écrit, il n'est plus associé à l'unité de calcul, le lien entre les deux dans la Q-table est donc effacé. La seconde est de gérer la disponibilité des opérandes. Pour cela, le résultat après application des deux masques est aussi utilisé pour détecter la disponibilité des opérandes, pour mettre à 1 le bit READ FLAG adéquat. Là encore, c'est la table de réservation qui s'en charge.

La détection des opérandes disponibles : la génération des READ FLAG et du signal GOREAD

Le désignateur d'ALU choise est envoyé à la table de réservation pour récupérer le nom de registre destination, mais aussi aux champs opérandes. Dans chaque entrée, il comparé aux deux désignateurs Qj et Qk, associés chacun à une opérande. Pour rappel, les désignateurs Qj et Qk sont des désignateurs d'unité de calcul, eux aussi encodés en unaire. S'il y a match, alors l'opérande est disponible. Le comparateur génère un signal qui met à 1 le bit de disponibilité READ FLAG (i pour le numéro de l'unité de calcul), le bit est dans une bascule pour ne pas être effacé au cycle suivant.

Le scoreboard contient donc une matrice de comparaison, qui compare le résultat de l'étape précédente avec tous les désignateurs associés à une opérande. L'avantage d'encoder les désignateurs en unaire fait que la comparaison est plus simple : elle se constitue uniquement de portes ET, pas besoin de portes XOR comme on en aurait eu besoin en utilisant des désignateurs en binaire. De plus, le calcul du désignateur à partir des signaux REQUEST est trivial, pas besoin de passer par un encodeur.

Quand les deux bits READ FLAG d'une instruction sont à 1, le scoreboard envoie un signal GOREAD à la mémoire et aux unités de calcul. Les numéros/noms de registre, présents dans les registres Fj et Fk, sont envoyés au banc de registre. Le signal envoyé à l'ALU lui demande de copier ces opérandes dans les registres opérandes et de démarrer l'instruction. L'opcode de l'instruction est déjà mémorisé dans le registre d'opcode, ou alors il est envoyé à ce moment. Puis les bits READ FLAG de l'entrée associée à l'ALU sont remis à zéro.

Le calcul du masque READ PENDING

Plus haut, nous avions vu le masque READ PENDING qui interdit d'écrire un résultat dans un registre si les conditions ne sont pas réunies, en cas de dépendance WAR. Le nom du signal indique comment sont détectées les dépendances WAR : l'écriture est interdite si une lecture de ce registre est en attente. Le CDC 6600 lit les deux opérandes d'une instruction en même temps, ce qui fait qu'une opérande peut être disponible mais pas encore lue. Une opérande dans ce cas a un READ FLAG à 1 pour le registre associé. Chaque bit du signal READ PENDING se détermine donc en faisant un ET logique entre tous les bits READ FLAG associé à un registre, encore faut-il les sélectionner en fonction du registre voulu et de l'unité de calcul associée au registre.

La méthode permet de gérer les dépendances WAR, mais pas les dépendances WAW. Le CDC 6600 bloquait l'instruction dans l'étage d'émission en cas de dépendance WAW. Si l'instruction à émettre avait pour registre de destination un registre de destination d'une instruction dans le pipeline, le processeur émettrait des bulles de pipeline tant que la première écriture n'a pas eu lieu. Son successeur, le CDC 7600 n'avait pas ce défaut et était capable de passer outre toutes les dépendances de données WAR et WAW. Une raison probable à cela est que le CDC 6600 a été terminé en cataastrophe et que ses concepteurs n'ont pas eu le temps d'implémenter une technique complexe de gestion des dépendances WAW. Mais ils ont eu le temps de terminer le design du scoreboard pour le successeur 7600. Une autre raison est que le pipeline étant court, les dépendances WAW avaient un effet très limité et que bloquer l'émission n'entrainait pas une baisse de performance notable.

Mais on peut en théorie faire autrement. Le principe est que les instructions sont émises en absence de dépendances RAW, mais que l'écriture de leur résultat peut être retardée à l'étage d'écriture dans les registres. En cas de dépendances WAR ou WAW, le résultat à écrire est maintenu sur la sortie d'une unité de calcul, dans un registre tampon placé sur cette même sortie, comme illustré plus bas. Les instructions sont donc bloquées dans l'unité de calcul, qui n'est plus disponible pour d'autres instructions. Le scoreboard sait qu'il ne peut plus envoyer d'instruction sur cette unité de calcul. A chaque cycle, l'étage d'enregistrement choisit le résultat à enregistrer dans les registres, en respectant les dépendances de données. C'est le scoreboard qui autorise ou non cette écriture, en commandant l'étage d'enregistrement en fin de pipeline. En clair : l'enchainement des signaux GOWRITE impose un enregistrement des résultats qui suit l'ordre du programme.

◄ Retour vers « Le renommage de registres »

Sommaire du livre

Continuer vers « Les unités mémoires à exécution dans l'ordre » ►