Fonctionnement d'un ordinateur/La prédiction de branchement

Sur un processeur sans pipeline, les branchements ne posent aucun problème. Mais si on rajoute un pipeline, les branchements sont une source de problèmes. Pour comprendre pourquoi, prenons l'exemple de l’exécution d'un branchement. Lorsqu'on charge un branchement dans le pipeline, l'adresse à laquelle brancher ne sera connue qu'après quelques cycles et des instructions seront chargées durant ce temps. Et ces instructions chargées à tord s’exécuteront à tord. Pour éviter tout problème, on doit faire en sorte que ces instructions ne modifient pas les registres du processeur ou qu'elles ne lancent pas d'écritures en mémoire.

Dans le chapitre sur les pipelines de longueur fixe, nous avions vu quelques techniques visant à éliminer les problèmes liés aux dépendances de contrôle. Les méthodes pour cela consistent à annuler les instructions chargées à tord. La première est de détecter les branchements dès l'étape de décodage et de remplacer les instructions chargées à tord par des NOPs (des instructions qui ne font rien). Elle marche bien pour les branchements inconditionnels, qui sont toujours pris. Pour les branchements conditionnels, dont on ne sait pas s'ils sont pris à l'étage de décodage, les solutions sont les mêmes que celles utilisées pour les exceptions précises. Dans les grandes lignes, on détecte qu'un branchement a été pris en sortie de l'ALU, et on annule les instructions suivantes en empêchant qu'elles enregistrent leurs résultats dans les registres et/ou la mémoire.

Les techniques précédentes ont pour défaut que de nombreux cycles d'horloge sont gâchés. Déjà, parce qu'ils ont chargé et décodés des instructions inutile. Mais aussi, pour les branchements conditionnels, car les instructions chargées à tord se sont exécutées et qu'il faut annuler tout ce qu'elles ont fait. Pour éviter ce gâchis, les concepteurs de processeurs ont inventé l'exécution spéculative de branchement, qui consiste à deviner l'adresse de destination du branchement et charger les bonnes instructions dès le départ. Le but est de ne pas charger d'instruction à tord, en prédisant quelle seront les bonnes instructions à charger. Et cela demande de résoudre trois problèmes :

reconnaître les branchements ;
savoir si un branchement sera exécuté ou non : c'est la prédiction de branchement ;
dans le cas où un branchement serait exécuté, il faut aussi savoir quelle est l'adresse de destination : c'est la prédiction de l'adresse de destination d'un branchement, aussi appelée branch target prediction.

Pour résoudre le second problème, le processeur contient un circuit qui déterminer si le branchement est pris (on doit brancher vers l'adresse de destination) ou non pris (on poursuit l’exécution du programme immédiatement après le branchement) : c'est l'unité de prédiction de branchement. La prédiction de direction de branchement est elle aussi déléguée à un circuit spécialisé : l’unité de prédiction de direction de branchement. C'est l'unité de prédiction de branchement qui autorise l'unité de prédiction de destination de branchement à modifier le program counter. Dans certains processeurs, les deux unités sont regroupées dans le même circuit.

La correction des erreurs de prédiction

Le processeur peut parfaitement se tromper en faisant ses prédictions, ce qui charge des instructions par erreur dans le pipeline. Dans ce cas, on parle d'erreur de prédiction.

La détection et la correction des erreurs de prédiction

Pour corriger les erreurs de prédictions, il faut d'abord les détecter. Pour cela, on rajoute un circuit dans le processeur : l’unité de vérification de branchement (branch verification unit). Elle compare l'adresse de destination prédite et celle calculée en exécutant le branchement. Pour cela, l'adresse prédite doit être propagée dans le pipeline jusqu’à ce que l'adresse de destination du branchement soit calculée.

Une fois la mauvaise prédiction détectée, il faut corriger le program counter immédiatement. En effet, s’il y a eu erreur de prédiction, le program counter n'a pas été mis à jour correctement, et il faut faire reprendre le processeur au bon endroit. Pour implémenter cette correction du program counter, il suffit d'utiliser un circuit qui restaure le program counter s'il y a eu erreur de prédiction. La gestion des mauvaises prédictions dépend fortement du processeur. Certains processeurs peuvent reprendre l’exécution du programme immédiatement après avoir détecté la mauvaise prédiction (ils sont capables de supprimer les instructions qui n'auraient pas dû être exécutées), tandis que d'autres attendent que les instructions chargées par erreur terminent avant de corriger le program counter.

En plus de la correction du program counter, il faut aussi que les autres registres soient préservés de l'erreur de prédiction ou corrigés. Il faut que les instructions chargées à tord n’enregistrent pas leurs résultats dans les registres ou la mémoire. Ou s'ils l'ont été, il faut trouver un moyen pour annuler ces modifications. N'importe quelle technique de gestion des exceptions précise fait le travail. Les processeurs modernes utilisent généralement un tampon de réordonnancement (reorder buffer), mais ils peuvent aussi utiliser des points de contrôle de registres (sauvegarder tous les registres quand un branchement est décodé, pour le restaurer en cas de mauvaise prédiction de branchement).

Les pénalités de mauvaise prédiction

Un point important est que les instructions chargée à tord se propagent jusqu'à la sortie du pipeline, où leurs résultats sont alors annulés. Le temps d'attente nécessaire pour vider le pipeline dépend du pipeline. La dernière instruction à être chargée dans le pipeline le sera en même temps qu'on détecte l'erreur de prédiction. Il faudra attendre que cette instruction quitte le pipeline, et donc qu'elle traverse tous les étages. Il y a donc un temps d'attente pour collecter les résultats de ces instructions et la décision de ne pas enregistre leurs résultats dans les registres.

Le temps en question correspond aussi à un nombre d'instructions chargées à tord. Plus le résultat du branchement est connu tard, plus le nombre d'instructions chargées à tord sera grand, plus le nombre de cycles gâchés le sera aussi. Le nombre de cycles gâchés par des instructions inutiles s'appelle la pénalité de mauvaise prédiction. Elle dépend du pipeline, et précisément de l'étage auquel on détecte une mauvaise prédiction de branchement. Plus celui-ci est éloigné du début du pipeline, plus la pénalité est importante. Elle correspond précisément au nombre de cycles/étages entre le premier étage du pipeline, et l'étage où le branchement est résolu (on connait l'adresse à laquelle brancher).

Elle est généralement d'autant plus longue que le pipeline lui-même est long. Il vaut mieux vaut utiliser des pipelines courts pour la limiter. Les concepteurs de processeurs font alors face à un compromis : un pipeline long permet d'exécuter plus d'instructions en parallèle, mais cela augmente aussi la pénalité de mauvaise prédiction. Un pipeline de 10-15 étapes est un bon compromis. Mais cela ne signifie pas que des pipelines plus longs soient forcément moins performants. En fait, les pipelines plus longs ont besoin d'une prédiction de branchement élaborée pour fonctionner correctement. Plus la prédiction de branchement est performante, plus le pipeline peut être long. Les pénalités de mauvaise prédiction seront plus importantes, mais les mauvaises prédictions seront plus rares, ce qui compense complétement.

En utilisant une technique du nom de minimal control dependency, seules les instructions qui dépendent du résultat du branchement sont supprimées du pipeline en cas de mauvaise prédiction, les autres n'étant pas annulées. Sans minimal control dependency, toutes les instructions qui suivent un branchement dans notre pipeline sont annulées. Pourtant, certaines d'entre elles pourraient être utiles. Prenons un exemple : supposons que l'on dispose d'un processeur de 31 étages (un Pentium 4 par exemple). Supposons que l'adresse du branchement est connue au 9éme étage. On fait face à un branchement qui envoie le processeur seulement 6 instructions plus loin. Si toutes les instructions qui suivent le branchement sont supprimées, les instructions en rouge sont celles qui sont chargées incorrectement. On remarque pourtant que certaines instructions chargées sont potentiellement correctes : celles qui suivent le point d'arrivée du branchement. Elles ne le sont pas forcément : il se peut qu'elles aient des dépendances avec les instructions supprimées. Mais si elles n'en ont pas, alors ces instructions auraient dûes être exécutées. Il serait donc plus efficace de les laisser enregistrer leurs résultats au lieu de les ré-exécuter à l’identique un peu plus tard. Ce genre de choses est possible sur les processeurs qui implémentent une technique du nom de Minimal Control Dependancy. En gros, cette technique fait en sorte que seules les instructions qui dépendent du résultat du branchement soient supprimées du pipeline en cas de mauvaise prédiction.

La reconnaissance des branchements

Pour prédire des branchements, le processeur doit faire la différence entre branchements et autres instructions, dès l'étage de chargement. Or, un processeur « normal », sans prédiction de branchement, ne peut faire cette différence qu'à l'étage de décodage, et pas avant. Les chercheurs ont donc dû trouver une solution.

La première solution se base sur les techniques de prédécodage vues dans le chapitre sur le cache. Pour rappel, ce prédécodage consiste à décoder partiellement les instructions lors de leur chargement dans le cache d'instructions et à mémoriser des informations utiles dans la ligne de cache. Dans le cas des branchements, les circuits de prédécodage peuvent identifier les branchements et mémoriser cette information dans la ligne de cache.

