Fonctionnement d'un ordinateur/Les processeurs à émission dans l'ordre

Les pipelines précédents sont des pipelines idéalisés, peu réalistes. Leur défaut est qu'ils partent du principe que toutes les instructions s’exécutent en un seul cycle, sans quoi le pipeline pose de nombreux problèmes pas évidents au premier abord. Et quand je dis toutes les instructions, c'est vraiment toutes les instructions, même les accès mémoire.

Mais des accès mémoire en un seul cycle, ça n'existe pas avec les technologie modernes. La réalité est que les accès mémoire dans le cache L1 peuvent faire un cycle si on a de la chance, mais le moindre défaut de cache entraine une latence de plusieurs dizaines à centaines de cycles d'horloge. De même, certaines instructions gourmandes comme les multiplications ou les divisions prennent facilement plusieurs cycles. Il faut alors adapter le pipeline pour qu'il gère ses instructions. pour cela, on est obligé d'introduire les notions de front-end et de back-end, d'émission, de pipeline stall et de quelques autres dans le même genre.

Nous allons aussi en profiter pour aborder en avance l’exécution dans le désordre, du moins une version limitée appelée le scoreboarding. C'est là une chose inusuelle, mais elle est en réalité nécessaire pour comprendre le chapitre sur les exceptions précises et notamment ce qui a trait au tampon de réordonnancement, qui lui-même sert à introduire le chapitre sur la prédiction de branchement. Parler de l’exécution dans le désordre après ces chapitres aurait posé un problème : le chapitre doit suivre celui sur l’exécution dans le désordre stricto sensus est celui sur le renommage de registres, et il faut aborder le tampon de réordonnancement avant celui-ci pour faire les choses correctement. Bref, la meilleure solution est de scinder tout ce qui a trait à l’exécution dans le désordre en deux : l’exécution dans le désordre avec un scoreboard (et donc une émission dans l'ordre), et le reste (avec émission dans le désordre). Bref, tout cela pour dire que le plan des 10 prochains chapitre sera quelque peu déroutant pour les habitués.

Les accès mémoire avec un pipeline

Un cas particulier d'instruction est celui des accès mémoire, qui n'ont pas de durée prédéterminée. Un accès au cache peut prendre deux à trois cycles d’horloge, un accès au cache L2 prend facilement 10 cycles, et un accès en RAM une centaine. Les latences ne sont pas compatibles avec un pipeline en un cycle. Le pipeline doit pouvoir gérer ce genre de situation, à savoir des instructions dont la durée est inconnue. Les solutions à cela sont assez nombreuses.

Les caches pipelinés

La première solution, compatible avec les suivantes, permet de gérer un cache L1 dont l'accès prend plus de 1 cycle. Elle ne peut rien en cas de défaut de cache, mais chaque chose en son temps. L'idée est que le processeur pipeline l'accès au cache ! L'idée est que l'accès au cache ne se fait pas en un seul cycle, mais en plusieurs. Cependant, on peut lancer un nouvel accès au cache à chaque cycle d'horloge, comme un processeur pipeliné lance une nouvelle instruction à chaque cycle. L'implémentation est assez simple : il suffit d'ajouter des registres dans le cache. Pour cela, on profite que le cache est composé de plusieurs composants séparés, qui échangent des données dans un ordre bien précis, d'un composant à un autre. De plus, le trajet des informations dans un cache est linéaire, ce qui les rend parfois pour l'usage d'un pipeline.

Voici ce qui se passe avec un cache directement adressé. Pour rappel ce genre de cache est conçu en combinant une mémoire RAM, généralement une SRAM, avec quelques circuits de comparaison et un MUX. L'accès au cache se fait globalement en deux étapes : la première lit la donnée et le tag dans la SRAM, et on utilise les deux dans une seconde étape. Nous avions vu il y a quelques chapitre comment pipeliner des mémoires, dans le chapitre sur les mémoires évoluées. Et bien ces méthodes peuvent s'utiliser pour la mémoire RAM interne au cache !L'idée est d'insérer un registre entre la sortie de la RAM et la suite du cache, pour en faire un cache pipéliné, à deux étages. Le premier étage lit dans la SRAM, le second fait le reste. L'implémentation sur les caches associatifs à plusieurs voies est globalement la même à quelques détails près.

Cache directement adressé pipeliné - deux étages

Avec le circuit précédent, il est possible d'aller plus loin, cette fois en pipelinant l'accès à la mémoire RAM interne au cache. Pour comprendre comment, rappelons qu'une mémoire SRAM est composée d'un plan mémoire et d'un décodeur. L'accès à la mémoire demande d'abord que le décodeur fasse son travail pour sélectionner la case mémoire adéquate, puis ensuite la lecture ou écriture a lieu dans cette case mémoire. L'accès se fait donc en deux étapes successives séparées, on a juste à mettre un registre entre les deux. Il suffit donc de mettre un gros registre entre le décodeur et le plan mémoire.

Cache directement adressé pipeliné - trois étages

Et on peut aller encore plus loin en découpant le décodeur en deux circuits séparés. En effet, rappelez-vous le chapitre sur les circuits de sélection : nous avions vu qu'il est possible de créer des décodeurs en assemblant des décodeurs plus petits, contrôlés par un circuit de prédécodage. Et bien on peut encore une ajouter un registre entre ce circuit de prédécodage et les petits décodeurs.

