Fonctionnement d'un ordinateur/Les optimisations du chargement des instructions

Les processeurs modernes disposent de plusieurs unités de calcul, de bancs de registres larges et de tout un tas d'optimisations permettent d’exécuter un grand nombre d'instructions par secondes. Les opérations de calcul, les accès mémoire : tout cela est très rapide. Mais rien de cela ne fonctionnerait si l'unité de chargement ne suivait pas le rythme. En soi, l'unité de chargement est simple : le program counter, les circuits pour l'incrémenter et gérer les branchements, l'unité de prédiction de branchement, et de quoi communiquer avec le cache. On doit aussi ajouter le registre d'instruction. Difficile de trouver de quoi l'optimiser, à part rendre l'unité de prédiction plus efficace.

Pourtant, les processeurs incorporent diverses optimisations qui rendent le tout beaucoup plus rapide. La plupart de ces optimisations consistent à ajouter des files d'attente ou des mémoires caches dans le front-end, que ce soit après l'étape de chargement ou de décodage. Les caches en question sont situés en aval du cache d'instruction, ce qui en fait des sortes de cache de niveau 0. Les optimisations incluent le préchargement d'instruction, l'usage de files d'attente pour découpler divers circuits et quelques autres. Voyons lesquelles dans ce chapitre.

Les optimisations de l'unité de chargement

L'unité de chargement contient de nombreux circuits fortement liés entre eux, et on peut découper le tout en plusieurs circuits. L'unité de calcul d'adresse émet les adresses des instructions à charger, qui sont consommées par le cache d'instruction, qui lui-même envoie les instructions lues dans le registre d'instruction ou la file d'instructions. L'unité de calcul d'adresse regroupe : l'unité de prédiction de branchement, le program counter, le circuit pour incrémenter le program counter, les MUX associés pour gérer les branchements.

Le couplage de ces structures fait qu'au moindre défaut de cache d'instruction, l'ensemble stoppe. Par exemple, l'unité de chargement stoppe en cas de défaut de cache. Même chose si jamais une instruction multicycle s’exécute dans le pipeline et bloque toutes les étapes précédentes. Pourtant, il est en théorie possible, et même utile, que certaines structures prennent de l'avance même si d'autres sont bloquées. Par exemple, si le pipeline est bloqué en aval de l'unité de chargement, l'unité de chargement peut en théorie précharger à l'avance des instructions. Ou encore, en cas de défaut de cache d'instruction, l'unité de calcul d'adresse peut précalculer les adresses destinées au cache et les mettre en attente. Pour cela, l'unité de chargement incorpore un paquet de mémoires FIFOs, que nous voir en détail dans ce qui suit.

La prefetch input queue

Avec un pipeline, plusieurs instructions sont présentes en même temps dans le pipeline. Et cela fait que des accès mémoires simultanés peuvent avoir lieu. Pour comprendre pourquoi, regardons dans quels étages du pipeline il peut y avoir un accès mémoire. Le premier, assez évident, est celui dédié aux accès mémoire, lors de l’exécution d'une instruction. Si une instruction effectue un accès mémoire, c'est cet étage qui le prend en charge. Il n'est pas systématique, seules certaines instructions l'utilisent. Par contre, un second étage utilise systématiquement un accès mémoire : le chargement de l'instruction depuis la mémoire ou le cache.

En clair, il n'est pas rare qu'on ait accès simultané à la mémoire : un pour charger l'instruction, un autre pour charger la donnée. Pour éviter cela, une solution simple consiste à séparer les voies d'accès aux instructions et aux données, de manière à autoriser des accès simultanés. Dans le cas le plus fréquent, les processeurs disposent d'un cache, et la solution est alors évidente : le cache L1 est séparé en deux, avec un cache d’instruction séparé du cache L1 de données. Les accès concurrents à la mémoire ne sont plus un problème. Sur les processeurs ne disposant pas de mémoire cache, la solution la plus est d'utiliser une architecture Harvard. Dans tous les cas, il faut utiliser une architecture harvard, ou harvard modifiée (caches séparés).

Sur les architectures Von Neumann, il est possible de limiter la casse en utilisant une optimisation appelée la prefetch input queue, vue dans le chapitre sur le chargement des instructions. l'idée est que le processeur précharge les instructions quand la mémoire est libre, dans une mémoire tampon située avant l'unité de décodage. Si un accès aux données a lieu, le processeur peut décoder les instructions préchargées, en les piochant dans la mémoire tampon, sans accéder à la RAM ou au cache.

Pour implémenter le préchargement d'instruction, le registre d'instruction est remplacé par une mémoire FIFO appelée la Prefetch input queue. On peut la voir comme un registre d'instruction sous stéroïde, capable de mémoriser plusieurs instructions consécutives. Les instructions sont chargées dans la Prefetch input queue et y attendent que le processeur les lise et les décode. Les instructions y sont conservées dans leur ordre d'arrivée, afin qu'elles soient exécutées dans le bon ordre, ce qui fait que la Prefetch input queue est une mémoire de type FIFO. L'étape de décodage pioche l'instruction à décoder dans la Prefetch input queue, cette instruction étant par définition la plus ancienne, puis la retire de la file.

Le premier processeur commercial grand public à utiliser cette méthode était le 8086, un processeur d'Intel de jeu d'instruction x86. Il pouvait précharger à l'avance 6 octets d’instruction. L'Intel 8088 avait lui aussi une Prefetch input queue, mais qui ne permattait que de précharger 4 instructions. La taille idéale de la FIFO dépend de nombreux paramètres. On pourrait croire que plus elle peut contenir d'instructions, mieux c'est, mais ce n'est pas le cas, pour des raisons que nous allons voir dans ce qui suit.