Une autre solution consiste à mémoriser les branchements déjà rencontrés dans un cache intégré dans l'unité de chargement ou de prédiction de branchement. Ce cache mémorise l'adresse (le program counter) des branchements déjà rencontrés : il s'appelle le tampon d’adresse de branchement (branch adress buffer). À chaque cycle d'horloge, l'unité de chargement envoie le program counter en entrée du cache. S’il n'y a pas de défaut de cache, l'instruction à charger est un branchement déjà rencontré : on peut alors effectuer la prédiction de branchement. Dans le cas contraire, la prédiction de branchement n'est pas utilisée, et l'instruction est chargée normalement.

La prédiction de l'adresse de destination

Les explications qui vont suivre vont faire intervenir deux adresses. La première est l'adresse de destination du branchement, à savoir l'adresse à laquelle le processeur doit reprendre son exécution si le branchement est pris. L'autre adresse est l'adresse du branchement lui-même, l'adresse qui indique la position de l'instruction de branchement en mémoire. L'adresse du branchement est contenu dans le program counter lorsque celui-ci est chargé dans le processeur, alors que l'adresse de destination est fournie par l'unité de décodage d'instruction. Il faudra faire bien attention à ne pas confondre les deux adresses dans ce qui suit.

La prédiction de l'adresse de destination d'un branchement détermine l'adresse de destination d'un branchement. Rappelons qu'il existe plusieurs modes d'adressage pour les branchements et que chacun d'entre eux précise l'adresse de destination à sa manière. Suivant le mode d'adressage, l'adresse de destination est soit dans l'instruction elle-même (adressage direct), soit calculée à l’exécution en additionnant un offset au program counter (adressage relatif), soit dans un registre du processeur (branchement indirect), soit précisée de manière implicite (retour de fonction, adresse au sommet de la pile).

La prédiction des branchements directs et relatifs se fait globalement de la même manière, ce qui fait que nous ferons la confusion dans ce qui suit. Pour les branchements implicites, ils correspondent presque exclusivement aux instructions de retour de fonction, qui sont un cas un peu à part que nous verrons dans la section sur les branchements indirects. Pour résumer, nous allons faire une différence entre les branchements directs pour lequel l'adresse de destination est toujours la même, les branchements indirects où l'adresse de destination est variable durant l’exécution du programme, et les instructions de retour de fonction. Les branchements directs sont facilement prévisibles, vu que l'adresse vers laquelle il faut brancher est toujours la même. Pour les branchements indirects, vu que cette adresse change, la prédire celle-ci est particulièrement compliqué (quand c'est possible). Pour les instructions de retour de fonction, une prédiction parfaite est possible.

La prédiction de l'adresse de destination pour les branchements directs

Lorsqu'un branchement est exécuté, on peut se souvenir de l'adresse de destination et la réutiliser lors d'exécutions ultérieures du branchement. Cette technique marche à la perfection pour les branchements directs, pour lesquels cette adresse est toujours la même, mais pas pour les branchements indirects. Pour se souvenir de l'adresse de destination, on utilise un cache qui mémorise les correspondances entre l'adresse du branchement et l'adresse de destination. Ce cache est appelé le tampon de destination de branchement, branch target buffer en anglais, qui sera abrévié en BTB dans ce qui suit. Ce cache est une amélioration du tampon d'adresse de branchement vu plus haut, auquel on aurait ajouté les adresses de destination des branchements. Le BTB est utilisé comme suit : on envoie en entrée l'adresse du branchement lors du chargement, le BTB répond au cycle suivant en précisant : s’il reconnaît l'adresse d'entrée, et quelle est l'adresse de destination si c'est le cas. Précisons que le BTB ne mémorise pas les branchements non-pris, ce qui est inutile.

Comme pour tous les caches, un accès au BTB peut entraîner un défaut de cache, c’est-à-dire qu'un branchement censé être dans le BTB n'y est pas. Comme pour les autres caches, les défauts de cache peuvent se classer en trois types : les défauts de cache à froid (cold miss) causés par la première exécution d'un branchement, les défauts liés à la capacité du BTB/cache, et les défauts par conflit d'accès au cache. Les défauts liés à la capacité du BTB sont les plus simples à comprendre. La capacité limitée du BTB fait que d'anciens branchements sont éliminées pour laisser la place à de nouveaux, généralement en utilisant algorithme de remplacement de type LRU. En conséquence, certains branchements peuvent donner des erreurs de prédiction si leur correspondance a été éliminée du cache. On peut en réduire le nombre en augmentant la taille du BTB.

Les défauts liés aux conflits d'accès au BTB sont eux beaucoup plus intéressants, car la conception du BTB est assez spéciale dans la manière dont sont gérés ce genre de défauts. Pour rappel, les défauts par conflit d'accès ont lieu quand deux adresses mémoires se voient attribuer la même ligne de cache. Pour un BTB, cela correspond au cas où deux branchements se voient attribuer la même entrée dans le BTB, ce qui porte le nom d’aliasing. Ne pas détecter ce genre de situation sur un cache normal entraînerait des problèmes : la donnée lue/écrite ne serait pas forcément la bonne. Les caches normaux utilisent un système de tags pour éviter ce problème et on s'attendrait à ce que les BTB fassent de même. S'il existe des BTB qui utilisent des tags, ils sont cependant assez rares. Pour un BTB, l'absence de tags n'est pas un problème : la seule conséquence est une augmentation du taux de mauvaises prédictions, dont les conséquences en termes de performance peuvent être facilement compensées. Les BTB se passent généralement de tags, ce qui a de nombreux avantages : le circuit est plus rapide, prend moins de portes logiques, consomme moins d'énergie, etc. Ces économies de portes logiques et de performances peuvent être utilisées pour augmenter la taille du BTB, ce qui compense, voire surcompense les mauvaises prédictions induites par l’aliasing.

Le BTB peut être un cache totalement associatif, associatif par voie, ou directement adressé, mais ces derniers sont les plus fréquents. Les BTB sont généralement des caches de type directement adressés, où seuls les bits de poids faible de l'adresse du branchement adressent le cache, le reste de l'adresse est tout simplement ignoré. Il existe aussi des BTB qui sont construits comme les caches associatifs à plusieurs voies, mais ceux-ci impliquent généralement la présence de tags, ce qui fait qu'ils sont assez rares.

D'autres processeurs se passent de BTB. À la place, ils mémorisent les correspondances entre branchement et adresse de destination dans les bits de contrôle du cache d'instructions. Cela demande de mémoriser trois paramètres : l'adresse du branchement dans la ligne de cache (stockée dans le branch bloc index), l'adresse de la ligne de cache de destination, la position de l'instruction de destination dans la ligne de cache de destination. Lors de l'initialisation de la ligne de cache, on considère qu'il n'y a pas de branchement dedans. Les informations de prédiction de branchement sont ensuite mises à jour progressivement, au fur et à mesure de l’exécution de branchements. Le processeur doit en même temps charger l'instruction de destination correcte dans le cache, si un défaut de cache a lieu : il faut donc utiliser un cache multi-port. L'avantage de cette technique est que l'on peut mémoriser une information par ligne de cache, comparé à une instruction par entrée dans un tampon de destination de branchement. Mais cela ralentit fortement l'accès au cache et gaspille du circuit (les bits de contrôle ajoutés ne sont pas gratuits). En pratique, on n'utilise pas cette technique, sauf sur quelques processeurs (un des processeurs Alpha utilisait cette méthode).

La prédiction de l'adresse de destination pour les branchements indirects et implicites

Passons maintenant aux branchements indirects. Les techniques précédentes fonctionnement quand on les applique aux branchements indirects et ne marchent pas trop mal, mais elles se trompent à chaque fois qu'un branchement indirect change d'adresse de destination. Tous les processeurs commerciaux datant d'avant le Pentium M sont dans ce cas. De nos jours, les processeurs haute performance sont capables de prédire l'adresse de destination d'un branchement indirect. Pour cela, ils utilisent un tampon de destination de branchement amélioré, qui mémorise plusieurs adresses de destination pour un seul branchement, en compagnie d'informations qui lui permettent de déduire plus ou moins efficacement quelle adresse de destination est la bonne. Mais même malgré ces techniques avancées de prédiction, les branchements indirects et appels de sous-programmes indirects sont souvent très mal prédits.

Certains processeurs peuvent prévoir l'adresse à laquelle il faudra reprendre lorsqu'un sous-programme a fini de s’exécuter, cette adresse de retour étant stockée sur la pile, ou dans des registres spéciaux du processeur dans certains cas particuliers. Ils possèdent un circuit spécialisé capable de prédire cette adresse : la prédiction de retour de fonction (return function predictor). Lorsqu'une fonction est appelée, ce circuit stocke l'adresse de retour d'une fonction dans des registres internes au processeur, organisés en pile. Avec cette organisation des registres en forme de pile, on sait d'avance que l'adresse de retour du sous-programme en cours d'exécution est au sommet de cette pile.

La prédiction de branchement