Théoriquement, toute l'adresse est fournie d'un seul coup au cache, la quasi-totalité des processeurs présentent l'adresse complète à un cache pipeliné. Mais le Pentium 4 fait autrement. Il faut noter que les premiers étages manipulent l'indice dans la SRAM, qui est dans les bits de poids faible, alors que les étages ultérieurs manipulent le tag qui est dans les bits de poids fort. Les concepteurs du Pentium 4 ont alors décidé de présenter les bits de poids faible lors du premier cycle d'accès au cache, puis ceux de poids fort au second cycle. Pour cela, l'ALU fonctionnait à une fréquence double de celle du processeur, tout comme le cache L1. Il n'y avait pas de pipeline proprement dit, mais cela réduisait grandement la latence d'accès au cache.

Les pipeline stalls

Pipeliner le cache permet de régler le problème des accès au cache L1, et elle est tout le temps utilisé sur les processeurs modernes. Mais que faire en cas de défaut de cache ?

La solution la plus simple gèle le pipeline en cas de défaut de cache. Par geler, on veut dire que le processeur cesse de charge des instructions et que chaque instruction reste dans l'étage où elle est au moment du gel. L'implémentation la plus simple de ce gel est la suivante : chaque étage fournit un signal qui indique s'il faut geler le pipeline ou non, et le tout est envoyé au séquenceur. Le séquenceur déclenche un gel en cessant d'envoyer le signal d'horloge aux registres du pipeline, qui restent dans leur état en attendant que le gel soit levé. Ce gel du pipeline s'appelle un pipeline stall. Plus bas, nous verrons que d'autres situations entrainent un gel du pipeline tant qu'une certaine condition n'est pas remplie, pour éviter un paquet de problèmes.

Le pipeline est conçu pour fonctionner avec la durée d'accès au cache L1. Pour simplifier, disons que l'accès au cache L1 se fait en un deux cycle d'horloge, dans deux étages dédiés, avec accès pipeliné au cache. Si l'accès mémoire entraine un succès de cache, alors l'instruction s’exécute normalement et en temps imparti, elle suit la progression normale dans le pipeline. Mais dès qu'on défaut de cache est détecté, on gèle le processeur en attendant que le défaut de cache se termine. L'unité d'accès mémoire prévient le séquenceur quand la lecture ou écriture est terminée, ce qui lui permet de savoir quand reprendre l’exécution.

L’exécution anticipée avec des lectures non-bloquantes

Une optimisation profite de l'unité de calcul en parallèle de l'unité d'accès mémoire. L'idée est de continuer à faire des calculs en parallèle de l'accès mémoire, sous condition que cela ne pose pas de problèmes. L'idée de base est assez simple : si le processeur rencontre une lecture, il continue d’exécuter des instructions malgré tout, en parallèle de la lecture. Les instructions indépendantes d'une lecture s’exécutent pendant que celle-ci attend la mémoire ou le cache. Par contre, le processeur stoppe immédiatement s'il rencontre un autre accès mémoire, que ce soit une écriture ou une lecture. Cette technique s'appelle les lectures non-bloquantes. Elle a été utilisée sur le processeur ARM Cortex A53 et sur son successeur, l'ARM Cortex A510, avec un certain succès.

Mais faire ainsi fait naitre pas mal de problèmes qu'il faut résoudre. Le premier problème est qu'il se peut qu'une instruction ultérieure utilise la donnée lue par l'accès mémoire. Par exemple, la lecture charge une donnée dans un registre et ce registre est ensuite utilisé comme opérande d'une addition. Dans ce cas, l'instruction de calcul ne doit pas s’exécuter tant que la donnée n'a pas été chargée.

Un autre cas est celui où une instruction écrit dans le registre de destination de la lecture. Sans lectures non-bloquantes, la lecture a lieu avant, ce qui fait que la lecture écrit dans ce registre, qui est ensuite modifié par l'instruction ultérieure. Mais avec des lectures non-bloquantes, l'instruction qui écrit dans ce registre ne doit pas démarrer tant que la lecture n'est pas terminée. Il faut garantir cela en insérant des bulles de pipeline.

L'implémentation de cette technique est assez simple. A chaque cycle, le décodeur tente de démarrer une nouvelle instruction. En premier lieu, il regarde si celle-ci est un calcul ou un accès mémoire. S'il s'agit d'une autre instruction d'accès mémoire, on n'a pas le choix : il faut stopper celle-ci dans le décodeur tant que le premier accès n'est pas terminé, en insérant un bulle dans le pipeline. Mais s'il s'agit d'une instruction de calcul, il vérifie si elle est dépendante de la lecture.

Pour détecter les instructions dépendantes d'une lecture, le décodeur marque le registre où la lecture charge la donnée comme « invalide », du moins tant que la lecture n'a pas écrit son résultat dedans. Toute instruction qui a un registre invalide comme opérande est mise en attente. idem pour les instructions qui ont un registre invalide comme registre de destination. Pour marquer les registres comme valides ou invalides, on utilise registre dont chaque bit est associé à un registre. Chaque bit indique si le registre associé contient une donnée valide ou non. Le bit de validité est automatiquement comme invalide quand le processeur démarre une lecture.

Le processeur ROCK, annulé en 2010, utilisait une version améliorée de la technique précédente, appelée la technique des éclaireurs matériels. La différence est que le processeur ne stoppe pas quand il rencontre une instruction dépendante de la lecture. A la place, les instructions dépendantes de la lecture sont mises en attente dans une file d'attente spécialisée, appelée la file d’attente différée (deferred queue), qui est une mémoire FIFO un peu modifiée. Une fois que la lecture renvoie un résultat, le processeur cesse l’exécution des instructions et exécute les instructions mises en attente. Les instructions mises en attente sont exécutées dans l'ordre, avant de reprendre là où le programme s'était arrêté.

Les instructions multicycles avec un pipeline

Sur un processeur non pipeliné, certaines instructions peuvent prendre 1 cycle, d'autres 7 cycles, d'autres 9, d'autres 25, etc. Le cas typique est celui de la multiplication ou de la division, ou de toute opération complexe. Les instructions qui mettent plus d'un cycle pour s’exécuter s’appellent des instructions multicycle. Il est possible d'implémenter des instructions multicycle sur les processeurs pipelinés, en rusant un peu.

