Fonctionnement d'un ordinateur/Fenêtres d’instruction et stations de réservation

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

Dans le chapitre précédent, nous avons vu les principes qui se cachent derrière l’exécution dans le désordre. Nous avons notamment vu que les processeurs modernes utilisent des fenêtres d’instruction, des tampons dans lesquels les instructions à exécuter sont mises en attente. Dans certains processeurs, ces fenêtres d’instruction sont découpées en plusieurs stations de réservation indépendantes. Il est maintenant temps de voir en quoi sont faites ces fenêtres d’instruction et ces stations de réservation. Nous allons aussi voir quelle est la logique d'émission associée.

Généralités[modifier | modifier le wikicode]

Les fenêtres d'instruction sont composées d'entrées, des blocs de mémoire qui servent à stocker une instruction. Une instruction réserve une entrée après son décodage et la libère, soit quand l'instruction est exécutée, soit quand elle termine son exécution (tout dépend du processeur). Le rôle du planificateur (scheduler) est de vérifier le contenu des entrées pour savoir quelle instruction émettre. Pour faciliter la détection des dépendances, chaque station de réservation indique le registre de destination du résultat et les registres de chaque opérande. Chaque entrée possède un bit empty qui indique si elle est vide, cette information étant utile pour réserver des entrées. De plus, chaque opérande est couplée à un bit de disponibilité, qui indique si elle est disponible. Quand un opérande est écrit dans l'entrée, le bit de présence correspondant est mis à jour.

Entrée d'une station de réservation

Seul un nombre limité d’entrées peut communiquer avec le chemin de données à un moment donné. Dans le cas qui va suivre, on ne peut émettre qu'une instruction à la fois : à chaque cycle, une entrée est sélectionnée et est connectée à l'entrée de l'ALU ou des stations de réservation. Cependant, seules les entrées dont tous les opérandes sont prêts peuvent émettre leurs instructions. Le processeur doit contenir un circuit qui détecte les entrées prêtes : la logique d’éveil (wake-up logic). Ce circuit vérifie si l'entrée n'est pas vide (le bit empty), et si tous les opérandes sont prêts (les bits de validité). Détecter la disponibilité d'une opérande, pour mettre à jour les bits de validité, demande de surveiller les écritures dans les registres. Une fois que la logique d'éveil a fait son travail, une entrée est choisie, ce choix doit être le plus pertinent possible, pour des raisons de performances. Ce rôle est dévolu à un circuit qu'on appelle la logique de sélection, ou select logic.

Fonctionnement complet de la logique d’émission.

CAM-based[modifier | modifier le wikicode]

Certaines fenêtres d'instruction se basent sur des mémoires associatives, des mémoires abordées il y a quelques chapitres. Pour rappel, ces mémoires servent à accélérer la recherche de données dans un ensemble. Or, une fenêtre d'instruction vérifie régulièrement si chaque entrée est prête : il s'agit d'un processus de recherche, ce qui fait que les mémoires associatives sont donc tout indiquées.

Comme vous le savez, les signaux de commande d'une instruction sont propagés avec celle-ci dans le pipeline, le nom du registre de destination ne faisant pas exception. Ce nom de registre est alors envoyé à la fenêtre d'instruction lors de l'écriture du résultat dans les registres. S'il y a correspondance, l'opérande est disponible. On peut adapter cette méthode pour tenir compte du contournement assez simplement.

Détection des dépendances par propagation du registre de destination.

En conséquence, le circuit de détection des dépendances est constitué d'un grand nombre de comparateurs : un par champ « nom de registre » dans chaque entrée. Si l'opérande est disponible, le bit de validité associé doit être positionné à 1 (il est remis à 0 lorsque l'instruction quitte l'entrée).

Gestion des bits de validité.

Le problème avec des fenêtres d'instruction de ce type est leur forte consommation énergétique, ainsi que le grand nombre de portes logiques utilisées, qui deviennent prohibitif pour des fenêtres d'instruction un peu grosses. Pour résoudre ce problème, certains ont optimisé les comparateurs. D'autres ont tenté de profiter du fait que la majorité des bits dans les entrées sont composés de zéros. Bref, les optimisations purement matérielles sont légion.