La prédiction de branchement tente de prédire si un branchement sera pris ou non-pris et décide d'agir en fonction. Si on prédit qu'un branchement est non pris, on continue l’exécution à partir de l'instruction qui suit le branchement. À l'inverse si le branchement est prédit comme étant pris, le processeur devra recourir à l'unité de prédiction de direction de branchement. Maintenant, voyons comment le processeur fait pour prédire si un branchement est pris ou non. La prédiction de branchement se base avant tout sur des statistiques, c’est-à-dire qu'elle détermine la probabilité d’exécution d'un branchement en fonction d'informations connues au moment de l’exécution d'un branchement. Elle assigne une probabilité qu'un soit branchement soit pris en fonction de ces informations : si la probabilité est de plus de 50%, le branchement est considéré comme pris.

Les contraintes d’implémentation de la prédiction de branchement

La prédiction de branchement n'a d'intérêt que si les prédictions sont suffisamment fiables pour valoir le coup. Rappelons que la pénalité lors d'une mauvaise prédiction est importante : vider le pipeline est une opération d'autant plus coûteuse que le pipeline est long. Et plus cette pénalité est importante, plus le taux de réussite de l'unité de prédiction doit être important. En conséquence, une simple prédiction fiable à 50% ne tiendra pas la route et il est généralement admis qu'il faut au minimum un taux de réussite proche de 90% de bonnes prédictions, voire plus sur les processeurs modernes. Plus la pénalité en cas de mauvaise prédiction est importante, plus le taux de bonnes prédiction doit être élevé. Heureusement, la plupart des branchements sont des branchements biaisés, c’est-à-dire qu'ils sont presque toujours pris ou presque toujours non-pris, sauf en de rares occasions. De tels branchements font que la prédiction des branchements est facile, bien qu'ils posent paradoxalement quelques problèmes avec certaines techniques, comme nous le verrons plus bas.

Un autre point important est que les unités de prédiction de branchement doivent être très rapides. Idéalement, elles doivent fournir leur prédiction en un seul cycle d'horloge. En conséquence, elles doivent être très simples, utiliser des calculs rudimentaires et demander peu de circuits. Un seul cycle d'horloge est un temps très court, surtout sur les ordinateurs avec une fréquence élevée, chose qui est la norme sur les processeurs à haute performance. Les techniques de prédiction dynamique ne peuvent donc pas utiliser des méthodes statistiques extraordinairement complexes. Cela va à l'encontre du fait que le tau de mauvaises prédictions doit être très faible, de préférence inférieur à 10% dans le meilleur des cas, idéalement inférieur à 1% sur les processeurs modernes. Vous comprenez donc aisément que concevoir une unité de prédiction de branchement est un véritable défi d’ingénierie électronique qui requiert des prouesses technologiques sans précédent.

La classification des techniques de prédiction de branchement

Suivant la nature des informations utilisées, on peut distinguer plusieurs types de prédiction de branchement : locale, globale, dynamique, statique, etc.

Il faut aussi distinguer la prédiction de branchements statique de la prédiction dynamique. Avec la prédiction statique, on prédit si le branchement est pris ou non en fonction de ses caractéristiques propres, comme son adresse de destination, la position du branchement en mémoire, le mode d'adressage utilisé, si le branchement est direct ou indirect, ou toute autre information encodée dans le branchement lui-même. Les informations utilisées sont disponibles dans le programme exécuté, et ne dépendent pas de ce qui se passe lors de l’exécution du programme en lui-même. Par contre, avec la prédiction dynamique, des informations qui ne sont disponibles qu'à l’exécution sont utilisées pour faire la prédiction. Typiquement, la prédiction dynamique extrait des statistiques sur l’exécution des branchements, qui sont utilisées pour faire la prédiction. Les statistiques en question peuvent être très simples : une simple moyenne sur les exécutions précédentes donne déjà de bons résultats. Mais les techniques récentes effectuent des opérations statistiques assez complexes, comme nous le verrons plus bas.

Pour ce qui est de la prédiction dynamique, il faut distinguer la prédiction de branchement dynamique locale et globale. La prédiction locale sépare les informations de chaque branchement, alors que la prédiction globale fusionne les informations pour tous les branchements et fait des moyennes globales. Les deux méthodes ont leurs avantages et leurs inconvénients, car elles n'utilisent pas les mêmes informations. La prédiction locale seule ne permet pas d'exploiter les corrélations entre branchements, à savoir que le résultat d'un branchement dépend souvent du résultat des autres, alors que la prédiction globale le peut. À l'inverse, la prédiction globale seule n'exploite pas des informations statistiques précise pour chaque branchement. Idéalement, les deux méthodes sont complémentaires, ce qui fait qu'il existe des prédicteurs de branchement hybrides, qui exploitent à la fois les statistiques pour chaque branchement et les corrélations entre branchements. Les prédicteurs hybrides ont de meilleures performances que les prédicteurs purement globaux ou locaux.

La prédiction statique de branchement

Avec la prédiction statique, on prédit le résultat du branchement en fonction de certaines caractéristiques du branchement lui-même, comme son adresse, son mode d'adressage, l'adresse de destination connue, etc.

Dans son implémentation la plus explicite, la prédiction est inscrite dans le branchement lui-même. Quelques bits de l'opcode du branchement précisent si le branchement est majoritairement pris ou non pris. Ils permettent d'influencer les règles de prédiction de branchement et de passer outre les réglages par défaut. Ces bits sont appelés des suggestions de branchement (branch hint). Mais tous les processeurs ne gèrent pas cette fonctionnalité. Et de plus, cette solution marche assez mal. La raison est que le programmeur ou le compilateur doit déterminer si le branchement est souvent pris ou non-pris, mais qu'il n'a pas de moyen réellement fiable pour cela. Une solution possible est d’exécuter le programme sur un ensemble de données réalistes et d'analyser le comportement de chaque branchement, afin de déterminer les suggestions de branchement adéquates, mais c'est une solution lourde et peu pratique, qui a de bonnes chances de donner des résultats peu reproductibles d'une exécution à l'autre.

Une autre idée part de la distinction entre les branchements inconditionnels toujours pris, et les branchements conditionnels au résultat variable. Ainsi, on peut donner un premier algorithme de prédiction statique : les branchements inconditionnels sont toujours pris alors que les branchements conditionnels ne sont jamais pris (ce qui est une approximation). Cette méthode est particulièrement inefficace pour les branchements de boucle, où la condition est toujours vraie, sauf en sortie de boucle ! Il a donc fallu affiner légèrement l'algorithme de prédiction statique.

Une autre manière d’implémenter la prédiction statique de branchement est de faire une différence entre les branchements conditionnels ascendants et les branchements conditionnels descendants. Un branchement conditionnel ascendant est un branchement qui demande au processeur de reprendre plus loin dans la mémoire : l'adresse de destination est supérieure à l'adresse du branchement. Un branchement conditionnel descendant a une adresse de destination inférieure à l'adresse du branchement : le branchement demande au processeur de reprendre plus loin dans la mémoire. Les branchements ascendants sont rarement pris (ils servent dans les conditions de type SI…ALORS), contrairement aux branchements descendants (qui servent à fabriquer des boucles). On peut ainsi modifier l’algorithme de prédiction statique comme suit :

les branchements inconditionnels sont toujours pris ;
les branchements descendants sont toujours pris ;
les branchements ascendants ne sont jamais pris.

La prédiction de branchement avec des compteurs à saturation

Les méthodes de prédiction de branchement statique sont intéressantes, mais elles montrent rapidement leurs limites. La prédiction dynamique de branchement donne de meilleures résultats. Sa version la plus simple se contente de mémoriser ce qui s'est passé lors de l’exécution précédente du branchement. Si le branchement a été pris, alors on suppose qu'il sera pris la prochaine fois. De même, s'il n'a pas été pris, on suppose qu'il ne le sera pas lors de la prochaine exécution. Pour cela, chaque entrée du BTB est associée à un bit qui mémorise le résultat de la dernière exécution du branchement : 1 s'il a été pris, 0 s'il n'a pas été pris. C'est ce qu'on appelle la prédiction de branchements sur 1 bit. Cette méthode marche bien pour les branchements des boucles (pas ceux dans la boucle, mais ceux qui font se répéter les instructions de la boucle), ainsi que pour les branchements inconditionnels, mais elle échoue assez souvent pour le reste. Sa performance est généralement assez faible, malgré son avantage pour les boucles. Il faut dire que les pénalités en cas de mauvaise prédiction sont telles qu'une unité de prédiction de branchement doit avoir un taux de succès très élevé pour être utilisable ne pratique, et ce n'est pas le cas de cette technique.

Une version améliorée calcule, pour chaque branchement, d'une moyenne sur les exécutions précédentes. Typiquement, on mémorise à chaque exécution du branchement si celui-ci est pris ou pas, et on effectue une moyenne statistique sur toutes les exécutions précédentes du branchement. Si la probabilité d'être pris est supérieure à 50 %, le branchement est considéré comme pris. Dans le cas contraire, il est considéré comme non pris. Pour cela, on utilise un compteur à saturation qui mémorise le nombre de fois qu'un branchement est pris ou non pris. Ce compteur est initialisé de manière à avoir une probabilité proche de 50 %. Le compteur est incrémenté si le branchement est pris et décrémenté s'il est non pris. Pour faire la prédiction, on regarde le bit de poids fort du compteur : le branchement est considéré comme pris si ce bit de poids fort est à 1, et non pris s'il vaut 0. Pour la culture générale, il faut savoir que le compteur à saturation du Pentium 1 était légèrement bogué. La plupart des processeurs qui utilisent cette technique ont un compteur à saturation par entrée dans le tampon de destination de branchement, donc un compteur à saturation par branchement.