Il existe deux manières de les implémenter, qui dépendent de la longueur du pipeline. On distingue les pipelines de longueur fixe, où toutes les instructions ont le même nombre de cycles d'horloge, des pipelines de longueur variable ou certaines instructions prennent plus de cycles que d'autres. La véritable définition est en réalité que certaines instructions ont des étages en plus sur les pipelines à longueur variable, mais passons.

Avec un pipeline de longueur fixe, toutes les instructions ont le même nombre d'étages. On doit se caler sur l'instruction la plus lente pour implémenter les opérations multicycle. Par exemple, si j'ai une addition en un cycle, et une multiplication en 3 cycles, on peut faire en sorte que les deux fassent trois cycles, l'ALU d'addition fera sont calcul en deux cycles, mais il sera enregistré dans les registres avec un retard de deux cycles. Pendant ces deux cycles de retard, le résultat sera passé d'un registre du pipeline à l'autre, sans que rien ne se passe. En clair, certains étages sont « facultatifs » pour certaines instructions. L'instruction doit passer par ces étages, mais ceux-ci ne doivent rien faire.

Les pipelines multiples et de longueur variable  : la séparation entre front-end et back-end

Pour avoir plusieurs pipelines de longueur différente, le pipeline du processeur est décomposé en plusieurs parties. La première partie, l’amont (front end), prend en charge les étages communs à toutes les instructions : la mise à jour du program counter, le chargement, l'étage de décodage, etc. L'amont est suivi par le chemin de données, découpé en plusieurs unités adaptées à un certain type d'instructions, chacune formant ce qu'on appelle un aval (back end). Un aval est spécialisé dans une classe d'instructions : un pour les instructions arithmétiques et logiques, un autre pour les opérations d'accès mémoire, un autre pour les instructions d'échange de données entre registres, et ainsi de suite.

Pipeline avec un aval et un amont (back-end et front-end).

Par exemple, il est possible de se contenter de deux avals : un pour les accès mémoire et un pour les calculs.

Pipeline à deux aval de type load-store.

On peut aussi utiliser une unité de calcul séparée pour les instructions de tests et branchements.

Pipeline avec un aval pour les instructions arithmétiques, un aval pour les accès mémoire et un aval pour les branchements.

Il est possible de scinder les avals précédents en avals plus petits. Par exemple, l'aval pour les instructions arithmétiques peuvent être scindés en plusieurs avals séparés pour l'addition, la multiplication, la division, etc. Niveau accès mémoire, certains processeurs utilisent un aval pour les lectures et un autre pour les écritures. De même, on a un aval différent pour les instructions entières et les instructions flottantes. La longueur de l’aval varie suivant le type d'instructions.

Pipeline avec un nombre variable d'étages par instructions.

Les dépendances structurelles dans un pipeline de longueur variable

L'ALU pour les instructions multicycles est une source de dépendances structurelle. Un exemple est celui où on veut faire deux instructions multicycle identiques à la suite. Par exemple, on veut faire deux multiplications à la suite, en supposant qu'une multiplication fasse 5 cycles. La première multiplication est lancée au premier cycle, la seconde ne peut pas être lancée au cycle suivant : le circuit multiplieur est en cours d'utilisation par la première.

Une solution simple pour éviter cela est de dupliquer le circuit multiplieur. Prenons un exemple : la multiplication prend cinq cycles sur le processeur. Avec une seule ALU, on doit attendre qu'une multiplication en cours soit terminée avant de lancer la suivante. Mais il est possible de lancer une nouvelle multiplication à chaque cycle si on dispose de 5 circuits multiplieurs : on lance une nouvelle multiplication à chaque cycle dans une ALU différente.

La seconde solution consiste à pipeliner, échelonner les instructions. Si jamais vous avez une opération qui prend cinq cycles, pourquoi ne pas lui fournir un seul circuit et l’échelonner en cinq étages ? Pour certains circuits, c'est possible : on peut totalement échelonner une unité de multiplication, par exemple. En faisant ainsi, il est possible de démarrer une nouvelle multiplication à chaque cycle d'horloge dans la même ALU, éliminant ainsi toute dépendance structurelle. Le problème est que certaines instructions s’échelonnent mal, notamment les divisions.

Exemple avec une unité de multiplication séparée, totalement pipelinée.

Dans la réalité, les statistiques montrent qu'il est rare que deux opérations nécessitant plusieurs cycles d’horloge se suivent dans un programme, ce qui fait que les unités de calcul sont rarement dupliquées. Par contre, échelonner un circuit permet un gain de performance pour un cout en circuits généralement ridicules : il suffit d'ajouter quelques registres dans le circuit. La plupart des processeurs se limitent à utiliser un seul circuit multiplieur, qui est éventuellement échelonné.

Une autre forme de dépendance a lieu à l'étage d'enregistrement dans les registres. Imaginons qu'on charge deux instructions à la suite dans le pipeline, mais que l'une prenne un cycle de plus que l'autre. Par exemple, la première prend 6 cycles à s’exécuter, mais la suivante n'en prend que 5. Dans ce cas, la première s’exécutera en 6 cycles, la seconde sera chargée un cycle plus tard et prendra 5 cycles : elles tenteront d'enregistrer leurs données en même temps. Pour le coup, on pourrait résoudre ce problème en ajoutant un port d'écriture dans le banc de registre, mais cela ne résout pas le problème de deux écritures simultanées dans le même registre. La solution idéale est d'insérer des bulles de pipeline pour retarder la seconde instruction.

