Introduction

• La technique du pipeline est une technique de mise en oeuvre

qui permet à plusieurs instructions de se chevaucher pendant
l'exécution.
• Une instruction est découpée dans un pipeline en petits
morceaux appelés étage de pipeline.
• La technique du pipeline améliore le débit des instructions
plutôt que le temps d'exécution de chaque instruction.
• La technique du pipeline exploite le parallélisme entre
instructions d’un flot séquentiel d’instructions.

1
 Notion de Pipeline
Exemple: Opération de lavage du linge
Séquentiel ou bien pipeline
4 personnes ; chacun doit : A B C D
laver, sécher, repasser, ranger
lavage : 30 minutes

séchage : 40 minutes

Repassage : 30 minutes

Rangement : 20 minutes
2
 Lavage du linge en séquentiel

6 PM 7 8 9 10 11 12 1 2 AM

O 30 40 30 20 30 40 30 20 30 40 30 20 30 40 30 20
r Time
A
d
r B
e C
T D
â
c
h D C B A
e L S Re Ra • 8 heures pour terminer
s
3
 Lavage linge en pipeline
6 PM 7 8 9 10 1
O Temps
1
r
d 30 40 40 40 40 30 20 =240mn/60 30 40 30 20
r A
L S Re Ra
e
B
T C
â D
c
h Phase de Phase de
remplissage déchargement
e
s Pipeline=Toutes les ressources
fonctionnent en parallèles
• 4 heures !
4
 Rappel : diagramme d’état

IR <- Mem[PC]; PC <– PC+4;

A <- R[rs]; B<– R[rt]

BEQ/BNE
S <– A + B; S <– A or ZX; S <– A + SX; S <– A + SX; If Cond
PC < PC+SX;

SW
M <– Mem[S] Mem[S] <- B 3 cyc
R type
R[rd] <– S;
I type
R[rt] <– S;
LW
R[rd] <– M;
4 cyc
4cyc 4cyc 5 cyc
1 Approche : toutes les instructions aient même nb d’étages 5 (5 Cyc)

2 Approche : chaque type d’instruction ait son nombre d’étage 5

 1 Approche de Pipeline : 5 étages
5 Etages pour Chargement (LW)
L’exécution de l’instruction se fait en 5 étapes comme suit !
1. Lecture de l’instruction
2. Décodage et en même temps lecture des registres
3. Calcul dans l’UAL
 Instruction UAL : appliquer l’opération
 Instruction Mémoire : Calculer l’adresse
 Instruction de branchement : Calculer l’adresse de branchement
et évaluer la condition
4. Accès mémoire
5. Mise à jour du registre destination (pour les UAL et loads)
ou CP (pour les branchements)

6
Rappel :Chemin de données de monocycle

une seule UAL et deux ADD et deux mémoires

7
 Rappel :Chemin de données de multicycle

une seule UAL et une seul mémoire : solution n’est pas

retenue pour insuffisance de matériels
8
 Idée de Base : Pipeline

Idée: Ajouter des registres intermédiaires pour sauvegarder les informations fournies par chaque étage

9
Pipeline : Ajout de registres intermédiaires

10
 Les instructions ne sont pas sauvegardées

IF: Instruction fetch ID: Instruction decode/ EX: Execute/ MEM: Me mory acce ss WB: Write
register file read addre ss calculation back
0
M
Num de reg Contenu reg
u
x Branchement
1
terminé étape
4

Ad d

Ad d
4 Ad d
re s ult

S hift
le ft 2

26 R ea d
PC Ad dre s s r e gis te r 1
Re a d

100
ADD R1, R2, R3
In s tru ctio n
37 R ea d
re gis te r 2
d a ta 1

R e gist ers Re a d
2 ALU
Ze ro

3 1
0 ALU
Write R ead
d a ta 2 r e s ult Ad dr e ss 1
da ta
15
In str u ction re gis te r M
u Da ta M
me m ory u
Write x me m ory x
104 Sub R5, R6, R7
d at a 1
Writ e
0
da t a
16 32

1
Sign
exte nd

1
L’instruction contient des informations (numéros des registres, signaux de contrôle, …)
11
qui seront utilisées bien après la lecture de l’instruction. Il faut les mémoriser.
 Chemin de données pipeline : ajout des buffers

0
Buffer pour stocker le résultat : le tapis roulant
M
u
x
1

IF/ ID ID/ EX EX/ MEM M E M/W B

Ad d

Ad d
4 A dd re s ult

S hift
left 2
Add R1, R2, R3
In struc ti o n