Les branchements posent des problèmes avec la Prefetch input queue : à cause d'eux, on peut charger à l'avance des instructions qui sont zappées par un branchement et ne sont pas censées être exécutées. Si un branchement est chargé, toutes les instructions préchargées après sont potentiellement invalides. Si le branchement est non-pris, les instructions chargées sont valides, elles sont censées s’exécuter. Mais si le branchement est pris, elles ont été chargées à tort et ne doivent pas s’exécuter.

Pour éviter cela, la Prefetch input queue est vidée quand le processeur détecte un branchement. Cette détection ne peut se faire qu'une fois le branchement décodé : on ne sait pas si l'instruction est un branchement ou autre chose tant que le décodage n'a pas eu lieu, par définition. En clair, le décodeur invalide la Prefetch input queue quand il détecte un branchement. Les interruptions posent le même genre de problèmes. Il faut impérativement vider la Prefetch input queue quand une interruption survient, avant de la traiter.

Un autre défaut est que la Prefetch input queue se marie assez mal avec du code auto-modifiant. Un code auto-modifiant est un programme qui se modifie lui-même, en remplaçant certaines instructions par d'autres, en en retirant, en en ajoutant, lors de sa propre exécution. De tels programmes sont rares, mais la technique était utilisée dans quelques cas au tout début de l'informatique sur des ordinateurs rudimentaires. Ceux-ci avaient des modes d'adressages tellement limités que gérer des tableaux de taille variable demandait d'utiliser du code auto-modifiant pour écrire des boucles.

Le problème avec la Prefetch input queue survient quand des instructions sont modifiées immédiatement après avoir été préchargées. Les instructions dans la Prefetch input queue sont l'ancienne version, alors que la mémoire RAM contient les instructions modifiées. Gérer ce genre de cas est quelque peu complexe. Il faut en effet vider la Prefetch input queue si le cas arrive, ce qui demande d'identifier les écritures qui écrasent des instructions préchargées. C'est parfaitement possible, mais demande de transformer la Prefetch input queue en une mémoire hybride, à la fois mémoire associative et mémoire FIFO. Cela ne vaut que très rarement le coup, aussi les ingénieurs ne s’embêtent pas à mettre ce correctif en place, le code automodifiant est alors buggé.

Les files d'instruction

Sur les processeurs modernes, la présence d'une Prefetch input queue stricto sensus n'est pas nécessaire, car ces processeurs disposent d'un cache d’instruction séparé. Mais ils ont une structure matérielle similaire, qui est utilisée pour des raisons totalement différentes. La structure matérielle en question s'appelle la file d'instruction; Comme son nom l'indique, c'est une mémoire FIFO, placée entre le cache d'instruction et les unités de décodage. Les instructions chargées par l'étape de chargement soient accumulées dans la file d'instructions et sont décodées quand l'unité de décodage est prête.

La file d'attente permet de précharger des instructions dans la file d’instructions à l'avance, permettant ainsi de masquer certains accès au cache ou à la mémoire assez longs. L'idée est que les instructions s'accumulent dans la file d'instruction si le processeur exécute les instructions moins vite qu'il ne les charge. C'est généralement signe qu'il effectue une instruction multicycle et/ou qu'il effectue un accès à la mémoire. À l'inverse, la file d'attente se vide quand le processeur éxecute les instructions plus vite qu'il n'en charge. C'est généralement signe qu'un défaut de cache d'instruction est en cours.

La présence d'une file d'attente fait que la première situation est compensée lors de la seconde. Les temps d'attentes liées aux instructions multicycles permettent de remplir la file d'attente, qui est ensuite vidée en cas de défaut de cache. Le processeur exécute en permanence des instructions, sans interruption. Alors que sans file d'attente, les défauts de cache entraineront des temps d'attente où le processeur s’exécuterait rien.

La seule limite de cette optimisation est l'influence des branchements. Lorsqu'un branchement est décodé, ce tampon d’instructions est totalement vidé de son contenu. Ce n'est ni plus ni moins ce que faisait la prefetch input queue des anciens processeurs Intel, dont nous avions parlé dans le chapitre sur l'unité de chargement et le séquenceur.

La macro-fusion

La présence d'une file d'instruction et/ou d'une Prefetch Input Queue permet d'ajouter une optimisation très importante au processeur, qui ne seraient pas possibles sans elle. L'une d'entre elle est la macro-fusion, une technique qui permet de fusionner une suite d'instructions consécutives en une seule micro-opération. Par exemple, il est possible de fusionner une multiplication suivie d'une addition en une seule instruction MAD (multiply and add), si les conditions adéquates sont réunies pour les opérandes. Comme autre exemple, il est possible de fusionner un calcul d'adresse suivi d'une lecture à l'adresse calculée en une seule micro-opération d'accès mémoire. Et enfin, il est possible de fusionner une instruction de test et une instruction de branchement en une seule micro-opération de comparaison-branchement. C'est surtout cette dernière qui est utilisée sur les processeurs Intel modernes.

La macro-fusion est effectuée pendant le décodage, en décodant des instructions dans le tampon d'instruction. Le décodeur reconnait que plusieurs instructions dans le tampon d'instruction peuvent être fusionnées et fournit en sortie la micro-opération équivalent. L'avantage de cette technique est que le chemin de données est utilisé plus efficacement. Notons que la macro-fusion diminue le nombre d'instructions à stocker dans le ROB et dans les différentes mémoires intégrées aux processeur, qui stocke les micro-opérations.