Le pipeline RISC classique implémentait les instructions multicycles d'une autre manière, du moins dans les premières implémentations. Les instructions multicycles regroupent globalement les multiplications et éventuellement les divisions, ou d'autres instructions arithmétiques assez gourmandes. Elles disposaient de leur propre set de registres rien que pour elles. Ce faisant, il n'y avait pas vraiment de conflits d'accès. Les instructions multicycle s’exécutaient en parallèle dans une unité de calcul spécialisée, et enregistraient leurs résultats dans un banc de registre séparé, ce qui élimine le fait que deux instructions tentent d'écrire en même temps dans le banc de registre.

Dans les exemples précédents, nous avons vu que l'on peut supprimer certaines dépendances structurelles en dupliquant certains circuits. Mais dupliquer des circuits a un cout en transistors qui peut être prohibitif. Échelonner les unités de calcul est une autre solution, mais elle n'est pas tout le temps applicable. Aussi, de nombreux concepteurs de processeurs laissent quelques dépendances structurelles, et les gèrent en insérant des bulles de pipeline si besoin.

Les problèmes causés par les instructions multi-cycles dans un pipeline

L'usage de plusieurs pipelines de longueur variables pose divers problèmes, assez semblables à ceux observés avec les accès mémoire. Si on exécute les instructions dans l'ordre du programme, il se peut qu'elles ne terminent pas dans le même ordre. Par exemple, prenons l'exemple où une instruction multicycle d'une dizaine de cycles, est suivie par une instruction s’exécutant en un seul cycle. La première instruction est lancée au cycle numéro 1, elle enregistre son résultat dans les registres 10 cycles plus tard. La seconde est lancée au cycle 2, mais elle enregistre son résultat dans les registres au cycle numéro 3.

Exemple de problème survenant avec des pipeline de longueur variable

L'ordre d'enregistrement des résultats des instructions s'est inversé, et cela peut causer des problèmes assez sérieux ! Imaginez par exemple que la seconde ait besoin des résultats de la première pour s’exécuter : la seconde instruction aura lu des registres pas encore mis à jour, et donnera un résultat incorrect.

Les problèmes surviennent quand deux instructions dans le pipeline ont une ou plusieurs dépendances de données. Pour rappel, deux instructions ont une dépendance de données quand elles accèdent (en lecture ou écriture) au même registre ou à la même adresse mémoire. Le cas typique est celui où une instruction a besoin du résultat d'une instruction précédente pour s’exécuter. Dans ce cas, la seconde instruction ne doit pas s’exécuter tant que la première n'a pas enregistré son résultat dans les registres, et doit rester dans l'unité de décodage en attendant. C'est le cas le plus évident, mais on a aussi des cas moins intuitifs.

Une limite à une utilisation efficiente du pipeline tient dans l'existence de dépendances entre instructions. Deux instructions ont une dépendance de données quand elles accèdent (en lecture ou écriture) au même registre ou à la même adresse mémoire. Différents cas se présentent alors :

• Read after read : Deux instructions lisent la même donnée, mais pas en même temps.
• Read after write : Une instruction a pour opérande le résultat d'une autre : la première lit le résultat écrit par la seconde.
• Write after read : Une instruction lit une donnée qui est modifiée ultérieurement par une autre instruction.
• Write after write : Deux instructions effectuent des écritures dans le même registre ou la même adresse mémoire, mais pas en même temps.

Pour les dépendances Read after read, on peut mettre les deux instructions dans n'importe quel ordre, cela ne pose aucun problème. Ce ne sont pas de vraies dépendances et je les présente par pur souci d'exhaustivité. Par contre, ce n'est pas le cas avec les trois autres types de dépendances, qui imposent d’exécuter la première instruction avant la seconde.

Dans ce qui va suivre, nous allons nous limiter au cas où les instructions ont pour seules opérandes des registres, mais pas des adresses mémoires, ce qui est le cas pour les instructions de calcul d'un processeur LOAD-STORE. L’exécution dans le désordre totale sera vue dans des chapitres ultérieurs. Avec un tel processeur, les quatre dépendances problématiques sont les suivants :

• Read after write : Une instruction lit un registre dans laquelle l'instruction précédente a écrit.
• Write after read : Une instruction lit un registre pour récupérer une opérande, mais ce registre est ensuite écrasé par une instruction ultérieure.
• Write after write : Deux instructions écrivent dans le même registre, mais à des instants différents.

Les deux dernières dépendances (WAR et WAW) n'existent pas sur un pipeline de longueur fixe, sauf en cas de "défaut de conception" ou de pipeline conçu avec des limitations précises. Mais ce n'est pas le cas avec un pipeline à instruction multicycle, car si l'ordre de démarrage des instructions est respecté, l'ordre des lectures/écritures ne l'est pas. Les dépendances WAR n'apparaissent que sur les pipelines où l'écriture des résultats a lieu assez tôt (vers le début du pipeline), et les lectures assez tard (vers la fin du pipeline). Les dépendances WAW n'apparaissent que si le pipeline autorise les instructions sur plusieurs cycles d’horloge ou les écritures qui prennent plusieurs étages.

Les dépendances WAR et WAW sont souvent appelées des dépendances de nom. Elles sont opposées aux dépendances vraies, à savoir les dépendances RAW. On verra dans quelques chapitres que ces dépendances RAW sont les seules vraies dépendances, les autres provenant du fait qu'un même registre nommé est réutilisé plusieurs fois pour des données différentes.

Les solutions possibles aux problèmes liés aux instructions multicycles