Optimisation sur le nombre d'opérandes[modifier | modifier le wikicode]

Certains chercheurs ont remarqué que le nombre d'opérandes varie suivant l’instruction : certaines n'ont besoin que d'un seul opérande. De plus, il arrive qu'une opération tout juste décodée ait déjà un ou plusieurs de ses opérandes de prêts. Cette constatation permet d'éviter d'utiliser des comparateurs pour les opérandes déjà prêts. Par exemple, on peut parfaitement utiliser trois fenêtres d'instruction :

  • une pour les instructions dont tous les opérandes sont prêts, mais qui sont quand même mises en attente, sans comparateur ;
  • une pour les instructions dont un seul opérande manque, qui n'utilise qu'un comparateur par entrée ;
  • une pour les instructions dont deux opérandes manquent à l'appel, qui utilise deux comparateurs par entrée.

C'est beaucoup plus économique que d'utiliser une seule grosse fenêtre d'instruction qui contiendrait autant d'entrées que les trois précédentes réunies, avec deux comparateurs par entrée. Certains sont même allés plus loin, et ont proposé de supprimer la fenêtre d'instruction avec deux opérandes par entrée. Les instructions dont deux opérandes sont inconnus au décodage sont stockées dans la fenêtre d'instruction pour instructions avec un comparateur par entrée. Un circuit de prédiction se charge alors de prédire l'opérande manquant, cette prédiction étant vérifiée plus loin dans le pipeline.

Optimisations sur la détection des opérandes prêts[modifier | modifier le wikicode]

D'autres chercheurs ont conservé une fenêtre d'instruction unique, avec autant de comparateurs par entrée qu'il y a d'opérandes possibles par instruction. Simplement, le processus de détection des opérandes prêts est légèrement ralenti : on ne vérifie qu'un opérande par cycle. Pour vérifier les deux opérandes d'une entrée, on doit attendre deux cycles.

Optimisation sur la segmentation de la fenêtre d'instruction[modifier | modifier le wikicode]

Enfin, certains chercheurs ont proposé des fenêtres d'instruction segmentées. Les instructions circulent à chaque cycle d'un segment vers le suivant : en conséquence, certains segments conservent les instructions les plus anciennes, un autre les instructions les plus jeunes, etc. Seul le denier segment, celui qui contient les instructions les plus vielles, peut émettre une instruction : la détection des opérandes se fait seulement dans le dernier segment, qui contient les instructions les plus anciennes. On économise ainsi beaucoup de comparateurs.

Optimisation du pipeline et spéculation[modifier | modifier le wikicode]

Certains chercheurs ont tenté de pipeliner l'étape de sélection des opérandes, ainsi que l'étage d'arbitrage. Mais en faisant cela, il faut plusieurs cycles pour détecter qu'une instruction a ses opérandes prêts, ce qui pose problème face à de nombreuses dépendances RAW. Pour éviter de trop perdre en performances, certains chercheurs ont décidé d'utiliser des techniques pour prédire quelles seront les instructions dont les opérandes seront bientôt prêts. Si détecter qu'une instruction est prête prend n cycles, le processeur devra tenter de prédire la future disponibilité des opérandes n cycles en avance pour obtenir des performances optimales.

Tables indexées[modifier | modifier le wikicode]

Certaines optimisations cherchent à supprimer les comparateurs présents dans chaque entrée en remplaçant la fenêtre d'instruction par une mémoire RAM, dont chaque mot mémoire correspondrait à une entrée.

Recherche directe par étiquette[modifier | modifier le wikicode]

La première de ces techniques, la recherche directe par étiquette (direct tag search) fut créée par Weiss et son collègue Smith. De base, chaque instruction produit un résultat, qui devra être rapatrié dans une ou plusieurs entrées de la fenêtre d'instruction. L'optimisation de la recherche directe par étiquette fonctionne dans le cas où le résultat de l'instruction n'est utilisé que par une seule entrée, et pas plusieurs.