Rappelons que chaque compteur est associé à une entrée du BTB. Ce qui fait que le phénomène d’aliasing mentionné plus haut peut perturber les prédictions de branchement. Concrètement, deux branchements peuvent se voir associés à la même entrée du BTB, et donc au même compteur à saturation. Cependant, cet aliasing entraine l'apparition d'interférences entre branchements, à savoir que les deux branchements vont agir sur le même compteur à saturation. L'interférence peut avoir des effets positifs, neutres ou négatifs, suivant la corrélation entre les deux branchements. L’aliasing n'est pas un problème si les deux branchements sont fortement corrélés, c’est-à-dire que les deux sont souvent pris ou au contraire que les deux sont très souvent non-pris. Dans ce cas, les deux branchements vont dans le même sens et l'interférence est neutre, voire légèrement positive. Mais si l'un est souvent pris et l’autre souvent non-pris, alors l'interférence est négative. En conséquence, les deux branchements vont se marcher dessus sans vergogne, chacun interférant sur les prédictions de l'autre ! Il est rare que l’aliasing ait un impact significatif sur les unités de prédiction des deux paragraphes précédents. Il se manifeste surtout quand la BTB est très petite et la seule solution est d'augmenter la taille du BTB.

La prédiction de branchement à deux niveaux avec un historique global

La prédiction par historique conserve le résultat des branchements précédents dans un registre d'historique, qui mémorise le résultat des N branchements précédents (pour un registre de N bits). Ce registre d'historique est un registre à décalage mis à jour à chaque exécution d'un branchement : on fait rentrer un 1 si le branchement est pris, et un 0 sinon. Une unité de prédiction globale utilise cet historique pour faire sa prédiction, ce qui tient compte d'éventuelles corrélations entre branchements consécutifs/proches pour faire les prédictions. C'est un avantage pour les applications qui enchaînent des if...else ou qui contiennent beaucoup de if...else imbriqués les uns dans les autres, qui s’exécutent plusieurs fois de suite. Le résultat de chaque if...else dépend généralement des précédents, ce qui rend l'utilisation d'un historique global intéressant. Par contre, ils sont assez mauvais pour le reste des branchements. Mais cette qualité devient un défaut quand elle détecte des corrélations fortuites ou parasites, inutiles pour la prédiction (corrélation n'est pas causalité, même pour prédire des branchements). Du fait de ce défaut, la prédiction globale a besoin de registres d'historiques globaux très larges, de plusieurs centaines de bits au mieux.

Dans les unités de prédiction à deux niveaux, le registre d'historique est combiné avec des compteurs à saturation d'une autre manière. Il n'y a pas un ou plusieurs compteurs à saturation par branchement, l'ensemble est organisé différemment. Les compteurs à saturation sont regroupés dans une ou plusieurs Pattern History Table, que nous noterons PHT dans ce qui suit. En clair, on a un registre d'historique, suivi par une ou plusieurs PHT, ce qui fait que de telles unités de prédiction de branchement sont appelées des unités de prédiction de branchement à deux niveaux. Il peut y avoir soit une PHT unique, appelée PHT globale, où une PHT associée chaque branchement, ce qui s'appelle une PHT locale. Mais laissons ce côté ce détail pour le moment. Sachez juste qu'il est parfaitement possible d'avoir des unités de prédiction avec plusieurs PHTs, ce qui sera utile pour la suite. Pour le moment, nous allons nous concentrer sur les unités avec une seule PHT couplé à un seul registre d'historique.

L'unité de prédiction à deux niveaux la plus simple utilise un registre d'historique global, couplé à une PHT unique (une PHT globale). Pour un registre d'historique global unique de n bits, la PHT globale contient 2^n compteurs à saturation, un par valeur possible de l'historique. Pour chaque valeur possible du registre d'historique, la PHT associée contient un compteur à saturation dont la valeur indique si le prochain branchement sera pris ou non-pris. Le choix du compteur à saturation utiliser se fait grâce au registre d'historique, et éventuellement avec d'autres informations annexes. Le choix du compteur à saturation à utiliser dépend uniquement du registre d'historique global, aucune autre information n'est utilisée.

Le circuit précédent a cependant un problème : si deux branchements différents s'exécutent et que l'historique est le même, le processeur n'y verra que du feu. Il y a alors une interférence, à savoir que les deux branchements vont agir sur le même compteur à saturation. On se retrouve alors dans une situation d’aliasing, conceptuellement identique à l’aliasing dans le BTB ou avec des compteurs à saturation. Sauf que les interférences sont alors beaucoup plus nombreuses et qu'elles sont clairement un problème pour les performances ! Et en réduire le nombre devient alors un problème bien plus important qu'avec les unités de prédiction précédentes. Si réduire l'aliasing avec de simples compteurs à saturation demandait d'augmenter la taille de la PHT, d'autres solutions sont possibles sur les unités de prédiction globales. Elles sont au nombre de deux : mitiger les interférences liées aux branchements biaisés, ajouter des informations qui discriminent les branchements. Voyons ces solutions dans le détail.

La mitigation des interférences par usage de l'adresse de branchement

La première solution pour réduire l'impact de l’aliasing est d'augmenter la taille de la PHT et de l'historique. Plus l'historique et la PHT sont grands, moins l’aliasing est fréquent. Mais avoir des historiques et des PHT de très grande taille n'est pas une mince affaire et le cout en termes de performances et de portes logiques est souvent trop lourd. Une autre solution consiste à utiliser, en plus de l'historique, des informations sur le branchement lui-même pour choisir le compteur à saturation à utiliser. Typiquement, on peut utiliser l'adresse du branchement en plus de l'historique, pour choisir le compteur à saturation adéquat.

Pour être précis, on n'utilise que rarement l'adresse complète du branchement, mais seulement les bits de poids faible. La raison est que cela fait moins de bits à utiliser, donc moins de circuits et de meilleures performances. Mais cela fait que l’aliasing est atténué, pas éliminé. Des branchements différents ont beau avoir des adresses différentes, les bits de poids faible de leurs adresses peuvent être identiques. Des confusions sont donc possibles, mais l'usage de l'adresse de branchement réduit cependant l’aliasing suffisamment pour que cela suffise en pratique.

Une unité de prédiction de ce type est illustrée ci-dessous. Sur cette unité de prédiction, le choix de la PHT est réalisé par l'historique, alors que le choix du compteur à saturation est réalisé par l'adresse du branchement. Pour concevoir le circuit, on part d'une unité de prédiction de branchement basée sur des compteurs à saturation, avec un compteur à saturation par branchement, sauf qu'on copie les compteurs à saturation en autant d'exemplaires que de valeurs possibles de l'historique. Par exemple, pour un historique de 4 bits, on a 16 valeurs différentes possibles pour l'historique, donc 16 PHT et donc 16 compteurs à saturation par branchement. Chaque compteur à saturation mémorise la probabilité que le branchement associé soit pris, mais seulement pour la valeur de l'historique associée. Le choix de la PHT utilisée pour la prédiction est réalisé par l'historique global, qui commande un multiplexeur relié aux PHT. Les compteurs à saturation d'un branchement sont mis à jour seulement quand le branchement s'est chargé pendant que l'historique associé était dans le registre d'historique. Cette méthode a cependant le défaut de gâcher énormément de transistors.

D'autres unités de prédiction fonctionnent sur le principe inverse de l'unité précédente. Sur les unités de prédiction qui vont suivre, le choix d'une PHT est réalisé par l'adresse du branchement, alors que le choix du compteur dans la PHT est réalisé par l'historique. C'est ce que font les unités de prédiction gshare et gselect, ainsi que leurs dérivées.

Avec les unités de prédiction gselect, on concatène les bits de poids faible de l'adresse du branchement et l'historique pour obtenir le numéro du compteur à saturation à utiliser. Avec cette technique, on utilise une PHT unique, mais il est possible de découper celle-ci en plusieurs PHT. On peut par exemple utiliser une PHT par branchement/entrée du BTB. Ou alors, on peut utiliser une PHT apr valeur possible de l'historique, ce qui fait qu'on retrouve l'unité de prédiction précédente.

Avec les unités de prédiction gshare, on fait un XOR entre le registre d'historique et les bits de poids faible de l'adresse du branchement. Le résultat de ce XOR donne le numéro du compteur à utiliser. Avec cette technique, on utilise une PHT globale et un historique global, mais le registre d'historique est manipulé de manière à limiter l'aliasing.

Intuitivement, on pourrait croire que les unités de prédiction gselect ont de meilleures performances. C'est vrai que les unités gshare combinent l'adresse du branchement et l'historique d'une manière qui fait perdre un peu d'information (impossible de retrouver l'adresse du branchement et l'historique à partir du résultat du XOR), alors que les unités gselect conservent ces informations. Mais il faut prendre en compte le fait que les deux unités doivent se comparer à PHT identique, de même taille. Prenons par exemple une PHT de 256 compteurs, adressée par 8 bits. Avec une unité gselect, les 8 bits sont utilisés à la fois pour l'historique et pour les bits de poids faible de l'adresse du branchement. Alors qu'avec une unité gshare, on peut utiliser un historique de 8 bits et les 8 bits de poids faible de l'adresse du branchement. L'augmentation de la taille de l'historique et du nombre de bits utilisés fait que l’aliasing est réduit, et cela compense le fait que l'on fait un XOR au lieu d'une concaténation.