La solution la plus simple est de retarder les instructions problématiques de quelques cycles d'horloges. Si une instruction est trop rapide et risque d'écrire son résultat avant ses prédécesseurs, il suffit simplement de l’exécuter avec un retard de cycles. Pour cela, lorsqu'une instruction multicycle est démarrée, les instructions qui suivent sont bloquées à l'étage de décodage en attendant le bon moment. Lors de cette attente, les étages qui précédent l'unité de décodage sont bloqués en empêchant l'horloge d'arriver aux étages antérieurs au décodage. De plus, le décodeur insère des vides après l'unité de décodage : certains étages seront inoccupés et n'auront rien à faire. Ces vides sont appelés des calages (stall), ou bulles de pipeline (pipeline bubble), terme qui n'est pas très évident au premier abord...

Bulle de pipeline.

Dans la suite du cours, nous verrons de nombreux cas dans lesquels insérer des bulles de pipeline est une obligation si on veut que le processeur fonctionne correctement. Il s'agit là d'une fonctionnalité très importante de tous les pipelines, anciens comme modernes. Évidemment, les bulles de pipeline sont une source de perte de performance : le pipeline ne fait rien tant qu'une instruction n'est pas terminée, ce qui va à l'encontre du principe du pipeline.

Pour éviter cela, les processeurs modernes incorporent des optimisations assez intéressantes pour éviter cela. Par exemple, on peut utiliser le contournement pour réduite l'usage de bulles de pipeline en cas de dépendance Read after write. Le contournement doit adapté sur les processeurs à instructions multicyle, mais il reste le même dans les grandes lignes. La différence est que la sortie de chaque unité de calcul doit être connectée aux entrées de toutes les autres. Le réseau d'interconnexion qui en découle est généralement très complexe.

Une autre méthode exécute des instructions indépendantes dans des unités de calcul séparées. Dans l'exemple précédent avec une instruction multicycle suivie par une instruction normale, on pourrait par exemple détecter les situations où ce n'est pas grave si la seconde instruction finisse avant la première : on peut lors lancer la seconde instruction immédiatement sans attendre. C'est impossible si les deux instructions sont liées, dans le sens où la première a besoin du résultat de la seconde, où si elles utilisent les mêmes registres. Mais c'est possible dans le cas où les deux instructions sont indépendantes.

La technique en question, pas forcément couplée à des lectures non-bloquantes, donne ce qu'on appelle l'exécution dans le désordre, une optimisation commune sur les processeurs modernes qui sera vue en détail dans plusieurs chapitres dans la suite du cours. Le point est que faire ainsi ne fonctionne que si on arrive à détecter que les instructions exécutées en parallèle sont indépendantes. Précisément, deux instructions ont une dépendance de données, si elles manipulent la même donnée, le même registre, la même adresse mémoire.

Ainsi, si une instruction bloque une ALU durant plusieurs cycles, on peut exécuter les instructions suivantes dans une autre ALU, mais seulement si elles sont indépendantes. Si le processeur dispose d'un grand nombre d'unités de calcul séparées, on peut facilement gagner en performances avec cette technique. Là encore, il faut que les instructions exécutées en parallèle ne manipulent pas les mêmes données, ni les mêmes registres, ni les mêmes adresses mémoires.

La différence avec les lectures non-bloquantes est que la technique des lectures non-bloquantes détecte si une instruction est dépendante d'une lecture, alors que l’exécution dans le désordre détectent toutes les dépendances entre instructions, pas seulement les dépendances avec un accès mémoire. Les dépendances de données feront l'objet d'un chapitre entier, aussi passons cela sous silence pour le moment.

Un point important est que cette technique émet les instructions dans l'ordre, mais qu'elles peuvent terminer dans le désordre. En clair, les instructions sont injectées dans les unités de calcul dans l'ordre. En soi, on pourrait chipoter et dire que ce n'est pas vraiment une technique d’exécution dans le désordre, tout est affaire de sémantique. Il faut contraster cela avec les autres techniques d’exécution dans le désordre, qui émettent les instructions dans le désordre. Il faut bien faire la différence entre les techniques d'émission dans l'ordre, et d'émission dans le désordre. Les deux n'ont rien à voir et sont implémentées de manière totalement différentes.

L'étage d'émission : bulles de pipeline et exécution dans le désordre

Pour éviter tout problème, il faut impérativement détecter à l'avance les dépendances de données, et agir en fonction. Pour cela, on rajoute un étage au pipeline, l'étage d'émission (issue), qui détecte les situations problématiques et rajoute des bulles de pipeline si besoin. Il suit immédiatement l'étage de décodage, et est situé avant le chemin de données. L'unité d'émission gère aussi bien les accès mémoire que les instructions multicycle, il peut aussi configurer les circuits de contournement pour les utiliser au mieux . Dans le meilleur des cas, elle gère à la fois l’exécution dans le désordre que les lectures non-bloquantes. Mais il se peut qu'elle ne gère qu'une seule des deux méthodes.

L'implémentation de l'étage d'émission sans exécution dans le désordre

L'unité d'émission doit détecter les dépendances de données entre instructions de calcul. Pour cela, il compare les registres utilisés par l'instruction à émettre et les compare avec les registres manipulés par les instructions émises dans le pipeline. Il n'y a pas de dépendance si ces registres sont différents, alors qu'il y a dépendance dans le cas contraire.

L'unité d'émission doit connaitre les registres de destination des instructions dans le pipeline, ce qui peut se faire de plusieurs manières. La première méthode utilise le fait que les noms de registres sont propagés dans le pipeline, comme tous les signaux de commande. Dans ces conditions, rien n’empêche de relier les registres tampons chargés de la propagation à l'unité d'émission. L'unité d'émission est donc un paquet de comparateurs reliés par des portes OU. En sortie, elle fournit un signal STALL, qui indique s'il faut sortir une bulle de pipeline ou non.

Détection des dépendances dans un pipeline, sans scoreboard.

