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 : la file d'instruction et le cache de macro-opération

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 file de micro-opérations et le cache de micro-opérations

Sur les processeurs modernes, la sortie du décodeur est reliée à une mémoire FIFO semblable à la file d'instruction, mais placée juste après le décodeur. 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, par simplicité. Le schéma ci-contre indique que la file de micro-opérations est située en sortie de l’unité de décodage, avant l'unité d'émission et avant l'unité de renommage de registres (que nous aborderons dans quelques chapitres).

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 que le processeur ne peut pas émettre de nouvelle instruction, soit car toutes les ALUs sont occupées, soit car il y a un accès mémoire qui bloque le pipeline, peu importe. Sans file de micro-opérations, tout ce qui précède l'unité d'émission devrait être totalement bloqué tant que l'instruction ne peut pas être émise. Mais avec une file de micro-opérations, le pipeline peut continuer à charger et décoder des instructions, et 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 des bulles de pipeline sont émises.

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 file de micro-opération est souvent complétée par plusieurs circuits, dont un circuit de micro-fusion, un cache de micro-opérations et le loop stream detector. Voyons ces circuits dans ce qui suit.

La micro-fusion

La présence d'une file de micro-opération permet d'effectuer une optimisation appelée la micro-fusion. Elle remplace deux micro-opérations simples consécutives en une seule micro-opération complexe équivalente. 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 Loop Stream Detector

Les boucles sont une opportunité d'optimisation très intéressante sur les CPU avec une file de micro-opérations. L'idée est que lors d'une boucle, des instructions sont chargées, décodées et exécutées plusieurs fois de suite. Mais à, chaque répétition d'une instruction, le chargement et le décodage donnent toujours le même résultat, seule l'exécution n'est pas la même (les registres renommés sont aussi différents, mais passons). L'idée est simplement de mémoriser les N dernières instructions décodées et de les ré-exécuter si besoin. Ainsi, on évite de charger/décoder une même instruction machine plusieurs fois, mais de réutiliser les micro-opérations déjà décodées.

L'implémentation la plus simple conserve les N dernières instructions décodées dans la file d'instruction, qui se comporte alors comme une sorte de pseudo-cache FIFO. Un circuit annexe, appelé le Loop Stream Detector (LSD), détecte lesboucles dans la file de micro-opérations et optimise leur exécution. Avec un LSD, la file d'instruction ne supprime pas les micro-opérations une fois qu'elles sont émises. Elle mémorise là où se trouve la dernière micro-opération émise, mais conserve celles qui ont déjà été émises. Si une boucle adéquate est détectée par le Loop Stream Detector, les micro-opérations 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, ce qui réduit la consommation d'énergie du CPU.

L'optimisation accélère les petites boucles, à condition qu'elles s'exécutent de la même manière à chaque exécution. De telles boucles exécutent une suite de N instructions, qui reste identique à chaque itération de la boucle. Le cas le plus simple est celui d'une boucle dans laquelle il n'y a pas de branchements. Pour les boucles normales, le processeur reprend 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.

L'optimisation vise surtout à désactiver les décodeurs et l'unité de chargement lors de l'exécution d'une boucle. La désactivation peut être du clock gating, voire du power gating, être partielle ou totale. Dans le pire des cas, les unités de chargement peuvent continuer à charger des instructions en avance dans une file d'instruction, mais les décodeurs peuvent être désactivés. Dans le meilleur des cas, 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. Y compris le cache de micro-opération.

Les CPU Intel modernes disposent d'un loop stream detector, les CPU AMD en avaient sur les microarchitectures Zen 4 mais il a disparu sur la microarchitecture Zen 5. Quelques CPU ARM avaient aussi un loop stream detector, notamment le Cortex A15. É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. De plus, toute la file de micro-opération n'est pas gérée par le loop 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. Pour donner quelques chiffres, les processeurs ARM Cortex A15 géraient des boucles de maximum 32 micro-opérations.

Mais les contraintes principales portent sur la détection des boucles. Le Loop Stream Detector ne peut pas détecter toutes les boucles qui existent, et certaines boucles ne sont pas détectées. Par exemple, le Loop Stream Detector' ne peut pas détecter les boucles si un appel de fonction a lieu dans la boucle. 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.

Il faut noter que le loop stream detector a été désactivé par des mises à jour de microcode sur quelques architectures, comme sur la microarchitecture Zen 4 d'AMD ou les CPU de microarchitecture Skylake et Kaby Lake d'Intel. Pour la microarchitecture Skylake , les raisons officielles pour cette désactivation sont un bug lié à l'interaction avec l'hyperthreading. Il est vraisemblable que des bugs ou des problèmes de sécurité aient amené à la désactivation sur les autres architectures.

Le cache de micro-opérations

Le cache de micro-opérations a le même but que le Loop Stream Detector, à savoir optimiser l'exécution des boucles. La différence avec le Loop Stream Detector est qu'il y a un cache séparé de la file de micro-opérations, qui mémorise des micro-opérations décodées, dans le cas où elles soient réutilisées par la suite. La première itération d'une boucle décode les instructions en micro-opérations, qui sont accumulées dans le cache de micro-opérations. Les itérations suivantes de la boucle vont chercher les micro-opérations adéquates dans le cache de micro-opération : on n'a pas à décoder l'instruction une nouvelle fois.

