Une instruction de branchement est une instruction qui signale au microprocesseur un changement dans le flot de contrôle d’un programme. Cette instruction lui indique de continuer l’exécution du programme à une adresse donnée en fonction d’une condition. Les instructions de branchement sont souvent appelées branch (abrévié b ou br) ou jump (abrévié j ou jmp) suivant les jeux d’instructions. La condition que le branchement doit vérifier afin de savoir s'il doit changer le flot d’exécution du programme peut résider dans un registre spécialisé (généralement appelé flags ou indicateur d'état) ou dans un registre générique. Cette condition appartient généralement à la liste suivante (non exaustive) : ==0 (eq), >=0 (ge), >0 (g), <0 (b), <=0 (be), !=0 (ne), 1 (a).

Exemple en jeu d'instruction x86 (définit par Intel et employé dans la majorité des PC)

jbe +32

Signifie que si la 'condition inférieur ou égal' est vraie dans les flags, le programme doit poursuivre son exécution 32 octets plus loin, et sinon d'exécuter l'instruction située juste après 'jbe'

Par la suite on emploiera le vocabulaire suivant pour parler des branchements :

• Pris (p), Non pris (n): un branchement pris est un branchement dont la condition de saut est vérifiée et qui va modifier le flot d'exécution des instructions. Un branchement non pris est un branchement dont la condition de saut n'est pas vérifiée et qui ne modifiera donc pas le flot d'instructions.



• Adresse du branchement : c'est l'adresse de l'instruction de branchement dans le programme que la machine exécute, à ne pas confondre avec l'adresse cible du branchement qui est l'adresse à laquelle le programme continuera son exécution si le branchement est pris.



• Branchement indirect, ou branchement calculé : C'est un branchement qui peut avoir plusieurs adresses cible.

L’idéee de branchement conditionnel a été une des inventions critiques de Von Neumann avec sa machine. La machine de Von Neumann est définie par une mémoire et une unité de calcul séparées, l’unité de calcul effectuant à chaque cycle une incrémentation du compteur de programme, le chargement de l’instruction pointée par celui-ci, le décodage de celle-ci, et son exécution. Les machines modernes fonctionnent toujours sur un principe similaire. Von Neumann avait introduit dans sa machine une instruction qui permettait de modifier la valeur du compteur de programme si une condition était respectée : l'instruction de branchement.

