Plan - Freefranki66.free.fr/Elec 4/Archives perso/Architecture/Ch5... · 2008-06-05 · Rechercher les endroits où le nombre de valeurs intermédiaires stockées sont réduit Exemple

Architecture de l’ordinateur - PipelineCopyright © F. Muller 2004

Ch5 - 1 -

PlanCh1 - IntroductionCh2 - Structure de l’ordinateurCh3 - Modèle de ProgrammationCh4 - Conception des ProcesseursCh5 - PipelineCh6 - Parallélisme d’instructionsCh7 - Systèmes MémoireCh8 - Mémoires CachesCh9 - Mémoire VirtuelleCh10 - Systèmes Multiprocesseurs

Ch5 - 2 -Copyright © F. Muller 2004

PipelineIntroductionPipeliningAléas d’instructionsPrédire le temps d’exécutionForwarding du résultat


Ch5 - 3 -

IntroductionObjectifs

Comprendre le pipeliningCalculer le temps de cycle d’un processeur pipelinéDécrire le forwarding de résultat et expliquer la manière dont il affecte le temps d’exécutionCalculer le temps d’exécution de petits segments de code sur processeurs pipelinés avec forwarding du résultat

IntroductionLes premiers ordinateurs

Chaque instruction (étapes de lecture, décodage, lecture du fichier de registre, calcul, …) était entièrement achevée avant d’exécuter la suivanteInconvénient : chaque étapes restent inopérantes la plupart du temps

De nos joursPipeline : Recouvrir l’exécution de plusieurs instruction afin de réduire le temps d’exécution d’une séquence d’instructionsInconvénient : nécessite quelques ajouts matériels au processeur mais la vitesse des instructions exécutées est augmentée


Ch5 - 4 -

Pipelining – Principe (1/3)

Processeur non PipelinéExécution des étapes pas à pas

Extractionde l’instruction

Décodagede l’instruction

Lecturedes registres

Exécutionde l’instruction

Écriture du résultatdans les registres

12

34

5

temps


Ch5 - 5 -

Pipelining – Principe (2/3)Extraction

de l’instruction

Latch

EIProcesseur Pipeliné

Division du chemin de données en plusieurs sectionsAjout de « latches » entre chaque sectionUne section s’appelle un étageChaque étage possède une latence d’un cycle horloge

1 cycled’horloge


Latch

DI1 cycle

d’horloge


Latch

LR1 cycle

d’horloge


Latch

EX1 cycle

d’horlogePipeline à 5 étages

1 cycled’horloge


ER


Ch5 - 6 -

Pipelining – Principe (3/3)Flux des instructions (5 étages)

Débit d’une instruction par secondeLatence de 5 cycles par instruction

Cycle

1 2 3 4 5 6 7EI Instruction 1 Instruction 2 Instruction 3 Instruction 4 Instruction 5 Instruction 6 Instruction 7

DI Instruction 1 Instruction 2 Instruction 3 Instruction 4 Instruction 5 Instruction 6

LR Instruction 1 Instruction 2 Instruction 3 Instruction 4 Instruction 5

EX Instruction 1 Instruction 2 Instruction 3 Instruction 4

ER Instruction 1 Instruction 2 Instruction 3

Étages du pipeline


Ch5 - 7 -

Exemple de Processeurs pipelinés (1/3)Processeur Profondeur du pipeline

Intel Pentium 4 Prescott 31Intel Pentium 4 20

Intel Core 2 Duo 14Intel Pentium II 14

AMD Opteron 1xx 12Intel Pentium III 10

Freescale G4 (PPC 7450) 7IBM Power4 12IBM Power5 16

IBM PowerPC 970 16Sun UltraSPARC III et IV 14

Intel Itanium 10MIPS R4400 8


Ch5 - 8 -

Exemple du processeur K7 & K8 - AMD (2/3)


Ch5 - 9 -

Exemple des processeurs ARM (3/3)ARM7TDMI (60 – 100 MHz)

Architecture Von Neumann3 étages de pipelineCPI ~ 1.9

ARM9TDMI (220 MHz)Architecture Harvard5 étages de pipelineCPI ~ 1.5


Ch5 - 10 -

Temps de cycle - PrincipeLe pipelining augmente en général le nombre de cycles d’horloge que nécessite un programme pour s’exécuter (instructions bloquées)L’amélioration provient du temps de cycle plus réduit entre chaque étage