Intuitivement, vous vous dites que son implémentation la plus simple mémorise les N dernières micro-opérations exécutées par le processeur, ce qui en fait un cache FIFO. Mais la réalité est que c'est déjà ce qui est fait par le couple LSD + file de micro-opération. Le cache de micro-opérations a une politique de remplacement des lignes de cache plus complexe que le FIFO, typiquement une politique LRU ou LFU approximée. De plus, le cache de micro-opération est séparé de la file de micro-opération. Et il est alimenté non pas par l'unité de décodage, mais par la file de micro-opérations. Ce sont les micro-opérations qui quittent la file de micro-opérations qui sont insérées dans le cache, pas celles qui quittent directement le décodeur.

Les avantages sont les mêmes qu'avec un Loop Stream Detector : une consommation énergétique réduite, des performances légèrement améliorées. Le décodeur et l'unité de chargement sont inutiles en cas de succès dans le cache de micro-opération, ce qui fait qu'ils sont désactivés, éteints, ou du moins subissent un clock-gating temporaire. Ils ne consomment pas d'énergie, seul le cache de micro-opération utilise de l'électricité. L'avantage en termes de performance est plus faible, assez variable suivant la situation, mais aussi bien le cache de micro-opérations que le LSD ne font pas de mal.

La différence avec le cache de micro-opération est que la boucle doit s’exécuter à l'identique avec un Loop Stream Detector, pas avec un cache de micro-opérations. 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. Le cache de micro-opération est donc plus efficace que le Loop Stream Detector, mais pour un cout en transistor plus élevé.

Le cache de micro-opérations et le Loop Stream Detector font la même chose, mais certains processeurs implémentaient les deux. L'avantage est que le cache de micro-opération peut être désactivé si jamais le LSD détecte une boucle dans la file d'instruction, ce qui réduit encore plus la consommation énergétique. En pratique, l'impact sur la consommation énergétique est très difficile à mesurer, mais il rajoute de la complexité pour la conception du processeur.

Le cache de micro-opération associe, pour chaque instruction machine, une ou plusieurs micro-opérations. Avec l'implémentation la plus simple, une ligne de cache est associée à une instruction machine. Par exemple, sur les processeurs Intel de microarchitecture Skylake, chaque ligne de cache était associée à une instruction machine et pouvait contenir de 1 à 6 micro-opérations. La suite de micro-opérations correspondant à une instruction devait tenir toute entière dans une ligne de cache, ce qui fait que les instructions décodées en plus de 6 micro-opérations ne pouvaient pas rentrer dans ce cache.

L'accès au cache de micro-opération se fait lors de l'étape de chargement. Le cache de micro-opérations est adressé en envoyant le program counter sur son entrée d'adresse, en parallèle du cache d'instruction. Le cache de micro-opération est une voie de chargement parallèle au front-end proprement dit. En clair, il y a une voie qui regroupe cache d'instruction, file d'instruction et décodeur, et une seconde voie qui se résume au cache de micro-opération. Les deux voies sont accédées en parallèle. En cas de succès dans le cache de micro-opération, les micro-opérations adéquates sont lues directement depuis le cache de micro-opération.

Il existe deux méthodes différentes pour encoder les micro-opérations dans le cache de micro-opérations. La première est la plus intuitive : on mémorise les micro-opérations dans la ligne de cache, directement. 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. Une ligne de cache mémorise non pas les micro-opération directement, 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.

Aussi bien le cache de macro-opérations que le cache de micro-opérations optimisent l'exécution des boucles, mais ils ne sont pas au même endroit dans le pipeline : avant et après l'unité de décodage. Et le premier mémorise des instructions machines, l'autre des micro-opérations décodées. Les avantages et inconvénients sont totalement différents. 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 cache de macro-opérations à capacité équivalente. Par contre, le cache de micro-opérations permet de désactiver les décodeurs en cas de succès de cache, vu que les instructions ne doivent plus être décodées et renommées. 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.

Le préchargement d'instructions et 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.

Une utilisation assez originale 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 !

Un avantage de la FTQ 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, qui est partiellement masquée par la FTQ au point où elle 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. La FTQ est aussi très utile avec les unités de branchement modernes, qui peuvent mettre plusieurs cycles pour fournir une prédiction. Prendre de l'avance avec une FTQ amorti partiellement le temps de calcul des prédictions.

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.

Mais l'avantage principal de la FTQ est qu'elle permet l'implémentation d'une optimisation très importante. 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. Il s'agit donc d'un préchargement dans le cache d'instruction. Mais il existe aussi une autre forme de préchargement, qui consiste à précharger à l'avance des instructions dans la file d'instruction et qui a été abordée dans la section sur la prefetch input queue. Les deux formes de préchargement n'ont pas lieu au même endroit dans la hiérarchie mémoire : l'une précharge du cache L2 vers le L1i, l'autre du cache L1i vers la file d'instruction (ou dans le cache de macro-opération). 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.

◄ Retour vers « La prédiction de branchement »

Sommaire du livre

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