Les premiers microprocesseurs travaillaient sur une seule instruction à la fois, c’est-à-dire que le branchement soit pris ou non, celui-ci ne changeait pas le temps d’exécution du programme puisque la condition était connue avant même de commencer l’exécution de ce branchement (l'exécution en soit est juste une addition au pointeur d’instruction si la condition est vraie). On peut décomposer les différentes étapes de l'exécution des instructions en plusieurs phases, la décomposition la plus simple étant la suivante en 4 étapes : celle où l’on charge l'instruction (F), la décode (D), l'exécute (E) et l'écrit (W) :

Microprocesseurs exemples: Intel 8086/80286, Motorola 6800. Dans ce modèle d'exécution, le temps d'exécution d'un programme correspond au nombre total d'instructions multiplié par le temps mis pour exécuter chaque instruction (dans notre cas la profondeur du pipeline p = 4 cycles). On a donc :

T = p * ni

Avec l’apparition des microprocesseurs pipelinés, les branchements ont commencé à être des instructions ayant un impact significatif sur la performance. L'idée même du pipeline était de ne plus attendre qu’une instruction ait fini son exécution  pour commencer à charger la suivante. Afin d'y parvenir les différentes étapes de l'exécution d'une instruction ont du être rendues complètement indépendantes, afin de pouvoir effectuer chacune de ces étapes en parallèle sur plusieurs instructions différentes.

On voit que ce modèle permet d’exécuter 4 fois plus d’instructions par cycle que le précédent tant que l’on ne rencontre pas de branchements. Au premier branchement rencontré on ne connait pas la cible de celui-ci tant que son exécution n'est pas finie, on ne peut donc pas charger l'instruction suivante, en l'occurence l'instruction x puisque le branchement a été pris.Dans ce modèle d'exécution, le temps d'exécution d'un programme correspond au nombre total d'instructions + 6 (amorce et fin du pipeline) s'il n'y a aucun branchement. Chaque branchement (il y en a Nb) ajoute une pénalité Pb de 2 cycles. On a donc :

T = ni + 2 * (p - 1) + Pb * Nb

Si l'on considère un code complexe avec 1 branchement toutes les 5 instructions et notre pipeline à 4 étages

T = ni + 6 + ni * 2 / 5 = 7/5 * ni + 6

donc le temps d'exécution du programme s'allonge de 40% juste en raison des branchements. Bien évidemment plus le pipeline est long plus cette pénalité l'est.

C’est à partir de cette période que l’on va commencer à accélérer les branchements en utilisant la prédiction de condition et les caches d’adresses destination, décrits dans la section suivante.

Les tout premiers microprocesseurs pipelinés continuaient à charger et décoder des instructions et ce même après un branchement, si le branchement était pris ils recommençaient l’exécution des instructions qui avaient été commencées à tort. Cela ne posait pas trop de problèmes car on connaissait la décision du branchement avant que celles-ci n’aient fini leur exécution et écrit des résultats incorrects.

Dans cet exemple le branchement a indiqué que le programme devait continuer à l’instruction 9, et les instructions 6 et 7 ont été annulées dès que l’exécution du branchement a été finie (et que l’on a su que l’on s’était trompé). Ce type de pipeline se retrouve sur les microprocesseurs MIPS R2000/R3000, intel 80386/80486.

Cette méthode simpliste donnait d’assez mauvais résultats, en particulier sur les boucles dont la caractéristique principale est que le branchement est pris dans la majorité des cas (tous sauf quand on sort de la boucle). La prédiction statique par défaut a donc été inversée, mais celà a posé un nouveau problème : comment peut on savoir l’adresse de l’instruction que l’on a chargé avant de l’avoir calculé avec le branchement ? Si on ne la connaît pas on va de toute façon devoir attendre la fin du branchement pour pouvoir continuer. Les premiers microprocesseurs adoptant cette solution ont cherché tout d’abord à minimiser le temps mis pour calculer un branchement afin de ne pas perdre trop de temps puis ils sont passé à la technique du cache d’adresse destination (BTB pour Branch Target Buffer). L’idée est assez simple, un branchement saute généralement à la même destination donc si on se souvient où il a été la dernière fois on peut utiliser cette adresse avant de connaître le résultat du branchement.

En supposant que ce n’est pas la première fois que l’on rencontre le branchement 1 on peut directement décider de charger l’instruction 9. Bien entendu la taille de la BTB est limitée donc on ne se souvient que des derniers branchements rencontrés (identifiés par l’adresse de l’instruction de branchement dans le programme).

Le problème semble résolu, mais le taux de bonnes prédictions reste relativement faible et on exécute beaucoup trop d’instructions inutiles. 2 améliorations ont été apportées à cet algorithme et ont été utilisées entre autre sur les premiers PowerPC. La première consiste à prédire les branchements arrières comme pris (pour les boucles) et les autres comme non pris. La seconde consistait à placer une indication dans le programme sur comment les prochains branchements devaient se comporter, par exemple avant une boucle le compilateur plaçait une instruction signalant que les prochains branchements devaient être prédits comme pris par défaut. Toutes ces techniques étaient suffisantes quand la profondeur du pipeline des machines était faible (typiquement <5) car la pénalité due à un branchement mal prédit était faible.

Notre mesure du temps d'exécution devient (Tm est le taux de mauvaises prédictions) :

T = ni + 2 * (p - 1) + Tm * Pb * Nb

Si l'on considère qu'un taux de prédiction est de 2/3, on arrive seulement à une pénalité de 13% sur le temps d'exécution du programme due aux mauvaises prédictions de branchements. On voit donc que pour des pipelines relativement courts cette méthode simple était particulièrement efficace, dans le cas d'un microprocesseur comme le Pentium 4, cette pénalité aurait été 10x (Pb > 20) plus importante avec ce type de prédicteur et aurait donc présenté des performances inacceptables.

Avec l’apparition de microprocesseurs à pipeline plus longs et surtout celle des superscalaires qui pouvaient charger et exécuter plusieurs instructions par cycle, la nécessité de mieux prédire les branchements se faisait sentir car la pénalité en cas d’échec devenait sévère.

On a donc commencé à utiliser les BTB et un prédicteur qui apprend et se souvient de la direction prise par chaque branchement. Les premiers utilisaient un compteur 1 bit à saturation. Si le branchement était non pris on décrémente le compteur et le prochain branchement sera prédit non pris, et vice-versa. Très rapidement les prédicteurs ont commencé à utiliser des compteurs 2 bits qui bien que nécessitant plusieurs exécutions pour s’initialiser donnaient des résultats bien plus fiables surtout dans le cas des boucles imbriquées. On associe chacune de ces prédictions à une entrée dans la BTB.

Exemple du compteur 2 bits du Pentium (P5, P54C). En fonction des microprocesseurs, la valeur à laquelle le prédicteur est initialisé la première fois peut changer, ainsi que ce que l’on fait en cas de saturation du compteur. Le P5 disposait d'une BTB de 256 entrées. Le cyrix 6x86 (M1) et l'AMD K5 appartiennent à cette génération mais présentent diverses petites améliorations par rapport au Pentium, y compris une BTB de 1 kilo pour le K5

Si l'on reprend notre équation précédente pour un processeur similaire au Pentium :

T = ni + 2 * (p - 1) + Tm * Pb * Nb

qui disposait de 5 étages de pipeline (on considère que la plupart du temps on n'utilise qu'un des 2 pipelines du P5, ce qui était effectivement le cas) et un taux de bonnes prédictions estimé de 80% on obtient :

T ~= ni + 1/5 * 3 * ni/5

Le principal problème du compteur 1 ou 2 bits est qu’il ne fonctionne efficacement guère que sur les boucles. L’étape suivante consiste à prédire un branchement en fonction de son contexte global, ce qui est particulièrement utile pour des conditions interdépendantes qui partagent un certain nombre de variables, par exemple dans le cas suivant il y a une corrélation entre la direction du premier et du second branchement :

x=?;

y=?;

if (x==0)

  y=1;

if (y!=0)

  …;

Dans un prédicteur global on va conserver dans un registre à décalage le comportement des n derniers branchements. On associera à ce registre 2^n compteurs 1 ou 2 bits qui seront mis à jour à chaque fois que l’une des conditions sera rencontrée, par exemple le prédicteur du Pentium MMX (P55C) où n=4 et la BTB dispose de 512 entrées :

Si l'on calcule le temps d'exécution pour un processeur similaire au Pentium MMX qui disposait de 6 étages de pipeline et un taux de bonnes prédictions estimé de 90% on obtient :

T ~= ni + 1/10 * 4 * ni/5

Le concept du g-share dérive du prédicteur à 2 niveaux vu précédemment mais cherche à combler une de ses lacunes principales, en effet si l’historique est le même entre 2 branchements, ils partageront leur compteur 2 bits et peuvent donc avoir des interactions néfastes l’un sur l’autre. Afin de combler cette lacune au lieu d’utiliser la valeur de l’historique global pour adresser les compteurs 2bits on va utiliser une fonction de hachage faisant intervenir à la fois l’historique et l’adresse du branchement en question. En pratique cette fonction de hachage est généralement un simple 'xor' entre les bits d’historique global et un certain nombre de bits de l’adresse du branchement.

Des processeurs comme l'AMD K6 (BTB de 8k!), le Pentium II, le MIPS R10000 et l'alpha 21264 ont utilisé des prédicteurs similaires et le taux estimé de bonnes prédictions atteint les 95%. Un point de départ pour une lecture approfondie sur le sujet de la performance de cette génération de prédicteurs ici :

• Analyse de performance de quelques prédicteurs dynamiques

Tous ces microprocesseurs employaient des pipelines plus longs (7-14 étages) et une réduction d'un facteur 2 des mauvaises prédictions était nécessaire pour compenser un tel allongement du pipeline (qui permit d'atteindre des fréquences bien plus élevées).