La mitigation des interférences par la structuration en caches des PHTs

Les techniques précédentes utilisent les bits de poids faible de l'adresse pour sélectionner la PHT adéquate, ou pour sélectionner le compteur dans la PHT. Mais le reste de l'adresse n'est pas utilisé. Cependant, il est théoriquement possible de conserver les bits de poids fort, afin d'identifier le branchement associé à un compteur. Pour cela, chaque compteur à saturation se voit associé à un tag, comme pour les mémoires caches. Ce dernier mémorise le reste de l'adresse du branchement associé au compteur. Lorsque l'unité de prédiction démarre une prédiction, elle récupère les bits de poids fort de l'adresse du branchement et compare ceux-ci avec le tag. S’il y a un match, c'est signe que le compteur est bien associé au branchement à prédire. Dans le cas contraire, c'est signe qu'on fait face à une situation d’aliasing et le compteur n'est pas utilisé pour la prédiction. Le résultat transforme la PHT en une sorte de cache assez particulier, qui associe un compteur à saturation à chaque couple adresse-historique.

La technique du paragraphe précédent peut être encore améliorée afin de réduire l’aliasing. L’aliasing sur une unité de prédiction de branchement est similaire aux conflits d'accès au cache, où deux données/adresses atterrissent dans la même ligne de cache. Une PHT peut formellement être vue comme un cache directement adressé. Une solution pour limiter ces conflits d'accès à de tels, est de les transformer en un cache associatif à n voies. On peut faire la même chose avec les unités de prédiction de branchement. On peut dupliquer les PHT, de manière à ce que les bits de poids faible de l'adresse se voient attribuer à plusieurs compteurs à saturation, un par branchement possible. Ce faisant, on réduit les interférences entre branchements. Mais cette technique augmente la quantité de circuits utilisés et la consommation d'énergie, ainsi que le temps d'accès, sans compter qu'elle requiert d'utilisation de tags pour fonctionner à la perfection. Pour les unités de prédiction de branchement, les mesures à ce sujet ne semblent pas montrer un impact réellement important sur les performances, comparé à une organisation de type directement adressé.

Il est possible de pousser la logique encore plus loin en ajoutant des caches de victime et d'autres mécanismes courant sur les caches usuels.

La mitigation des interférences liées aux branchements biaisés

D'autres techniques limitent encore plus l’aliasing en tenant compte de certains points liés au biais des branchements. L’aliasing a un impact négatif quand deux branchements aliasés (qui sont attribués au même compteur à saturation) vont souvent dans des sens différents : si l'un est non-pris, l'autre a de bonnes chances d'être pris. De plus, la plupart des branchements sont biaisés (presque toujours pris ou presque toujours non-pris, à plus de 90/99% de chances) ou sont du moins très fortement orientés dans une direction qu'une autre. Plus un branchement a une probabilité élevée d' être pris ou non-pris, plus sa capacité à interférer avec les autres est forte. En conséquence, les branchements biaisés ou quasi biaisés sont les plus problématiques pour l’aliasing. Or, il est possible de concevoir des prédicteurs de branchements qui atténuent fortement les interférences des branchements biaisés ou quasi biaisés. C’est le cas de l’agree predictor et de l'unité de prédiction bimodale, que nous allons voir dans ce qui suit.

La prédiction par consensus (agree predictor) combine une unité de prédiction à historique global (idéalement de type gshare ou gselect, mais une unité normale marche aussi) et avec une unité de prédiction à un bit qui indique la direction privilégiée du branchement. L'unité de prédiction à un bit est en quelque sorte fusionnée avec le BTB. Le BTB contient, pour chaque branchement, un compteur à saturation de 1 bit qui indique si celui-ci est généralement pris ou non-pris. L'unité à historique global a un fonctionnement changé : elle calcule non pas la probabilité que le branchement soit pris ou non-pris, mais la probabilité que le résultat du branchement soit compatible avec le résultat de l'unité de prédiction de 1 bit. La prédiction finale vérifie que ces deux circuits sont d'accord, en faisant un NXOR entre les résultats des deux unités de prédiction de branchement. Des calculs simples de probabilités montrent que l'agree predictor a des résultats assez importants. Ses résultats sont d'autant meilleurs que les branchements sont biaisés et penchent fortement vers le côté pris ou non-pris.

L'unité de prédiction bimodale part d'une unité gshare, mais sépare la PHT globale en deux : une PHT dédiée aux branchements qui sont très souvent pris et une autre pour les branchements très peu pris. Les branchements très souvent pris vont interférer très fortement avec les branchements très souvent non-pris, et inversement. Par contre, les branchements très souvent pris n'interféreront pas entre eux, de même que les branchements non-pris iront bien ensemble. D'où l'idée de séparer ces deux types de branchements dans des PHT séparées, pour éviter le mauvais aliasing. Les deux PHT fournissent chacune une prédiction. La bonne prédiction est choisie par un multiplexeur commandé par une unité de sélection, qui se charge de déduire quelle unité a raison. Cette unité de sélection est une unité de prédiction basée sur des compteurs à saturation de 2bits. On peut encore améliorer l'unité de sélection de prédiction en n'utilisant non pas des compteurs à saturation, mais une unité de prédiction dynamique à deux niveaux, ou toute autre unité vue auparavant.

Les unités de prédiction à deux niveaux locales

Une autre solution pour éliminer l’aliasing est d'utiliser une PHT par branchement. C’est contre-intuitif, car on se dit que l'usage d'un registre d'historique global va avec une PHT unique, mais il y a des contre-exemples où un historique global est associé à plusieurs PHT ! Dans ce cas, chaque PHT est associée à un branchement, ce qui leur vaut le nom de PHT locale, à l'opposé d'une PHT unique appelée PHT globale. L'intérêt est de faire des prédictions faites sur mesure pour chaque branchement. Par exemple, le branchement X sera prédit comme pris, alors que le branchement Y sera non-pris, pour un historique global identique. La PHT à utiliser est choisie en fonction d'informations qui dépendent du branchement, typiquement les bits de poids faible de l'adresse du branchement. De telles unités fonctionnent comme suit : on choisit une PHT en fonction du branchement, puis le compteur à saturation est choisi dans cette PHT par le registre d'historique global. C'est conceptuellement la méthode utilisée sur les unités gselect, mais avec une implémentation différente. L'aliasing est aussi fortement réduit, bien que cette réduction soit semblable à celle obtenue avec les méthodes précédentes.

On peut aller plus loin et utiliser non seulement des PHT locales, mais aussi faire quelque chose d'équivalent sur l'historique. Au lieu d'utiliser un historique global, pour tous les branchements, on peut utiliser un historique par branchement. Concrètement, là où les méthodes précédentes mémorisaient le résultat des n derniers branchements, les méthodes qui vont suivre mémorisent, pour chaque branchement dans le BTB, le résultat des n dernières exécutions du branchement. Par exemple, si le registre d'historique contient 010, cela veut dire que le branchement a été non pris, puis pris, puis non pris. L'information mémorisée dans l'historique est alors totalement différente. Il y a un historique par entrée du BTB, soit un historique par branchement connu du processeur. Combiner PHT et historiques locaux donne une unité de prédiction à deux niveaux locale. Elle utilise des registres d'historique locaux de n bits, chacun étant couplé avec sa propre PHT locale contenant 2^n compteurs à saturation. Quand un branchement est exécuté, la PHT adéquate est sélectionnée, le registre d'historique de ce branchement est sélectionné, et l'historique local indique quel compteur à saturation choisir dans la PHT locale.

Implémenter cette technique demande d'ajouter un circuit qui sélectionne l'historique et la PHT adéquate en fonction du branchement. Le choix de la PHT et de l'historique se fait idéalement à partir de l'adresse du branchement. Mais c'est là une implémentation idéale, qui demande beaucoup de circuits pour un pouvoir de discrimination extrême. Généralement, l'unité de prédiction n'utilise que les bits de poids faible de l'adresse du branchement, ce qui permet de faire un choix correct, mais avec une possibilité d'aliasing. Pour récupérer l'historique local voulu, les bits de poids faible adressent une mémoire RAM, dont chaque byte contient l'historique local associé. La RAM en question est appelée la Branch History Table, ou encore la table des historiques locaux, que nous noterons BHT dans ce qui suivra. L'historique local est ensuite envoyé à la PHT adéquate, choisie en fonction des mêmes bits de poids faible du PC. Un bon moyen pour cela est d'accéder à toutes les PHT en parallèle, mais de sélectionner la bonne avec un multiplexeur, ce dernier étant commandé par les bits de poids faible du PC.

