Fonctionnement d'un ordinateur/Les dépendances de données et l'exécution dans le désordre
Dans les chapitres précédents, nous avons parlé des techniques d’exécution dans le désordre. L'idée est d’exécuter une nouvelle instruction à chaque cycle, dans des unités de calcul séparées. Les instructions sont lancées consécutivement, elles s’exécutent en parallèle dans des unités de calcul séparées, mais elles peuvent se finir dans le désordre. Une conséquence est que les instructions vont écrire dans les registres dans un ordre différent du programme, ce qui est courant quand on mélange des instructions de durée différentes.
Et changer l'ordre des écritures dans les registres peut poser problème. Cela fonctionne bien si elles sont indépendantes, mais cela ne marche pas si elles ont une dépendance de données, à savoir qu'elles lisent ou écrivent dans le même registre, voire la même adresse mémoire. Les différente techniques d’exécution dans le désordre détectent les dépendances et exécutent les instructions d'une manière qui fait que ces dépendances ne posent pas de problèmes.
Il existe différents types d'exécution dans le désordre : le scoreboarding, l'algorithme de Tomasulo et diverses autres techniques. Nous avons déjà vu le scoreboarding dans un chapitre précédent. Avec lui, le circuit d'émission émet les instructions dans l'ordre, mais elles peuvent terminer dans le désordre. Il s'agit d'une forme limitée d’exécution dans le désordre. Je dis limitée, pour une raison simple. Le scoreboard est capable de fournir des gains proches de 10 à 30 % suivant les programmes. Mais celui-ci a un défaut : si le scoreboard détecte une dépendance bloquante lors de l'émission, l'instruction est bloquée dans l'étage d'émission et bloque tout le pipeline. Le front-end stoppe et le processeur émet des bulles de pipeline tant que la dépendance n'est pas résolue. En clair, les instructions suivantes ne sont pas chargées. Mais les techniques que nous allons voir dans ce chapitre, n'ont pas ce genre de problèmes.
Les fenêtres d’instruction et les stations de réservation[modifier | modifier le wikicode]
Avec les techniques avancées d’exécution dans le désordre, le processeur ne s'arrête pas de décoder des instructions, même si une instruction précédente ne peut pas être émise. Pour que cela fonctionne, il faut que l'étage d'émission mette en attente les instructions, sans bloquer le pipeline (chose que fait le scoreboard).
Pour cela, on doit ajouter une sorte de file d'attente où les instructions attendent de pouvoir être émises. Ainsi, si une instruction ne peut pas être émise, on la place dans la file d'attente et on passe à la suivante. Dès que les conditions sont réunies, que les dépendances ont disparues, l'instruction en attente est exécutée. En clair, si une instruction attend que ses opérandes soient disponibles, on peut lancer une instruction indépendante en parallèle au lieu de bloquer le pipeline.
Dans le cas qui va suivre, on suppose que le processeur ne peut émettre qu'une instruction à la fois. Chaque cycle, une instruction est sélectionnée et est envoyée dans le chemin de données, soit à l'étage de lecture des registres, soit directement à l'ALU. Seules les instructions dont tous les opérandes sont candidates pour l'émission. Le processeur contient un circuit qui détecte les instructions prêtes : la logique d’éveil (wake-up logic). Il 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é).
Une fois que la logique d'éveil a fait son travail, une instruction 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.
La fenêtre d'instruction centralisée[modifier | modifier le wikicode]
Le cas le plus simple n'utilise qu'une seule mémoire file d'attente : la fenêtre d'instruction. Avec elle, l'unité d'émission, détecte les dépendances et répartit les instructions sur les unités de calcul. Elle consulte la totalité de la fenêtre d'instruction à chaque cycle pour vérifier si une instruction est disponible pour s’exécuter. LA fenêtre d'instruction doit spécialement être conçue pour, c'est une sorte de mémoire associative très complexe.
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). Une entrée contient son opcode (les signaux de commande à envoyer à l'ALU), le registre de destination du résultat, les registres de chaque opérande. 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 les registres, le bit de présence correspondant est mis à jour. Enfin, chaque entrée possède un bit empty qui indique si elle est vide, cette information étant utile pour réserver des entrées.
À chaque cycle, les instructions décodées sont ajoutées dans la fenêtre d'instruction, dans des entrées vides. Vu que les instructions quittent celle-ci dans le désordre, ces vides sont dispersés dans la fenêtre d'instruction, ce qui pose problème pour déterminer où placer les nouvelles instructions. La solution la plus triviale consiste à conserver une liste des vides, mise à jour à chaque insertion ou émission d'instruction. Une autre solution consiste à éliminer les vides en compactant la fenêtre d'instruction à chaque cycle d'horloge. Des circuits se chargent de détecter les vides et de regrouper les instructions en un unique bloc. Il faut signaler que certaines processeurs arrivent à se passer de cette étape de compactage, mais au prix de fenêtres d'instruction nettement plus complexes.
Autre problème : quand il faut choisir quelle instruction émettre, il y a toujours plusieurs candidats. Si on choisit mal, des instructions restent en attente trop longtemps parce que d'autres instructions plus jeunes leur passent devant. Pour éviter cela, les instructions les plus vielles, les plus anciennes, sont prioritaires. Pour cela, on peut utiliser une FIFO un peu spéciale pour la fenêtre d'instruction. Si les ajouts d'instruction se font dans l'ordre, les instructions ne quittent pas forcément la fenêtre d'instruction dans l'ordre imposé par une FIFO : les instructions restent triées dans leur ordre d'ajout, même s'il y a des vides entre elles. Dans ces condition, il est préférable que le compactage conserve l'ordre FIFO des instructions. Dans ces conditions, l'instruction la plus ancienne est celle qui est située à l'adresse la plus faible : le circuit de sélection peut donc être fabriqué avec des encodeurs, et est relativement simple.
Les fenêtres d'instruction décentralisées[modifier | modifier le wikicode]
Une autre solution utilise plusieurs fenêtres d'instruction, souvent une par aval. L'émission se fait alors en deux étapes. La première se contente de répartir les instructions sur les unités de calcul, la détection des dépendances étant prise en charge par les stations de réservation. Pour faire la différence avec l'usage d'une fenêtre d'instruction unique, nous allons parler de fenêtre d'instruction centralisée s'il n'y en a qu'une dans le processeur, de fenêtre d'instruction décentralisée s'il y en a plusieurs.
Si on compare les deux techniques, ont s’aperçoit que les avantages et inconvénients de chaque méthodes sont assez nombreux. Mais dans les grandes lignes, l'avantage des fenêtre décentralisées est qu'elles sont plus petites qu'une grosse fenêtre d'instruction. L'autre avantage, c'est qu'il est possible de démarrer l'exécution de plusieurs instructions simultanément : une instruction par fenêtre décentralisée, contre une par fenêtre d'instruction. Mais les stations de réservation sont souvent sous-utilisées, partiellement remplies, contrairement aux fenêtres d'instruction.
Un autre avantage est que l'on peut utiliser des fenêtres d'instructions très simples, souvent limitée à de vulgaires mémoires FIFOs. Et malgré cela, on peut avoir de l’exécution dans le désordre. L'idée est que les instructions sont envoyées aux unités de calcul dans l'ordre FIFO, mais seulement à l'intérieur d'une fenêtre décentralisée. Les instructions s’exécutent dans le désordre si elles sont envoyées à des fenêtres différentes. C'était ce qui était fait sur le processeur Pentium 4, qui avait deux FIFOs séparées : une pour les instructions d'accès mémoire et une autre pour les autres instructions. Les FIFOs étant très simples à implémenter comparé aux autres fenêtres d'instruction plus complexe, c'était un sacré gain en circuits, pour les pertes de performance qui vont avec.
- Fait amusant, les ALU entières étaient cadencées à une fréquence double de celle du processeur, ce qui fait que les fenêtres d'instruction pour les unités de calcul entière sont aussi censées l'être. Les circuits qui détectent la disponibilité des opérandes dans les fenêtres sont censés faire de même. Sauf qu'en réalité, les circuits étaient dupliqués : l'un allait à une fréquence double, l'autre allait à la fréquence normale.
Mais cela ne signifie pas que ce soit forcément le cas, beaucoup de processeurs utilisent des fenêtres décentralisées, chacun pouvant émettre des instructions dans le désordre. Un exemple de ce type est celui du processeur Alpha 21264. Il contenait deux fenêtres d'instructions, une pour les instructions entières, une autre pour les instructions flottantes. Mais les deux fenêtres n'étaient PAS des mémoires FIFOs. Les instructions quittaient les fenêtres d'instructions dès que leurs opérandes sont disponibles, sans se préoccuper de l'ordre des instructions du programme. Il y avait bien émission dans le désordre à l'intérieur des fenêtres d'instruction. Et c'était possible parce que chaque fenêtres était liée à plusieurs ALUs.
Les stations de réservation[modifier | modifier le wikicode]
Les fenêtres d'instructions décentralisées sont souvent modifiées de manière à faciliter l'implémentation du contournement (bypass). Les fenêtres d'instruction de ce type sont appelées des stations de réservation. Pour cela, les opérandes d'une instruction sont mémorisées dans les stations de réservation elle-mêmes. 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.
Les résultats d'une instruction sont non seulement envoyés vers le ROB ou les registres, mais ils sont aussi envoyés vers les stations de réservation. Le réseau d'interconnexion, essentiel pour le contournement, qui connecter la sortie de l'ALU aux stations de réservation, s'appelle le Common memory bus. Le résultat en sortie de l'ALU est fournit avec le registre de destination associé, qui est transmis dans le pipeline depuis l'unité d'émission. Les stations de réservation vérifient si le registre de destination correspond au registre de destination mémorisé dans leurs entrées. S'il y a correspondance, le résultat est enregistré dans l'entrée associée.
Faire la même chose avec une fenêtre d'instruction n'est pas très pertinent, car elles sont plus découplées des unités de calcul. On a globalement une station de réservation par unité de calcul, ou pour 2/3 unités de calcul, ce qui rend le contournement plus facile à implémenter.
Il est maintenant temps de voir en quoi sont faites les fenêtres d’instruction et les stations de réservation. Nous allons aussi voir quelle est la logique d'émission associée. Attention : dans ce qui va suivre, j'utiliserai le terme « fenêtre d'instruction » pour parler des stations de réservation, ainsi que de la fenêtre d'instruction.
Les fenêtres d'instruction basées sur une mémoire associative[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 d'une instruction qui respecte une condition bien précise dans la mémoire, ce qui fait que les mémoires associatives sont donc tout indiquées.
Le principe général[modifier | modifier le wikicode]
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. Le nom de registre est 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 et son bit de disponibilité est mis à 1. On peut adapter cette méthode pour tenir compte du contournement assez simplement.
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.
Les optimisations possibles[modifier | modifier le wikicode]
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.
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.
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.
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.
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.
Les fenêtres d'instruction basées sur des tables indexées[modifier | modifier le wikicode]
D'autres 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.
La 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.
La 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.
L'é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.
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.
Les fenêtres d’instruction avec 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.
L'usage de 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.
La technique du 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.
La technique du 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.
Les 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.