La technique est parfois couplée à un circuit de prédiction, qui détermine si une série d'instruction à fusionner va apparaitre sous peu. L'idée est que dans certains cas, le tampon d'instruction contient le début d'une suite d'instruction combinables. Suivant ce qui sera chargé après, la macro-fusion pourra se faire, ou non. Mais le processeur ne sait pas exactement quelles seront les instructions chargées juste après et il ne sait pas si la macro-fusion aura lieu. Dans ce cas, il peut utiliser un circuit de prédiction de macro-fusion, qui essaye de prédire si les instructions chargées sous peu autoriseront une macro-fusion ou non. Si c'est le cas, les instructions potentiellement fusionnables, le début de la série macro-fusionnable, est mise en attente dans le tampon d'instruction, en attendant les futures instructions.

Le cache de macro-opérations

Le cache de macro-opérations est un cache présent en aval de l'unité de chargement, à côté de la file d’instruction. Il mémorise les dernières instructions envoyées à l'unité de décodage, à savoir non pas les instructions préchargées, mais celles qui sont en cours de décodage ou d’exécution, celles qui ont quitté la file d'instruction. Il sert dans le cas où ces instructions sont ré-éxecutées, ce qui est souvent le cas avec des boucles de petite taille.

A chaque cycle d'horloge, ce cache est consulté, de manière à vérifier si l'instruction voulue est dans ce cache ou non. Cela évite un accès au cache d'instruction. Son implémentation est simple : il s'agit d'un petit cache adressé par le program counter. Si l'instruction a été chargée il y a peu, l'instruction machine est mémorisée dans une ligne de cache, le tag de cette ligne n'est autre que son adresse, le program counter associé. L'accès au cache de macro-opérations est de un seul cycle, pas plus.

L'intérêt n'est pas évident, mais disons que l'accès à ce cache gaspille moins d'énergie qu’accéder au cache d'instruction. C'est là l'intérêt principal, même s'il se peut qu'on puisse avoir un gain en performance. Le gain en question vient du fait que l'accès est plus rapide dans ce cache, ce qui n'est le cas que dans des conditions précise : si le cache d'instruction est pipeliné et a un temps d’accès de plusieurs cycles.

La Fetch Target Queue

Les processeurs modernes incorporent une optimisation assez intéressante : ils découplent l'unité de prédiction de branchement et le program counter de l'accès au cache d'instruction. Pour cela, ils incorporent une mémoire FIFO entre l'unité de prédiction de branchement et le cache d'instruction. Les premiers articles scientifiques, qui ont proposé cette solution, l'ont appelée la Fetch Target Queue, abréviée FTQ. Elle accumule les adresses à lire/écrire dans le cache d'instruction, peu importe que ces adresses viennent du program counter ou de l'unité de prédiction de branchement.

Elle se remplit quand le cache d'instruction est bloqué, soit à cause d'un défaut de cache, soit à cause d'un pipeline bloqué en amont de l'unité de chargement. Par exemple, si le cache d’instruction est bloqué par un défaut de cache, l'unité de prédiction de branchement peut accumuler des prédictions à l'avance dans la FTQ, qui sont ensuite consommées par le cache d'instruction une fois qu'il est redevenu disponible. De même, si l'unité de prédiction de branchement est bloquée par un évènement quelconque, le cache d'instruction peut consommer les prédictions faites à l'avance. Cela arrive sur les unités de branchement modernes, qui peuvent mettre plusieurs cycles pour fournir une prédiction. Dans ce cas, si l'unité de branchement prend beaucoup de cycles pour faire une prédiction, le cache ne l'attend pas et consomme les prédictions disponibles dans la FTQ en attendant.

L'unité de chargement et le cache fonctionnent donc de manière indépendante, les deux ne sont pas forcés d'aller au même rythme. Le principe est similaire à celui de la file d'instruction, qui accumule des instructions en sortie du cache d'instruction. Les deux techniques sont d'ailleurs souvent utilisées ensemble.

Un autre avantage tient dans le fait que les caches d'instructions sont pipelinés, sur le même modèle que les processeurs. On peut leur envoyer une demande de lecture/écriture par cycle, alors que chaque lecture/écriture prendra plusieurs cycles à s'effectuer. L'accès au cache d'instruction a donc une certaine latence. Mais avec une FTQ, cette latence est cachée et ne s'exprime qu'en cas de défaut de cache assez important. Par exemple, si l'accès au cache d'instruction prend 4 cycles, une FTQ qui met en attente 4 adresses camouflera le temps d'accès au cache, tant qu'il n'y a pas de mauvaise prédiction de branchement.

Si le cache d'instruction est multiport et accepte plusieurs accès simultanés, il peut consommer plusieurs entrées dans la FTQ à la fois.

Enfin, la FTQ permet l'implémentation de nombreuses optimisations. Par exemple, le préchargement d'instruction est grandement facilité par la présence d'une FTQ, comme nous allons le voir dans la section suivante.

Une utilisation assez intelligente de la FTQ s'est vu sur les processeurs AMD d'architectures bulldozer. Sur cette architecture, les cœurs étaient regroupés par paquets de deux, et les deux cœurs partageaient certains circuits. Notamment, l'unité de prédiction de branchement était partagée entre les deux cœurs ! Pourtant, chaque cœur disposait de sa propre FTQ !

Le préchargement d'instruction guidé par la prédiction de branchement

Il y a quelques chapitres, nous avions parlé des techniques de préchargement d'instruction, qui permettent de charger à l'avance des instructions dans le cache d'instruction. Nous avions volontairement laissé de côté le préchargement des instructions, pour tout un tas de raisons. Et la raison est justement que la prédiction de branchement et le préchargement des instructions sont fortement liés sur les processeurs modernes. Il est maintenant possible d'aborder le préchargement pour les instructions, d’où cette section.

