Smail.Niar@univ-valenciennes.fr

1

Ch 5 : La Prédiction des Branchements

IUP3/ Master Info. 1Smail Niar

ISTV Université de Valenciennes

smail.niar@univ-valenciennes.fr

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

2

Les prédictions de branchement

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.

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

3

Prédiction branchements ….suite

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)

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

4

3 cycles perdus à chaque branchement (pris)

Reg

CC 1

Time (in clock cycles)

40 beq $1, $3, 7

Programexecutionorder(in instructions)

IM Reg

IM

IM

IM

DM

DM Reg

RegIM72 lw $4, 50($7)

CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

5

Solution uniquement pour pour : beqz R1, etiq

Deux cycles perdus au lieu de 3

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

6

possibilités dans le traitement des aléas de contrôle

#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

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

7

Prédiction Branchement ..suite

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

#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

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

8

CP

Adresse des branchements

adresse de l ’instruction

valide

1 0

CP CP+4

Branchement Prédit pris

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/0

Branch Target Buffer BTB

Control

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

9

Prédiction par le compilateurStatique

Les branchement arrière sont toujours prédit pris et les branchement avant sont toujours prédit non pris

Freq

uenc

y of

Mis

pred

icti

on

0%

10%

20%

30%

40%

50%

60%

70%

alvi

nn

com

pres

s

dodu

c

espr

esso gc

c

hydr

o2d

mdl

jsp2 or

a

swm

256

tom

catv

Mis

pre

dic

tio

n R

ate

0%

2%

4%

6%

8%

10%

12%

14%

alvi

nn

com

pres

s

dodu

c

espr

esso gc

c

hydr

o2d

mdl

jsp2 or

a

swm

256

tom

catv

Always taken Taken backwardsNot Taken Forwards

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

10

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 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

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

11

Une instruction après le branchement est toujours

exécutée

Sub r6, r3, r2Add r1, r2, r3

add r4, r5, r6Beqz r4, etiq……….

etiq:

add r4, r5, r6Beqz r4, etiqSub r6, r3, r2Add r1, r2, r3……….

etiq:

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

12

La prédiction dynamique des branchements

Utilisation d ’une mémoire « tampon de branchement » BHT : Branch History Table (prédiction)

BHT Indexée par l ’adresse de l’instruction branchement

1 bit à chaque branchement 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

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

13

Prédicteur sur 1 bit

NT

NTT

T

Predict TakenPredict Not

Taken

Inconv Boucles : si le branch est toujours pris il y a 2 prédictions incorrects (mispredictions): la première et la dernière

BOUCLE etiq: …..…….……..boucle: bne r1,r2, etiq

Supposant: Bit prédiction initialisé à NT 0il y a 10 itérationsPremière itération : Prédiction NT , erreurDernière itération : Prédiction T, erreur

1 0

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

14

Exemple : Exemple:

etiq1: i1 début Boucle1

i2

…..

…..

etiq2: i3 Début Boucle2

i4

Si cond go to étiq2

….

Go to etiq1

Si boucle externe fait m itérationset la boucle interne fait n itération:2m fausses prédictions/ mn itérations

exemple m=n=1020% de fausses prédictions

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

15

Schéma de prédiction avec 2 bits

On associe à chaque branchement deux bits YX

Si Y=1 on prend le branchsi Y= 0 on ne prend pas le branch

11P

10P

01NP

00NP

NP

P

NP

P

P P

NP NP

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

16

Rappel : BTB : Branch Target buffer, Buffer des @

destinations des branchements

BHT : « tampon de branchement » : Branch History Table, table des prédictions pour chaque (basée sur l’historique)

Etiquette, @ BranchementPC

10PC (prédicateur BIMODAL)

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

17

La corrélation entre les branchements

Dans certains programmes, il y a des relations entre les instructions de branchementsBranchements « biaisés »

Un exemple de la vie courante: Orientation des étudiants pour des cours de mise à niveau.

Les étudiants entrant à une université proviennent de 2 options .

A : Option Math B : Option Physiqueb1: Test à l'entrée du lycéeb2: Test à l ’entrée de l’université.

Collège

Test à l’entrée du lycée

Série Math

Série appliqué

Lycée

Université

Test à l’entrée de l ’université.

b1

b2

MIASSPI

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

18

Collège

Test à l’entrée du lycée

Série Math

Série appliqué

Test à l ’entrée de l ’univer.

b1

b2

CollègeTest à l’entrée du lycée

Série Math

Série appliqué

Test à l ’entrée de l ’univer.

b1

b2

bonne prédiction mauvaise prédiction

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….?

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

19(Transparent P.Michaud IRISA)

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

20

Exemple

if (d==0) /*branchement b1*/ d=1

if(d==1) /*branchement b2*/ …….

Si d==0 avant le premier « If » , alors dans le deuxième If on trouvera d==1

Supposons que d est dans R1

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

21

Exemple

if (d!=0) go to L1/*branchement b1*/ d=1

L1 :if(d!=1) go to L2/*branchement b2*/

L2 : …….

Bnez R1, L1 ;branch vers L1 si d<>0

Addi R1, R0, #1 ;d= =0, alors d =1L1: Sub R3, R1, #1 ;d- -

Bnez R3, L2 ;branch. B2 (si d<>0)…..

L2: …..

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

22

Résultat : Si on ne branche pas sur L1 alorson ne branche pas sur L2

NT : Not Taken ou branchement

non pris NP

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

23

