Chapitre 3 : Pipeline
Explication par l'exemple :
Exemple du restaurant universitaire
•Opération: se servir un repas
Architecture de la chaîne de service décomposée en sous-éléments indépendants:
•Un présentoir pour les entrées
•Un présentoir pour les desserts
•Un présentoir pour les plats de résistance
•Une caisse
Entrées Desserts Plats Caisse
Chaine de service du repas
Dans l'ordre, nous devons passer devant ces 4 éléments
Exemple: restaurant universitaire
2 modes d'utilisation pour se servir un repas.
1ère méthode :
•Une seule personne à la fois dans toute la chaîne de repas.
•Quand elle a passé toute la chaîne et est sortie, une autre personne entre pour se servir.
Soit Te, le temps de passage à chaque étape.
Alors Tp = n * Te, Tp le temps de passage et n le nombre d'étapes dans un
passage.
Donc, le temps total Tt pour m personnes est de Tt = m * TP.
Tt = n * m * Te
2ème méthode
•Plusieurs personnes à la fois, en décalé.
•Une personne à chaque présentoir (élément).
•Une personne passe à l'élément suivant quand il est libre et qu'elle en a fini avec son
élément courant
Soit Te, le temps de passage à chaque étape.
Alors Tp = n * Te, Tp le temps de passage et n le nombre d'étapes dans un passage.
temps de passage de la 1ère personne.
Il faut 1 temps d'étape par personne supplémentaire, i.e. 1 * Te , donc pour m personnes Tt
= Tp + (m — 1) * Te , m — 1 car m personne moins la première
*Dans l'exemple pour 3 personnes si Te = 10s alors
•Passage séquentiel = 120s.
•Pipeline = 60s.
Intérêts du deuxième mode.
•Plusieurs personnes se servent en même temps.
•Gain de temps : plus de personnes passent pendant une même durée.
•Meilleure gestion des éléments : toujours utilisés.
Pipeline: définition
p1 p3p2 p4 p5
Instruction
Définition
Technique utilisée pour optimiser le temps d'exécution d'une opération répétitive.
Principes
•Lancer le traitement d'une opération avant que la précédente ne soit terminée
recouvrement des opérations.
•A chaque étape de l'opération est affectée une ressource indépendante, de façon à pouvoir
exécuter plusieurs opérations en parallèle, chacune à une étape différente
exploite le parallélisme entre les opérations d'un flot d'opérations séquentielles.
•Optimiser le temps d'utilisation des différents éléments.
Découpage des opérations en sous-parties élémentaires.
•En relation avec les étapes de traitement de l'opération.
•Définition des étages du pipeline.
•«travail à la chaine».
Exécution des sous-parties élémentaires dans les étages
correspondants du pipeline.
PIPELINE
Historique du Pipeline:
Terme introduit au début des années 80;
Mise en œuvre pour l’amélioration des performances.
Premier processeur avec la technique pipeline: INTEL
8086.
Basé sur le fait qu'un processeur peut exécuter plus d'une
seule instruction à la fois si les instructions sont divisés
en étapes;
Premiers processeurs divisaient les instructions en
respectant les 3 étapes d’exécution;
Le pipeline
Technique utilisée pour optimiser le temps d'exécution d'un processus
Méthode : ne pas attendre d'avoir finir toutes les étapes du traitement du 1er processus
pour commencer le 2ème ....
Le traitement des étapes s'effectue en parallèle, c'est à dire simultanément pour
plusieurs processus
Pipeline: découpage d’une instruction
Découpage d'une instruction dans le cas d'un processeur MIPS.
•En sous parties élémentaires.
•En relation avec les étapes de traitement de l'instruction.
Cas du processeur: sans pipeline
Traitement normal non-pipeliné (séquentiel) du flot d'instructions.
• Les instructions sont traitées les unes à la suite des autres.
• Lorsque le traitement se situe à une étape, les autres éléments sont au repos i.e. inutilisés.
• Pas de recouvrement.
Dans un micro-processeur sans pipeline, les instructions sont exécutées les unes après les
autres. En supposant que chaque étape met 1 cycle d'horloge pour s'exécuter
- 5 cycles pour exécuter une instruction
- 15 cycles pour 3 instructions.
Cas du processeur: avec pipeline
Solution avec pipeline:
• A chaque étape du processus est affectée une ressource indépendante, de façon à pouvoir
exécuter plusieurs processus en parallèle, chacun à une étape différente.
Exécuter simultanément les différentes étapes sur des données distinctes (parallélisme
d'instructions).
• 3 instructions sont traitées en parallèle en 7 cycles d'horloge:
Permet de multiplier le débit avec lequel les instructions sont exécutées par le
processeur.
Le gain se situe au niveau du débit, le temps de traitement d'une instruction reste le même.
Exemple pipeline à 5 étages
Gain important en utilisant le pipeline:
• Sans : exécution séquentielle de 2 instructions en 10 cycles.
• Avec : exécution parallèle de 5 instructions en 9 cycles.
L'idéal est d'équilibrer la longueur des étages du pipeline, sinon les étages les plus rapides
attendent les plus lents.
Temps de passage dans chaque étape identique (ou très proche).
Ici, nous pouvons voir que chaque élément du processeur est
en utilisation.
aucun élément au repos.
Exemple pipeline à 5 étages
• Autre représentation
IF Instruction1 Instruction2 Instruction3 Instruction4 Instruction5
ID Instruction1 Instruction2 Instruction3 Instruction4 Instruction5
EX Instruction1 Instruction2 Instruction3 Instruction4 Instruction5
MA Instruction1 Instruction2 Instruction3 Instruction4 Instruction5
WB Instruction1 Instruction2 Instruction3 Instruction4 Instruction5
Calcul de performances
Deux paramètres sont souvent utilisé pour mesurer la performance d'un processeur:
• La latence: Le temps de réponse ou temps d'exécution d'une certaine tâche:
• Temps écoulé entre le début et la fin d'exécution de la tâche (instruction).
• Le débit: quantité totale de travail réalisé dans un certain emps.
• Nombre d'opérations (tâches, instructions) exécutées par unités de temps.
L'amélioration du temps de réponse implique toujours une amélioration du débit. Le
contraire n'est pas toujours vrai.
• Par exemple, augmenter le nombre de processeurs augmentera le débit mais pas le
temps d'exécution.
L’accélération: nombre de fois plus vite qu'en séquentiel.
Calcul de performances
Cas réel = insertion de registres intermédiaires entre les étages
Calcul de performances
- Calcul du temps total d’exécution des instructions:
• Si Te , le temps d'exécution d'un élément,
• n le nombre d'éléments que compose une instruction
• Tp , le temps d'exécution d'une instruction
• m le nombre d'instruction à effectuer
• Et Tt , le temps total
- Séquentiel
Tt = m * Tp , avec Tp = n * Te
Tt = m * n * Te
- Pipeline
Tt = Tp + m — 1 * Te Fin de la première instruction à Tp = n * Te
Tt = n * Te + m — 1 * Te Toutes les unités de temps suivantes
Tt = Te * (n +m— 1) => fin d'une nouvelle instruction.
Si m est beaucoup plus grand que n, alors on peut considérer:
Tt ≈ m * Te
• Calcul de l’accélération:
Si m très grand alors A = n
cas idéal,
• Calcul du débit du pipeline
, temps exécution total ramené à 1 instruction
est souvent appelé le cycle machine
Exemple de profondeur
• Exemples de profondeur de pipeline (nombre d'étages d'un pipeline)
Intel Pentium 4 Prescott 31
Intel Pentium 4 20
AMD K10 16
IBM POWER5 16
IBM PowerPC 970 16
Intel Core2 Duo 14
Intel Pentium II 14
Sun UltraSPARCIV 14
Sun UltraSPARCIIi 14
AMD Opteron1xx 12
AMD Athlon 12
IBM POWER4 12
Intel Pentium III 10
Intel Itanium 10
MIPS R4400 8
Architecture de pipeline
Exemple de pipeline à 5 étages ou niveaux :
Le traitement s'effectue en 5 étapes ( ou 5 cycles) Chaque étage est isolé par un registre
Temps de cycle identique pour chaque étape ( ou phase) Les traitements 1, 2, 3, 4 et 5
s'effectuent en parallèle
Traitement des instructions
Suivant les types de processeurs :
Pipeline à 3 niveaux :
Fetch, decode , execute
Pipeline à 5 niveaux (processeurs ARM 9, MIPS) :
IF, ID, EX, MEM, WB
Jusqu'à 25 niveaux ! ( 20 niveaux pour le Pentium 4 )
PIPELINE
Pipeline RISC (basique):
Etapes d’exécution d’une instruction RISC sont:
1. Recherche de l'instruction;
2. Décodage de l'instruction;
3. Recherche des opérandes;
4. Exécution de l’instruction;
5. Sauvegarde des résultats.
PIPELINE
Pipeline RISC (basique):
Exécution à 5 phases => 5 étages dans le pipeline :
programme Cycles d’Horloge
1 2 3 4 5 6 7 8 9
Inst n° 1 I1 D1 O1 E1 S1
Inst n° 2 I2 D2 O2 E2 S2
Inst n° 3 I3 D3 O3 E3 S3
Inst n° 4 I4 D4 O4 E4 S4
Inst n° 5 I5 D5 O5 E5 S5
PIPELINE
Pipeline RISC (basique):
Pour 5 instructions, réduit le temps d'exécution de 25
unités de temps à 9 unités de temps.
Supposition : chaque instruction traverse les 5 étages;
Ce n’est pas toujours le cas; par exemple: chargement en
mode immédiat ne nécessite pas d'étage de recherche de
l'opérande en mémoire (Ox).
Pour simplifier le hardware du pipeline, le temps est
calculé en supposant que chaque instruction nécessite les
cinq étages.
PIPELINE
Exécution dans le pipeline: passe par trois phases
1. Amorçage du pipeline;
2. Exécution normale;
3. Vidage du pipeline.
Pendant les deux dernières phases, une instruction s e
termine à chaque cycle d’horloge
PIPELINE
Déséquilibre entre les étages:
Les étages n’ont pas les mêmes temps de traitement; Il est
nécessaire donc d’utiliser des buffers (files d’attentes)
entre les étages.
Exemple: Si Temps d'exécution > Temps de recherche
. L'étage de recherche devra attendre avant de vider son
buffer;
1
PIPELINE
Déséquilibre entre les étages:
Temps de passage d’un étage à l’autre pour une
instruction est appelé cycle machine.
Cycle machine inclut le temps de traitement de l’étage +
temps de traversée des buffers
L’étage le plus lent détermine la longueur d'un cycle
machine
2
PIPELINE
Aléas du pipeline:
Le bon fonctionnement du pipeline peut être perturbé par
plusieurs événements appelés aléas (pipeline hazard en
anglais). Ces événements sont classés en trois catégories.
1. aléas structurels qui surviennent lorsque deux instructions
dans des étages différents du pipeline nécessitent la même ressource.
2. aléas de données qui surviennent lorsqu’une instruction
nécessite une donnée qui n’a pas encore été calculée par une
instruction précédente. Ceci provient du fait que les instructions
lisent leurs arguments dans les premiers étages du pipeline alors
qu’elles produisent leur résultat dans les derniers étages.
PIPELINE
Aléas du pipeline:
Le bon fonctionnement du pipeline peut être perturbé par
plusieurs événements appelés aléas (pipeline hazard en
anglais). Ces événements sont classés en trois catégories.
1. aléas structurels
2. aléas de données
3. aléas de contrôle qui surviennent dès qu’une instruction de
branchement est exécutée. Si le branchement est effectué, les
instructions qui suivent dans le pipeline ne doivent pas être
exécutée. Ceci provient du fait que la nouvelle adresse est
calcu l ée
34
alors que les instructions qui suivent ont déjà été chargées.
PIPELINE
Aléas Structurels: interviennent lors de conflits de
ressources:
Exemple : la machine a une seule mémoire pour les
données et les instructions, alors que deux étages du
pipeline veulent faire des opération simultanées (I3 et O1
par exemple).
PIPELINE
Aléas Structurels: interviennent lors de conflits de
ressources:
Solutions:
1. Suspendre (ou bloquer) une des instructions jusqu'à ce
que l'unité demandée soit disponible. On voit alors
apparaître des bulles dans le pipeline.
2. Multiplier les ressources; par exemple, séparer entre
mémoire d’instruction et mémoire de programme.
PIPELINE
Aléas Structurels: interviennent lors de conflits de
ressources:
Solution 1: Suspendre (bloquer) une des instructions
jusqu'à ce que l'unité demandée soit disponible.
Problème: l'introduction de suspensions dégrade les
performances.
PIPELINE
Aléas de Données:
Interviennent lorsque deux instructions sont liées par des
dépendances de données: Une instruction a besoin du
résultat d'une instruction précédente;
Considérons ce code: c=b+a
e=c+d
En langage d’assembleur:
Inst2: add R6, , R5
Dépendance: Inst 2 a besoin du résultat dans le regist re
R4
PIPELINE
Aléas de Données: interviennent lorsque deux
instructions sont liées par des dépendances de données.
Exemple:
PIPELINE
Aléas de Données: interviennent lorsque deux
instructions sont liées par des dépendances de données.
Solutions:
1. Suspendre une des instructions jusqu'à ce que la
donné soit disponible (calculé).
2. Envoyer au plus tôt la donnée (lorsqu’elle soit
disponible) au pipeline.
3. Réordonnancer (changer l'ordre de) l'exécution des
instructions pour éviter ou réduire le problème
PIPELINE
Aléas de Données: interviennent lorsque deux
instructions sont liées par des dépendances de données.
Solution 1: Suspendre une des instructions jusqu'à ce que
la donné soit disponible (calculé).
PIPELINE
Aléas de Données: interviennent lorsque deux
instructions sont liées par des dépendances de données.
Solution 2: Envoyer au plus tôt la donnée (lorsqu’elle soit
calculé) au pipeline.
PIPELINE
Aléas de Données: interviennent lorsque deux
instructions sont liées par des dépendances de données.
Solution 3: Réordonnancer l'exécution des instructions.
PIPELINE
Aléas de Contrôle: interviennent lorsque qu’une
instruction de branchement est exécutée.
Exemple: Si (R1 > 30) alors R3 10 + R1
Sinon R3 20 + R1
Fonctionnement du saut conditionnel
En fonction du résultat du test, le contenu de CO est modifié avec
l'adresse de la prochaine instruction
Phase Ex : exécution de la comparaison par l'UAL
Phase Sx : écriture de CO en fonction du résultat du test
Problème: On doit connaître la valeur du test de valeur de
R1 pour savoir quelle est l'instruction suivante à exécuter
PIPELINE
Aléas de Contrôle: Interviennent lorsque qu’une
instruction de branchement est exécutée.
Exemple: Si (R1 > 30) alors R3 10 + R1
Sinon R3 20 + R1
Solutions:
1. Attendre que le bon CO soit connu : peu efficace
2. Réordonnancer le code : pas toujours suffisant et
possible
3. Prédire quelle sera la valeur de R1 et commencer le
calcul suivant selon cette prédiction
PIPELINE
Aléas de Contrôle: Interviennent lorsque qu’une
instruction de branchement est exécutée.
Exemple: Si (R1 > 30) alors R3 10 + R1
Sinon R3 20 + R1
Solution avec attente:
Attendre le Sx précédent avant de faire le Ix : on passe en
exécution purement séquentielle !
PIPELINE
Aléas de Contrôle: interviennent lorsque qu’une
instruction de branchement est exécutée.
Solution avec prédictions:
A l'aide de tables statistiques dynamiques, le résultat
d'un test est prédit. On commence ensuite l'instruction
suivante prédite.
Problème si prédiction erronée
On a commencé des calculs inutiles
Vidage du pipeline pour reprendre dans un état correct
Très couteux en temps
Très pénalisant pour des pipelines profonds
PIPELINE
Aléas de Contrôle: Interviennent lorsque qu’une
instruction de branchement est exécutée.
Solution avec prédiction:
PIPELINE
Aléas de Contrôle: Interviennent lorsque qu’une
instruction de branchement est exécutée.
Solution avec prédiction:
PIPELINE
Aléas de Contrôle: Solution avec prédiction: