Mathieu Escouteloup
mardi 13 janvier 2026
Architecture des processeurs 5: Prédiction de branchement
Pour effectuer les différentes simulations de cette page, ouvrez l’ensemble du répertoire riscv-sim avec Visual Studio Code.
Dans le terminal de l’IDE, configurez l’environnement du simulateur puis placez-vous dans le répertoire sw/uarch/br.
Redirection de l’exécution
La majorité des programmes s’exécutent de manière linéaire: les instructions se suivent directement en mémoire. Cependant, afin d’optimiser la compilation et le support de fonctionnalités, il peut être nécessaire de rediriger l’exécution:
- Pour exécuter un code situer ailleurs en mémoire (e.g. une fonction),
- Pour exécuter conditionellement un bout de code (e.g. une structure de type
if ... else ...), - Pour répéter l’exécution d’un bout de code (e.g. une boucle),
- etc.
Pour cela, des instructions dédiées sont généralement utilisées dans les différentes ISA. Dans le cas du jeu d’instructions RISC-V, on retrouve notamment:
- l’instruction de saut direct
jal, qui permet d’effectuer une redirection vers une adresse fixe, - l’instruction de saut indirect
jalr, qui permet d’effectuer une redirection vers une adresse calculée à partir d’un registre, - les instructions de branchement conditionnel (
beq,bne,bge,bgeu,blt,bltu), qui permettent d’effectuer une redirection vers une adresse fixe si une condition est bien remplie.
On considère une instruction RISC-V. Quelles sont les trois informations nécessaires avant d’effectuer une potentielle redirection ?
On considère un processeur avec un pipeline 5 étages standard. À partir de quel(s) étage(s) sont connues les différentes informations ?
Aide supplémentaire
On considèrera l’organisation interne suivante:
- IF: Récupération de l’instruction,
- ID: Décodage de l’instruction, des immédiats et lecture des registres,
- EX: Exécution de l’opération, réalisation des sauts,
- MA: Opération mémoire,
- WB: Rangement du résultat.
Pour chaque type d’instruction de redirection (saut direct, saut indirect et branchement conditionnel), les différentes informations nécessaires sont-elles connues ? Déduisez le nombre de bulles insérées pour chaque type en cas d’erreur de prédiction.
Anticipation matérielle Les instructions de redirection sont problématiques pour les architectures à base de pipeline car l’opération de branchement et le calcul du prochain PC s’effectue généralement à des cycles différents. C’est d’autant plus le cas si le pipeline possède un grand nombre d’étages. Ainsi, une stratégie possible au niveau du matériel est d’anticiper certains de ces aléas en les réalisant le plus tôt possible.
Dans le cas où l’adresse de destination est fixe, on peut généralement la calculer dès que les différentes valeurs immédiates nécessaires sont connues.
Pour notre processeur core_0, quel impact cela pourrait-il avoir sur les bulles insérées pour chaque type d’instruction de redirection ?
À quel étage chaque pourrait être finalement exécuté ?
Prédiction de branchement
Pour les différentes simulations, la macro UARCH_OPT2_EN nous permettra d’activer les mécanismes de prédiction de branchement.
Les différentes manipulations peuvent aussi bien être effectuées en langage d’assemblage RISC-V dans main.S ou en langage C dans func.c.
Dans le second cas, pensez à appelez la fonction func depuis votre fonction main avec la pseudo-instruction call func.
Détection d’une redirection
Modifiez votre programme pour effectuer un saut direct jal.
Combien de bulles sont insérées lors d’une mauvaise prédiction dans le processeur core_0 ?
Modifiez votre programme pour effectuer un saut direct jal.
Combien de bulles sont insérées lors d’une mauvaise prédiction ?
loop:
nop
j loop
Au sein du processeur core_0, le Branch Target Buffer (BTB) est responsable de la sauvegarde des informations des redirections rencontrées pour de futures prédictions.
Son fonctionnement est similaire à celui d’une mémoire cache, avec un découpage en sous-ensembles afin d’accélérer l’adressage et la sélection.
Ici, c’est le PC de l’instruction qui est utilisé pour placer les informations dans un emplacement et effectuer les différentes comparaisons (BTB hit / BTB miss).
Gérénélement, afin de simplifier l’opération de comparaison qui doit s’effectuer en moins d’un cycle, seuls certains bits du PC sont stockés: dans le cas du core_0, seuls 8 bits sont considérés.
Les instructions étant toutes de 32 bits et étant forcément alignées, les bits [1:0] du PC sont ici toujours égaux à 0b00.
Ainsi, on utilise plutôt les bits [9:2].
Au sein du chronogramme, vous retrouverez les informations du BTB dans Pipeline -> NLP -> BTB.
Au sein du BTB du core_0, quelles sont les différentes informations qui sont stockées pour chaque instruction de redirection rencontrée ?
Lesquelles de ces informations sont nécessaires pour correctement prédire le saut direct j loop ?
À partir de combien d’exécution de l’instruction la prédiction est-elle correcte ?
Redirection conditionnelle
Dans le cas des instructions de branchement conditionnel, une information supplémentaire est nécessaire par rapport à un saut direct: si le saut doit être pris (taken) ou non (not-taken).
Dans le cas d’un branchement conditionnel, les informations stockées ici dans le BTB sont-elles suffisantes ?
Au sein du processeur core_0, le Branch History Table (BHT) est responsable du décompte des sauts pris (taken) / non-pris (not-taken).
Son fonctionnement est similaire à une liste de compteurs 2 bits.
Chacun d’entre eux est adressé en utilisant les bits du PC: pour N compteurs, log2(N) bits du PC sont utilisées (ici les bits [log2(N) + 2 - 1:2]).
Dans le chronogramme, vous retrouverez les informations du BHT dans Pipeline -> NLP -> BHT.
Dans le cas du core_0, retrouvez le nombre de compteur dans le chronogramme et déduisez-en le nombre de bits du PC utilisés.
Modifiez votre programme pour incrémenter une variable de 0 à 9 à l’aide d’une boucle.
Combien de fois une même instruction de branchement conditionnel est-elle exécutée ?
Avec les mécanismes de prédiction de branchement activés, combien de mauvaises prédictions de cette instruction de branchement conditionnel sont effectuées ?
Imbriquez votre boucle dans une autre boucle comptant de 0 à 3. Combien de mauvaises prédictions de la même instruction de branchement conditionnel sont effectuées à chaque fois ?
Considérons deux instructions de branchements conditionnels placés aux adresses A et A + N * 4 avec N le nombre de compteurs dans le BHT.
Que se passera-t-il au niveau du BHT ?
Déduisez-en l’intérêt d’avoir un grand nombre de compteurs.
Appel de fonction
Ajoutez une fonction dans votre fichier main.S puis appelez cette fonction 3 fois depuis votre code principal.
Sans mécnaisme de prédiction, combien de mauvaises prédictions obtenez-vous pour les 3 call / ret ?
Observez les PC des instructions de saut associées aux call et les adresses de destination des instructions de saut associées aux ret.
Quelle relation exist-t-il entre eux ?
Au sein du processeur core_0, le Return Stack Buffer (RSB) (aussi appelé Return Address Stack dans la littérature) est le mécanisme matériel utilisé pour prédire les adresses de retour.
Son fonctionnement est similaire à celui d’une pile: la valeur lue est la dernière valeur stockée.
Dans le chronogramme, vous retrouverez les informations du BHT dans Pipeline -> NLP -> RSB.
Que se passe-t-il dans le RSB lorsqu’un appel de fonction / un retour de fonction est détecté ?
Nous considérons le cas où le programme effectue un grand nombre d’appels de fonctions imbriqués.
À partir de quand le RSB du core_0 sera-t-il supposément rempli ?
Quel comportement adopte le RSB lorsque celui-ci est rempli et qu’un nouvelle appel de fonction est effectué ?
D’après vous, il y a-t-il un réel intérêt à implémenter un RSB de très grande taille (> 128 entrées) ?