Notons que par préchargement des instructions, on peut parler de deux formes de préchargement, fortement différentes. La première correspond au préchargement normal, à savoir le préchargement des instructions dans le cache d'instruction L1, à partir du cache L2. Les niveaux de cache en dessous n'utilisent pas vraiment de préchargement d'instruction, bien que ce soit théoriquement possible. Il s'agit donc d'un préchargement dans le cache d'instruction.

Mais il existe aussi une autre forme de préchargement, cette fois-ci liée à la file d'instruction. Pour rappel, la file d'instruction est une mémoire FIFO qui mémorise les instructions chargées, en attendant que le décodeur d'instruction soit disponible. Les instructions sont chargées à l'avance dans la file d'instruction. Nous avions déjà abordé cette forme de préchargement dans le chapitre sur le pipeline, avec la prefetch input queue. Mais il est possible d'améliorer le tout avec la prédiction de branchement.

Les deux formes de préchargement sont techniquement très différentes. L'une précharge du cache L2 vers le L1i, l'autre du cache L1i vers la file d'instruction (qu'on peut voir comme une sorte de cache de niveau 0, de type FIFO). Mais les algorithmes utilisés pour sont sensiblement les mêmes. Aussi, nous allons les voir en même temps. Pour faire la distinction, nous parlerons de préchargement L2-L1i pour la première, de préchargement interne pour l'autre.

Les algorithmes de préchargement d'instructions

Les techniques basiques de préchargement consistent à charger des instructions qui suivent la dernière ligne de cache accédée. Quand on charge des instructions dans le cache d’instruction, les instructions qui suivent sont chargées automatiquement, ligne de cache par ligne de cache. il s'agit due préchargement séquentiel, la technique la plus simple de préchargement, qui profite de la localité spatiale. Elle est utilisée pour précharger des instructions du cache L2 vers le cache L1i, mais aussi pour le préchargement interne dans la file d'instructions.

Mais un prefetcher purement séquentiel gère mal les branchements. Si un branchement est pris, les instructions de destination ne sont pas chargées, si elles ne sont pas dans la ligne de cache suivante. Pour le préchargement L2-L1i, cela ne pose pas de problèmes majeurs, au-delà de la pollution du cache L1i par des instructions inutiles. Mais pour le préchargement interne, c'est autre chose. Les instructions préchargées par erreurs doivent être supprimées pour éviter qu'elles soient décodées et exécutées, ce qui fait que la file d’instruction doit être invalidée.

Il existe des techniques de préchargement plus élaborées qui marchent mieux en présence de branchements. Elles utilisent toutes une collaboration de l'unité de prédiction de branchement. Elles accèdent au Branch Target Buffer, pour détecter les branchements, leur destination, etc. Le tout peut se coupler à la technique du prédécodage. Avec cette dernière, le prédécodage décode en partie les instructions lors de leur chargement dans le cache, et détecte les branchements et leur adresse de destination à ce moment-là. Ces informations sont alors mémorisées dans une table à part, ou dans le BTB. Mais la plupart des designs utilisent le BTB, par souci de simplicité. Il existe globalement deux à trois techniques principales, que nous allons voir dans ce qui suit.

La première technique prédit si le branchement est pris ou non, et agit différemment si le branchement est pris ou non. Si le branchement est pris, elle précharge les instructions à partir de l'adresse de destination des branchements pris. Sinon, elle précharge les instructions suivantes avec préchargement séquentiel. Il s'agit du target line prefetching

Une autre technique ne prédit pas les branchements et précharge à la fois les instructions suivantes avec le next-line prefetching, et la ligne de cache de destination du branchement avec le target line prefetching. Comme ça, peu importe que le branchement soit pris ou non, les instructions adéquates seront préchargées quand même. On appelle cette technique le préchargement du mauvais chemin (wrong path prefetching).

Le target line prefetching est plus complexe à implémenter, car il demande de prédire les branchements. Mais elle a l'avantage de ne pas précharger inutilement deux lignes de cache par branchement, seulement une seule. Par contre, le préchargement est inutile en cas de mauvaise prédiction de branchement : non seulement on a préchargé une ligne de cache inutilement, mais en plus, la ligne de cache adéquate n'a pas été chargée. On n'a pas ce problème avec le préchargement du mauvais chemin, qui garantit que la ligne de cache adéquate est toujours préchargée.

L'implémentation du préchargement interne, dans la file d'instruction

Le préchargement dans la file d'instruction est généralement de type séquentiel, mais certains processeurs font autrement. Déjà, il faut remarquer que le target line prefetching correspond en réalité à la prédiction de branchement classique. L'adresse de destination est prédite, et on charge les instructions adéquates dans la file d'instruction. La prédiction de branchement, associée à une file d'instruction, est donc une forme de préchargement. Il fallait y penser. Enfin, des processeurs assez rares utilisaient le préchargement du mauvais chemin.

Le préchargement du mauvais chemin demande d'utiliser deux files d'instructions séparées. L'une dans laquelle on précharge de manière séquentielle, l'autre dans laquelle on utilise la prédiction de branchement pour faire du target line prefetching. Une fois que l'on sait si la prédiction de branchement était correcte, on est certain qu'une des deux files contiendra les instructions valides. Le contenu de la file adéquate est conservé, alors que l'autre est intégralement invalidée. Le choix de la bonne file se fait avec un multiplexeur. C'est approximativement la technique qui était implémentée sur le processeur de mainframe IBM 370/165, par exemple, et sur quelques modèles IBM similaires.

