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

Les processeurs avec un pipeline sont découpés en deux sections : un front-end qui charge et décode les instructions, et un ou plusieurs back-end qui exécutent les instructions. L'exécution des micro-opérations est optimisée par des techniques que nous verrons dans la suite du cours : exécution dans le désordre, superscalarité, renommage de registre. Mais un point important est que le front-end a des optimisations dédiées. La prédiction de branchement est l'une de ces optimisation, mais elle n'est pas la seule. Ce chapitre aborde les optimisations autres que la prédiction de branchement. Nous allons voir le découplage des étages du front-end, le pré-décodage et quelques améliorations liées indirectement à la prédiction de branchement.

Le découplage du front-end

Le séquenceur d'un processeur contient une unité de chargement, un décodeur et un chemin de données. Avec un pipeline, le couplage de ces structures fait que si l'une d'entre elle prend plus d'un cycle pour faire son travail, les étages précédents et/ou suivants sont stoppés. Par exemple, lors d'un défaut dans le cache d'instruction, l'ensemble stoppe. De même, si jamais le décodeur doit décoder une instruction via le micro-code, cela prend plusieurs cycles : l'unité de chargement et le cache d'instruction sont inutilisés. Même chose si jamais une instruction multicycle s’exécute dans le pipeline : cela bloque toutes les étapes précédentes.

Mais il s'agit là d'un défaut inhérent aux pipelines basiques, qui relient chaque étage avec des registres. Avec un peu d'astuce, il est possible que certains étages prennent de l'avance même si l'étage suivant est bloqué. Par exemple, si le décodeur bloque le pipeline en utilisant son micro-code pendant 4-5 cycles, l'unité de chargement peut en théorie précharger à l'avance les instructions suivantes, et les mettre en attente. Ou encore, en cas de bulle de pipeline (pipeline stall), le décodeur peut décoder en avance des instructions et les mettre en attente tant que la bulle de pipeline est en cours.

Dans les deux cas, une unité prend de l'avance et met en attente ses résultats tant que l'étage suivant est occupé. La mise en attente est réalisée en remplaçant/complémentant les registres du pipeline avec des mémoires FIFOs. Elles remplacent ou complémentant les registres de pipeline, les deux sont possibles. Si elles remplacent ces registres, si aucune mise en attente n'est requise, elles fonctionnent comme un registre de pipeline.

La file d'instruction

Les processeurs modernes intègrent une file d'instruction, à savoir une mémoire FIFO placée entre le cache d'instruction et le décodeur d'instruction. 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 charger des 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 exécute 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 file de micro-opérations

L'optimisation précédente peut aussi s'appliquer entre le décodeur d'instruction et le chemin de données. Pour cela, la sortie du décodeur est reliée à une mémoire FIFO semblable à la file d'instruction. 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 elle porte de nombreux noms et la terminologie des différents fabricants est assez confuse. 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 charger et décoder des instructions, il a juste à accumuler les instructions décodées dans la file de micro-opérations. En clair, la file de micro-opérations met en attente les instructions décodées 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. Pendant un défaut de cache, aucune instruction n'est chargée ni 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 se rattrape en émettant les instructions en attente dans la file de micro-opérations, s'il y en a. 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.

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 nous verrons cela dans plusieurs chapitres). 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 utiliser la file de micro-opérations comme une sorte de pseudo-cache FIFO. La file de micro-opérations 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. Un circuit annexe, appelé le Loop Stream Detector (LSD), détecte les boucles dans la file de micro-opérations et optimise leur exécution. 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, qui tiennent toutes entières dans la file de micro-opérations, et sous 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.

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

É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. Pour donner quelques chiffres, les processeurs ARM Cortex A15 géraient des boucles de maximum 32 micro-opérations. 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.

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.

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. 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 accumule les instructions décodées dans le cache de micro-opérations, les itérations suivantes de la boucle lisent les micro-opérations adéquates dans le cache de micro-opération : on n'a pas à décoder l'instruction une nouvelle fois. Sur de nombreux processeurs, le cache de micro-opération est alimenté non pas par l'unité de décodage, mais par la file de micro-opérations. Ainsi, seules les micro-opérations émises sont copiées dans ce cache.

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.

Une différence avec le cache de micro-opération est qu'une 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, un cache de macro/micro-opération mémorisera les micro-opérations du IF et du ELSE et les fournira selon les besoins. La raison est que 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. Le cache de micro-opération est donc plus efficace que le Loop Stream Detector, pour un cout en transistor plus élevé.

Le cache de micro-opération est une voie de chargement parallèle au front-end proprement dit. 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. 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.

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

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 son envoi au chemin de données, lors de son é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 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 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 préchargement d'instructions et la Fetch Target Queue