plus de cycles par secondeNombre d’instruction par unité de temps plus élevé

Temps de cycle Moins négligeable lorsque le nb. d’étages augmente

Temps de cyclenon pipelinéTemps de cyclepipeliné + Latence d’un latch du pipeline=Nombre d’étages du pipeline

Remarque: On considère que la logique est répartie de manière égale entre les étages


Ch5 - 11 -

Temps de cycle - ExempleExemple

Un processeur non pipeliné possède un temps de cycle de 25ns. Quel est le temps de cycle d’une version pipelinée du processeur avec 5 étages de pipeline en considérant que chaque latch possède une latence de 1ns ? Même question avec 50 étages de pipeline ?


Ch5 - 12 -

Temps de cycle – Cas RéalisteLa logique du chemin de données ne peut pas être répartie en différents étages de pipeline de latence égale

Accès au fichier de registres : 3 nsDécodage d’une instruction : 4 nsetc …

Le concepteur doit trouver le juste milieuLogique de décodage irrégulière (difficile à diviser)Rechercher les endroits où le nombre de valeurs intermédiaires stockées sont réduit

ExempleSupposons qu’un processeur non pipeliné possédant un temps de cycle de 25ns soit divisé en 5 étages avec des latences de 5,7,3,6 et 4 ns et ayant une latence de latch de 1 ns.Quel est le temps de cycle du processeur ?


Ch5 - 13 -

Latence de pipelineLe pipeline réduit le temps de cycle d’un processeur et augmente le débit des instructions MAISLe pipeline augmente la latence du processeur

cycleT×= étaged' nombre pipelinedu Latence

Exemple 1Tcycle non pipeliné = 25ns, 5 ou 50 étages, latence latch = 1 ns

Pour 5 étages Tcycle = 6 ns Pour 50 étages Tcycle = 1,5 ns

Latence = 6 ns x 5 = 30 ns Latence = 1,5 ns x 50 = 75 ns

Exemple 2Tcycle non pipeliné = 25ns, 5 étages (latence = 5,7,3,6,4 ns), latence latch = 1 ns

Tcycle = 8 ns

Latence = 8 ns x 5 = 40 ns


Ch5 - 14 -

Les aléas d’instructionIntroduction

Le pipelining augmente la performance du processeur en accélérant le débit des instructionsDébit

Processeur pipeliné à 5 étages, Tcycle de 6 ns offre un débit idéal de 1/6ns = 1,67x108 instructions/sProcesseur non pipeliné, Tcycle = 25ns offre un débit de 4x107 instructions/sConclusion : le processeur pipeliné va 4 fois plus vite

Hélas, c’est trop beau pour être vrai …Dépendance entre les instructionsLes branchementsAccès à la mémoire


Ch5 - 15 -

Les aléas d’instructionPrésentation (1/3)

Aléas (dépendances) surviennent lorsque les instructions lisent ou écrivent dans des registres, utilisés par d’autres instructions, il existes 4 catégories:LAL (Lecture Après Lecture)

2 instructions lisent dans le même registreNe posent pas de problème au processeur

ExempleExemple

…ADD r1, r2, r3SUB r4, r5, r3…

Aléas LAL


Ch5 - 16 -


LAE (Lecture Après Écriture)Une instruction lit un registre qui a été écrit par une instruction précédenteAppelé aussi dépendances de données ou dépendances réellesBlocage du pipeline, apparition d’une « bulle » (NOP)


Aléas LAE

Cycle

1 2 3 4 5 6 7 8

EI ADD r1,r2,r3 SUB r4,r5,r1

SUB r4,r5,r1

DI ADD r1,r2,r3 SUB r4,r5,r1

LR ADD r1,r2,r3 SUB r4,r5,r1 SUB r4,r5,r1 SUB r4,r5,r1

EX ADD r1,r2,r3 NOP (Bulle) NOP (Bulle) SUB r4,r5,r1

ER ADD r1,r2,r3 NOP (Bulle) NOP (Bulle)

Étages du pipeline


Ch5 - 17 -


EAL (Écriture Après Lecture)Une instruction écrit après que l’instruction précédente est lu le même registre

EAE (Écriture Après Écriture)Une instruction écrit après que l’instruction précédente écrit aussi dans le même registre


Aléas EAL


Aléas EAE