Le principe est simple : chaque champ « opérande » d'une entrée est adressable via le nom de registre de cette opérande. Pour faire le lien entre entrée et nom de registre, la recherche directe par étiquette ajoute une table de correspondances matérielle, une mémoire RAM qui mémorise les adresses des champs « opérande » des entrées. Les adresses envoyées dans cette mémoire sont les noms de registres des résultats. Lors de l'émission, la table de correspondances est mise à jour. Les numéros des champs « opérande » réservés lors de l'émission sont mémorisés dans les mots mémoire qui correspondent aux deux registres sources. Toutefois, une petite vérification est faite lors de l'émission : si il y a déjà une correspondance dans la table pour un registre source, alors une autre instruction compte lire ce registre. Pour éviter d'écraser les données de l'instruction précédente dans la table de correspondances, l'émission de l'instruction est bloquée.

Recherche directe par étiquette.

Table de première utilisation[modifier | modifier le wikicode]

Dans leur papier de recherche nommé « A Low-Complexity Issue Logic », Ramon Canal et Antonio González ont trouvé une solution assez similaire. Leur algorithme se base sur trois structures matérielles :

  • une mémoire RAM nommée la table de première utilisation (first-use table) ;
  • une mémoire de type FIFO, qui sert de file d'attente pour les instructions ;
  • une fenêtre d'instruction normale.

Le fonctionnement de cet algorithme peut se résumer en trois cas.

  • Si une instruction a tous ses opérandes disponibles, celle-ci est placée dans la mémoire FIFO.
  • Deuxième cas : l'instruction lit une valeur/donnée déjà lue/utilisée par une précédente instruction. Dans ce cas, l'instruction est placée dans la fenêtre d'instruction.
  • Dans le dernier cas, l'instruction va lire une donnée qui n'a jamais été lue auparavant : le résultat à lire a été écrit dans un registre, mais pas encore été utilisé. Dans ce cas, l'instruction est mémorisée dans la table de première utilisation. Le registre lu en question servira d'adresse, et déterminera l'adresse de l'instruction dans la table de première utilisation. L'opcode de l'instruction sera stocké dans cette table de première utilisation avec le numéro de registre de l'opérande restant. Quand l'instruction qui produit la donnée à lire terminera, la donnée sera disponible. Le numéro du registre de destination sera alors envoyé en entrée d'adresse de la table de première utilisation : l'instruction qui consomme le résultat sera alors directement accessible. L'entrée sera alors mise à jour, et le registre de l'opérande restant est analysé. Si celui-ci ne pointe pas vers une instruction, alors l'instruction mise à jour a tous ses opérandes disponibles, elle est déplacée dans la mémoire FIFO.
Table de première utilisation.

Éveil par matrice de bits[modifier | modifier le wikicode]

Une dernière solution se passe totalement de comparateurs complexes dans la fenêtre d'instruction. Le processeur mémorise juste les registres qui contiennent une donnée valide dans un registre de disponibilité d’opérandes, avec un bit par registre qui indique si celui-ci est valide ou non. Cette technique détecte la disponibilité des opérandes avec l'aide d'une matrice de bits, où chaque ligne correspond à une entrée et chaque colonne à un registre. À chaque croisement entre une ligne et une colonne, on trouve un bit. Si le bit de la ligne n et de la colonne m est à 1, cela veut dire : l'instruction dans l'entrée n a besoin de lire le registre m. S’il est à 0, alors cela veut dire que l'instruction stockée dans la ligne n n'a pas besoin de la donnée dans le registre m.

Planificateur à matrice de bits.

Lorsqu'une 'instruction réserve une entrée, elle initialise la ligne en fonction des registres qu'elle souhaite lire. Pour vérifier si une instruction a ses opérandes prêts, il suffit de comparer ce registre de disponibilité à la ligne qui correspond à l'instruction. L'instruction est prêt à s’exécuter quand les deux sont égaux. Cela demande donc d'ajouter, à chaque intersection ligne-colonne, un comparateur.

