11.2.2.3.6 : Supprimer certain branchements
Figure 33 : Branchement dû à une condition dans un programme C/C++.
Un branchement est une instruction qui fait sauter le programme à un autre endroit du code. On parle de branchement conditionnel lorsque le branchement s'effectue ou non selon la valeur d'un booléen, appelé condition.
Le mot-clé if des langages de programmation se traduit généralement par un branchement conditionnel au niveau matériel, voir figure 33. Si la condition est vraie, alors le programme continue d'exécuter les instructions internes au bloc derrière le if. Si la condition est fausse, en revanche, le programme sautera aux instructions correspondantes et poursuivra l'exécution du programme après le bloc.
Ce mécanisme n'est pas anodin, car il interfère avec une optimisation de performance interne du CPU, le pipelining.
Figure 34 : Différentes étapes d'un pipeline CPU.
L'exécution de chaque instruction CPU se décompose en plusieurs étapes, pour simplifier on peut considérer 5 étapes (voir figure 34) :
- IF, Instruction Fetch : Aller chercher l'instruction à exécuter en RAM.
- ID, Instruction Decode : Décoder l'instruction.
- EX, EXecute : Exécuter l'instruction.
- MEM, MEMory : Échanger avec la mémoire.
- WB, Write Bytes : Écrire le résultat.
Figure 35 : Utilisation du pipeline CPU en fonction du temps.
Les premiers CPU n'exécutaient qu'une étape à la fois. Mais dans la mesure où chaque étape est gérée par un composant différent du processeur, les fabricants de matériel ont rapidement commencé à faire fonctionner ces composants en même temps.
L'idée était de traiter les différentes étapes de traitement comme des parties d'une chaîne de montage industrielle, un pipeline (voir figure 35).
Les instructions entrent dans le pipeline à tour de rôle. Pendant que la première instruction est en train d'être décodée, la deuxième est rapatriée. Pendant que la première instruction est exécutée, la deuxième est en train d'être décodée et la troisième d'être rapatriée. Et ainsi de suite.
Une fois que le pipeline a traité les 5 premières instructions, il fonctionne à plein régime et fournit des résultats en sortie au même rythme que les instructions arrivent en entrée.
Si l'on suppose que chaque étape de traitement d'une instruction prend le même temps, cela représente une accélération d'un facteur 5 par rapport au cas où le CPU attend qu'une instruction soit complètement traitée avant d'aller chercher la suivante.
Toutefois, les choses se compliquent lorsque le CPU rencontre une condition. En effet, le CPU ne peut pas, a priori, précharger l'instruction suivante, car il ne peut pas deviner si la condition va être vraie ou fausse, et ne peut donc pas savoir quelle est l'instruction suivante à charger.
Comme l'utilisation du pipeline CPU a permis d'accélérer considérablement les performances, une solution a été développée pour atténuer le problème des branchements : le prédicteur de branchement. Un prédicteur de branchement est un automate à quatre états qui détermine si un branchement a une probabilité plus importante d'être pris ou non (voir figure 36).
Figure 36 : Fonctionnement d'un prédicteur de branchement.
Le prédicteur prédit initialement que les branchements auront lieu, ce qui est vrai dans $60\,\%$ des cas à cause des boucles. À chaque fois qu'un branchement conditionnel est effectué, l'état de l'automate va vers une plus grande certitude que le branchement suivant sera effectué. À chaque fois qu'il n'est pas effectué, il va vers une plus grande certitude que le branchement suivant ne sera pas effectué.
L'existence d'états extrêmes "highly branch" et "never branch" permet au prédicteur de prendre en compte des exceptions, où un branchement a presque toujours lieu ou bien n'a presque jamais lieu.
Pour chaque condition, le CPU poursuit l'exécution selon l'hypothèse prédite, tout en se préparant à annuler les opérations effectuées s'il s'avérait que la prédiction était fausse. De nos jours les prédicteurs de branchement sont très performants, ils ont un taux de bonnes réponses supérieur à $95\,\%$ . Mais les quelques pourcents restant peuvent être problématiques pour les performances. Lorsque le prédicteur de branchement donne une bonne réponse, le CPU va chercher les bonnes instructions et le programme n'est pas ralenti. En revanche, lorsqu'il se trompe, les instructions préchargées ne sont pas les bonnes. Il faut donc vider le pipeline et le remplir de nouveau. Or, les pipelines des CPUs actuels sont composés de $40$ à $80$ étapes, chacune prenant plusieurs cycles d'horloge. Vider et remplir le pipeline coûte environ $300$ cycles.
Si cela se produit trop fréquemment, on peut y dépenser une fraction conséquente du temps total de calcul. C'est ce qui s'est produit dans le traitement d'image historique des analyses de type CTA. Utile de mentionner une expérience précise ?
Un exemple de performance est donné dans l'annexe 10.10.