close

Se connecter

Se connecter avec OpenID

Ch 5 : La Prédiction des Branchements

IntégréTéléchargement
Ch 5 : La Prédiction des
Branchements
IUP3/ Master Info. 1
Smail Niar
ISTV Université de Valenciennes
smail.niar@univ-valenciennes.fr
Smail.Niar@univ-valenciennes.fr
1


Il est intéressant de réduire au max les aléas de
contrôle afin de maintenir un IPC=1 pour un
processeur pipeliné, ou IPC>>1 pour un SS ou
un VLIW
Superscalaire ou VLIW: les instructions arrivent
n fois plus rapidement => n cycles perdus à
chaque suspension ou à chaque mauvaise
prédiction de direction de branchement.
2
Smail.Niar@univ-valenciennes.fr
Les prédictions de
branchement



15 à 30% des instructions sont des branchements
Le résultat de la condition du branchement est
connu tard ( cycle 4 sur MIPS/DLX)
La cible du branchement est connu tard dans le
pipeline :




cycle 4 dans Mips pipeliné et dans Intel Xscale
cycle 11 sur Pentium Pro (plus sur le pentium4)
Cycle 6 sur Dec alpha 21164
idée: Evaluer ou prédire (spéculation) au plus tôt la
condition et l ’adresse de branchement

Si la prédiction n ’est pas bonne en fait marche arrière
(annulation)
3
Smail.Niar@univ-valenciennes.fr
Prédiction branchements ….suite
3 cycles perdus à chaque
branchement (pris)
40 beq $1, $3, 7
IM
CC 3
Reg
CC 4
CC 5
DM
Reg
CC 6
CC 7
CC 8
CC 9
DM
Reg
Smail.Niar@univ-valenciennes.fr
Time (in clock cycles)
Program
execution
CC 1
CC 2
order
(in instructions)
IM
IM
IM
72 lw $4, 50($7)
IM
Reg
4
Solution uniquement pour pour : beqz
R1, etiq
Smail.Niar@univ-valenciennes.fr
Deux cycles perdus au lieu de 3
5


#1: Attendre et suspendre le pipeline tant que le
branchement n ’est pas résolu (résultat compa. non connu)
#2: On prédit toujours que le branchement n ’est
pas pris



Exécuter les instruction qui suivent le branchement
Annuler les instructions chargées si branchement pris
Il n’y a pas de danger de modifier l’état des registres

car l ’écriture se fait à la fin du pipeline, après que la condition
a été évaluée
6
Smail.Niar@univ-valenciennes.fr
possibilités dans le traitement des
aléas de contrôle



Dans 47% des branchements MIPS, le branchement n ’est
pas pris
Avantage : PC+4 à été déjà calculé, il suffit de l ’utiliser
pour avancer
Smail.Niar@univ-valenciennes.fr
Prédiction Branchement ..suite
#3: On prédit que le branchement est pris et on
commence à exécuter les instructions du branchement


53% des branchement sont pris dans le cas de la machines MIPS
Mise en œuvre : pour chaque instruction de branchement on stocke l ’@
du branchement dans une mémoire cache spécialisée
7
Branchement Prédit pris
Branch Target Buffer BTB
Adresse des
valide
branchements
adresse de
l ’instruction
1/0
Control
Lors de la phase Fetch Instruction on écrit dans PC, l ’@
de la prochaine instruction à exécuter
soit PC + 4 ou bien l ’@du branchement
1
Smail.Niar@univ-valenciennes.fr
CP+4
CP
0
CP
8
Always taken
6%
4%
0%
0%
Taken backwards
Not Taken Forwards
9
Smail.Niar@univ-valenciennes.fr
8%
tom c atv
2%
s w m 25 6
10%
ora
20%
m d ljs p 2
30%
hy dro2d
40%
gc c
10%
es pres s o
50%
do duc
12%
c o m pres s
60%
M is p re d ictio n R ate
70%
al v inn
t om c at v
s w m 25 6
ora
m d ljs p 2
hy dro2d
gc c
es pres s o
do duc
c o m pre s s

al v inn
F r eq u e n cy o f M i sp r ed i cti o n
Prédiction par le compilateur
Statique
Les branchement arrière sont toujours prédit pris et les
branchement avant sont toujours prédit non pris
14%
Le branchement retarde
Delayed Branch
#4: Delayed Branch(se faire aider par le compilo)

Les n instructions suivant l ’instr Branch sont toujours
exécutées (pas de prédiction)
branch instruction
sequential successor1
sequential successor2
........
sequential successorn
branch target if taken
cas particulier : BEQZ