Logique de détection de la disponibilité d'une instruction.

Préplanification[modifier | modifier le wikicode]

Avec la préplanification (prescheduling), la fenêtre d’instruction est composée de mémoires tampons dans lesquelles les instructions sont triées dans l'ordre d'émission. Il n'y a pas de logique d’émission proprement dite, celle-ci se bornant à vérifier si l'instruction située au début de la fenêtre d’instruction peut s’exécuter. Par contre, le préplanificateur détecte les dépendances et en déduit où insérer les instructions dans le tampon d'émission, à l'endroit le plus adéquat.

Préplanification.

FIFO multiples[modifier | modifier le wikicode]

La technique de préplanification la plus simple consiste à scinder la fenêtre d’instruction en plusieurs FIFO. Quand une instruction a une dépendance avec une instruction présente dans une FIFO, elle est ajoutée dans celle-ci. Ainsi, le préplanificateur se charge de détecter les chaines d'instructions dépendantes, et place les instructions d'une même chaine dans une seule FIFO. Si jamais l'instruction située au tout début de la FIFO n'a pas ses opérandes disponibles, alors la FIFO est bloquée : l'instruction attend que ses opérandes soient disponibles, bloquant toutes les instructions précédentes. Mais les autres FIFO ne sont pas bloquées, laissant de la marge de manœuvre.

Préplanification par FIFO multiples.

Tampon trié[modifier | modifier le wikicode]

Une autre technique, celle du tampon trié, trie les instructions selon le temps d'attente avant leur exécution : les instructions qui sont censées s’exécuter bientôt étant au tout début de cette mémoire, tandis que les instructions qui s’exécuteront dans un long moment sont situées vers la fin. Des techniques similaires se basent sur le même principe, avec un ordre des instructions différent, tel les relations de dépendance entre instructions. Comme précédemment, si jamais l'instruction au bout de la mémoire, celle prête à être émise n'a pas ses opérandes prêts, elle est mise en attente et bloque toute la fenêtre d’instruction. Le temps avant exécution dépend du temps de calcul de ces opérandes et du temps avant exécution des instructions qui produisent ces opérandes. Évidemment, celui-ci n'est pas toujours connu, notamment pour les instructions qui accèdent à la mémoire, ou des instructions dépendantes de celles-ci. Pour résoudre ce genre de problèmes, le préplanificateur doit faire des prédictions.

Préplanification par tampon trié.

Tampon de scoreboard[modifier | modifier le wikicode]

La technique précédente peut être améliorée. Au lieu de bloquer totalement la fenêtre d’instruction lorsqu'une instruction émise n'a pas tous ses opérandes disponibles, on peut réinsérer celle-ci dans la fenêtre d’instruction. Ainsi, l'instruction fautive ne bloque pas la fenêtre d’instruction, et retente sa chance autant de fois qu'il le faut.

Préplanification par fenêtre d’instruction scorebarodée.

Techniques hybrides[modifier | modifier le wikicode]

Il est possible de marier les techniques précédentes (préplanification et autres formes de fenêtres d’instruction), en utilisant deux fenêtres d’instruction : une gérée par la préplanification, et une autre pour les instructions dont le temps d'attente ne peut pas être déterminée. Certains processeurs utilisent ainsi une fenêtre d’instruction qui précède la préplanification, afin de gérer les temps d'attente des instructions d'accès mémoire et des instructions dépendantes. Quand le temps d'attente d'une instruction devient connu, celle-ci est migrée dans le tampon de préplanification. Une autre technique consiste à d'abord tenter de prédire le temps d'attente de l'instruction avec la préplanification, et de basculer sur une fenêtre d’instruction normale si la prédiction s’avère fausse.

Préplanification avec fenêtre d’instruction. Préplanification avec fenêtre d’instruction avec techniques de prédiction de latence.