Nous venons de voir qu'il est possible de découpler les étages de chargement, décodage et le chemin de données, en insérant des mémoires FIFOs dans le pipeline. Il en est de même avec l'unité de chargement elle-même. Elle est composée de deux circuits entre lesquels on peut ajouter des mémoires FIFO : une unité de calcul d'adresse et le cache d'instruction. 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. L'unité de calcul d'adresse émet les adresses des instructions à charger, qui sont consommées par le cache d'instruction.

Les processeurs modernes incorporent une optimisation assez intéressante : ils découplent l'unité de calcul d'adresse 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.

Le prédécodage d'instructions

La présence d'un cache d'instruction permet l'implémentation de certaines optimisations, dont la plus connue est la technique dite du prédécodage. Avec elle, lorsque les instructions sont chargées dans le cache d'instruction, elles sont partiellement décodées, grâce à un circuit séparé de l'unité de décodage d'instruction. Le décodage de l'instruction proprement dit est plus court, car une partie du travail est faite en avance, on gagne quelques cycles.

Le prédécodage est particulièrement utile avec des instructions de taille variable : il permet de pré-déterminer où commencent/terminent les instructions dans une ligne de cache, indiquer leur taille, etc. Autre possibilité, le prédécodage peut indiquer s'il y a des branchements dans une ligne de cache et où ils se trouvent, ce qui est très utile pour la prédiction de branchement.

Pour chaque ligne de cache, le décodage partiel fournit des informations utiles au décodeur d'instruction. Les informations pré-décodées sont soit intégrée dans la ligne de cache, soit mémorisées dans une banque séparée. En clair : une partie de la capacité totale du cache d'instruction est utilisée pour les informations de pré-décodage. Le prédécodage est donc un compromis : un cache d'instruction de plus faible capacité, mais un décodage plus simple.

Le pré-décodage est surtout utile pour les instructions qui sont ré-exécutées souvent. Pour les instructions exécutées une seule fois, le gain en performance dépend de l'efficacité du préchargement et d'autres contraintes, mais ce qui est gagné lors du décodage est souvent partiellement perdu lors du prédécodage. Par contre, si une instruction est exécutée plusieurs fois, le pré-décodage est fait une seule fois, alors qu'on a un gain à chaque ré-exécution de l'instruction.

Les sélecteurs de branchement intégrés au cache L1

Le pré-décodage peut être utilisé afin de faciliter le travail de la prédiction de branchement. L'idée est d'incorporer une partie de la prédiction de branchement dans le cache L1 d'instruction. Une ligne de cache mémorise alors des informations de prédiction de branchement dans ses bits de contrôle. Les informations en question peuvent être des adresses de destination, ou simplement de quoi déterminer si le branchement est pris ou non. Il s'agit d'une démarche inverse à celle de la Fetch Target Queue, qui découple l'unité de prédiction de branchement du cache, en insérant une mémoire FIFO entre les deux. Là, la démarche est au contraire de fusionner partiellement cache d'instruction et unité de prédiction de branchement.

Les premiers processeurs AMD utilisaient cette technique, au moins dans les grandes lignes. Une ligne de cache contient potentiellement plusieurs branchements, dont la position est identifiée par le prédécodage. Pour chaque octet, la ligne de cache associe un bit de contrôle qui indique si un branchement démarre à cet octet, si c'est le premier octet d'un branchement. Le prédécodage peut identifier entre un et plusieurs branchement par ligne de cache, il y a une limite. Le prédécodage n'identifie typiquement que les 3 à 5 premiers branchements, les suivants sont ignorés, faute de place dans les bits de contrôle.

Prenons par exemple une ligne de cache de 8 octets, dans laquelle on a 2 branchements de 2 octets chacun.

Ligne de cache, en octets
Instruction	Branch 1	Branch 1	Instruction	Branch 2	Branch 2	Instruction	Instruction
Bits d'identification des branchements.
0	1	0	0	1	0	0	0

Il est possible d'améliorer le tout en précisant quel est le type du branchement. Par exemple, on peut distinguer les branchements inconditionnel et conditionnels, ou encore les instruction de retour de fonction. L'intérêt n'est pas évident, mais c'est lié au fait que les branchements inconditionnels sont toujours pris, et que les retour de fonction ont une adresse de destination qui est prédite par une unité de branchement séparée, le return adress predictor, pas par un BTB. Deux bits suffisent pour indiquer : si c'est un branchement conditionnel, inconditionnel, un retour de fonction, ou une instruction qui n'est pas un branchement.

