Prédiction de branchement

Le chapitre sur le pipeline se terminait sur un problème. Un branchement conditionnel n’est tranché qu’en EX, mais l’étage de fetch doit choisir l’adresse suivante à chaque cycle. Dans le pipeline à 5 étages, une erreur coûte 2 cycles. Dans un cœur moderne, où 15 à 20 étages séparent le fetch de la résolution du branchement, elle coûte environ 15 à 20 cycles. Et dans un code typique, on trouve un branchement toutes les cinq à sept instructions.

Les CPU n’attendent donc pas. Ils prédisent l’issue de chaque branchement et continuent de lire le long du chemin prédit. Quand la prédiction est juste, le branchement ne coûte rien. Quand elle est fausse, les instructions lues après lui sont jetées et la lecture repart de la bonne adresse.

Même un jmp inconditionnel a besoin d’être prédit. L’étage de fetch doit choisir l’adresse suivante avant que l’instruction ait été décodée : il ne sait pas encore que les octets qu’il vient de lire forment un saut.

Jeter le mauvais chemin

Les instructions lues après un branchement prédit s’exécutent de façon spéculative : leurs résultats ne doivent pas devenir définitifs tant que le branchement n’est pas confirmé. Un CPU peut soit garder les nouvelles valeurs de registres dans un stockage caché et les recopier une fois le branchement confirmé, soit noter les anciennes valeurs pour pouvoir revenir en arrière. Dans les deux cas, cela demande beaucoup de comptabilité, surtout quand un second branchement est prédit avant que le premier ait été vérifié. Le chapitre suivant, sur l’exécution dans le désordre et la spéculation, montre comment font les cœurs modernes. Celui-ci parle de la prédiction elle-même.

La prédiction statique

Les prédicteurs les plus simples ignorent l’historique et appliquent une règle fixe :

• Toujours non pris : continuer à lire en séquence. C’est ce que faisait le pipeline à 5 étages.
• Arrière pris, avant non pris (BTFN, backward taken, forward not taken) : un branchement qui saute en arrière est probablement le bas d’une boucle, donc on parie « pris ». Un branchement qui saute en avant est souvent un if qui contourne du code rare, comme la gestion d’erreurs, donc on parie « non pris ».

Les compilateurs peuvent aider en disposant le code pour que le chemin probable soit le chemin qui continue en séquence. En C, __builtin_expect (GCC, Clang) et les attributs [[likely]] / [[unlikely]] de C++20 indiquent dans quel sens un branchement va d’habitude, et l’optimisation guidée par profil le mesure sur une vraie exécution. Le x86 a eu des préfixes d’indication de branchement, mais la plupart des cœurs les ignorent depuis des années. C’est la disposition du code qui compte.

La démo ci-dessous exécute deux boucles imbriquées : une boucle interne de 5 itérations, lancée 10 fois. Elle rejoue ensuite ses 60 branchements conditionnels dans le prédicteur de votre choix :

Always not taken rate presque tous les branchements, car les deux boucles sautent en arrière presque à chaque fois. Passez à backward taken : seules les sorties de boucle sont fausses, 11 en tout — 10 sorties de la boucle interne et une de la boucle externe.

La prédiction dynamique : se souvenir

Un prédicteur dynamique tient une petite table, indexée par l’adresse du branchement, qui note comment chaque branchement s’est comporté. Elle est organisée comme un cache : les bits de poids faible de l’adresse choisissent une entrée, et deux branchements dont les adresses partagent ces bits peuvent entrer en collision.

Un bit : « comme la dernière fois »

La table la plus simple garde un bit par branchement : pris ou non, la dernière fois. Choisissez 1-bit dans la démo ci-dessus : 20 erreurs, plus que la règle statique.

Regardez le jl interne dans le tableau par branchement. À chaque exécution de la boucle interne, le prédicteur se trompe deux fois : une fois à la sortie (il attendait « pris »), et une autre à la première itération de l’exécution suivante, car la sortie a laissé son bit sur « non pris ». Une boucle placée dans une autre boucle paie ce double prix à chaque fois.

Deux bits : une seconde chance

La solution est de ne changer la prédiction qu’après deux erreurs consécutives. La conception habituelle est un compteur saturant de 2 bits par branchement, avec quatre états :

Un branchement pris fait monter le compteur, un branchement non pris le fait descendre, avec un arrêt à 0 et à 3. Une seule sortie de boucle ne fait passer le compteur que de fortement à faiblement pris : l’exécution suivante de la boucle est toujours bien prédite. Choisissez 2-bit : 11 erreurs, seulement les sorties.

Tanenbaum décrit la même idée sous forme d’une machine à quatre états qui garde « ce que le branchement devrait faire » et « ce qu’il a fait la dernière fois ». Le compteur saturant est la version que la plupart des conceptions utilisent, et il se comporte de la même façon sur les boucles.

Quand l’historique compte : la corrélation

Un compteur par branchement ne sait que combien de fois un branchement est pris. Certains branchements suivent plutôt un motif. Cette boucle teste si i est pair : son jz alterne entre pris et non pris :

Avec 2-bit, le jz est faux les 32 fois. Le compteur fait l’aller-retour entre faiblement non pris et faiblement pris, toujours avec un temps de retard. 1-bit ne fait pas mieux.