ProblèmesToutes les instructions ne possèdent pas la même latenceProcesseurs OOO (Out-of-Order)


Ch5 - 18 -

Les aléas d’instructionBranchement (aléas de contrôle)

Les instructions de branchements conditionnels peuvent engendrerdes retard car le processeur ne peut pas déterminer la prochaine instruction à exécuter

…ADD r5, r2, r3BEQ sautSUB r1,r5,r2… Cycle

1 2 3 4 5 6

EI ADD r5,r2,r3 BEQ saut NOP (bulle) NOP (bulle) NOP (bulle) SUB r1,r5,r2

DI ADD r5,r2,r3 BEQ saut NOP (bulle) NOP (bulle) NOP (bulle)

LR ADD r5,r2,r3 BEQ saut NOP (bulle) NOP (bulle)

EX ADD r5,r2,r3 BEQ saut NOP (bulle)

ER ADD r5,r2,r3 BEQ saut

Étages du pipeline

Écriture des flags dans le registre d’état

On suppose que le résultat du registre r5 est différent de 0

Écriture du CO

Améliorations possiblesAjout d’un dispositif matériel qui calcule à l’avance le branchementAjout d’un mécanisme de prédiction


Ch5 - 19 -

Les aléas d’instructionAléas structurels

Survient lorsque l’architecture du processeur n’est pas capable d’exécuter simultanément toutes les instructions dans le pipelineExemple

Fichier de registres

Écriture dans le fichier de registres

même cycle

Lecture dans le fichier de registres

Les aléas structurels sont plutôt rares dans les processeurs modernesLes processeurs qui exécutent plus d’une instruction par cycle sont restreints sur le type d’instruction à exécuter en parallèleExemple : opération sur les entiers // opérations sur les flottants


Ch5 - 20 -

Les aléas d’instructionMarquage sur les registres

Le processeur pipeliné doit tenir compte des registres qui doivent être écrits par les instructions présentes dans le pipelinePermet aux instructions suivantes de savoir lors de l’étage LR si les registres sont disponiblesMarquage des registres (scoreboarding)

Ajout d’un bit de présence par registreBit à 1 : lecture possible (rempli)Bit à 0 : attente qu’une instruction vienne écrire (vide)

Si le ou les registres ne sont pas près, ajout d’une bulle

Fichier de registres

registreBit de présence


Ch5 - 21 -

Prédire le temps d’exécutionPrincipe (1/2)

Processeur non pipelinéLe temps d’exécution est la somme des temps de chaque instruction

Processeur pipelinéPlus complexe, Tenir compte des dépendancesDans le cas idéalTemps d’exécution (en cycle) = nb. d’étage + (nb. Inst. – 1)

Cycle

n n+1

EI … …

DI … …

LR ADD r5,r2,r3 …

EX … ADD r5,r2,r3

ER … …

Étages du pipeline

SolutionsDessiner un diagramme de flux du pipeline (pas très utilisable pour de longs programmes)Diviser le temps d’exécution en 2 parties

La latence du pipelineLe temps requis pour émettre toutes les instructions du programme

Instructionémise


Ch5 - 22 -

Prédire le temps d’exécutionPrincipe (2/2)

La durée d’émission totaleCommence au cycle d’émission de la première instructionAjout de cycles intermédiaires lorsque le pipeline est bloqué(bulle)Se termine au cycle d’émission de la dernière instruction

Temps d’exécutionLatence du pipeline + temps d’émission des inst. – 1

Dans la pratiqueLatence pour chaque type d’instructionLes instructions sont émises

Soit durant le cycle qui suit l’émission de l’instruction que les précèdentSoit lorsque toutes les latences de toutes les instructions dont elles dépendent ont terminées

Le nombre de cycles d’un programme requis peuvent être calculéen suivant pas à pas l’écoulement séquentiel des instructions afin de repérer à quel moment chacune des instructions parvient à être émise


Ch5 - 23 -

Prédire le temps d’exécutionExemple 1

Si notre pipeline possède des latences d’instruction de 4 cycles pour les instructions de branchement, 3 cycles pour les autres, quel est le temps d’exécution de la séquence suivante d’instruction ?

ADD r1, r2, r3SUB r4, r5, r6MUL r8, r2, r1ASH r5, r2, r1OR r10, r11, r4