Smail.Niar@univ-valenciennes.fr

2 cycle d ’attente pour le calcul de l’adresse de branchement
=> n=2 (2 instruction dans le délai) cf. tr 25
On peut soit déplacer des instructions ou mettre des nops
10
Une instruction après le branchement
est toujours exécutée
add r4, r5, r6
Beqz r4, etiq
Sub r6, r3, r2
Add r1, r2, r3
……
….
etiq:
Smail.Niar@univ-valenciennes.fr
Sub r6, r3, r2
Add r1, r2, r3
add r4, r5, r6
Beqz r4, etiq
……
….
etiq:
11
La prédiction dynamique des
branchements

Utilisation d ’une mémoire « tampon de
branchement » BHT : Branch History Table


BHT Indexée par l ’adresse de l’instruction
branchement
1 bit à chaque branchement



Smail.Niar@univ-valenciennes.fr
(prédiction)
0 on prédit «Non pris » noté NP ou NT
1 on prédit « pris » noté P ou T
si la prédiction n ’est pas bonne on inverse le bit
12
Prédicteur sur 1 bit
T
Predict Taken
1
BOUCLE
etiq: …..
…….
……..
boucle: bne r1,r2, etiq
T
Predict Not
Taken
Smail.Niar@univ-valenciennes.fr
NT
0
NT
Supposant: Bit prédiction initialisé à NT 0
il y a 10 itérations
Première itération : Prédiction NT , erreur
Dernière itération : Prédiction T, erreur
Inconv Boucles : si le branch est toujours pris il y a 2
prédictions incorrects (mispredictions): la première et la
dernière
13
Exemple :
Exemple:
i1 début Boucle1
i2
…..
…..
etiq2:
Smail.Niar@univ-valenciennes.fr
etiq1:
Si boucle externe fait
m itérations
et la boucle interne fait
n itération:
2m fausses prédictions/ mn
itérations
i3 Début Boucle2
i4
Si cond go to étiq2
….
exemple m=n=10
20% de fausses prédictions
Go to etiq1
14
Schéma de prédiction avec 2 bits
P
11
P
On associe à chaque
branchement deux bits YX
Si Y=1 on prend le branch
si Y= 0 on ne prend pas
le branch
10
P
NP
NP
P
P
01
NP
00
NP
NP
NP
15
Smail.Niar@univ-valenciennes.fr
P
Rappel :
BTB : Branch Target buffer, Buffer des @ destinations
des branchements
PC

Etiquette,
@ Branchement
BHT : « tampon de branchement » : Branch History
Table, table des prédictions pour chaque (basée sur
l’historique)
(prédicateur BIMODAL)
PC
10
16
Smail.Niar@univ-valenciennes.fr

La corrélation entre les
branchements
Dans certains programmes, il y a
des relations entre les
Test à l’entrée
instructions de branchements
du lycée
Branchements « biaisés »
Collège
b1
Série
Série

Un exemple de la vie courante:
Math
appliqué
Orientation des étudiants pour des cours
de mise à niveau.
Les étudiants entrant à une université
Test à l’entrée
b2
de l ’université.
proviennent de 2 options .
A : Option Math
B : Option Physique
SPI
MIAS
b1: Test à l'entrée du lycée
b2: Test à l ’entrée de l’université.
Lycée
Smail.Niar@univ-valenciennes.fr

Université
17
Les résultats des test à l ’entrée de l ’université
ne sont connus qu ’un mois après, mais il faut
commencer l ’année….?
Collège
Collège
Série
Math
Série
appliqué
Test à l ’entrée
de l ’univer.
Série
Math
Série
appliqué
Test à l ’entrée
de l ’univer.
b2
bonne prédiction
b2
Smail.Niar@univ-valenciennes.fr
Test à l’entrée b1
du lycée
Test à l’entrée b1
du lycée
mauvaise prédiction
18
Smail.Niar@univ-valenciennes.fr
(Transparent P.Michaud IRISA)
19
Exemple
Smail.Niar@univ-valenciennes.fr
Si d==0 avant le premier
« If » ,
alors dans le deuxième If on
if (d==0) /*branchementtrouvera
b1*/
d==1
d=1
if(d==1)
Supposons que d est dans R1
/*branchement b2*/
…….
20
if (d!=0) go to L1
/*branchement b1*/
R1, L1
;branch vers L1 si
Addi
Sub
Bnez
…..
…..
R1, R0, #1 ;d= =0, alors d =1
R3, R1, #1 ;d- R3, L2
;branch. B2 (si d<>0)
d<>0
d=1
L1:
L1 :
if(d!=1) go to L2
/*branchement b2*/
Bnez
L2:
L2 : …….
21
Smail.Niar@univ-valenciennes.fr
Exemple
Smail.Niar@univ-valenciennes.fr
Résultat : Si on ne branche pas sur L1 alors
on ne branche pas sur L2
NT : Not Taken
ou branchement
non pris NP
22
Performance de la prédiction avec 1 bit
avec une séquence: 2, 0, 2, 0
T
NT
Predict Taken
Predict Not
Taken
T
NT
Avec 1 bit 100% de mauvaise prédiction, initialement P1=NP
Branch1
Branch. 2
P2=NP
D= ?
2
Prédiction Action Nouvelle
b1
b1
prédiction
b1
NP
P*
P
0
P
2
NP
0
P
NP*
P*
NP*
Smail.Niar@univ-valenciennes.fr