Choisissez global history. Ce prédicteur garde un registre à décalage des 8 dernières issues de tous les branchements, et l’utilise avec l’adresse du branchement pour choisir un compteur de 2 bits. Le même jz a désormais un compteur pour « après une itération impaire » et un autre pour « après une paire ». Une fois chaque compteur entraîné, le jz ne se trompe plus : quelques erreurs pendant l’apprentissage, puis aucune. Le prix, c’est l’entraînement : chaque nouveau motif d’historique part de zéro, si bien que sur des exécutions courtes, un prédicteur à historique peut faire moins bien qu’un simple compteur de 2 bits. Essayez-le sur les boucles imbriquées ci-dessus : 13 erreurs au lieu de 11.

L’historique capte aussi la corrélation entre branchements. Si un if teste x > 0 et un autre, plus loin, teste x > 5, l’issue du premier en dit long sur le second. Les prédicteurs à deux niveaux comme celui-ci, et leurs nombreux descendants, sont au cœur de tous les prédicteurs de branchement modernes.

Les prédicteurs modernes

Les cœurs actuels combinent plusieurs idées :

• Les prédicteurs de type TAGE tiennent plusieurs tables qui utilisent des historiques de longueurs différentes, de quelques branchements à plusieurs centaines, et font confiance au plus long historique qui correspond. Les prédicteurs à perceptron apprennent un poids pour chaque bit d’historique. AMD a indiqué que ses cœurs Zen utilisent les deux. Sur du code typique, la précision dépasse largement 95 %.
• Un tampon de cibles de branchement (BTB, branch target buffer) associe l’adresse d’un branchement à sa cible : l’étage de fetch peut se rediriger dès le cycle où il lit le branchement, avant même que le décodage sache qu’il s’agit d’un branchement.
• Une pile d’adresses de retour prédit ret : chaque call empile son adresse de retour sur une petite pile matérielle, et chaque ret en dépile une. Elle a presque toujours raison, sauf si la pile logicielle a été trafiquée.
• Des prédicteurs de branchements indirects devinent la cible de jmp rax ou call [rax+8] — issus des tables de saut des switch et des appels de méthodes virtuelles — à partir de l’adresse et de l’historique.

Le prédicteur est un état matériel partagé, et cela a des conséquences en sécurité. La variante 2 de Spectre (2018) a montré qu’un programme pouvait entraîner le prédicteur pour faire sauter spéculativement un autre programme vers du code choisi par l’attaquant. Parmi les parades : IBPB, un nouveau mécanisme qui vide l’état du prédicteur quand on passe d’un programme à un autre, ajouté par des mises à jour de microcode, et les retpolines, des séquences générées par le compilateur qui remplacent les sauts indirects par une astuce call/ret à travers laquelle le prédicteur indirect ne peut pas être détourné.

Des données imprévisibles

Certains branchements dépendent de données en pratique aléatoires, et aucun prédicteur ne peut battre un tirage à pile ou face. Cette boucle génère des nombres pseudo-aléatoires (xorshift) et compte les impairs :

Essayez chaque prédicteur : le jz reste faux environ une fois sur deux, quel que soit votre choix. L’historique global fait même pire, sur le jz comme sur le jl de la boucle, car les issues aléatoires remplissent son historique de bruit. À 15 cycles par erreur, ce seul branchement coûte des centaines de cycles.

La solution consiste à supprimer le branchement. Le x86 a des transferts conditionnels (cmovcc) et des positionnements conditionnels (setcc), qui calculent une valeur à partir des drapeaux sans aucun saut :

Le seul branchement restant est celui de la boucle, et il est prévisible. Les compilateurs font d’eux-mêmes cette réécriture quand le corps d’un branchement est petit et que la condition semble imprévisible : quand vous voyez cmov ou setcc dans un désassemblage, il y avait probablement un if ou un ?: dans le source. Le même raisonnement explique un benchmark célèbre : additionner seulement les valeurs au-dessus d’un seuil devient plusieurs fois plus rapide une fois le tableau trié. Les données ne changent pas, mais le branchement devient prévisible — faux pour la première moitié, vrai pour la seconde.

Le mesurer

Sous Linux, perf stat -e branches,branch-misses ./prog compte les branchements exécutés par un vrai programme et le nombre de mauvaises prédictions. Sur la plupart des programmes, le taux d’erreur est de quelques pour cent. Quelques pour cent de centaines de millions de branchements, à 15 ou 20 cycles chacun, cela reste beaucoup de temps.

À retenir

• Un pipeline doit choisir la prochaine adresse de fetch avant qu’un branchement soit tranché : les CPU modernes prédisent donc chaque branchement et reviennent en arrière quand ils se trompent. Une erreur coûte à peu près la profondeur du pipeline : 15 à 20 cycles aujourd’hui.
• Les règles statiques (arrière pris, avant non pris) et la disposition du code par le compilateur règlent les cas faciles.
• Les prédicteurs 1 bit se trompent deux fois par boucle ; les compteurs saturants de 2 bits, une seule.
• Les prédicteurs à historique global apprennent les motifs et les corrélations entre branchements. Les prédicteurs TAGE et à perceptron en sont la forme moderne.
• Le BTB, la pile d’adresses de retour et les prédicteurs indirects prédisent où va un branchement, pas seulement s’il est pris.
• Des données imprévisibles mettent en échec tous les prédicteurs. cmov/setcc suppriment alors le branchement, et le partage du prédicteur est ce qu’exploite Spectre v2.