Ligne de cache, en octets
Instruction	Saut inconditionnel	Saut inconditionnel	Instruction	Branch cond	Branch cond	Instruction	Retour de fonction
Bits d'identification des branchements.
00	01	00	00	10	00	00	11

L'idée est alors d'ajouter, pour chaque branchement détecté, un sélecteur de branchement qui indique si le branchement est pris ou non. En clair, des informations de prédiction de branchement sont ajoutés à chaque octet de position. Intuitivement, on se dit qu'il y a seulement un bit par branchement, qui indique si le branchement est pris ou non.

Les prédictions peuvent venir soit de l'unité de prédiction de branchement, soit provenir du prédécodage. Le prédécodage peut faire de la prédiction statique. Elle peut notamment détecter les branchements inconditionnels et les marquer comme pris. Elle peut aussi détecter les branchements conditionnels et le marquer comme non-pris par défaut. L'unité de prédiction de branchement met à jour les sélecteurs de branchements si besoin, pour les branchements conditionnels.

L'incorporation du Branch Target Buffer dans le cache d'instruction

Une première optimisation permet de se passer de Branch Target Buffer. Pour rappel, celui-ci est un cache qui mémorise, pour chaque branchement, quelle est son adresse de destination. Il peut contenir d'autres informations de prédiction, mais laissons-les de côté pour le moment.

L'idée est de déplacer les adresse de destination des branchements dans le cache d'instruction, dans les lignes de cache. Si une ligne de cache contient un branchement, elle mémorise l'adresse de destination de ce branchement, en plus des bits de pré-décodage. En général, les processeurs ne supportent qu'une seule adresse de destination. Si il y a plusieurs branchements dans une ligne de cache, c'est l'adresse de destination du premier branchement pris dans cette ligne de cache qui est mémorisée. Par exemple, l'AMD K5 se passe de Branch Target Buffer grâce à cela.

Il faut cependant remarquer qu'à ce petit jeu, les instructions de retour de fonction sont à part. Leur adresse de destination est souvent donnée par une unité de branchement séparée, le return adress predictor, séparée du Branch Target Buffer. Leurs adresses de destination n'ont pas forcément besoin d'être mémorisées dans les lignes de cache.

La technique décrite ici est simple à comprendre. Cependant, les processeurs AMD anciens, d'architecture K6 à K10 n'utilisaient pas cette méthode, mais une variante plus complexe, capable de prédire jusqu'à deux adresses de destination par branchement. A partir de l'architecture K6, le prédécodage déterminait la position des branchements dans les lignes de cache, dans une limite de 4 branchements par ligne de cache. Pour chaque branchement, la ligne de cache mémorisait un sélecteur de branchement, codé sur 2 bits. La valeur des bits indiquait que le branchement n'est pas pris si elle vaut 00, que c'est une instruction de retour de fonction si elle vaut 01, qu'il faut brancher à l'adresse de destination X si elle vaut 10, qu'il faut brancher à l'adresse de destination X si elle vaut 11. Les adresses de destination sont quand à elles mémorisées dans un cache séparé, appelé le Branch Target Cache. Le mécanisme pour adresser ce cache à partir du cache d'instruction n'est pas très détaillé dans la documentation d'AMD.

Les avantages et inconvénients

L'avantage de faire ainsi est que la prédiction de branchement est plus rapide. Lire une instruction depuis le cache renvoie non seulement l'instruction lue, mais aussi des informations de prédiction de branchement. L'unité de prédiction de branchement peut alors utiliser ces informations au cycle suivant pour savoir quelle est l'instruction suivante à charger.

Un défaut de cette approche est que si le branchement à prédire n'est pas dans le L1 d'instruction, aucune prédiction de branchement ne peut être faite et le préchargement ne peut pas fonctionner. C'est une limitation que n'ont pas les BTB découplées du cache L1 : elles peuvent prédire les adresses de destination et la direction d'un branchement, tant que l'entrée associée est dans le BTB. Et l'entrée peut être conservée, même si l'instruction en question a quitté le cache L1 et qu'elle est dans le L2, le L3 ou même en mémoire RAM. Les prédictions peuvent même servir à précharger les instructions utiles.

Sur l'Itanium et l'AMD Opteron, une optimisation assez intéressante permet de conserver les prédictions de branchement lorsque l'un branchement est évincé du cache L1 et se retrouve dans le cache L2. En théorie, les informations de prédiction, présentes dans la ligne de cache, sont perdues lorsque le branchement est évincé. Mais ces processeurs conservent ces prédictions dans un cache séparé, appelé le L2 Branch Cache.

◄ Retour vers « La prédiction de branchement »

Sommaire du livre

Continuer vers « Les pipelines multicycles » ►