La technique du pipeline

Universitylib.com

il y a 4 ans

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

Exemple: Opération Séquentiel de lavage ou bien du linge pipeline

4 personnes ; chacun doit :

laver, sécher, repasser, ranger lavage : 30 minutes

séchage : 40 minutes

Repassage : 30 minutes

Rangement : 20 minutes

Notion de PipelineA B C D

Lavage du linge en séquentiel

O30 rdre

6 PM 7 8 9 10 11 12 1 2 AM

30 40 30 20 A 40 Time 30 20 30 40 30 20 30 40 30 20 BeTâche• 8 heures pour terminer s

C B A L S Re Ra 3

OrdreT Tâches Phase de

remplissage

Phase de déchargement

Pipeline=Toutes les ressources fonctionnent en parallèles

Lavage linge en pipeline

6 PM 7 8 9 10 11 Temps

A BC30 40 40 40 40 30 20

=240mn/60

4 heures !

30 40 30 20 L S Re Ra

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;

R[rd] <– S;

SW M <– Mem[S]

Mem[S] <- B

3 cyc

R type I type LW

4 cyc R[rt] <– S; R[rd] <– M; 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 Instruction UAL UAL : : appliquer appliquer l’opération 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)

une seule UAL et deux ADD et deux mémoires

Rappel :Chemin de données de monocycle

une seule UAL et une seul mémoire : solution n’est pas retenue pour insuffisance de matériels

Rappel :Chemin de données de multicycle

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

Idée de Base : Pipeline

Pipeline : Ajout de registres intermédiaires

2PC

100

6R ea d ADD R1, R2, R3

re gister 1 37

Rea d re gister 21

5Re ad data 1

re Write

gister

R e gist ers

data Re ad 2 3 2MuWrite x data

Zero ALU

ALU res ult 1

Ad dre ss

R e ad data Data me mory 1

Write

1 Mux0 data

16 Sign

exte nd

11 L’instruction contient des informations qui seront utilisées bien après la lecture 104 Sub R5, R6, R7

(numéros de l’instruction. des registres, Il faut les signaux mémoriser.

de contrôle, 11

…)

Les instructions ne sont pas sauvegardées

4 Add Add re s ult

Shift

EX: Execute/ address calculation

MEM: Memory access

Num de reg Contenu reg Branchement terminé étape 4 IF: Instruction fetch ID: Instruction decode/

back

Mux1Ad d

le ft 2

Addres s

Instruction

me mory

R ea d PC

re gister 1

R e a d

R ea d

dat a 1 re gister 2Ze ro

R egiste rs Write re gister

R e a d dat a 2

Write 0 dat a

16 Sign

ext e nd

ALU

ALU Mre s ult R uD ata x

me mory

ea d da ta

Write data

Ad dre ss

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 : FI/IDWrite, ID/ExWrite, EX/MemWrite, Mem/RbWrite

1 Mux12

Chemin de données pipeline : ajout des buffers

0Buffer pour stocker le résultat : le tapis roulant Mux1Ad d

4 Add Ad d

re s ult

S hift left 2

In str uction

me mory

IF/ID ID/EX

EX/ MEM MEM/W B

Addre ss

3 2

R ea d PC

re gister 1

R e a d

R ea d

dat a 1 re gister 2Ze ro

R egiste rs Write re gister

R e a d dat a 2

ALU

ALU Mre s ult uD ata x

me mory

Write 0 dat a

16 Sign

ext e nd

R ea d da ta

Write data

Ad dre ss

1 Mux

Chemin de données pipeline : ajout des buffers

0MuBuffer pour stocker le résultat : le tapis roulant x1Ad d

4 Add Ad d

re s ult

S hift left 2

In str uction

me mory

IF/ID ID/EX

EX/ MEM MEM/W B

Addre ss

3 2

R ea d PC

re gister 1

R e a d

R ea d

dat a 1 re gister 2Ze ro

R egiste rs Write re gister

R e a d dat a 2

ALU

ALU Mre s ult uD ata x

me mory

Write 0 dat a

16 Sign

ext e nd

R ea d da ta

Write data

Ad dre ss