Dès lors que les microprocesseurs sont devenus superscalaires et ont commencé à exécuter les instructions dans le désordre, le problème de l'annulation des instructions exécutées lors d'une mauvaise prédiction a commencé à devenir complexe. En effet dans les premiers pipelines scalaires la condition et l'adresse du branchement étaient toujours connus avant la phase d'écriture des résultats des instructions qui avaient été exécutées spéculativement (Instructions que l'on a exécuté avant d'être certain que la prédiction est bonne). Mais avec les superscalaires à exécution dans le désordre comme l' Intel P6, l'AMD K6, l'Alpha 21264, le Mips R1000, le PowerPC 604 et leurs successeurs il devient possible qu'une instruction ait écrit son résultat dans les registres de la machine avant que le résultat du branchement soit connu. Il est donc fondamental de pouvoir annuler ces opérations pour retourner dans l'état où la prédiction a été effectuée. Tout d'abord on retarde les écritures mémoires pour être sûr qu'aucune écriture spéculative en mémoire a eu lieu. Ensuite on traque les écritures dans les registres de manière à se souvenir lesquelles sont encore spéculatives à un instant donné et on dispose de copies de ces valeurs pour les restaurer en cas de mauvaise prédiction.

L’idée des prédicteurs hybrides est que certains branchements seront plus efficacement prédits par un prédicteur local et d’autres par un prédicteur global de type g-share. On va donc utiliser les 2 types de prédicteurs et utiliser un 3 ème prédicteur qui choisira pour chaque branchement la prédiction du global ou du local. On peut étendre cette méthode à l'utilisation de plusieurs prédicteurs global utilisant des longueurs d'historique variables et des meta-prédicteurs complexes basés sur le perceptron. Beaucoup d'efforts de recherche sont effectués afin de trouver les techniques les plus efficaces pour prédire les branchements, en particulier l'an dernier une compétition avait été organisée à l'occasion de la conference Micro, visant à produire le meilleur prédicteur possible. Vous pourrez trouver les algorithmes en question ici, et noterez la présence de 2 français parmi les 5 finalistes :

