Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Architecture des ordinateurs

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/

Pas encore de vote : soyez le premier à noter cette page.

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 :

    \[ \Delta CPI = f_{branch}\cdot m\cdot p \]

avec f_{branch} la fraction d’instructions qui sont des branchements, m la fraction mal prédite et p 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

Machine à états du prédicteur à compteur saturant à deux bits
Quatre états, de 11 (fortement pris) à 00 (fortement non pris). Un branchement pris (T) déplace l’état vers la gauche, un non pris (N) vers la droite, sans sortir des extrémités. Dans les deux états de gauche la prédiction est « pris », dans ceux de droite « non pris » : il faut deux erreurs consécutives pour changer la prédiction.

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 à n itérations, exécutée de façon répétée, a un branchement de fermeture pris n - 1 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 n - 2 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 n = 10, 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 h 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 (cmov sur 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.
S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x