R ea d
PC Add r e s s r e gis t er 1
Read
d at a 1
R ea d
r e gis t er 2 Zero
In str uct ion
R e gist e r s R e a d ALU ALU
m e m o ry Writ e 0 R ea d
d at a 2 r e s ult Ad dr e s s 1
r e gis t er M da ta
M
u D at a
Writ e x u
m e m o ry x
d at a 1
0
Write
da t a

16 32
Si g n
e xt e n d

Ces « buffers » sont utilisés non seulement pour stocker les données mais aussi les signaux de contrôle.
L'écriture dans les buffers est faite à chaque fin de cycle par les signaux : 12
FI/IDWrite, ID/ExWrite, EX/MemWrite, Mem/RbWrite
 Chemin de données pipeline : ajout des buffers

0
M
u
Buffer pour stocker le résultat : le tapis roulant
x
1

IF/ ID ID/ EX EX/ MEM M E M/W B

Ad d

Ad d
4 A dd re s ult

S hift
left 2

Add R1, R2, R3

Sub R5, R6, R7
In struc ti o n

R ea d
PC Add r e s s r e gis t er 1
Read
d at a 1
R ea d
r e gis t er 2 Zero
In str uct ion
R e gist e r s R e a d ALU ALU
m e m o ry Writ e 0 R ea d
d at a 2 r e s ult Ad dr e s s 1
r e gis t er M da ta
M
u D at a
Writ e x u
m e m o ry x
d at a 1
0
Write
da t a

16 32
Si g n
e xt e n d

13
 Chemin de données pipeline : ajout des buffers

0
Buffer pour stocker le résultat : le tapis roulant
M
u
x
1

IF/ ID ID/ EX EX/ MEM M E M/W B

Ad d

Ad d
4 A dd re s ult

Add R1, R2, R3

S hift
left 2
In struc ti o n

R ea d
PC Add r e s s r e gis t er 1
Read
LW …..

Sub ….
d at a 1
R ea d
r e gis t er 2 Zero
In str uct ion
R e gist e r s R e a d ALU ALU
m e m o ry Writ e 0 R ea d
d at a 2 r e s ult Ad dr e s s 1
r e gis t er M da ta
M
u D at a
Writ e x u
m e m o ry x
d at a 1
0
Write
da t a

16 32
Si g n
e xt e n d

14
 Chemin de données pipeline : ajout des buffers

0
M
u
Buffer pour stocker le résultat : le tapis roulant
x
1

IF/ ID ID/ EX EX/ MEM M E M/W B

Ad d

Ad d
4 A dd re s ult

S hift
left 2

Add R1, R2, R3

In struc ti o n

R ea d
PC Add r e s s r e gis t er 1
Add ……

Read
d at a 1
R ea d
r e gis t er 2 Zero
In str uct ion

LW …..

Sub ….
R e gist e r s R e a d ALU ALU
m e m o ry Writ e 0 R ea d
d at a 2 r e s ult Ad dr e s s 1
r e gis t er M da ta
M
u D at a
Writ e x u
m e m o ry x
d at a 1
0
Write
da t a

16 32
Si g n
e xt e n d

15
 Processeur avec pipeline

ER
ER ER
M M

EX

Contrôle

EI/DI DI/EX EX/MEM MEM/ER

NHA/MMY Pipeline

Based on UCB

Page : 16
17
 Remarques sur le traitement en pipeline
• Traitement en pipeline n ’améliore pas le temps de
chaque tâche, mais le débit des opérations
• Tâches multiples en parallèles avec ressources
différentes
• Débit de pipeline est limité par l ’étage le plus lent
Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5

Ifetch Reg/Dec Exec Mem Wr CLK=15ns

15ns 5ns 10ns 15ns 5ns

IRDE Mem Wr CLK=30ns

30ns 15ns 5ns

18
 Remarques sur le traitement en pipeline

• Longueur non-équilibrée réduit le gain de

temps
• Temps pour « remplir » et « décharger »
pipeline réduit le gain de temps
• Gain de temps = Nombre d ’étages (un µp à k
étages est k fois plus rapide qu’un µp simple)

19
 Représentation d’exécution en pipeline à 5 étages
Temps

IFetch Dcd Exec Mem WB

IFetch Dcd Exec Mem WB

IFetch Dcd Exec Mem WB

IFetch Dcd Exec Mem WB

IFetch Dcd Exec Mem WB

Déroulement du programme
IFetch Dcd Exec Mem WB