• Compétition du meilleur prédicteur de branchements

C'est une question légitime que tout programmeur concerné par la performance de son application doit se poser. Tout d'abord les branchements utilisés pour les boucles seront systématiquement bien prédits, certains microprocesseurs ne faisant même pas de mauvaise prédiction lors de la sortie de la boucle qui correspond pourtant à un changement de comportement du branchement. Pour les autres conditions, si en lisant votre code vous arrivez à déterminer des corrélations entre plusieurs branchements, le microprocesseur y arrivera sans problèmes.

Si vos conditions sont dépendantes de données complètement aléatoires, le prédicteur aura un taux de succès similaire à la répartition statistique des résultats de la condition : si la condition est vérifiée 90% du temps vous pouvez compter sur approximativement 90% de bonnes prédictions, si cette répartition tombe à 50% vous prédirez mal la moitié des branchements. Bien souvent les données ne sont jamais complètement aléatoires et les résultats de la condition 50/50, en effet la plupart des tests effectués sur des données sont souvent des conditions d'arrêt de boucle (par exemple test de convergence d'une série) et ont donc une probabilité faible d'être vérifiés, et une fois que cette condition a été vérifiée une fois la probabilité qu'elle le soit une deuxième fois d'affilée est quasiment nulle.

Les branchements indirects sont souvent prédits avec moins de fiabilité que les branchements conditionnels, en effet avoir plus d'un destination possible complique le travail du prédicteur. Les branchements indirects sont souvent générés pour des appels de librairies dynamiques, la résolution dynamique d'objets dans des langages orientés objet, ou plus simplement les tests de type 'switch/case'. Un nombre faible de destinations et un comportement régulier favoriseront bien sûr l'efficacité du prédicteur.