Le problème est que cette méthode demande de charger deux instructions à chaque cycle. Cela demande donc d'utiliser un cache d'instruction multiport, avec un port par file d'instruction. Le cout en circuit d'un cache double port n'est pas négligeable. Et le gain en performance est assez faible. Le préchargement dans la file d’instruction permet d'économiser quelques cycles lors de l'accès au cache d'instruction, guère plus. Le gain est maximal lorsque les instructions préchargées ont généré un défaut de cache, qui a rapatrié les instructions adéquates pendant que le processeur exécutait les mauvaises instructions, avant que la mauvaise prédiction de branchement soit détectée. Dans ce cas, le défaut de cache a eu lieu pendant la mauvaise prédiction et sa réparation, et non après.

La gestion des branchements successifs

Un autre défaut de cette méthode est la présence de branchements successifs. Par exemple, si jamais on rencontre un branchement, le flux d'instructions se scinde en deux : un où le branchement est pris, un autre où il ne l'est pas. Chacun de ces flux peut lui-même contenir un branchement, et se scinder lui aussi. Et ainsi de suite. Et le processeur doit gérer cette situation en termes de préchargement.

Plusieurs solutions existent. La méthode la plus simple stoppe le chargement du flux en attendant que le premier branchement soit terminé. Cette solution est intuitive, mais est celle où on a les gains en performance les plus faibles. Elle est couramment implémentée d'une manière assez particulière, qui ne correspond pas tout à fait à un stop du chargement, mais qui utilise les lignes de cache. L'unité de préchargement est conçue pour copier des lignes de cache entières dans la file d'instruction. Le processeur (pré-)charge deux lignes de cache : celle du bon chemin, celle du mauvais chemin. Il les précharge dans deux files d'instructions, qui contiennent généralement une ligne de cache grand maximum. Le temps que l'on ait chargé les deux files d'instruction, le résultat du branchement est connu et on sait laquelle est la bonne.

L'autre possibilité est d'utiliser la prédiction de branchement pour ce flux, afin de poursuivre le chargement de manière spéculative. Elle donne de bonnes performances, mais demande des unités de prédiction de branchement spéciales, dans le cas où les deux flux tombent sur un branchement en même temps. Cette technique est indirectement liée au cache de traces que nous verrons dans le chapitre sur les processeurs superscalaires. Nous n'en parlons pas ici, car ce genre de techniques est plus liée aux processeurs superscalaires qu'un processeur avec un pipeline normal.

Une autre possibilité consiste à scinder ce flux en deux et charger les deux sous-flux. Cette dernière est impraticable car elle demande des caches avec un grand nombre de ports et la présence de plusieurs files d'instructions, qui sont utilisées assez rarement.

Les processeurs à exécution de chemins multiples

L'idée précédente peut en théorie être améliorée, afin de non seulement charger les instructions en provenance des deux chemins (celui du branchement pris, et celui du branchement non pris), mais aussi de les exécuter : c'est ce qu'on appelle l'exécution stricte (eager execution). Bien sûr, on n’est pas limité à un seul branchement, mais on peut poursuivre un peu plus loin.

Quelques papiers de recherche ont étudié l'idée, mais ses défauts font qu'elle n'a jamais été utilisée dans un processeur en dehors de prototypes destinés à la recherche. Le gros problème de l'exécution stricte est qu'on est limité par le nombre d'unités de calculs, de registres, etc. Autant ce serait une technique idéale sur des processeurs avec un nombre illimité de registres ou d'unités de calcul, autant ce n'est pas le cas dans le monde réel. Au bout d'un certain nombre d’embranchements, le processeur finit par ne plus pouvoir poursuivre l’exécution, par manque de ressources matérielles et doit soit stopper, soit recourir à la prédiction de branchement. Il y a le même problème avec le préchargement interne simple, quand on utilise le préchargement du mauvais chemin, comme vu juste au-dessus.

L'implémentation matérielle du préchargement de cache L2-L1i

Pour comprendre comment s'effectue le préchargement L2-L1i, il faut regarder comment l'unité de chargement communique avec les caches. L'unité de prédiction de branchement est généralement regroupée avec le program counter et les circuits associés (les incrémenteurs/MUX associés), pour former l'unité de chargement proprement dite. L'unité de chargement émet des adresses consommées par le cache d'instruction, qui lui-même envoie les instructions lues dans le registre d'instruction ou la file d'instructions.

Le couplage de ces structures fait qu'au moindre défaut de cache d'instruction, l'ensemble stoppe. Et notamment, l'unité de prédiction de branchement stoppe en cas de défaut de cache. Même chose si jamais une instruction multicycle s’exécute dans le pipeline et bloque toutes les étapes précédentes. Les pertes de performance ne sont pas très importantes, mais elles existent. Et le préchargement se manifeste dans ces situations.

Le préchargement d'instructions consiste à découpler ces structures de manière à ce qu'elles fonctionnent plus ou moins indépendamment. Le but est qu'en plus des accès normaux au cache d'instruction, l'unité de chargement envoie des informations au cache L2 ou L1i en avance, pour effectuer le préchargement. L'unité de chargement doit alors prendre de l'avance sur le cache, pour effectuer les accès au cache L2 en avance, tout en maintenant l'état normal pour effectuer les accès normaux. C'est donc plus ou moins l'unité de chargement qui s'occupe du préchargement, ou du moins les deux sont très liées.

L'anticipation du program counter

Avec la solution la plus simple, on a une unité de chargement qui s'occupe des accès au cache d'instruction, et une unité de préchargement qui prend de l'avance sur l'unité de chargement, et communique avec le cache L2. La technique la plus basique se base sur un Lookahead program counter, un second program counter qui ne fonctionne que lors d'un défaut de cache d'instruction. Il est initialisé avec le program counter lors d'un défaut de cache, puis il est incrémenté à chaque cycle et les branchements sont prédits, ce qui fait qu'il est mis à jour comme si l’exécution du programme se poursuivait, alors que le reste du processeur est mis en attente.