1 Mux

Chemin de données pipeline : ajout des buffers

0Buffer pour stocker le résultat : le tapis roulant Mux1Ad d

4 Add Ad d

re s ult

S hift left 2

In str uction

me mory

IF/ID ID/EX

EX/ MEM MEM/W B

Addre ss

3 2

R ea d PC

re gister 1

R e a d

R ea d

dat a 1 re gister 2Ze ro

R egiste rs Write re gister

R e a d dat a 2

ALU

ALU Mre s ult uD ata x

me mory

Write 0 dat a

16 Sign

ext e nd

R ea d da ta

Write data

Ad dre ss

1 Mux

Chemin de données pipeline : ajout des buffers

0MuBuffer pour stocker le résultat : le tapis roulant x1Ad d

4 Add Ad d

re s ult

S hift left 2

In str uction

me mory

IF/ID ID/EX

EX/ MEM MEM/W B

Addre ss

3 2

NHA/MMY Pipeline

Based on UCB

Page : 16

Contrôle

ERMEX

ERM

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

Processeur avec pipeline

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

15ns 5ns 10ns 15ns 5ns

IRDE Mem Wr 30ns 15ns 5ns

CLK=15ns

CLK=30ns

Remarques sur le traitement en pipeline

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

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

Temps

IFetch Dcd Exec Mem WB

IFetch IFetch Dcd Dcd Exec Exec Mem Mem WB WB

IFetch Dcd Exec Mem WB

Déroulement du programme

IFetch Dcd Exec Mem WB Phase de déchargement: sauvegarde des résultats19

Comparaison: 1-Cycle, Multi-Cycle, Pipeline

Clk

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

Implémentation Multi-Cycle:

LW SW

Ifetch Reg Exec Mem Wr

Implementation Pipeline:

LW Ifetch Reg Exec Mem Wr

Ifetch Reg Exec Mem Wr R-type

Ifetch Reg Exec Mem

Ifetch

R-type

Ifetch Reg Exec Mem Wr 20

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 21

OrdreI

nstructions

Temps (cycles)

Inst 0

Inst 1

Im Reg Dm Reg

Inst 1

Im Reg Dm Reg

Inst 2 Inst 3

Inst 4

Ressources Disponibles!

Im Reg Dm Reg

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

Load

Mem Reg Mem Reg

Instr 1

Mem Reg Mem Reg

Instr 2

Mem Reg Mem Reg

Instr 3

Reg Mem Reg

Instr 4

Mem Reg Mem Reg

Mem

NHA/MMY Détection Pipeline

facile ! Solution limite la performance.

Based on UCB

Page : 24

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

14: and r2,r3,r5

18: or r6,r1,r7

22: sub r8,r1,r9

36: xor r10,r1,r11 37: ori r2,r1,20 38: add r9,r3,r5 10: beq r1,r3,36

Ifetch Reg DMem Reg

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

Ifetch Reg DMem Reg

25 Page : 25

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 Add

Beq

And

Mem Reg Mem Reg

Bulle Bulle

Mem Reg Mem Reg Stall

Suspension

Temp (en cycles)

Add Mem Reg Mem Reg

sub

Mem Reg Mem Reg

Mem Reg Mem Reg xor

27 Pas de cycle perdu

2éme Solution: Prédiction

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

Add

Beq

Mem Reg Mem Reg

*: condition n’est pas

Mem Reg *

Mem Reg

vérifiée

And

Mem Reg Mem Reg

2éme Solution: Prédiction

Beq NOP And

Mem Reg Mem Reg

Xor

2 cycles perdues

Mem Reg Mem Reg

37: ori

Impact: 1 cycles / instruction saut si prédiction est correcte zf=1, 2 cycle en cas d ’erreur zf=0 Mem Reg Mem Reg (condition correcte = saut =50%)

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

Add Mem Reg Mem Reg

Mem Reg *

Mem Reg

Mem Reg Mem Reg

*: condition vérifiée

Aléas de donnée

Problème est la dépendances en arrière de la donnée r1

Temps (en cycles)

add r1,r2,r3

sub r4,r1,r3

F ID/R EX ME ER Im