Predicti Action Nouvelle
on b2
b2
prédiction
b2
NP
P*
P
NP
P
NP*
P
NP
P*
NP
P
NP*
NP
P
NP
23
P
P
^m chôse avec deux bits par
P
branchement

10
P
NP
NP
P
01
avec deux bits
NP
 Supposons qu ’on démarre de l ’état 00.
NP
 A chaque branchement est associé deux bits (le
prédicateur)
D= ?
2
0
Prédiction Action Nouvelle
b1
b1
prédiction
b1
NP
P*
NP
00
NP
NP
01
2
0
NP
00
NP
01
01
NP
00
P*
NP
NP
Predicti Action Nouvelle
on b2
b2
prédiction
b2
NP
P*
NP
00
NP
01
01
NP
00
NP
NP
00
01
NP
00
NP
NP
01
NP
00
P*
NP
NP
NP
01
00
50 % de mauvaise prédictions sur les deux branchement
24
Smail.Niar@univ-valenciennes.fr
11
P
Prédiction avec un bit et un bit
de corrélation
Chaque branchement est représenté dans la table par deux bits :
D= ?
Dernière
Branch
NP
Prédiction Action Nouvelle Dernière
b1
b1
prediction Branch
b1
NP/NP
P*
P/NP
P
Predicti Action Nouvelle
on b2
b2
prédiction
b2
NP/NP P*
NP/P
2
0
P
P/NP
NP
P/NP
NP
NP/P
2
NP
P/NP
P
P/NP
P
0
P
P/NP
NP
P/NP
NP
NP/P
NP/P
Deux mauvaises prédictions au début notées par *
NP
NP/P
P
NP/P
NP
NP/P
Smail.Niar@univ-valenciennes.fr
Prédiction si dernier branchement non pris/prédiction si dernier branchement pris
Exemple: pour b1= P/NP Si dern Branch non pris
alors branchement
Si dern Branch pris
alors pas branchement
25
Mise en œuvre matérielle
Table des prédicateurs
0
1
1
0
Adresse
branchement
...
0
...
1
1 bit de prédiction et
1 bit de corrélation
Smail.Niar@univ-valenciennes.fr
Corrélation Prédiction
...
prédiction
1
...
0
selectionner
0
bascule D
dernier branchement
26
Prédiction avec deux bits et
deux bits de corrélations
0
Adresse
branchement...
10 bits
...
...
...
...
...
(1 , 1)
...
...
1023
11
10
01
00
Smail.Niar@univ-valenciennes.fr
•on prend en compte les
deux
derniers branchements
•Il y a 4 combinaisons
possibles
00, 01, 10, 11
pour chaque combinaison
il y a
deux bits de prédictions.
Pattern History Tables PHTs
(2-bit predictors)
selectionner
Le registre BHR indique
le résultat des deux derniers
branchements
Registre de l’historique des branchements1 0
Branch History Register BHR
(2-bit shift register)
27