La technique initiale utilisait ce second program counter pour accéder à une table de prédiction, qui associe à chaque valeur du program counter, l'adresse des données chargées par l'instruction associée. Les adresses fournies à chaque cycle par cette table sont alors envoyées aux unités de préchargement pour qu'elles fassent leur travail. La technique permettait donc de précharger des données en cas de défaut de cache, mais pas d'instructions. Il ne s'agissait pas d'une technique de préchargement des instructions, mais de préchargement de données.

La technique a ensuite été adaptée pour le chargement des instructions par Chen, Lee et Mudge. Leur idée utilisait deux unités de prédiction de branchements : une couplée à l'unité de chargement, l'autre pour le préchargement. La première utilisait le program counter normal, l'autre se déclenchait en cas de défaut de cache et utilisait un lookahead program counter. Les adresses générées par le lookahead program counter étaient envoyée au cache d'instruction, sur un port de lecture séparé. La ligne de cache lue était alors prédécodée pour détecter les branchements, qui étaient prédits, et rebelote. Il est possible d'adapter la méthode pour que les adresses soient accumulées dans une mémoire FIFO, et étaient consommée par le cache d'instruction L2 pour le préchargement si la ligne de cache associée n'était pas dans le cache d’instruction.

Les techniques modernes n'utilisent plus de seconde unité de prédiction de branchement, mais conservent un lookahead program counter. Par contre, le BTB dispose de plusieurs ports : un pour la prédiction de branchement normale, l'autre pour le préchargement. L'unité de préchargement et l'unité de chargement accèdent toutes deux au BTB quand elles ont besoin de faire leurs prédictions, en parallèle. Typiquement, le BTB est accédé à chaque cycle pour la prédiction de branchement, à un rythme plus faible pour le préchargement.

Le Fetch Directed Instruction Prefetching