Cette unité de prédiction peut correctement prédire des branchements mal prédits par des compteurs à saturation. Tel est le cas des branchements dont le résultat est le suivant : pris, non pris, pris, non pris, et ainsi de suite. Même chose pour un branchement qui ferait : pris, non pris, non pris, non pris, pris, non pris, non pris, non pris, etc. En clair, il s'agit de situations où l'historique d'un branchement montre un pattern, un motif qui se répète dans le temps. Notons que l'apparition de tels motifs correspond le plus souvent à la présence de boucles dans le programme. Quand une boucle s’exécute, les branchements qui sont à l'intérieur tendent à exprimer de tels motifs. Avec de tels motifs, les compteurs à saturation feront des prédictions incorrectes, là où les prédicteurs avec registre d'historique feront des prédictions parfaites. Par contre, elles sont assez mauvaises pour les autres types de branchements. Les boucles étant très fréquentes dans de nombreux programmes, de telles unités de prédiction donnent généralement de bons résultats.

Un défaut des unités de prédiction purement locales de ce type est leur cout en termes de circuits. Utiliser un registre d'historique et une PHT par branchement a un cout élevé. Elles utilisent beaucoup de transistors, consomment beaucoup de courant, chauffent beaucoup, prennent beaucoup de place. Elles ont aussi des temps de calcul un peu plus important que les unités purement globales, mais pas de manière flagrante. De plus, les mesures montrent que l'historique global donne de meilleures prédictions que l'historique local, quand on regarde l'ensemble des branchements, mais à condition qu'on utilise des historiques globaux très longs, difficiles à mettre en pratique. Autant dire que les unités de prédiction avec un historique purement local sont rarement utilisées. Les gains en performance avec un historique local s'observent surtout pour les branchements qui sont dans des boucles ou pour les branchements utilisés pour concevoir des boucles, alors que l'implémentation globale marche bien pour les if..else (surtout quand ils sont imbriqués). Les deux sont donc complémentaires. Dans les faits, elles sont rarement utilisées du fait de leurs défauts, au profit d'unités de prédiction hybrides, qui mélangent historiques et PHT locaux et globaux.

Les unités de prédiction à deux niveaux mixtes (globale/locale)

Nous venons de voir les unités de prédiction de branchement à deux niveaux, aussi bien les implémentations avec un historique global (pour tous les branchements) et des historiques locaux (un par branchement). L'implémentation globale utilise un seul registre d'historique pour tous les branchements, alors que l’implémentation locale connaît l'historique de chaque branchement. Il est admis que l'historique global donne de meilleure prédiction que l'historique local. Mais les deux informations, historique global et historique de chaque branchement, sont des informations complémentaires, ce qui fait qu'il existe des approches hybrides. Certaines unités de prédiction utilisent les deux pour faire leur prédiction.

Par exemple, on peut citer la prédiction mixte (alloyed predictor). Avec celle-ci, la table des compteurs à saturation est adressée avec la concaténation : de bits de l'adresse du branchement, du registre d'historique global et du registre d'historique local adressé par l'adresse du branchement.

Une version optimisée de ce circuit permet d’accéder à la PHT et à la BHT en parallèle. Avec elle les bits de poids faible de l'adresse du branchement sont concaténés avec l'historique global. Le résultat est ensuite envoyé à plusieurs PHT locales distinctes, en parallèle. Les différences PHT envoient leurs résultats à un multiplexeur, commandé par l'historique local, qui sélectionne le résultat adéquat. L'inconvénient de cette mise en œuvre est que le circuit est assez gros, notamment en raison de la présence de plusieurs PHT séparées.

La prédiction de branchement avec des perceptrons

Les méthodes précédentes utilisent de un ou plusieurs comparateurs à saturation par historique possible. Sachant qu'il y a 2^n valeurs possibles pour un historique de n bits, le nombre de compteurs à saturation augmente exponentiellement avec la taille de l'historique. Cela limite grandement la taille de l'historique, alors qu'on aurait besoin d'un historique assez grand pour faire des prédictions excellentes. Pour éviter cette explosion exponentielle, des alternatives basées sur des techniques d'apprentissage artificiel (machine learning) existent. Un exemple est celui des unités de prédiction de branchement des processeurs AMD actuels se basent sur des techniques dites de neural branch prediction, basée sur des perceptrons.

La quasi-totalité des unités de prédiction de ce type se basent sur des perceptrons, un algorithme d'apprentissage automatique très simple, que nous aborderons plus bas. En théorie, il est possible d'utiliser des techniques d'apprentissage automatiques plus élaborées, comme les techniques de back-propagation, mais cela n'est pas possible en pratique. Rappelons qu'une unité de prédiction de branchement doit idéalement fournir sa prédiction en un cycle d'horloge, et qu'un temps de calcul de la prédiction de 2 à 3 cycles est déjà un problème. L'implémentation d'un perceptron est déjà problématique de ce point de vue, car elle demande d'utiliser beaucoup de circuits arithmétiques complexes (multiplication et addition). Autant dire que les autres techniques usuelles de machine learning, encore plus gourmandes en calculs, ne sont pas praticables.

Les perceptrons et leur usage en tant qu'unité de prédiction de branchements

L'idée derrière l'utilisation d'un perceptron est que l'historique est certes utile pour prédire si un branchement sera pris ou non, mais certains bits de l'historique sont censés être plus importants que d'autres. En soi, ce genre de situation est réaliste. Il arrive que certains branchements soient pris uniquement si les deux branchements précédents ne le sont pas, ou que si l'avant-dernier branchement est lui aussi pris. Mais les autres résultats de branchement présents dans l'historique ne sont pas ou peu utiles. En conséquence, deux historiques semblables, qui ne sont différents que d'un ou deux bits, peuvent donner des prédictions presque identiques. Dans ce cas, on peut faire la prédiction en n'utilisant que les bits identiques entre ces historiques, ou du moins en leur donnant plus d'importance qu'aux autres. On exploite alors des corrélations avec certains bits de l'historique, plutôt qu'avec l'historique entier lui-même.

Pour coder ces corrélations, on associe un coefficient à chaque bit de l'historique, qui indique à quel point ce bit est important pour déterminer le résultat final. Ce coefficient est proportionnel à la corrélation entre le résultat du branchement associé au bit de l'historique, et le branchement à prédire. Notons que ces coefficients sont des nombres entiers qui peuvent être positifs, nuls ou négatifs. Un coefficient positif signifie que si le branchement associé a été pris, alors le branchement à prédire a de bonnes chances de l'être aussi (et inversement). Un coefficient nul signifie que les deux branchements sont indépendants et que le bit de l'historique associé n'est pas à prendre en compte. Pour un coefficient négatif, cela signifie que si le branchement associé a été pris, alors le branchement à prédire a de bonnes chances d'être non-pris (et inversement). Les coefficients en question sont généralement compris entre -1 et 1.

Une fois qu'on connait ces coefficients de corrélations, on peut calculer la probabilité que le branchement à prédire soit pris, avec des calculs arithmétiques simples. Par contre, cela demande que l'interprétation de l'historique soit modifiée. L'historique est toujours codé avec des bits, avec un 1 pour un branchement pris et un 0 pour un branchement non-pris. Mais dans les calculs qui vont suivre, un branchement pris est codé par un 1, alors qu'un branchement non-pris est codé par un -1 ! Ce détail permet de simplifier grandement les calculs. Dans sa version la plus simple, le perceptron calcule un nombre Z qui est positif ou nul si le branchement est pris, négatif s'il ne l'est pas. Tous les coefficients $p_{i}$ sont alors des nombres relatifs, pouvant être positifs, nuls ou négatifs. Ils sont généralement compris entre -1 et 1. La formule devient donc celle-ci :

Z=w_{0}+\sum _{i}(h_{i}\times w_{i})

Sur le plan mathématique, le perceptron effectue un produit scalaire entre deux vecteurs : l'historique et le vecteur des poids.

Choisir les coefficients adéquats est le but de l'algorithme du perceptron. L'unité de prédiction part de poids par défaut, qui sont mis à jour à chaque bonne ou mauvaise prédiction. Toute la magie de cet algorithme tient dans la manière dont sont mis à jour les poids. L'idée est de prendre le vecteur des poids, puis d'ajouter ou soustraire l'historique suivant le résultat du branchement. Les poids évoluent ainsi à chaque branchement, améliorant leurs prédictions d'une exécution à l'autre. La règle de mise à jour des poids est donc la suivante :

w_{i}\leftarrow w_{i}+t\times h_{i}

, avec t = 1 pour un branchement pris, -1 pour un branchement non-pris.

L'implémentation matérielle des perceptrons et ses optimisations

Les calculs réalisés par un perceptrons sont simples, juste des multiplications et des additions et cela se sent dans la conception du circuit. Le circuit est composé de plusieurs perceptrons, un par entrée du BTB, un par branchement pour simplifier. Pour cela, on utilise une mémoire SRAM qui mémorise les poids de chaque perceptron. La SRAM est adressée par les bits de poids faible du program counter, de l'adresse du branchement. Une fois les poids récupérés, ils sont envoyés à un circuit de calcul de la prédiction, composé de circuits multiplieurs suivis par un additionneur multi-opérande. Le circuit de mise à jour des poids récupère la prédiction, les poids du perceptron, mais aussi le résultat du branchement. La mise à jour étant une simple addition, le circuit est composé d'additionneurs/soustracteurs, couplés à des registres pour mémoriser la prédiction et les poids du perceptron en attendant que le résultat du branchement soit disponible. Vu qu'il y a un délai de quelques cycles avant que le résultat du branchement soit disponible et que les prédictions doivent continuer pendant ce temps, les poids du perceptron et la prédiction sont stockés dans des FIFOs lues/écrites à chaque cycle.