BTB : Branch Target buffer, Buffer des @ destinations
des branchements
BHT : « tampon de branchement » : Branch History
Table, table des prédictions (basée sur l’historique)
PHT : c ’est une BHT qui prend en compte les
derniers branchements. Pour chaque configuration
des n derniers branchements il y a une prédiction (un
BHT)
BHR : Branch History Register, registre à décalage
contenant les résultats des derniers branchements
exécutés. Utilisé pour accéder à la PHT
28
Smail.Niar@univ-valenciennes.fr
Résumé des symboles
Prédicteurs GAg et GAp
Gag (4 bits)
BHR 1
1
0
0
...
1100
1
Branch Pattern
History Table
(PHT)
predict:
taken
1
Index
...
Deux bits de prédiction
@ de branchements
2**n tables, # BHT
n
BHR
GAp (4 bits)
...
...
...
1 1 0 0
Index
1 seul reg d ’historique mais avec @de branchement
1
...
...
...
1
...
...
29
Smail.Niar@univ-valenciennes.fr
1 seul BHT
shift direction
Plusieurs Registres à décalage
(historique local)
BHT
1 BHR par Branch
...
...
1 1
0 0
Branch address
Plusieurs reg à dec d ’historique, 1 par
branchement
mais pas d ’@
1 1
0 0
Index
...
b1
Per-address
BHT
Pap(4)
...
b2
# BHT
Branch address b1
...
1 1 0 0
...
...
Branch address b2
1 1 0 0
1 1
0 1
...
...
...
1 1
Smail.Niar@univ-valenciennes.fr
Branch address
Pag(4)
Index
...
...
...
30
•3 programmes de références SPEC CPU2000 : Gcc (compilateur),
Equake (….), Wupwise (…)
•Simulateur : SimpleScalar, Pénalité miss Pred = 3
•Sauter : 5M inst et exécuter : 10M, env 20% ins sont des
branchements
•BTP : 512 sets et associativité : 4
•Les 4 prédicateurs avec une complexité equivalentes
•Complexité évaluée avec Wattch : Évaluation de la consommation de
puissance (4.9 nJ par accès à la BTP+BHR+BHT)
#BHR
Gag : 1
Gap 1
Pag
8
Pap
8
#BHT
1*4096
16*256
1*4096
16*256
#Corrélation = # bits reg Dec
12
8
12
4
31
Smail.Niar@univ-valenciennes.fr
Évaluation des Performances
Nombre de Misses
Échelle Logarithmique
Nbr Miss sur Pred de Branch
Smail.Niar@univ-valenciennes.fr
10000000
1000000
100000
10000
GCC
Wupwise
Equake
32
Nbr Cycles Exec
2.25E+07
Parfait
ToujoursPris
1.75E+07
JamaisPris
1.25E+07
Gag
Gap
7.50E+06
Pag
PaP
2.50E+06
Wupwise
Equake
Speed Up / Jamais Pris
1.8
1.7
1.6
Parfait
1.5
Toujours Pris
1.4
Jam ais Pris
1.3
Gag
1.2
Gap
1.1
Pag
1
PaP
0.9
0.8
GCC
Wupwis e
Equake
33
Smail.Niar@univ-valenciennes.fr
GCC
IPC
1.85
Parfait
1.65
ToujoursPris
1.45
1.25
JamaisPris
1.05
Gag
0.85
Gap
0.65
Pag
0.45
GCC
Wupw ise
Equake
Speed Up par rapport Jamais Pris
2
Parfait
1.8
Smail.Niar@univ-valenciennes.fr
PaP
0.25
ToujoursPris
1.6
JamaisPris
1.4
Gag
1.2
Gap
1
Pag
0.8
PaP
GCC
Wupwis e
Equake
34
Autres prédicateurs à deux
niveaux...
gselect : Concaténation de qq bits de poids
faible de l ’@ce branchement avec le registre
BHR
 gshare : Appliquer un OUX sur une partie
de l’@ de branchement et le BHR
Addresse Instruction. BHR
gselect4/4 gshare8/8
00000000
00000001 00000001 00000001
00000000
00000000 00000000 00000000
11111111
00000000 11110000 11111111
11111111
10000000 11110000 01111111
Smail.Niar@univ-valenciennes.fr

35
gselect et gshare
PHT
m
Conca
m
PC
gselect
Smail.Niar@univ-valenciennes.fr
m+n
PHT
OUX
n
BHR
m
m
PC
BHR
gshare
36
Quelques chiffres
Processeurs hautes performances :





P4 : prédiction dynamique des branchements : Adresse de la
prochaine Trace BTB : 4 way set associative, 512 lignes, BHT : 4
bits. Lorsque pas de prediction possible  Pred Statique : Forward
NT, Backward T
G5 : 3 tables Local/global/selector taille de 16KB
Athlon 64 bits :
Digital/Compaq 21386 :
Processeurs embarqués :


Arm7 :
Intel Xscale : BTB 128-entry (the address of a branch instruction,
the target address associated with the branch instruction, and a
previous history of the branch being taken or not taken), 4 states
predictions (two bits)
37
Smail.Niar@univ-valenciennes.fr

Auteur
Документ
Catégorie
Без категории
Affichages
11
Taille du fichier
606 Кб
Étiquettes
1/--Pages
signaler