Une autre implémentation utilise un registre, dont chaque bit est associé à un registre. Le bit numéro 0 est associé au registre numéro 0, le bit numéro 1 au registre numéro 1, etc. Ce registre sera appelé le vecteur de registres dans ce qui suit. Le bit associé à un registre est mis à 1 si le registre est utilisé par une instruction dans le pipeline. Lorsque l'unité d'émission injecte une instruction dans le reste du pipeline, il regarde les registres utilisés et consulte le vecteur de registres. Si un seul de ces registres est associé à un bit à 1 dans le vecteur de registres, il bloque l'instruction tant que le bit ne repasse pas à 0. Sinon, il émet l'instruction et met à jour le vecteur de registres avec les registres utilisés par l'instruction tout juste émise. Le vecteur de registres est aussi mis à jour lorsqu'une instruction écrit son résultat dans un registre, à l'étape d’enregistrement : le vecteur de registres met le bit correspondant à zéro.

L'implémentation des lectures non-bloquantes

L'unité d'émission peut aussi gérer les lectures non-bloquantes. Si on prend l'exemple d'une architecture LOAD-STORE, il vérifie s'il y a un conflit de registre entre accès mémoire et instruction. L'unité d'émission mémorise le registre de destination de la lecture, le registre dans lequel la donnée est chargée. Et elle vérifie les dépendances grâce à ce registre.

Si l'instruction à émettre est un accès mémoire, il est immédiatement bloqué dans le pipeline (du moins, sans techniques avancées de d’exécution dans le désordre). Ensuite, si l'instruction à émettre a ce registre comme opérande, ou comme registre de destination, alors il y a conflit et risque de problème : l'instruction est bloquée dans le pipeline. Mais dans le cas contraire, l'instruction de calcul est indépendante de l'accès mémoire, et peuvent démarrer sans trop de problèmes.

L'implémentation de l'exécution dans le désordre avec scoreboarding

Avec l’exécution dans le désordre, le vecteur de registres est remplacé par une matrice de registres, ou du moins quelque chose d'équivalent qui a la même fonction. Dans son implémentation la plus simple, le circuit équivalent est appelé un scoreboard. C'est un circuit qui commande le circuit d'émission et autorise l’exécution dans le désordre. Grâce à lui, les instructions sont lancées dans le pipeline dans l'ordre, mais elles peuvent s’exécuter dans le désordre et fournir leurs résultats dans le désordre. Cette forme d’exécution dans le désordre s'appelle le scoreboarding.

Un point important du scoreboarding est qu'il émet une instruction par cycle, si les conditions sont réunies. Il faut qu'il y ait absence de dépendance de données, mais aussi absence de dépendances structurelles, les deux étant détectées par l'unité d'émission. L'unité d'émission traite une information par cycle. Si les conditions l'imposent, l'unité d'émission émet des bulles de pipeline et bloque l'instruction dans l'étage d'émission tant que la dépendance n'est pas réglée. L'ensemble du pipeline est bloqué.

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. La séparation entre lecture et écriture dans les registres facilite grandement l'implémentation, car détecter les dépendances demande de détecter quels registres sont lus et écrits.

Scoreboard avec exceptions imprécises

Il faut noter que toutes les dépendances de données ne bloquent pas l'émission. En réalité, 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 et WAR font que les instructions sont retenues dans l'étage d'enregistrement des données. Il faut noter que des techniques d’exécution dans le désordre plus complexes n'ont pas cette contrainte, et peuvent éliminer les dépendances WAR er WAW, mais nous les verrons dans un chapitre dédié.

Pour gérer les dépendances, l'algorithme est assez simple, bien que contre-intuitif : lire dans un registre est autorisé en absence de dépendances pour les écritures, et inversement.

Premier cas : lire dans un registre est autorisé en absence de dépendances pour les écritures. Ainsi, une instruction peut entrer dans l'étage de lecture des registres, seulement si les registres lus ne seront pas écrits par une instruction déjà dans le pipeline. Cela permet de détecter les dépendances RAW, et de mettre en attente les instructions affectées dans l'étage d'émission. Une dépendance de ce type est détectée quand un registre opérande est le registre de destination d'une instruction déjà dans le pipeline. Si c'est le cas, les opérandes de l'instruction ne sont pas disponibles, et l'instruction est mise en attente. Une fois ses opérandes prêts, l'instruction est envoyée à une unité de calcul et est exécutée, sans se soucier de l'ordre des instructions dans le programme. Quand le résultat d'une instruction est calculé, le scoreboard est prévenu par l'unité de calcul, ce qui lui permet de détecter la disponibilité des opérandes.

Second cas : écrire dans un registre est autorisé en absence de dépendances pour les lectures. En théorie, cela permet de gérer les les dépendances WAW et WAR, mais l'implémentation dépend du processeur considéré. Le premier processeur avec un scoreboard, le CDC 6600, bloquait l'instruction dans l'étage d'émission en cas de dépendance WAW : si l'instruction 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.

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

Enregistrement des données dans les registres avec un pipeline avec scoreboarding

Une description du scoreboard du CDC 6600 est disponible dans ce document, qui décrit dans les moindres détails cette architecture : Design of a computer : the CDC 6600

La détection des dépendances structurelles par l'unité d'émission

L'étage d'émission détecte les situations de dépendances structurelles, où un conflit d'accès à l'unité de calcul peut survenir. Si un tel conflit potentiel est détecté, il met en attente l'instruction tant qu'un conflit est possible. Reste à détecter les conflits d'accès, les dépendances structurelles.

