Prédiction de branchement

La prédiction de branchement est une fonctionnalité d'un processeur qui lui permet de prédire le résultat d'un branchement. Cette technique permet à un processeur de rendre l'utilisation de son pipeline plus efficace. Avec cette technique, le processeur va faire de l’exécution spéculative : il va parier sur le résultat d'un branchement, et va poursuivre l’exécution du programme avec le résultat du pari. Si le pari échoue, les instructions chargées par erreur dans le pipeline sont annulées.

Le processeur peut parier sur deux paramètres d'un branchement :

• son adresse de destination : c'est la prédiction de direction de branchement ;
• le fait qu'il soit pris ou non : c'est la prédiction de branchement.

Par pari, on veut dire que le branchement fera poursuivre l’exécution du programme à une instruction différente de celle qui est placée immédiatement après le branchement en mémoire.

Unités de prédiction de branchement

Ces deux problèmes sont délégués à l'unité de prédiction de branchement, qui travaille de concert avec l'unité qui charge les instructions. Cette unité détermine les branchements à effectuer, et donc les instructions à charger. Une mauvaise prédiction aura pour effet de charger des instructions inutiles, qui devront être annulées.

Erreurs de prédiction

Bien évidemment, le processeur peut se tromper en faisant ses prédictions : il peut se tromper d'adresse de destination par exemple. C'est une erreur de prédiction. Lorsque le résultat du branchement est connu, une telle erreur peut être détectée.

Le processeur doit alors faire en sorte que les instructions chargées par erreur dans le pipeline ne modifient pas l'état du processeur. En clair, elles ne doivent pas enregistrer leurs résultats dans les registres, ou alors ces modifications doivent être annulées. Ces mécanismes de correction ou d'annulation peuvent reposer sur l'usage d'un Reorder Buffer, d'un Future File, d'un History Buffer, ou sur la base de sauvegarde régulière des registres du processeur.

Algorithmes de prédiction de direction de branchement

La prédiction de direction de branchement permet de prédire l'adresse de destination d'un branchement. Cette adresse est souvent codée directement dans l'instruction, auquel cas la prédiction est simple, mais il peut aussi s'agir d'un retour de fonction, ou d'un branchement indirect, dont l'adresse de destination n'est pas constante ou est inconnue à la compilation.

Branch target buffer

L'idée la plus simple consiste à se souvenir de l'adresse de destination du branchement lors de sa première exécution, et de la réutiliser lors des exécutions ultérieures de ce branchement. Pour se souvenir de l'adresse de destination d'un branchement, on a besoin d'une petite mémoire cache capable de retenir, pour chaque branchement, l'adresse correspondante : on l'appelle le branch target buffer (BTB).

Ce branchement est une instruction qui est placée à une adresse bien précise. Le branchement est ainsi identifié dans le branch target buffer par son adresse en mémoire. Celui-ci stocke, pour chaque branchement, son adresse et l'adresse de destination. Ce branch target buffer est souvent implémenté comme une mémoire cache.

Le branch target buffer des processeurs actuels ne peut stocker qu'un nombre limité d'adresses. Sur les processeurs x86 actuels, le nombre d'adresses est d'environ 64, et varie suivant le processeur. Quand le branch target buffer est rempli et qu'un nouveau branchement s’exécute, on doit éliminer un branchement du branch target buffer pour faire de la place au nouveau venu. Cela peut poser un problème : un branchement qui aurait pu être exécuté dans un futur proche peut se retrouver supprimé du branch target buffer. On ne peut prédire l'adresse vers laquelle il branchera alors qu'avec un branch target buffer plus grand, on aurait pu. Cela s'appelle un BTB Miss. Il est évident que le choix du branchement à enlever du branch target buffer est déterminant pour les performances, comme pour une mémoire cache classique.