Performance de la prédiction avec 1 bit avec une séquence: 2, 0, 2, 0

Avec 1 bit 100% de mauvaise prédiction, initialement P1=NP P2=NP

NT

NTT

T

Predict TakenPredict Not

Taken

D= ? Prédictionb1

Actionb1

Nouvelleprédictionb1

Prediction b2

Actionb2

Nouvelleprédictionb2

2 NP P* P NP P* P

0 P NP* NP P NP* NP

2 NP P* P NP P* P

0 P NP* NP P NP* NP

Branch1 Branch. 2

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

24

^m chôse avec deux bits par branchement

avec deux bits Supposons qu ’on démarre de l ’état 00. A chaque branchement est associé deux bits (le

prédicateur) D= ? Prédiction

b1Actionb1

Nouvelleprédictionb1

Prediction b2

Actionb2

Nouvelleprédictionb2

2 NP P* NP NP P* NP

0 NP NP NP NP NP NP

2 NP P* NP NP P* NP

0 NP NP NP NP NP NP

00

11P

10P

01NP

00NP

NP

P

NP

P

P P

NP NP

0001

01 00

01

01

01

01

00 01

01 00

00

00

00

50 % de mauvaise prédictions sur les deux branchement

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

25

D= ? DernièreBranch

Prédictionb1

Actionb1

Nouvellepredictionb1

DernièreBranch

Prediction b2

Actionb2

Nouvelleprédictionb2

2 NP NP/NP P* P/NP P NP/NP P* NP/P

0 P P/NP NP P/NP NP NP/P NP NP/P

2 NP P/NP P P/NP P NP/P P NP/P

0 P P/NP NP P/NP NP NP/P NP NP/P

Prédiction avec un bit et un bit de corrélation

Chaque branchement est représenté dans la table par deux bits : Prédiction si dernier branchement non pris/prédiction si dernier branchement prisExemple: pour b1= P/NP Si dern Branch non pris alors branchement

Si dern Branch pris alors pas branchement

Deux mauvaises prédictions au début notées par *

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

26

Mise en œuvre matérielle

1 0

011...

...

0

...

...

1

Adresse branchement

0

selectionner

0

dernier branchement

bascule D

prédiction

Table des prédicateurs

1 bit de prédiction et 1 bit de corrélation

Corrélation Prédiction

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

27

Prédiction avec deux bits et deux bits de corrélations

•on prend en compte les deux derniers branchements•Il y a 4 combinaisons possibles00, 01, 10, 11pour chaque combinaison il y adeux bits de prédictions.

Le registre BHR indique le résultat des deux derniers

branchements

11 10 01 00

...

...

...

...

...

...

Pattern History Tables PHTs (2-bit predictors)

...

...

(1 , 1)

Adresse branchement

10 bits

0Registre de l’historique des branchements Branch History Register BHR

(2-bit shift register)

1

selectionner

0

1023

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

28

Résumé des symboles

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

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

29

Prédicteurs GAg et GAp

1 1 00

1100

...

...

1 1Index

predict: taken

BHR

Branch Pattern History Table

(PHT)

shift direction

Gag (4 bits)

1 seul BHT

n

...

...

...

...

2**n tables, # BHT

1 1 00...

...

1 1Index

...

@ de branchements

BHR

...GAp (4 bits)

1 seul reg d ’historique mais avec @de branchement

Deux bits de prédiction

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

30

Plusieurs Registres à décalage (historique local)

...

...

...

...

# BHT

...

...

1 1

b1

Index

Per-address BHT

...

...

0 01 1

0 01 1...Branch address b2

Branch address b1

0 1

b2

Pap(4)

...

...

1 1Index

BHT

...

...

0 01 1Branch address

0 01 1Branch addressPag(4)

Plusieurs reg à dec d ’historique, 1 par branchement

mais pas d ’@

1 BHR par Branch

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

31

Évaluation des Performances

•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 #BHT #Corrélation = # bits reg Dec

Gag : 1 1*4096 12Gap 1 16*256 8Pag 8 1*4096 12Pap 8 16*256 4

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

32

Nombre de Misses

Nbr Miss sur Pred de Branch

10000

100000

1000000

10000000

GCC Wupwise Equake

Échelle Logarithmique

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

33

Nbr Cycles Exec

2.50E+06

7.50E+06

1.25E+07

1.75E+07

2.25E+07

GCC Wupwise Equake

Parfait

ToujoursPris

JamaisPris

Gag

Gap

Pag

PaP

Speed Up / Jamais Pris

0.8

0.9

1

1.1

1.2

1.3

1.4

1.5

1.6

1.7

1.8

GCC Wupwise Equake

Parfait

ToujoursPris

JamaisPris

Gag

Gap

Pag

PaP

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

34

IPC

0.25

0.45

0.65

0.85

1.05

1.25

1.45

1.65

1.85

GCC Wupw ise Equake

Parfait

ToujoursPris

JamaisPris

Gag

Gap

Pag

PaP

Speed Up par rapport Jamais Pris

0.8

1

1.2

1.4

1.6

1.8

2

GCC Wupwise Equake

Parfait

ToujoursPris

JamaisPris

Gag

Gap

Pag

PaP

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

35

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

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

36

gselect et gshare

PC BHR

Conca

PHT

nm

m+n

PC BHR

OUX

PHT

mm

m

gselect gshare

Sm

ail.

Nia

r@u

niv

-vale

nci

enn

es

.fr

37

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)