Rien de bien compliqué sur le principe, mais un tel circuit pose un problème en pratique. Rappelons que le perceptron doit fournir un résultat en moins d'un cycle d'horloge, et cela tient compte du temps nécessaire pour sélectionner le perceptron à partir de l'adresse du branchement. C'est un temps très court, surtout pour un circuit qui implique des multiplications. Or, le temps de calcul d'une addition est déjà très proche d'un cycle d'horloge, alors que les multiplications prennent facilement deux à trois cycles d'horloge. Autant dire que si on ajoute le temps d'accès à une petite SRAM, pour récupérer le perceptron, c'est presque impossible. Mais quelques optimisations simples permettent de rendre le calcul plus rapide.

Premièrement, la taille de la SRAM est réduite grâce à quelques économies assez simples. Notamment, le perceptron utilise des poids codés sur quelques bits, généralement un octet, parfois 7 ou 5 bits, guère plus. Les poids sont encodés en complément à 1 ou en complément à 2, là où les perceptrons normaux utilisent des nombres flottants. Rien que ces deux choix simplifient les circuits et les rendent plus rapides. Le désavantage d'utiliser peu de bits par poids est une perte mineure en termes de taux de prédiction, qui est plus que compensée par l'économie en portes logiques, qui permet d'augmenter la taille de la SRAM. D'autres optimisations portent sur le circuit de calcul. Par exemple, la multiplication $h_{i}\times w_{i}$ est facultative. Vu que l'historique contient les valeurs et -1, il suffit d'additionner le poids associé si la valeur est 1 et de le soustraire s'il vaut -1. On peut même simplifier la soustraction et se limiter à une complémentation à un (une inversion des bits du poids). En faisant cela, les circuits multiplieurs disparaissent et le circuit de prédiction se résume à un simple additionneur multi-opérande couplé à quelques inverseurs commandables.

Certains perceptrons prennent en compte à la fois l'historique global et l'historique local pour faire leur prédiction. Les deux historiques sont simplement concaténés et envoyés en entrée du perceptron. Cela marche assez bien car les perceptrons peuvent utiliser des historiques de grande taille sans problèmes. Par contre, il y a besoin d'ajouter une branch history table au circuit, ce qui demande des portes logiques en plus, mais aussi un temps de calcul supplémentaire (l'accès à cette table n'est pas gratuit).

Les avantages et inconvénients des perceptrons pour la prédiction de branchements

L'avantage des unités de prédiction à base de perceptrons est qu'elles utilisent un nombre de portes logiques qui est proportionnel à la taille de l'historique, et non pas exponentiel. Cela permet d'utiliser un historique de grande taille, et donc d'obtenir un taux de bonnes prédictions très élevé, sans avoir à exploser le budget en portes logiques. Leur désavantage est que leurs performances de prédiction sont moins bonnes à historique équivalent. C’est la contrepartie du fait d'utiliser beaucoup moins de portes logiques. Là où les unités de prédictions précédentes avaient des taux de prédictions très corrects mais devaient se débrouiller avec des historiques courts, les perceptrons font l'inverse. Un autre désavantage est que les calculs des perceptrons prennent du temps, et leur prédiction peut facilement prendre deux voire trois cycles d’horloge.

Un autre défaut est que les perceptrons ont des taux de prédiction correctes élevées seulement quand certaines conditions mathématiques sont respectées par les historiques. La condition en question est que les historiques correspondants à un branchement pris et les historiques où ce même branchement est non-pris doivent être linéairement séparables. La notion de linéairement séparable est un peu difficile à comprendre. Pour l'expliquer, imaginez que les N bits de l'historique forme un espace à N-dimensions discrets. Chaque historique est un point dans cet espace N-dimensionnel et chaque bit sert de coordonnée pour se repérer dans cet espace. Une fonction est linéairement séparable si l'espace N-dimensionnel peut être coupé en deux par un hyperplan : d'un côté de ce plan se trouvent les historiques des branchements pris, de l'autre se trouvent les historiques des branchements non-pris. Cet hyperplan est défini par l'ensemble des points qui respecte l'équation suivante :

w_{0}+\sum _{i}(h_{i}\times w_{i})=0

Un exemple où cette condition est respectée est quand le résultat d'une prédiction se calcule avec un ET entre plusieurs branchements de l'historique. Si un branchement est pris quand plusieurs branchements de l’historique sont tous pris ou tous non-pris, la condition est respectée et le perceptron donnera des prédictions correctes. Un exemple où cette condition n'est pas respectée est une banale fonction XOR. Prenons l'exemple d'un historique global de 2 bits. Imaginons que le branchement à prédire soit pris : soit quand le premier branchement de l'historique est pris et le second non-pris, soit quand le premier est non-pris et le second pris. Concrètement, la prédiction exacte se calcule en faisant un XOR entre les deux bits de l'historique. Mais dans ce cas, la condition "linéairement séparable" n'est pas respectée et le perceptron n'aura pas des performances optimales. Heureusement, les branchements des programmes informatiques sont une majorité à respecter la condition de séparation linéaire, ce qui rend les perceptrons parfaitement adaptés à la prédiction de branchements.

Les unités de prédictions de branchement neuronales utilisent idéalement un perceptron par branchement. Cela demande d'associer, l'adresse du branchement pour chaque perceptron, généralement en donnant un perceptron par entrée du BTB. Mais une telle organisation n'est pas possible en pratique, car elle demanderait d'ajouter un tag à chaque perceptron/entrée du BTB, ce qui demanderait beaucoup de circuits et de ressources matérielles. Dans les faits l'association entre un branchement et un perceptron se fait en utilisant les bits de poids faible de l'adresse de branchement. Ces bits de poids faible de l'adresse de branchement sélectionnent le perceptron adéquat, puis celui-ci utilise l'historique global pour faire sa prédiction. Mais faire cela entrainera l'apparition de phénomènes d'aliasing, comme pour les unités de prédiction à deux niveaux. Les techniques vues précédemment peuvent en théorie être adaptées sur les unités à perceptrons, dans une certaine mesure.

Notons que les perceptrons sont des algorithmes ou des circuits qui permettent de classer des données d'entrée en deux types. Ici, la donnée d'entrée est l'historique global et la sortie du perceptron indique si le branchement prédit est pris ou non-pris. Ils ne sont donc pas adaptés à d'autres tâches de prédiction, comme pour le préchargement des lignes de cache ou la prédiction de l'adresse de destination d'un branchement, ou toute autre tâche d'exécution spéculative un tant soit peu complexe. Leur utilisation reste cantonnée à la prédiction de branchement proprement dit, guère plus. Par contre, les autres techniques vues plus haut peuvent être utilisées pour le préchargement des lignes de cache, ou d'autres mécanismes de prédiction plus complexes, que nous aborderons dans la suite du cours.

La prédiction des branchements des boucles

Les unités de prédiction avec un historique marchent très bien pour prédire les branchements des if...else, mais elles sont inadaptées pour prédire les branchements des boucles. L'usage de la prédiction statique ou de compteurs à saturation permet d'obtenir de meilleures performances pour ce cas de figure. L'idée est d'utiliser deux unités de prédiction séparées : une unité avec un historique, et une autre spécialisée dans les boucles. Concrètement, les unités de prédiction modernes essayent de détecter les branchements des boucles afin de les mettre à part. En soi, ce n'est pas compliqué les branchements des boucles sont presque toujours des branchements descendants et réciproquement. De plus, ces branchements sont pris à chaque répétition de la boucle, et ne sont non-pris que quand on quitte la boucle. Dans ces conditions, la prédiction statique marche très bien pour les boucles, notamment les boucles FOR. De telles unités prédisent que les branchements des boucles sont toujours pris, ce qui donne des prédictions qui sont d'autant meilleures que la boucle est répétée un grand nombre de fois.

Certaines unités de prédiction de branchement sont capables de prédire spécifiquement les branchements de boucles FOR imbriquées, à savoir où une boucle FOR est dans une autre boucle FOR. Concrètement, cela permet de répéter la première boucle FOR plusieurs fois de suite, souvent un grand nombre de fois. Rappelons qu'une boucle FOR répète une série d'instruction N fois, le nombre N étant appelé le compteur de boucle. Ce qui fait que les branchements d'une boucle FOR sont pris n − 1 fois, la dernière exécution étant non prise. Avec les boucles imbriquées, le compteur de boucle peut changer d'une répétition à l'autre, mais ce n'est que rarement le cas. Dans de nombreux cas, le compteur de boucle reste le même d'une répétition à l'autre. Ce qui fait qu'une fois la boucle exécutée une première fois, on peut prédire à la perfection les exécutions suivantes. Pour cela, il suffit de déterminer le compteur de boucle après la première exécution de la boucle, puis de le mémoriser dans un compteur. Lors des exécutions suivantes de la boucle, on compte le nombre de fois que le branchement de la boucle s'exécute : il est prédit comme pris tant que le compteur est différent du compteur de boucle, mais non-pris en cas d'égalité.