Les processeurs modernes semblent utiliser un algorithme connu sous le nom de Fetch Directed Instruction Prefetching. Il utilise les adresses contenues dans la FTQ pour précharger les instructions adéquates du cache L2 vers le cache L1 d'instruction (L1i). L'unité de préchargement est placée en aval de la FTQ, elle lit son contenu, détecte quelles adresses correspondent à des lignes de cache à précharger, et envoie celles-ci au cache L2. Le préchargement du L2 vers le L1i a lieu quand le cache L2 est inutilisé, ou du moins quand il peut accepter une nouvelle lecture (dans le cas d'un cache multiport et/ou pipeliné).

On peut améliorer légèrement le design précédent sur plusieurs points. Pour éviter de polluer le cache L1 avec des lignes de caches préchargées à tort, il est possible d'ajouter un équivalent des stream buffer vus dans le chapitre sur le préchargement. Il s'agit d'une autre mémoire FIFO qui mémorise les lignes de cache préchargées. Les lignes de cache préchargées ne sont pas placées dans le cache L1i, mais dans cette file d'attente. Lors d'un accès au L1i, la file d'attente est consultée en parallèle. Si l'instruction voulue est dans la file d'attente, elle est lue depuis la file, et la ligne de cache associée est copiée dans le cache L1i. Mais c'est là une possibilité facultative.

Un autre point est que l'unité de préchargement doit attendre que le cache L2 puisse accepter une nouvelle lecture pour lancer le préchargement d'une autre ligne de cache. Pour corriger cela, on ajoute une file d'attente entre le cache L2 et l'unité de préchargement, qui est évidemment une mémoire FIFO. Son utilité dépend des temps de lectures du cache L2, ainsi que de la taille de la FTQ. Elle n'est pas toujours nécessaire, certains processeurs ont un cache L2 assez lent pour qu'on ne puisse précharger qu'une seule ligne de cache avant que la FTQ soit complétement vide.

Ces deux optimisations sont facultatives, mais elles étaient présentes dans l'article originel qui a proposé la technique.

L'unité de préchargement doit détecter quelles sont les adresses de la FTQ qui ne sont pas déjà chargées dans le L1i. En effet, il est inutile de précharger une ligne de cache si celle-ci est déjà dans le cache L1i. L'unité de préchargement doit donc filtrer au mieux les adresses de la FTQ en deux classes : celles qui correspondent à une ligne de cache déjà dans le L1i, celles qui doivent être préchargées.

Pour cela, l'unité de préchargement utilise la technique dit du Cache Probe Filtering. L'idée part du principe que le cache d'instruction L1 est multiport. Les ports du cache d'instruction ne sont pas toujours utilisés en même temps et il arrive qu'il y ait un port de lecture de libre. Le CPF utilise alors ce port inutilisé pour vérifier si la prochaine ligne de cache à précharger est dans le cache ou non. Si c'est le cas, on aura un succès de cache : la ligne de cache est oubliée, elle ne sera pas préchargée. Si ce n'est pas le cas on aura un défaut de cache : la ligne sera préchargée.

Notez que l'on a pas besoin de lire la ligne en question, juste de vérifier les tags du cache. Dans ce cas, on peut ajouter des signaux de commande spécifiques pour le CPF, qui font une demi-lecture, qui ne vérifie que les tags, mais ne lit pas la donnée. On peut par exemple ajouter un port spécifique pour le CPF, purement en lecture et qui ne permet que de vérifier les tags. Ce port en plus a un cout en circuits plus faible qu'un port de lecture normal, mais ce n'est pas gratuit du tout.

Les optimisations de l'unité de décodage

Outre les caches et files d'attentes dans l'unité de chargement, il existe des files d'attentes en sortie de l'étape de décodage, qui ont une utilité similaire. Dans cette section, nous allons parler de ces caches. Ils sont au nombre de trois : le cache de micro-opérations, la file de micro-opérations, et le loop stream detector. Les deux caches servent à accélérer les boucles, la file de micro-opérations à découpler l'unité de décodage du reste du processeur.

La file de micro-opérations

Sur certains processeurs modernes, la sortie du décodeur est reliée à une mémoire FIFO semblable à la file d'instruction, mais placée entre le décodeur et le reste du processeur. Elle mémorise les micro-opérations émises par le décodeur, et les met en attente tant que le reste du pipeline n'est pas prêt. Nous l’appellerons la file de micro-opérations, mais le nom classiquement utilisé est file d'instruction, terme polysémique utilisé pour d'autres files d'attentes dans le pipeline. Nous utiliserons le dernier terme, par simplicité.

Elle se place entre l'unité de décodage et l'unité d'émission. L'unité de décodage accumule des instructions dans la file de micro-opérations tant qu'elle n'est pas pleine, elle ne tient pas compte de ce que fait l'unité d'émission. L'unité d'émission regarde l'instruction qui est au bout de la file, celle qui est la plus ancienne, et elle vérifie si elle peut s'exécuter. Si c'est le cas, l'instruction est retirée de la FIFO et est envoyée aux ALU, on dit qu'elle est dépilée. Si ce n'est pas le cas, elle n'est pas émise, et aucune instruction n'est dépilée.

La file de micro-opérations permet aux décodeurs de faire leur travail même si le reste du pipeline n'est pas prêt. Par exemple, imaginons qu'une instruction ne peut pas être émise, soit parce qu'une instruction multicycle est en cours d’exécution, soit car l'ALU n'est pas libre ou toute autre raison. Sans file de micro-opérations, le pipeline devrait être totalement bloqué tant que l'instruction ne peut pas être émise, une bulle de pipeline est émise (voir chapitre sur les dépendances de données/structurelles). Mais avec une file de micro-opérations, le pipeline peut continuer à charger et décoder des instructions, l'instruction qui ne peut pas être émise ne bloque pas tout le pipeline.

L'unité d'émission met en attente les instructions dans la file de micro-opérations, mais le décodeur peut continuer à accumuler des instructions décodées dans la file de micro-opérations. En clair, la file de micro-opérations met en attente les instructions quand une instruction ne peut pas être émise.

Et à l'inverse, elle permet d'émettre des instructions quand les unités de décodage/chargement sont bloquées. Le cas classique est celui d'un défaut de cache dans le cache d'instruction. Des instructions ne peuvent plus être chargée et décodées durant quelques cycles. Sans file de micro-opérations, le processeur ne peut plus rien faire durant quelques cycles. Mais avec une file de micro-opérations, il peut en profiter pour émettre les instructions en attente dans la file de micro-opérations. En clair, si l'unité d'émission a mis en attente des instructions, le processeur se rattrape au prochain défaut de cache d'instruction.

Une autre situation où le décodeur bloque est le cas où certaines instructions mettent du temps à être décodées. C'est notamment le cas de certaines instructions complexes, dont le décodage prend facilement 2 à 3 cycles d'horloge, voire plus. Le pire est le décodage des instructions microcodées, qui peut demander plusieurs cycles. Or, le pipeline demande qu'on décode une instruction par cycle pour éviter de bloquer le pipeline. Mais ce temps de décodage peut être masqué si des micro-opérations sont en attente dans la file, elles sont exécutées pendant le décodage long.

La présence d'une file de micro-opération permet d'effectuer diverses optimisations. La plus importante est celle de la micro-fusion, qui fusionne deux micro-opérations simples et une seule micro-opération complexe. Par exemple, sur certains processeurs, le chemin de données est capable d'effectuer une lecture/écriture en adressage base+index en une seule micro-opération. Mais le jeu d'instruction est une architecture Load-store où le calcul d'adresse et l'accès mémoire se font en deux instructions séparées. Dans ce cas, la micro-fusion peut faire son travail et fusionner le calcul d'adresse avec l'accès mémoire.

C'est une optimisation compatible avec la macro-fusion, les deux se ressemblant beaucoup. On peut se demander pourquoi les deux existent ensemble. La raison est historique, et tient au design des processeurs x86. Les premiers processeurs x86 avaient un chemin de données simple, avec les décodeurs qui allaient avec. Sur de tels processeurs, le calcul d'adresse et l'accès mémoire étaient séparés en deux instructions. Puis, avec l'évolution de la technologie, le chemin de données est devenu capable de faire les deux en une seule micro-opération. Pour compenser cela, Intel et AMD auraient pu changer leurs décodeurs en profondeur. A la place, ils ont préféré utiliser la technique de la micro-fusion, par simplicité.

Le cache de micro-opérations

Le cache de micro-opérations mémorise les N dernières micro-opérations exécutées par le processeur. Il est adressé par le program counter. Si jamais une instruction machine doit être ré-éxecutée, ses micro-opérations sont déjà présentes dans ce cache et on n'a pas à décoder l'instruction une nouvelle fois. Ce genre de cas survient lorsqu'on exécute une boucle, ce qui fait que ce cache accélère les boucles.

La différence avec le loop stream detector est que la boucle doit s’exécuter à l'identique avec un loop stream detector, pas avec un cache de micro-opérations. Avec un cache de micro/macro-opération, ce n'est pas le cas. Prenons l'exemple d'une boucle contenant quelques instructions suivies par un IF...ELSE. Il arrive qu'une itération de la boucle exécute le IF, alors que d'autres exécutent le ELSE. Dans ce cas, le loop stream detector ne sera pas activé, car la boucle ne s’exécute pas pareil d'une itération à l'autre. Par contre, avec un cache de macro/micro-opération, on pourra lire les instructions précédant le IF...ELSE dedans.

Une autre conséquence est que le front-end n'est pas éteint lorsqu'on accéde au cache de micro-opérations. Avec un loop stream detector, on est certain que la boucle s’exécutera à l'identique, donc on coupe les décodeurs et les unités de chargement, en laissant fonctionner que l'unité de prédiction de branchement et le program counter. Mais cette garantie n'est pas garantie avec un accès au cache de micro-opération : peut-être que certaines micro-opérations seront réutilisées, pas d'autres. A vrai dire, si ce cache est couplé à un loop stream detector, on est certain que non.

Le cache de micro-opération est alimenté par l'unité de décodage. Quand le décodeur d'instruction a fini de décoder une instruction, il l'envoie dans la suite du pipeline. La micro-opération décodée est alors insérée dans le cache de micro-opération. Attention, cependant, ce n'est le cas que dans des cas simples, où la micro-opération est directement envoyée dans le reste du pipeline. Sur les processeurs avec une file de micro-opérations, ce sont les micro-opérations qui quittent la file d'attente sont insérées dans le cache, pas celles qui quittent directement le décodeur.

Il est plus ou moins équivalent au cache de macro-opérations, sauf qu'il se situe après l'unité de décodage. Il ne mémorise pas des instructions machines, mais des micro-opérations. La taille du cache de micro-opérations est limitée, aussi il est intéressant de le comparer au cache de macro-opérations. Niveau capacité des deux caches, l'encodage des instructions machines est plus compact que la ou les micro-instructions équivalente, ce qui est un avantage pour le macro-opérations à capacité équivalente. Mais à nombre de transistors équivalent, les choses sont différentes.

Niveau décodage des instructions, il y a une différence assez marquée. Le cache de macro-opérations impose que les instructions dans ce cache soient décodées. Par contre, avec un cache de micro-opération, les instructions ne doivent plus être décodées et renommées. L'absence de décodage fait que l’exécution totale de l'instruction (décodage inclus) est plus rapide. Le gain est d'autant plus important si les instructions ont un encodage complexe, ou si les instructions sont à longueur variable, ce qui rend leur décodage complexe et donc lent. Globalement, plus le décodage est complexe et/ou long, plus le cache de micro-opérations fait des merveilles.

Il existe deux méthodes différentes pour implémenter le cache de micro-opération. La première est la plus intuitive : on mémorise des micro-opérations décodées dans le cache, avec une micro-opération par ligne de cache. Elle est utilisée sur les processeurs AMD, et sans doute sur les processeurs Intel récents. Mais les anciens processeurs Intel, comme ceux des architectures Sandy Bridge et Netburst, utilisent une autre méthode. Chaque ligne de cache mémorise non pas la micro-opération, mais un pointeur vers le control store, qui indique à quelle adresse dans le micro-code se situe la micro-opération. La micro-opération est donc lue depuis le micro-code lors de l'émission.

Il faut noter que pour des raisons de performance, le cache de micro-opérations est virtuellement tagué, ce qui fait qu'il est invalidé en cas de changement de programme. Sur l'architecture Sandy Bridge, il est carrément inclus dans le cache L1, les deux sont des caches inclusifs l'un avec l'autre. Les premières implémentations étaient très limitées. Les micro-opérations devaient être séquentielles dans le code, le cache était consulté seulement après un branchement et non à chaque émission d'instruction, pour limiter la consommation d'énergie an détriment des performances. Ces limitations ne sont pas présentes sur les architectures récentes.

Le Loop Stream Detector

Le loop stream detector détecte certaines boucles dans la file de micro-opérations et optimise leur exécution. Il permet d'utiliser le contenu de la file de micro-opération comme une sorte de pseudo-cache dans lequel lire les micro-opérations d'une petite boucle. L'intérêt est d'éviter que les instructions de la boucle soient chargées et/ou décodées plusieurs fois de suite. Les instructions de la boucle sont lues dans la file de micro-opération et sont injectées directement dans la suite du pipeline. De plus, les unités de chargement et de décodage sont désactivées pendant l’exécution de la boucle.

Le processeur détecte l’exécution des boucles et il active automatiquement ce pseudo-cache quand le processeur détecte une seconde exécution de la boucle. La totalité de ce qui précède la file de micro-opération est désactivé tant que la boucle s’exécute normalement. Le processeur reprendre une exécution normale quand on quitte la boucle ou quand son exécution change, par exemple quand un if...else, un return ou tout autre changement de flot de contrôle a lieu. Vu que toutes ces situations impliquent un branchement qui n'a pas été pris comme avant, le processeur n'utilise plus le loop stream detector en cas de mauvaise prédiction de branchement. Les autres caches ne fonctionnent pas sur le même principe.

Évidemment, la taille des boucles optimisées ainsi est limitée par la taille de la file de micro-opération, ce qui fait que l'optimisation ne fonctionne que pour des boucles de petite taille. Il y a aussi des contraintes quant au nombre de branchements à l'intérieur de la boucle et le nombre d'accès mémoire. De plus, toute la file de micro-opération n'est pas gérée par le lopp stream detector. Par exemple, les processeurs avec une file de micro-opération de 64 micro-opération peuvent gérer des boucles de maximum 32 à 40 micro-opérations.

◄ Retour vers « La prédiction de branchement »

Sommaire du livre

Continuer vers « L'émission dans l'ordre des instructions » ►