Une solution consiste à déterminer les paires d'instructions consécutives qui peuvent donner lieu à des dépendances structurelles. Par exemple, si une instruction de multiplication est dans le pipeline, je sais que je ne peux pas démarrer de nouvelle multiplication immédiatement après, s'il n'y a qu'un seul multiplieur. Détecter les dépendances structurelles consiste à comparer l'opcode de l'instruction à émettre, avec les opcodes des instructions en cours d’exécution dans le pipeline. Si jamais l'opcode de l'instruction à émettre et une opcode dans le pipeline forment une paire d'opérations interdite, il y a dépendance structurelle et on doit insérer des bulles de pipeline.

Les branchements et exceptions précises sur un pipeline avec exécution dans le désordre

L’exécution dans le désordre interagit assez mal avec les branchements, ainsi qu'avec les exceptions. En effet, avec l’exécution dans le désordre, les instructions fournissent leur résultat dans le désordre, les enregistrements dans les registres se font dans le désordre. Or, cela empêche de restaurer l'état initial du processeur après un branchement. Un autre problème survient avec les exceptions matérielles. Les écritures dans les registres ont lieu dans un ordre différent de celui imposé par le programme, ce qui pose problème quand on veut reprendre là où l'exception arrêté le programme.

Mais il y a une solution toute simple : exécuter les instructions dans le désordre, mais de faire les écritures dans les registres l'ordre naturel du programme. Les écritures dans les registres sont donc retardées, tant que les instructions précédentes ne sont pas terminées. Une autre solution effectue les écritures immédiatement, mais corrigent les écritures erronées en cas de problème. Les instructions démarrent dans l'ordre du programme, mais les plus rapides peuvent écrire leur résultat avant les autres.

Toutes ces techniques demandent d'ajouter un étage de pipeline pour remettre les écritures dans l'ordre du programme. Celui-ci est inséré entre l'étage d’exécution et celui d'enregistrement. De plus, le processeur doit mémoriser l'ordre d'émission des instructions en cours dans une mémoire spéciale, à mi-chemin entre mémoire FIFO et mémoire associative. La mémoire en question varie suivant la technique utilisée, elles portent des noms très particulier : un tampon de réordonnancement, un result shift register, etc.

Toujours est-il que ces mémoires contiennent des entrées, des sortes de cases mémoires qui contiennent tout ce qu'il faut mémoriser sur une instruction. Le contenu d'une entrée dépend de la méthode utilisée, mais elle mémorise généralement le registre de destination de la donnée et un identifiant d'instruction (typiquement le program counter). Les entrées sont allouées dans l'ordre d'émission, ce qui fait que les instructions rentrent dans la mémoire à l'étage d'émission. Elles ne sortent quand leur résultat est connu et que toutes les instructions précédentes dans l'ordre du programme se sont exécutées. Il s'agit donc d'une mémoire FIFO. Seulement, il arrive que le contenu d'une entrée soit modifié entre temps.

Le result shift register

Une première implémentation se charge de mettre en attente les écritures en utilisant un result shift register. Ne vous fiez pas à son nom, il s'agit en réalité d'une mémoire FIFO tout bête. Chaque byte de la mémoire mémorise toutes les informations pour décider quand écrire le résultat de l'instruction dans les registres, et comment configurer l'étape d'enregistrement dans les registres.

Elle mémorise : l'unité de calcul utilisée, le registre de destination, et son program counter. L'unité de calcul est utilisée pour savoir comment configurer le multiplexeur qui relie les sorties des ALU au port d'écriture du banc de registres. Cela suppose que le résultat est maintenu en sortie de l'unité de calcul, dans un registre tampon sur cette sortie, tant qu'il n'est pas écrit dans les registres. Le registre de destination sert à configurer le port d'écriture du banc de registres. Le program counter sert surtout pour la gestion des interruptions et exceptions précises. L'ensemble est mémorisé dans un byte, aussi appelé une entrée du result shift register.

Les instructions sont insérées dans ce result shift register dans l'étage d'émission. Si une instruction prend N cycles pour s’exécuter, elle est placée dans le byte numéro N. A chaque cycle, les entrées sont déplacés, décalés : l'instruction passe de l'entrée N à l'entrée N-1. La mémoire se comporte donc comme une sorte de registre à décalage, ou mieux : comme une mémoire FIFO à l'adressage bizarre. Les instructions quittent cette mémoire dans l'ordre des entrées : l'entrée sortante sert à configurer les MUX et le port d'écriture.

Le tampon de réordonnancement

Le tampon de réordonnancent est une technique complémentaire de la précédente, où on insère une mémoire tampon dans laquelle les écritures se font, avant d'être envoyés dans les registres. La technique précédente forçait les résultats à attendre en sortie de l'unité de calcul, si nécessaire. La technique du tampon de réordonnancent fusionne ces registres dans une seule mémoire tampon insérée avec le banc de registres. Le tampon de réordonnancent s'appelle le Re-order buffer en anglais, ce qui fait que j'utiliserais parfois l'abréviation ROB dans ce qui suit.

Les résultats des instructions quittent les unités de calcul dès que possible, mais ils ne sont pas écrits directement dans les registres ou la RAM. A la place, ils sont mémorisés dans le tampon de réordonnancent. Ils quitteront le tampon de réordonnancent dans l'ordre du programme, comme s'il n'y avait pas d’exécution dans le désordre, afin que les résultats soient envoyés aux registres dans le bon ordre.