La prédiction basée sur un l'utilisation de plusieurs unités de branchement distinctes

Il est possible de combiner plusieurs unités de prédiction de branchement différentes et de combiner leurs résultats en une seule prédiction. Il est par exemple possible d'utiliser plusieurs unités de prédiction, chacune utilisant des historique de taille différente. Pour donner un exemple simple, on pourrait avoir une unité avec un historique de 2 bits, une autre avec un historique de 3 bits, une autre de 4 bits, etc. Il est fréquent que les tailles d'historiques utilisées suivent une formule mathématique précise, appelée suite géométrique, ce qui est un mot bien barbare pour dire que l'on passe d'un historique au suivant en multipliant sa taille par une constante bien précise. Par exemple, on pourrait avoir des historiques de taille 2, 4, 8, 16, 32. Avec cette méthode, les branchements qui ont un motif répétitif sont alors parfaitement détectés, peu importe sa taille. Par exemple, un branchement avec un historique dont le cycle est pris, non-pris, non-pris, sera parfaitement prédit avec un historique de 3 bits, 6 bits, ou de 3*n bits, mais pas forcément avec un historique de 4 ou 8 bits. De ce fait, utiliser plusieurs unités de branchement avec plusieurs tailles d'historique fonctionne plutôt bien.

De nombreuses unités de prédiction de branchement combinent les résultats de plusieurs unités de prédiction différentes. Mais elles ne vont pas utiliser un historique par unité, mais une unité d'un certain type (compteurs à saturation, historique global, autre) ou des unités spécialisée dans un type de branchements bien précis. On peut par exemple combiner une unité de prédiction spécialisée dans les boucles, une unité de prédiction 2 bits basée sur des compteurs à saturation, une unité de prédiction statique et une unité gshare. Tout le problème est de décider quelle unité a fait la bonne prédiction, comment combiner les résultats des différentes unités de prédiction. Soit on choisit un résultat qui parait plus fiable que les autres, soit on combine les résultats pour faire une sorte de moyenne des prédictions.

La méta-prédiction

La méthode la plus simple de choisir le résultat d'une unité de prédiction parmi toutes les autres. Pour implémenter le tout, il suffit d'un multiplexeur qui effectue le choix de la prédiction. Reste à commander le multiplexeur, ce qui demande un circuit méta-prédicteur qui sélectionne la bonne unité de prédiction. Le circuit méta-prédicteur est conçu avec les mêmes techniques que les unités de prédiction de branchement elle-mêmes. Dans le cas le plus simple, il s'agit d'un simple compteur à saturation, mis à jour suivant la concordance des prédictions avec le résultat effectif du branchement. On peut aussi utiliser toute autre technique de prédiction vue plus haut, mais cela demande alors plus de circuits. C'est cette technique qui est utilisée dans l'unité de prédiction bimodale vue précédemment.

La fusion de prédictions

Une autre solution est de combiner le résultat des différentes unités de prédiction avec une fonction mathématique adéquate. Avec un nombre impair d'unités de prédiction, une méthode assez efficace est de simplement prendre le résultat majoritaire. Si une majorité d'unités pense que le branchement est pris, alors on le considère comme pris, et comme non pris dans le cas contraire. Par contre, avec un nombre pair d'unités, cette méthode simple ne marche pas. Il y a un risque que la moitié des unités de prédiction donne un résultat différent de l'autre moitié. Et faire un choix dans ce cas précis est rarement facile. Une solution serait de prioriser certaines unités, qui auraient un poids plus important dans le calcul de la majorité, de la moyenne, mais elle est rarement appliquée, car elle demande un nombre d'unités important (au moins 4).

L'unité de prédiction de branchement « e-gskew » utilise trois unités gshare et combine leurs résultats avec un vote à majorité. Les trois unités gshare utilisent des XOR légèrement différents, dans le sens où les bits de l'adresse du branchement choisi ne sont pas les mêmes dans les trois unités, sans compter que le résultat du XOR peut subir une modification qui dépend de l'unité de prédiction choisie. Autrement dit, la fonction de hachage qui associe une entrée à un branchement dépend de l'unité.

La priorisation des unités de prédiction

Une autre technique consiste à prioriser les unités de prédiction de branchement. Une unité de prédiction complexe est utilisé en premier, mais une seconde unité plus simple (généralement des compteurs à saturation) prend le relai en cas de non-prédiction.

Les optimisations de la prédiction de branchements

La prédiction de branchement est complexe et toute économie est bonne à prendre. Pour améliorer les performances, ou simplement améliorer l'utilisation du BTB et des PHT, diverses techniques ont été inventées. Ces techniques marchent quel que soit l'unité de prédiction prise en compte. Elles peuvent s'appliquer aussi bien aux unités basées sur des perceptrons, que sur des unités à deux niveaux ou des unités de prédiction dynamique en général. Ces techniques sont assez variés : certaines profitent du fait que de nombreux branchements sont biaisés, d'autres tentent de réduire les interférences entre branchements sans utiliser l'historique global/local, etc.

Le filtrage de branchements

Une première optimisation permet d'économiser l'usage des différentes ressources matérielles, comme la BTB ou les PHT, en les réservant aux branchements non-biaisés. Idéalement, les branchements biaisés peuvent être prédits en utilisant des techniques très simples. D'où l'idée d'utiliser deux unités de prédiction spécialisées : une pour les branchements biaisés et une autre plus complexe. L'unité de prédiction pour les branchements biaisés est une unité de prédiction à 1 bit qui indique si le branchement est pris ou non, ce qui suffit largement pour de tels branchements.

Cette technique s'appelle le filtrage de branchement et son nom est assez parlant. On filtre les branchements biaisés pour éviter qu'ils utilisent des PHT et d'autres ressources qui gagneraient à être utilisées pour des branchements plus difficiles à prédire. Appliquer cette idée demande de reconnaître les branchements fortement biaisés d'une manière ou d'une autre, ce qui est plus facile à dire qu'à faire. Une solution similaire enregistre quels branchements sont biaisés dans le BTB, et utilise cette information pour faire des prédictions.

L'usage de fonctions de hashage pour indexer les diverses SRAM/tables

Plus haut, nous avons vu que les unités de prédiction de branchement contiennent des structures qui sont adressées par l'adresse de branchement. Tel est le cas du Branch Target Buffer, de certaines PHT globales ou locales, de la Branch History Table qui stocke les historiques locaux, ou encore de la SRAM des poids des unités à base de peerceptrons. En pratique, ces structures sont adressées non pas par l'adresse de branchement complète, mais pas les bits de poids faible de cette adresse. Cela a pour conséquence l'apparition d'un aliasing lié au fait que ces structures vont confondre deux branchements pour lesquels les bits de poids faible de l'adresse sont identiques. Il est possible d'utiliser autre chose que les bits de poids faible de l'adresse du branchement, afin de limiter les interférences. Et les possibilités sont multiples. Les possibilités en question s'inspirent des traitements effectués sur les adresses des banques dans les mémoires évoluées.

Une première solution serait de faire un XOR entre les bits de poids faible de l'adresse du branchement, et d'autres bits de cette même adresse. Ainsi, deux branchements éloignés en mémoire donneraient des résultats différents, même si leurs bits de poids faible sont identiques.

Une autre possibilité serait de diviser l'adresse du branchement par un nombre et de garder le reste. Ce calcul de modulo n'est en soi pas très différent du fait de conserver seulement les bits de poids faible. Conserver les N bits de poids faible consiste en effet à prendre le modulo par 2^N de l'adresse. Ici, l'idée serait de faire un modulo par un nombre P, qui serait un nombre premier proche de 2^N. Le fait que le nombre soit premier limite les cas où deux adresses différentes donneraient le même reste, ce qui réduit l'aliasing. Le fait de prendre un nombre proche de 2^N pour une entrée de N bits est que le résultat reste assez proche de ce qu'on obtiendrait en gardant les bits de poids faible, cette dernière étant une solution pas trop mauvaise. D'autres possibilités similaires se basent sur des réductions polynomiales ou d'autres astuces impliquant des nombres premiers.

L'efficacité de ces méthodes dépend grandement de la taille de la SRAM/table considérée, des adresses des branchements et de beaucoup d'autres paramètres. La réduction des interférences par telle ou telle méthode dépend aussi de l'unité de prédiction considérée. Les résultats ne sont pas les mêmes selon que l'on parle d'une unité à perceptrons ou d'une unité à deux niveaux ou d'unités à base de compteurs à saturation, ou que l'on parle du BTB. Par contre, toutes les méthodes ne sont pas équivalentes en termes de temps de calcul ou de portes logiques. Autant la première solution avec un XOR ajoute un temps de calcul négligeable et quelques portes logiques, autant les autres méthodes requièrent l'ajout d'un diviseur très lent et gourmand en portes logiques pour calculer des modulos. Elles ne sont généralement pas praticables pour ces raisons, le temps de calcul serait trop élevé.

◄ Retour vers « Les exceptions précises et branchements »

Sommaire du livre

Continuer vers « Les optimisations du chargement des instructions » ►