cycle n cycle n+1 (indépendante)cycle n+3 (dépend de ADD)cycle n+4 (dépend de ADD)cycle n+5 (indépendante)

6 cycles pour émettre les instructions

Cycle

1 2 3 4 5 6 7 8 9 10

OR r10,r11,r4

OR r10,r11,r4

ASH r5,r2,r1

OR r10,r11,r4

ASH r5,r2,r1

MUL r8,r2,r1

EI ADD r1,r2,r3 SUB r4,r5,r6 MUL r8,r2,r1 ASH r5,r2,r1 OR r10,r11,r4 OR r10,r11,r4

DI ADD r1,r2,r3 SUB r4,r5,r6 MUL r8,r2,r1 ASH r5,r2,r1 ASH r5,r2,r1 OR r10,r11,r4

LR ADD r1,r2,r3 SUB r4,r5,r6 MUL r8,r2,r1 MUL r8,r2,r1 ASH r5,r2,r1

EX ADD r1,r2,r3 SUB r4,r5,r6 NOP (bulle) MUL r8,r2,r1

ER ADD r1,r2,r3 SUB r4,r5,r6 NOP (bulle)

Étages du pipeline

VVéérificationrification


Ch5 - 24 -

Prédire le temps d’exécutionExemple 2

Le pipeline possède 7 étages, les instructions de branchement possèdent une latence de 5 cycles, les autres instructions une latence de 2 cycles. Nous supposerons que le branchement n’est pas effectuéBNE r4, #0, r5DIV r2, r1, r7ADD r8, r9, r10SUB r5, r2, r9MUL r10, r5, r8


Ch5 - 25 -

Forwarding de résultatPrincipe

Une grande partie des délai (dépendance de données) est due au temps requis pour écrire le résultat d’une instruction dans le fichier de registreSolution: transmettre le résultat de l’étage d’exécution directement aux instructions situées dans les précédents étages du pipeline

Forwarding de résultat (bypassing)

Cycle

1 2 3 4 5 6 7 8

EI ADD r1,r2,r3 SUB r4,r5,r1

SUB r4,r5,r1

DI ADD r1,r2,r3 SUB r4,r5,r1

LR ADD r1,r2,r3 SUB r4,r5,r1 SUB r4,r5,r1 SUB r4,r5,r1

EX ADD r1,r2,r3 NOP (Bulle) NOP (Bulle) SUB r4,r5,r1

ER ADD r1,r2,r3 NOP (Bulle) NOP (Bulle)

Étages du pipeline

Exécution de ADD Écriture du résultat dans r1 Lecture de r1 Exécution de SUB


Ch5 - 26 -

Forwarding de résultatExemple d’implémentationLes processeurs implémentent le forwarding de résultat différemment.Par exemple, on peut éviter l’ajout d’un chemin de bypass:

1er demi cycle : Écriture du fichier de registres2ème demi cycle : lecture du fichier de registres

BilanRamène à 2 cycles de latence l’exemple précédentSi on ajoute un chemin de bypass, la latence est de 1 cycle

Extractionde l’instruction

Latch


Latch


Latch


Latch


LR

EX

ER

EI

DI

Chemin du forwarding de

résultatChemin habituel


Ch5 - 27 -

Forwarding de résultatExemple

Quel est le temps d’exécution (en cycles) du code suivant (cf. Aléas LAE) si le forwarding de résultat est implémenté dans notre pipeline à 5 étages ?

ADD r1, r2, r3SUB r4, r5, r1

cycle ncycle n+1 (bypass)

2 cycles pour émettre les instructions


Ch5 - 28 -

SynthèseLe pipeline améliore la performance des processeurs en recouvrant l’exécution de plusieurs instructionsLa performance crête d’un système pipeliné dépend

Du nombre d’étagesDe l’équilibrage de répartition de la logique d’exécutionDélai des latches

L’impact du pipeline diminue à mesure que le nombre d’étages augmente (latches non négligeables)La performance d’un système pipeliné est limitée par les dépendances de données : LAE, EAL et EAELes branchements limitent la performance du pipelineLe forwarding est utilisé pour réduire le délai causé par les dépendances LAE, c’est-à-dire la latence des instructions

Documents

Plan - Freefranki66.free.fr/Elec 4/Archives perso/Architecture/Ch5... · 2008-06-05 · Rechercher les endroits où le nombre de valeurs intermédiaires stockées sont réduit Exemple