Phase de déchargement:
sauvegarde des résultats
20
 Comparaison: 1-Cycle, Multi-Cycle, Pipeline
Cycle 1 Cycle 2
Clk
Implémentation 1-Cycle:
LW SW Perte

Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10
Clk

Implémentation Multi-Cycle:
LW SW R-type
Ifetch Reg Exec Mem Wr Ifetch Reg Exec Mem Ifetch

Implementation Pipeline:
LW Ifetch Reg Exec Mem Wr

SW Ifetch Reg Exec Mem Wr

R-type Ifetch Reg Exec Mem Wr

21
 Pourquoi le pipeline?
Ifetch Reg Exec Mem Wr

10 +7 +10 +10 +7
• Exécution de 100 instructions

• Machine 1-Cycle (10+7+10+10+7)

– 44 ns/cycle x 1 CPI x 100 inst = 4400 ns
• Machine Multi-Cycle
– 10 ns/cycle x 4.1 CPI (mixte d ’instructions) x 100 inst = 4100 ns

• Machine en Pipeline
– 10 ns/cycle x (1 CPI x 100 inst + 4 cycles remplissage) = 1040 ns

CPI=Cycle Par Instruction 22

 Ressources Disponibles!
Temps (cycles)
O
r
d
r

ALU
Im Reg Dm Reg
e Inst 0

ALU
I
n
Inst 1 Im Reg Dm Reg

ALU
t Inst 2 Im Reg Dm Reg
r
u Inst 3

ALU
c Im Reg Dm Reg
t
i Inst 4

ALU
Im Reg Dm Reg
o
n
s
23
 Problèmes avec les Pipelines?
• Types d ’aléas (« hazards ») :
– Aléas de contrôle: prendre décision avant d’évaluer la
condition
• instruction de saut conditionnel
– Aléas de données: utilisation d’une donnée avant qu’elle
soit prête
• instruction dépend des résultats d ’une instruction
antérieure encore dans le pipeline
– Aléas de structure: utilisation d’une même ressource
plusieurs fois en même temps

- Aléas résolus par suspension (attente)

- Aléas résolus par prédiction (correcteur)
- Aléas résolus par renvoi (envoyer l’information d’un étage à
un autre)
 Mémoire : Aléas de structure
Temps

ALU
Mem Reg Mem Reg
Load

ALU
Mem Reg Mem Reg
Instr 1

ALU
Mem Reg Mem Reg
Instr 2

ALU
Mem Reg Mem Reg
Instr 3

ALU
Mem Reg Mem Reg
Instr 4

Détection
NHA/MMY Pipeline facile ! Solution limite la performance.
Based on UCB

Page : 25
26
27
 Aléas de contrôle
Si la condition est vérifiée le problème se situe au niveau de
l’éxcétion des instructions and, or et sub qui viennent de commencer
à être excéuter : perte de temps

06: add r8,r1,r9

ALU
Ifetch Reg DMem Reg
10: beq r1,r3,36

ALU
14: and r2,r3,r5 Ifetch Reg DMem Reg

18: or r6,r1,r7

ALU
Ifetch Reg DMem Reg

22: sub r8,r1,r9

ALU
Ifetch Reg DMem Reg

36: xor r10,r1,r11

ALU
Ifetch Reg DMem Reg
37: ori r2,r1,20
38: add r9,r3,r5
28
Page : 28
 1prémiére Solution: Suspension
• Suspension: possibilité de prendre la décision après 2 cycles par
ajout de hardwares : attendre jusqu’à ce que la décision puisse
être prise

Temp (en cycles)

ALU
Mem Reg Mem Reg
Add

ALU
Mem Reg Mem Reg
Beq

ALU
And Bulle Bulle Mem Reg Mem Reg
Stall
Suspension

29
 2éme Solution: Prédiction
a) Prédiction: Bonne (pas de saut : ZF=0)
Temps (en cycles)

ALU
Mem Reg Mem Reg *: condition
Add n’est pas
vérifiée

ALU
Beq
Mem Reg * Mem Reg

ALU
And Mem Reg Mem Reg

ALU
Mem Reg Mem Reg
or

ALU
Mem Reg Mem Reg
sub

xor

ALU
Mem Reg Mem Reg

Pas de cycle perdu 30

 2éme Solution: Prédiction
Prédiction: est fausse (il ya un saut ZF=1)
Temps (en cycles)

ALU
Mem Reg Mem Reg *: condition
Add vérifiée

ALU
Beq
Mem Reg * Mem Reg
NOP

ALU
And Mem Reg Mem Reg