Dans un souci d’optimisation, certains branch target buffer ne mémorisent pas les branchements non pris (du moins, ceux qui n'ont jamais été pris auparavant). Cela permet de faire un peu de place et évite de remplacer des données utiles par une adresse qui ne servira jamais.

Prédiction d'adresse de retour

Certains processeurs possèdent un circuit spécialisé capable de prédire l'adresse de retour d'une fonction. Lorsqu'une fonction est appelée, ce circuit stocke l'adresse de retour dans des registres internes au processeur organisés sous forme d'une pile. Avec cette organisation, on sait d'avance que l'adresse de retour du sous-programme en cours d'exécution est au sommet de cette pile.

Le nombre de ces registres est limité. La limite actuelle tourne autour de 8 (c'est le cas du processeur Atom d'Intel) ou 16 (sur les processeurs les plus performants).

Prédiction des branchements indirects

Sur les processeurs qui n'implémentent pas de techniques capables de prédire l'adresse de destination d'un branchement indirect, le processeur considère qu'un branchement indirect se comporte comme un branchement direct : le branchement va brancher vers l'adresse destination utilisée la dernière fois qu'on a exécuté le branchement. À chaque fois que ce branchement change d'adresse de destination, on se retrouve avec une mauvaise prédiction.

Certains processeurs haute performance sont capables de prédire l'adresse de destination d'un branchement indirect. À une condition cependant : que l'adresse destination change de façon répétitive, en suivant une régularité assez simple. Ces techniques de prédiction de branchement indirect utilisent un branch target buffer amélioré, qui est capable de stocker plusieurs adresses de destination pour un seul branchement. De plus, il stocke pour chaque branchement et pour chaque adresse de destination des informations qui lui permettent de déduire plus ou moins efficacement quelle adresse de destination est la bonne.

Algorithmes de prédiction de branchement

Pour prédire si un branchement est pris ou non pris, notre unité de prédiction de branchement implémente un algorithme matériel. Il existe divers algorithmes de prédiction de branchement.

Prédiction statique

Le premier algorithme est celui de la prédiction statique. L'idée est de faire une distinction entre les différents types de branchements qui ont beaucoup de chance d'être pris et ceux qui ne seront jamais ou presque jamais pris.

L'algorithme de prédiction statique le plus simple est de faire une distinction entre branchements conditionnels et branchements inconditionnels. Par définition un branchement inconditionnel est toujours pris, tandis qu'un branchement conditionnel peut être pris ou ne pas être pris. Ainsi, on peut donner un premier algorithme de prédiction dynamique :

• les branchement inconditionnels sont toujours pris ;
• les branchements conditionnels ne sont jamais pris.

Cet algorithme se trompe toutefois assez souvent pour les branchements conditionnels, notamment en présence de boucles.

Pour résoudre ce problème, il suffit de repérer les branchements qui sont utilisés pour créer des boucles, et ceux utilisés pour d'autres structures de contrôle. Les boucles comportent un saut dont l'adresse de destination est inférieure à l'adresse du dit branchement, permettant de revenir au début.

Un algorithme amélioré de prédiction de branchement consiste donc à prédire ces retours en arrière comme pris, et les autres branchements conditionnels comme non pris. L'algorithme de prédiction statique devient donc :

• les branchements inconditionnels sont toujours pris ;
• les retours en arrière sont toujours pris ;
• les autres branchements ne sont jamais pris.

Cet algorithme nommé BTFN (Backward Take Forward Never) donne de bons résultats. Son efficacité peut être améliorée via l'utilisation d'indications (branch hints).

Compteurs à saturation

La prédiction statique a un défaut : si un branchement est exécuté plusieurs fois, elle ne tient pas en compte des exécutions précédentes du branchement. Ces exécutions peuvent pourtant donner des indices sur le résultat probable de celui-ci. Aussi, d'autres algorithmes de prédiction de branchement ont été inventés pour prendre en compte cet historique.

Le plus simple de ces algorithmes est celui des compteurs à saturation. Il consiste à mémoriser le nombre de fois qu'un branchement a été pris, et à comparer ce nombre au nombre total des exécutions du branchement. Ainsi, on peut faire une moyenne pour savoir si le branchement est plus souvent pris ou non pris. Cette mémorisation se base sur des compteurs, intégrés dans l'unité de prédiction de branchement. On trouve un compteur par branchement mémorisé dans le branch target buffer.

Branch prediction 2bit saturating counter-dia.

Ce compteur est modifié à chaque fois qu'un branchement est pris ou non pris : s'il est pris, le compteur est incrémenté (sauf s'il est déjà à sa valeur maximale) ; s'il ne l'est pas, sa valeur est décrémentée.

Le compteur ne fait généralement pas plus de 2 bits. Il s'agit d'une taille appropriée : le fait de n'avoir que 2 bits permet de ne considérer que les derniers événements, et permet d'éliminer les cas exceptionnels (un branchement qui ne serait pas pris occasionnellement, comme dans une boucle, par exemple).

La prédiction de branchement consiste simplement à comparer le contenu de ce compteur : si celle-ci est supérieure à 1/2 de sa valeur maximale, alors le branchement est prédit comme pris. Sinon, il est considéré comme non pris.

Prédicteur de branchement adaptatif à deux niveaux

Les compteurs à saturations donnent une estimation moyenne de l'issue d'un branchement. Même un branchement qui suit un schéma répétitif ne sera pas prédit à la perfection. Par schéma répétitif, on veut dire que son exécution suit un cycle du genre : pris, non pris, pris, non pris, etc. Un tel cycle sera mal prédit par un compteur à saturation.

Une solution pour régler ce problème est de se souvenir des 2, 3, 4 (ou plus suivant les modèles) exécutions précédentes du branchement. Ainsi, un branchement qui ferait pris, non pris, pris, non pris, etc ; sera parfaitement prédit si l'unité de prédiction de branchement est capable de se souvenir des deux exécutions précédentes du branchement. Un branchement qui ferait : pris, non pris, non pris, non pris, pris, non pris, non pris, non pris, etc ; demandera une unité de prédiction de branchements capable de se souvenir des quatre dernières exécutions d'un branchement.

Two-level branch prediction.

Pour cela, on va utiliser un registre qui stockera l'historique des derniers branchements exécutés. Ce registre est ce qu'on appelle un registre à décalage, qui fonctionne exactement comme un registre qu'on aurait couplé à un décaleur (ici, un décaleur par 1), qui est chargé de décaler son contenu. À chaque fois qu'un branchement s’exécute, on décale le contenu du registre et on fait rentrer dans celui-ci un 1 si le branchement est pris, et un zéro sinon.

Pour chaque valeur possible contenue dans le registre, on trouvera un compteur à saturation qui permettra de prédire quelle est la probabilité que le prochain branchement soit pris. Ce registre est donc couplé à plusieurs compteurs à saturations : pour un registre de n bits (qui se souvient donc des n derniers branchements exécutés), on aura besoin de $2^{n}$ compteurs à saturation. Chacun de ces compteurs permettra de mémoriser le nombre de fois qu'un branchement a été pris à chaque fois que celui-ci a été exécuté après s'être retrouvé dans une situation telle que décrite par le registre. Par exemple, si le registre contient 010, le compteur associé à cette valeur (qui est donc numéroté 010), sert à dire : à chaque fois que je me suis retrouvé dans une situation telle que le branchement a été non pris, puis pris, puis non pris, le branchement a été majoritairement pris ou non pris.

En utilisant une unité de prédiction de branchement de ce type, on peut prédire tout branchement qui suivrait un schéma qui se répète tous les n branchements ou moins, en utilisant un registre d'historique de n bits (et les $2^{n}$ compteurs à saturation qui vont avec).

Prédicteur de boucle

Les unités de prédiction de branchement des processeurs haute performance modernes sont capables de prédire à la perfection les branchements utilisés pour créer des boucles FOR. Ce genre d'unité de branchement contient un circuit spécialisé dans la prédiction des branchements de ce genre de boucles : le prédicteur de boucle ou loop predictor.

Pour une boucle devant s’exécuter N fois, les branchements permettant d'implémenter cette boucle vont être pris N-1 fois, le dernier branchement étant non pris. Un tel prédicteur peut fonctionner sur un principe simple : si une boucle est détectée, alors on mémorise le nombre d'itérations rencontrées lors de la première exécution, et on le mémorise pour les fois suivantes, en espérant que ce nombre ne variera pas.

Ces unités de branchement utilisent un compteur. Lorsqu'une boucle est exécutée la première fois, le nombre de fois qu'elle est exécutée est mémorisé dans l'unité de prédiction de branchement. Les prochaines fois que ce branchement est rencontré, ce compteur est initialisé à N, avec le nombre d'itération de la boucle, mémorisé lors de sa dernière exécution. Ce compteur sera décrémenté à chaque exécution du branchement. Tant que le compteur contient une valeur non nulle, le branchement est prédit comme pris. Lorsque ce compteur atteint zéro, on atteint la fin de la boucle, et le branchement est considéré comme non pris.