Reg Dm Reg

Im Reg Dm Reg

and r6,r1,r7

or r8,r1,r9

xor r10,r1,r11

Im Reg Dm Reg

Solution Aléas de Données:

Solution est de “Renvoyer” résultat d ’une étape vers une autre

Temps (en cycles)

add r1,r2,r3

sub r4,r1,r3

IF ID/RF EX MEM WB Im Reg Dm Reg

Im Reg Dm Reg

and r6,r1,r7

or r8,r1,r9

xor r10,r1,r11

Im Reg Dm Reg

Aléas de données: cas Load

Dépendances en arrière

Temps (en cycles)

lw r1,0(r2)

sub r4,r1,r3

ID/RF Probléme IEX MEM WB F Im Reg Dm Reg

Im Reg Dm Regsolution Im Reg

Bulle Dm Reg Suspension

Renvoi impossible
Suspension est la seule solution

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;

R[rd] <– S;

SW M <– Mem[S]

Mem[S] <- B

3 cyc

R type I type LW

4 cyc R[rt] <– S; R[rd] <– M; 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

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 temps

-Résolution: par suspension (attente) ou ajout d’étape

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 Port lecture lecture du du Banc Banc Registres Registres (bus (bus A A et et bus bus B) B) pour pour étape é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

Rappel : Instruction type-R

Ifetch

– Lecture de l ’instruction de mémoire instructions

Reg/Dec

Cycle 1 Cycle 2 Cycle 3 Cycle 4

R-type Ifetch Reg/Dec Exec Wr • 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

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 Ifetch Reg/Dec Reg/Dec Exec Exec Mem Mem Wr 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 dans le Banc registre en

Deux Solutions possibles: -suspendre même temps! – Un seul port écriture

-ralentir

Solution 1: Suspension du pipeline

Clock

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

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

Ifetch Reg/Dec Exec

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 38

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;

M <– Mem[S]

Mem[S] <- B

if Cond PC < PC+SX;

M <– S M <– S

Beq/Bne M <– S

M <– S

M <– Mem[S] Mem[S] <- B R[rd] <– M;

R[rt] <– M; R[rd] <– M; R type I type Load

S M

Solution pour instruction SW

Cycle 1 Cycle 2 Cycle 3 Cycle 4

Ifetch Reg/Dec Exec Mem SW Wr

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

Solution pour Beq

Cycle 1 Cycle 2 Cycle 3 Cycle 4

Ifetch Reg/Dec Exec Mem Beq Wr

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

Conclusion : On converge vers utilisation de Pipeline à 5 étages

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 28 ori r8, r9, 17

32 add r10, r11, r12

…100 and r13, r14, 15

n n n

Mem Ctrl

rs rt

Exec Ctrl

WB Ctrl

Fetch 10

A S

10 lw r1, r2(35)

14 addI r2, r2, 3

20 sub r3, r4, r5

24 beq r6, r7, 100

30 ori r8, r9, 17

34 add r10, r11, r12

…100 and r13, r14, 15

rs rt

Fetch 14, Decode 10 n

n n

Exec Ctrl

Mem Ctrl

A S

WB Ctrl

10 lw r1, r2(35)

14 addI r2, r2, 3

20 sub r3, r4, r5

24 beq r6, r7, 100

30 ori r8, r9, 17

34 add r10, r11, r12

…100 and r13, r14, 15

Fetch 20, Decode 14, Exec 10

n n

Exec Ctrl

A S

Mem Ctrl

WB Ctrl

2 rt

10 lw r1, r2(35) D

14 addI r2, r2, 3

20 sub r3, r4, r5

24 beq r6, r7, 100

30 ori r8, r9, 17

34 add r10, r11, r12

…100 and r13, r14, 15

Fetch 24, Decode 20, Exec 14, Mem 10

Exec Ctrl

Mem Ctrl

WB Ctrl

4 5

lw r1, r2(35) D

addI r2, r2, 3

sub r3, r4, r5

beq r6, r7, 100

ori r8, r9, 17

add r10, r11, r12

…100 and r13, r14, 15

télécharger gratuitement cours de La technique du pipeline