ALU
Mem Reg Mem Reg
or

ALU
2 cycles perdues Mem Reg Mem Reg
Xor
Impact: 1 cycles / instruction saut

ALU
37: ori si prédiction est correcte zf=1, 2 Mem Reg Mem Reg
cycle en cas d ’erreur zf=0
(condition correcte = saut =50%)
31
 Aléas de donnée
• Problème est la dépendances en arrière de la donnée r1

Temps (en cycles)

F ID/R EX ME ER
Im Reg
add r1,r2,r3

ALU
Reg Dm

ALU
Im Reg Dm Reg
sub r4,r1,r3

ALU
Im Reg Dm Reg
and r6,r1,r7

ALU
Im Reg Dm Reg
or r8,r1,r9

ALU
Im Reg Dm Reg
xor r10,r1,r11

32
 Solution Aléas de Données:
• Solution est de “Renvoyer” résultat d ’une étape vers une autre

Temps (en cycles)

IF ID/RF EX MEM WB

ALU
Reg Reg
add r1,r2,r3 Im Dm

ALU
Im Reg Dm Reg
sub r4,r1,r3

ALU
Im Reg Dm Reg
and r6,r1,r7

ALU
Im Reg Dm Reg
or r8,r1,r9

ALU
Im Reg Dm Reg
xor r10,r1,r11

33
 Aléas de données: cas Load
• Dépendances en arrière
Probléme
Temps (en cycles)
I ID/RF EX MEM WB

ALU
F Reg Reg
lw r1,0(r2) Im Dm

ALU
Im Reg Dm Reg
sub r4,r1,r3

ALU
Im Reg
Bulle Dm Reg

solution Suspension

• Renvoi impossible
• Suspension est la seule solution

34
35
 Rappel : diagramme d’état

IR <- Mem[PC]; PC <– PC+4;

A <- R[rs]; B<– R[rt]

BEQ/BNE
S <– A + B; S <– A or ZX; S <– A + SX; S <– A + SX; If Cond
PC < PC+SX;

SW
M <– Mem[S] Mem[S] <- B 3 cyc
R type
R[rd] <– S;
I type
R[rt] <– S;
LW
R[rd] <– M;
4 cyc
4cyc 4cyc 5 cyc
1 Approche : toutes les instructions aient même nb d’étages 5 (5 Cyc)

2 Approche : chaque type d’instruction ait son nombre d’étage

36
Problème avec Pipeline à n étages
suivant type d’instruction
-Aléas de structure: utilisation d’une
même ressource plusieurs fois en même
temps

-Résolution: par suspension (attente) ou

ajout d’étape

37
 Rappel : Instruction de chargement LW
Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7
Clock

1er lw Ifetch Reg/Dec Exec Mem Wr

• Les 5 unités indépendantes du chemin données pipeline:

– Mémoire Instruction pour étape Ifetch
– Port lecture du Banc Registres (bus A et bus B) pour étape
Reg/Dec
– ALU pour étape Exec
– Mémoire données pour étape Mem
– Port lecture du Banc Registres port écriture (bus W) à l ’
étape Wr

38
 Rappel : Instruction type-R
Cycle 1 Cycle 2 Cycle 3 Cycle 4

R-type Ifetch Reg/Dec Exec Wr

• Ifetch
– Lecture de l ’instruction de mémoire instructions
• Reg/Dec
– Lecture registres et décodage de l ’instruction
• Exec
– Opération ALU sur les deux registres
• Wr
– Ecriture résultat dans un registre

39
 Aléas de structure
Pipeline avec type-R et LW
Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9
Clock

R-type Ifetch Reg/Dec Exec Wr Problème!

R-type Ifetch Reg/Dec Exec Wr

LW Ifetch Reg/Dec Exec Mem Wr

R-type Ifetch Reg/Dec Exec Wr

R-type Ifetch Reg/Dec Exec Wr

• Un conflit (aléas de structure ou
matériel):
– Deux instructions :écriture
Deux Solutions possibles:
dans le Banc registre en -suspendre
même temps!
– Un seul port écriture
-ralentir
40
 Solution 1: Suspension du pipeline
Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9
Clock
Ifetch Reg/Dec Exec Wr
Load Ifetch Reg/Dec Exec Mem Wr

R-type Ifetch Reg/Dec Exec Wr

R-type Ifetch Reg/Dec Bulle Exec Wr

R-type Ifetch Pipeline Reg/Dec Exec Wr
Ifetch Reg/Dec Exec

