Prédiction des branchements : compteurs à deux bits, prédicteurs corrélés et cibles
Le coût d'une mauvaise prédiction, prédiction statique, compteur saturant à deux bits avec démonstration sur les boucles, gshare et TAGE, tampon des cibles de branchement et pile de retour, code sans branchements.
https://www.electronics-engineering.com/fr/prediction-des-branchements-compteur-a-deux-bits-gshare-tage/
Dans un programme typique, une instruction sur cinq ou six est un branchement. Dans un processeur à pipeline profond et à large fenêtre d’exécution dans le désordre, chaque branchement dont la direction est inconnue bloquerait le flux pendant des dizaines de cycles. La solution est de deviner, et de le faire très bien : les prédicteurs modernes se trompent sur moins d’un branchement sur cent. Dans cette leçon, nous regardons le coût d’une mauvaise prédiction, les compteurs à deux bits avec la démonstration de leur avantage sur les boucles, les prédicteurs corrélés, la prédiction de la cible et la façon d’écrire du code que les prédicteurs aiment.
Le coût d’une mauvaise prédiction
Quand le processeur s’aperçoit qu’il a mal prédit, il jette toutes les instructions spéculatives et repart de la bonne adresse (leçon sur l’exécution dans le désordre). Les cycles perdus, la pénalité, sont à peu près autant qu’il en faut entre la recherche de l’instruction et la résolution du branchement : 15-20 dans les processeurs modernes. Avec l’équation des performances avec les arrêts :
![]()
avec
la fraction d’instructions qui sont des branchements,
la fraction mal prédite et
la pénalité. Avec 20 % de branchements, 5 % d’erreurs et une pénalité de 15 cycles, on ajoute 0,15 cycle par instruction : sur un processeur qui pourrait valider 4 instructions par cycle (CPI idéal 0,25), le temps d’exécution augmente de 60 %. Chaque point de pourcentage de précision compte.
Prédiction statique et compteurs à un bit
La prédiction statique décide sans regarder l’historique : par exemple « les branchements en arrière sont pris » (ce sont presque toujours des fermetures de boucles) et « ceux en avant ne le sont pas ». Elle fonctionne pour environ 70 % des branchements.
La prédiction dynamique la plus simple mémorise, pour chaque branchement, ce qu’il a fait la dernière fois : un bit, dans une table indexée par quelques bits de l’adresse du branchement. Elle a un défaut évident sur les boucles.
Le compteur à deux bits

Le compteur saturant à deux bits compte de 0 à 3 : il augmente quand le branchement est pris, diminue quand il ne l’est pas, sans dépasser les extrémités. Il prédit « pris » dans les états 2 et 3, « non pris » dans les états 0 et 1.
Théorème. Une boucle interne à
itérations, exécutée de façon répétée, a un branchement de fermeture pris
fois et non pris à la dernière. Le prédicteur à un bit se trompe deux fois par exécution de la boucle, celui à deux bits une seule fois.
Démonstration. *Un bit.* À la dernière itération, le bit dit « pris » (c’était le cas la fois précédente) et le branchement ne l’est pas : première erreur, et le bit devient « non pris ». À la première itération de l’exécution suivante, le bit dit « non pris » mais le branchement est pris : deuxième erreur. Les
autres itérations sont bien prédites. *Deux bits.* Après les itérations prises, le compteur est à 3. À la dernière itération, il prédit « pris » et se trompe, mais il ne descend qu’à 2, qui prédit encore « pris ». À la première itération de l’exécution suivante, la prédiction est juste et le compteur revient à 3. Une seule erreur par exécution. ∎
Avec
, la précision passe de 80 à 90 %. L’hystérésis du compteur empêche une exception isolée de changer la prédiction.
Les prédicteurs corrélés
Beaucoup de branchements dépendent de ce que des branchements précédents ont fait : si un if (x > 0) a été pris, un if (x < 0) suivant ne le sera pas. Un prédicteur corrélé garde un registre d’historique global, les résultats des
derniers branchements exécutés (1 si pris, 0 sinon), et l’utilise avec l’adresse du branchement pour choisir le compteur. Dans le prédicteur gshare, l’indice de la table est le XOR des bits de l’adresse et des bits de l’historique : le même branchement utilise des compteurs différents dans des contextes différents.
Les prédicteurs actuels, comme la famille TAGE, combinent des tables avec des historiques de longueurs différentes, de quelques branchements à des centaines, et choisissent la prédiction de la table à l’historique le plus long qui a une information fiable. Ils atteignent des précisions de 97-99 % sur des programmes typiques. Certains utilisent aussi de petits perceptrons, une forme élémentaire de réseau de neurones.
Prédire aussi où l’on saute
Savoir qu’un branchement est pris ne suffit pas : il faut savoir où il va, avant même que l’instruction soit décodée. Le tampon des cibles de branchement (BTB) est un cache indexé par l’adresse de l’instruction qui renvoie l’adresse de destination de la dernière fois. Les retours de fonction ont un prédicteur dédié, la pile des adresses de retour, qui imite la pile d’appels : à chaque appel on empile l’adresse de retour, à chaque retour on la dépile. Les branchements indirects (appels de fonctions virtuelles, instructions switch compilées en tables) ont des prédicteurs qui utilisent aussi l’historique.
Écrire du code prévisible
Le prédicteur ne fait pas de miracles avec des branchements qui dépendent de données aléatoires. L’exemple classique : une boucle qui additionne seulement les éléments d’un tableau supérieurs à un seuil va beaucoup plus vite si le tableau est trié, parce que le branchement devient une longue suite de « non pris » suivie d’une longue suite de « pris ». Sur des données aléatoires, le prédicteur se trompe une fois sur deux. Les contre-mesures :
- transformer le branchement en opération sans branchement, avec des déplacements conditionnels (
cmovsur x86, select en RISC-V avec extensions) ou avec l’arithmétique :sum += (x > threshold) * x. Les compilateurs le font tout seuls quand les deux branches sont courtes ; - réordonner les données ou les tests, en mettant d’abord les cas les plus fréquents ;
- avec des profils d’exécution, laisser le compilateur disposer le code de sorte que le chemin courant ne branche pas.






Sono l'autore di questa pagina su «Predizione dei salti: contatori a due bit, predittori correlati e bersagli». Se qualcosa non è chiaro, se vi serve un esempio in più o volete approfondire un punto, scrivetelo qui sotto nei commenti: rispondo personalmente. Se la pagina vi è stata utile, lasciate un voto con le stelle in cima all'articolo.I am the author of this page on “Branch prediction: two-bit counters, correlating predictors and targets”. If something is unclear, if you need another example or want to go deeper into a point, write it in the comments below: I answer personally. If the page was useful, leave a star rating at the top of the article.