Un résultat est enregistré dans un registre lorsque les instructions précédentes (dans l'ordre du programme) ont toutes elles-mêmes enregistré leurs résultats. Dit autrement, seule l'instruction la plus ancienne peut quitter le ROB et enregistrer son résultat, les autres instructions doivent attendre. De ce point de vue, le tampon de réordonnancent est donc une mémoire FIFO. Pour garantir que les instructions sont triées dans l'ordre du programme, les instructions sont ajoutées dans le ROB à l'étape d'émission. Les instructions étant émises dans l'ordre du programme, l'ajout des instructions dans le tampon de réordonnancent se fait automatiquement dans l'ordre du programme.

Tampon de réordonnancement.

Le tampon de réordonnancement est un mélange entre une mémoire FIFO et une mémoire associative. En effet, il faut non seulement insérer les résultats dans le tampon de réordonnancent, mais il faut aussi le faire dans le bon ordre. Pour cela, il faut faire le lien entre un résultat et une instruction, ce qui ressemble un petit peu à ce que fait une mémoire cache, d'où le fait que le tampon de réordonnancent ressemble un peu à une mémoire associative.

Les entrées du ROB contiennent de quoi faire le lien entre un résultat et l'instruction associée. Il est possible de le voir comme un result shift register amélioré, sur lequel on aurait ajouté des informations en plus dans chaque entrée. Ce qui fait qu'on retrouve le program counter associé à l'instruction, le registre de destination du résultat, et quelques autres informations. Mais à cela il faut ajouter de quoi mémoriser le résultat, ce qui demande de mémoriser : le résultat de l'instruction, écrit dans un champ initialement laissé vide, et un bit de présence qui est mis à 1 quand le résultat de l'instruction est écrit dans l'entrée. Ce dernier sert à indiquer que le résultat a bien été calculé.

A cela, certaines implémentation ajoutent un bit Exception qui précise si l'instruction a levé une exception ou non. Lorsqu'un résultat quitte le ROB, pour être enregistré dans les registres, le bit Exception est vérifié pour savoir s'il faut ou non vider le ROB. Si une exception a lieu, le ROB se débarrasse des instructions qui suivent l'instruction fautive (celle qui a déclenché l'interruption ou la mauvaise prédiction de branchement) : ces résultats ne seront pas enregistrés dans les registres architecturaux.

Pour rappel, certaines instructions ne renvoient pas de résultat, comme les branchements ou les écritures en mémoire. La logique voudrait que ces instructions ne prennent pas d'entrée dans le ROB. Mais n'oubliez pas qu'on détermine à quelle adresse reprendre en se basant sur le program counter de l'instruction qui quitte le ROB : ne pas allouer d'entrées dans le ROB à ces instructions risque de faire reprendre le processeur quelques instruction à côté. Pour éviter cela, on ajoute quand même ces instructions dans le ROB, et on rajoute un champ qui stocke le type de l'instruction, afin que le ROB puisse savoir s'il s'agit d'une instruction qui a un résultat ou pas. On peut aussi utiliser cette indication pour savoir si le résultat doit être stocké dans un registre ou dans la mémoire.

Rappelons qu'un result shift register suppose que le résultat est maintenu en sortie de l'unité de calcul, dans un registre tampon sur cette sortie. Et cela se marie bien avec la technique du contournement. Mais avec un ROB, les choses sont plus compliquées. Il est possible de garder un réseaux d'interconnexions entre ALU pour gérer le contournement. Mais on peut aussi modifier le tout de manière à récupérer les opérandes à contourner dans le ROB directement. Ainsi, les résultats des instructions sont écrites dans le ROB, et peuvent être lues dedans directement. Les comparateurs utilisés pour déterminer s'il faut contourner ou non sont alors fusionné avec le ROB, ce qui colle bien avec sa nature de mémoire associative. Évidemment, les deux solutions peuvent être mélangées : on peut faire du contournement avec des interconnexion directes entre ALU, et contourner avec le ROB, les deux ne sont pas incompatibles, mais complémentaires. Par exemple, les processeurs avec beaucoup d'ALU regroupent leurs ALU en paires ou groupes de 3/4 ALU, effectuer du contournement direct à l'intérieur de ces groupes, mais effectuent du contournement via le ROB entre ces groupes.

Le ROB est une mémoire FIFO de taille variable, c'est à dire qu'on peut y ajouter un nombre variable d'instructions, jusqu'à une limite maximale. Si la limite maximale est atteinte, le ROB est plein et on ne peut pas y ajouter de nouvelle instruction. En conséquence, le processeur bloque les étages de chargement, décodage, etc.

Le tampon d’historique

Une autre solution laisse les instructions écrire dans les registres dans l'ordre qu'elles veulent, mais conserve des informations pour remettre les écritures dans l'ordre, pour retrouver les valeurs antérieures. Ces informations sont stockées dans ce qu'on appelle le tampon d’historique (history buffer ou HB).

Comme pour le ROB, le HB est une mémoire FIFO dont chaque mot mémoire est une entrée qui mémorise les informations dédiées à une instruction. Lorsqu'une instruction modifie un registre, le HB sauvegarde une copie de l'ancienne valeur, pour la restaurer en cas d'exception. Pour annuler les modifications faites par des instructions exécutées à tort, on utilise le contenu de l'HB pour remettre les registres à leur ancienne valeur. Plus précisément, on vide le HB dans l'ordre inverse d'ajout des instructions, en allant de la plus récente à la plus ancienne, jusqu'à vider totalement le HB. Une fois le tout terminé, on retrouve bien les registres tels qu'ils étaient avant l’exécution de l'exception.

Tampon d’historique.

Le banc de registres futurs

Avec un HB, remettre les registres à l'état normal prend du temps. Pour éviter cela, on peut utiliser deux bancs de registres. Le premier est mis à jour comme si les exceptions n’existaient pas, et conserve un état spéculatif : c'est le banc de registres futurs (future file ou FF). L'autre stocke les données valides en cas d'exception : c'est le banc de registres de retrait (retirement register file ou RRF). Le FF est systématiquement utilisé pour les lectures et écritures, sauf en cas d'exception : il laisse alors la main au RRF. Le RRF est couplé à un ROB ou un HB, histoire de conserver un état valide en cas d'exception.

Banc de registres futurs.