• Insertion de “bulle” pour élimination de conflit:

– Logique de contrôle compliquée.
– Pas de démarrage de nouvelle instruction.
• Pas de démarrage d’instruction en Cycle 6!

41
 Solution 2: Ralentir l’instruction type-R
– Écriture dans le banc registre se fait au cycle 5 au lieu de 4
– NOP (pas d’opération) pour étape Mem insertion
1 2 3 4 5
R-type Ifetch Reg/Dec Exec Mem Wr

Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9

Clock

R-type Ifetch Reg/Dec Exec Mem Wr

R-type Ifetch Reg/Dec Exec Mem Wr

Load Ifetch Reg/Dec Exec Mem Wr

R-type Ifetch Reg/Dec Exec Mem Wr

R-type Ifetch Reg/Dec Exec Mem Wr

Chargement de pipeline 42
 Solution : Modification Chemin&Contrôle
IR <- Mem[PC]; PC <– PC+4;

A <- R[rs]; B<– R[rt]

S <– A + B; S <– A or ZX; S <– A + SX; S <– A + SX; if Cond PC

< PC+SX;

Beq/Bne
M <– S M <– S M <– Mem[S] Mem[S] <- B

Sw

Cond=
R[rd] <– M; R[rt] <– M; R[rd] <– M;

R type I type Load

Regs.
Banc
Inst. Mem

Exec
Reg
Next PC

A M
File

S
PC

IR

Access
Mem

Mem
Data
D
43
 Solution pour instruction SW
Cycle 1 Cycle 2 Cycle 3 Cycle 4

SW Ifetch Reg/Dec Exec Mem Wr

NOP (pas d’opération) pour étape WR

44
 Solution pour Beq

Cycle 1 Cycle 2 Cycle 3 Cycle 4

Beq Ifetch Reg/Dec Exec Mem Wr

NOP (pas d’opération) pour étape Mem et WR

Conclusion : On converge vers utilisation de

Pipeline à 5 étages

45
 Exemple

10 lw r1, r2(35)
14 addI r2, r2, 3
20 sub r3, r4, r5
24 beq r6, r7, 100
28 ori r8, r9, 17
32 add r10, r11, r12
…
100 and r13, r14, 15

46
 Fetch 10
n n n n
Mem Inst

Decode
Exec WB
Mem
Ctrl Ctrl
Ctrl
rs rt

Banc
Reg.
Banc
Reg.
A M

Exec
S

B 10 lw r1, r2(35)

Donn.
Accé
Mem
Mem
D 14 addI r2, r2, 3
20 sub r3, r4, r5
PC Suiv.

24 beq r6, r7, 100

10
30 ori r8, r9, 17
34 add r10, r11, r12
…
100 and r13, r14, 15
47
 Fetch 14, Decode 10
n n n

lw r1,r2,3
Mem Inst

Decode
Exec WB
Mem
Ctrl Ctrl
Ctrl
rs rt

Banc
Reg.
Banc
Reg.
A M

Exec
S

B 10 lw r1, r2(35)

Donn.
Accé
Mem
Mem
14 addI r2, r2, 3
D
20 sub r3, r4, r5
PC Suiv.

24 beq r6, r7, 100

14
30 ori r8, r9, 17
34 add r10, r11, r12
…
100 and r13, r14, 15
48
 Fetch 20, Decode 14, Exec 10
n n

addi r2, r2, 3

Mem Inst

lw r1
Decode
Exec WB
Mem
Ctrl Ctrl
Ctrl

35
2 rt

Banc
Reg.
Banc
Reg.
A M

Exec
S

B
10 lw r1, r2(35)

Donn.
Accé
Mem
Mem
D 14 addI r2, r2, 3
20 sub r3, r4, r5
PC Suiv.

20 24 beq r6, r7, 100

30 ori r8, r9, 17
34 add r10, r11, r12
…
100 and r13, r14, 15
49
 Fetch 24, Decode 20, Exec 14, Mem 10
n

sub r3,r4, r5

addi r2, r2
Mem Inst

Lw r1
Decode
Exec WB
Mem
Ctrl Ctrl
Ctrl

3
4 5

Banc
Reg.
Banc
Reg.
A M

Exec

r2+3
B
10 lw r1, r2(35)

Donn.
Accé
Mem
Mem
D 14 addI r2, r2, 3
20 sub r3, r4, r5
PC Suiv.

24 24 beq r6, r7, 100

30 ori r8, r9, 17
34 add r10, r11, r12
…
100 and r13, r14, 15
50
???………….FIN

51