pipline.doc

TD pipeline


Contrôle


1 Construction de l'architecture

Modifier l'architecture pour réaliser l'instruction Saut Inconditionnel. On
cherchera à minimiser le coût matériel en utilisant le matériel existant et
en ajoutant le minimum de multiplexeur.
le matériel nécessaire et le contrôle associé sont à dessiner sur la
feuille

2 Construction du contrôle

Indiquer le contrôle à associer à chaque cycle pour exécuter l'instruction
Saut Inconditionnel , en remplissant le tableau représentant les valeurs du
contrôle. On ajoutera des signaux de contrôle si nécessaire.

| | |Valeur |
| | |booléen |
|C|C1 | |
| |C2 | |
| | | |
|B|B1 | |
| |B2 | |
| |B3 | |
| | | |
|A|A1 | |
| |A2 |XX |
| |A3 | |
| | | |
| |... | |


Format de l'instruction :
Saut Inconditionnel 100 ; aller en 100 relativement à CP+4 (100 est une
adresse d'instruction).

|Op |x |x |100 |
|6 bits |5 Bits |5 Bits |16 Bits |






Les performances de base du pipeline


1 Exercice

Soit une machine non pipelinée. On suppose qu'elle a des cycles d'horloge
de 10 ns, et qu'elle utilise quatre cycles pour les opérations UAL et les
branchements et cinq cycles pour les opérations mémoire. On suppose que les
fréquences relatives de ces opérations sont respectivement de 40%, 20% et
40%. On suppose qu'à cause des dispersions d'horloge et des temps
d'établissement, le fait de pipeliner la machine ajoute 1ns de surcoût au
cycle d'horloge. Sans perdre compte l'impact de la latence, quelle est
l'accélération de l'exécution des instructions liée au pipeline ?
Le temps moyen d'exécution d'une instruction sur la machine non pipelinée
est :
Tps d'exécution moyen d'une instruction = Cycle d'horloge * CPI moyen
= 10*((40%+20%)*4+40%*5) = 44ns.
Dans la machine pipelinée, l'horloge doit fonctionner à la vitesse de
l'étage le plus lent plus le surcoût, ce qui fera 10+1 = 11 ns ; ceci est
le temps moyen d'exécution d'une instruction. Ainsi l'accélération due au
pipeline est :
Accélération = Tps moyen sans pipeline/ Tps moyen d'exécution avec pipeline
= 44/11=4 fois


2 exercice

On suppose que les temps utilisés par les cinq unités fonctionnelles qui
opèrent dans chacun des cinq cycles sont les suivants : 10ns,8 ns, 10ns
10ns et 7ns. On suppose que le pipeline ajoute 1ns de surcoût. Quelle est
l'accélération par rapport au chemin de données en un seul cycle ?

Puisque la machine non pipelinée exécute toutes les instructions en un seul
cycle d'horloge, son temps moyen d'exécution d'une instruction est
simplement le temps de cycle d'horloge. Ce temps de cycle est égal à la
somme des temps d'exécution de chaque étape :
Tps d'exécution moyen d'instruction = 10+8+10+10+7 = 45ns
Le temps de cycle sur la machine pipelinée doit être le plus grand de tous
les étages du pipeline 10ns plus le surcoût (1ns) soit un total de 11ns.
Puisque le CPI est 1, cela donne un temps d'exécution moyen de 11 ns.
On a donc :
Accélération pipeline = Tps moyen d'exécution d'une instruction sans
pipeline/Temps moyen d'exécution d'une instruction avec pipeline
= 45/11 = 4,1 fois.

Déroulement des instructions pipelinées


Indiquer les différents signaux à chaque étapes de pipeline pour la suite
d'instructions suivante :
add $2,$3,$1
beq $6,$12,100


|Instruct|Lignes de contrôle |Lignes de contrôle |Lignes de |
|ion |étage exécution |étage mémoire |contrôle étage |
| | | |d'écriture |


|RegDst |UAL
Op1 |UAL
Op2 |UALSrc |Branchement |Lire
MEM |Ecr
Mem |Ecrire
Reg |MemversReg | |format R |1 |1 |0 |0 |0 |0 |0 |1 |0 | |Lw |0 |0 |0 |1 |0
|1 |0 |1 |1 | |Sw |x |0 |0 |1 |0 |0 |1 |0 |x | |Beq |x |0 |1 |0 |1 |0 |0 |0
|x | |
[pic]


Performances

Performances des pipelines avec suspension
Les aléas empêchent l'instruction suivante du flux d'instruction de
s'exécuter au cycle d'horloge prévu :
Les aléas sont :
Les aléas structurels interviennent lors de conflits de ressources, quand
le matériel ne peut gérer toutes les combinaisons possibles de recouvrement
d'instructions au moment de l'exécution.
Les aléas de données interviennent quand une instruction dépend du résultat
d'une instruction précédente.
Les aléas de contrôle résultent de l'exécution en pipeline des branchements
et des autres instructions qui modifient le CP.
On a [pic]

1 Exercice

Ragardons combien peut coûter l'aléa structurel de chargement. Supposons
que les références données constituent 40% des instruction, et que le CPI
idéal de la machine pipelinée est de 1 en ignorant l'aléa structurel. On
suppose que la machine avec aléa structurel a une fréquence d'horloge qui
est 1,05 fois plus élevée que celle de la machine sans aléa. Sans
considérer d'autres dégradations de performance, quel pipeline, avec ou
sans al éa structurel, est le plus rapide, et de combien ?
Il y a plusieurs manière de resoudre ce problème. Le plus simple est peut
être de calculer le temps moyen d'une instruction sur les deux machines :
D'abord, calculons l'accélération du pipeline pour chaque machine en
utilisant la formule :
[pic]
Puisqu'il n'y a pas de suspensions, le temps moyen d'une instruction pour
la machine idéale est simplement le temps de cycle idéal. Le temps moyen
d'une instruction pour la machine avec aléas structurel est :
[pic]
La machine sans aléa structurel est de manière évidente plus rapide. On
peut utiliser le rapport des temps moyens d'exécution d'une instruction
pour dire qu'elle est de 1,33 fois plus rapide.
Pour éviter cet aléa structurel, le concepteur peut fournir un accès
mémoire séparé pour les instructions, soit en divisant le cache en caches
séparés pour les instructions et données.

2 Exercice

Supposons que 30% des instructions soient des chargements, et qu'une fois
sur deux, une instruction qui suit une instruction de chargement dépende du
résultat du chargement. Si cet aléa crée un délai d'un seul cycle, de
combien la machine pipelinée idéale (avec un CPI de 1), qui n'ajoute pas de
délai au pipeline, est-elle plus rapide que celle avec un pipeline réel ?
Ignorer toutes les suspensions autres que celles du pipeline.

La machine idéale est plus rapide du rapport des CPI. Le CPI pour les
instructions qui suivent un chargement est de 1,5, car elles sont
suspendues une fois sur deux. Parce que les chargements représentent 30%
des instructions, le CPI effectif est (0,7*1+0,3*1,5). La machine idéale
est donc 1,15 fois plus rapide.

Les aléas de données


1 exercice


Considérons l'exécution pipelinée de ces instructions :

add r1,r2,r2
sub r4,r1,r5
and r6,r1,r7
or r8,r1,r9
xor r10,r1,r11

indiquer le nombre d'aléas de données.

2 exercice

même exercice avec :
add r1,r2,r2
sub r4,r3,r5
and r6,r1,r7
or r8,r1,r4
xor r10,r1,r11

3 Exercice

Pour la séquence d'instructions des exercices précédents indiquer les
chemins d'envois et le nombre restant à traiter.
Tous les aléas ont disparus



add r1,r2,r2 |MI |DI |EX |M |ER | | | | | | | | |sub r4,r1,r5 | |MI |DI
|nop |nop |nop |EX |M |ER | | | | |and r6,r1,r7 | | |MI |nop |nop |nop |DI
|EX |M |ER | | | |or r8,r1,r9 | | | |nop |nop |nop |MI |DI |EX |M |ER | |
|xor r10,r1,r11 | | | | | | | |MI |DI |EX |M |ER | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | |add r1,r2,r2 |MI |DI |EX |M |ER | | | | |
| | | |sub r4,r1,r5 | |MI |DI |EX |M |ER | | | | | | | |and r6,r1,r7 | |
|MI |DI |EX |M |ER | | | | | | |or r8,r1,r9 | | | |MI |DI |EX |M |ER | | |
| | |xor r10,r1,r11 | | | | |MI |DI |EX |M |ER | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | |add r1,r2,r2 |MI |DI |EX |M |ER | | |
| | | | | |sub r4,r3,r5 | |MI |DI |EX |M |ER | | | | | | | |and r6,r1,r7 |
| |MI |DI |nop |nop |EX |M |ER | | | | |or r8,r1,r4 | | | |MI |nop |nop |DI
|EX |M |ER | | | |xor r10,r1,r11 | | | | | |nop |MI |DI |EX |M |ER | | | |
| | | | | | | | | | | | |add r1,r2,r2 |MI |DI |EX |M |ER | | | | | | | |
|sub r4,r3,r5 | |MI |DI |EX |M |ER | | | | | | | |and r6,r1,r7 | | |MI |DI
|EX |M |ER | | | | | | |or r8,r1,r4 | | | |MI |DI |EX |M |ER | | | | | |xor
r10,r1,r11 | | | | |MI |DI |EX |M |ER | | | | |

4 Exercice

Mêmes questions que l'exercice 5.3 pour la séquence suivante
add r1,r2,r3
lw r4,0(r1)
sw 12(r1),r4

add r1,r2,r3 |MI |DI |EX |M |ER | | | | | | | |lw r4,0(r1) | |MI |DI |nop
|nop |nop |EX |M |ER | | | |sw 12(r1),r4 | | |MI |nop |nop |nop |nop |nop
|nop |DI |EX | | | | | | | | | | | | | | |add r1,r2,r3 |MI |DI |EX |M |ER |
| | | | | | |lw r4,0(r1) | |MI |DI |EX |M |ER | | | | | | |sw 12(r1),r4 | |
|MI |DI |EX |M |ER | | | | | |

Tous les aléas ont disparus


5 Exercice

Même questions que l'exercice précédent pour la séquence :
lw r1,0(r2)
sub r4,r1,r5
and r6,r1,r7
or r8,r1,r9
lw r1,0(r2) |MI |DI |EX |M |ER | | | | | | | |sub r4,r1,r5 | |MI |DI |nop
|nop |nop |EX |M |ER | | | |and r6,r1,r7 | | |MI |nop |nop |nop |DI |EX |M
|ER | | |or r8,r1,r9 | | | |nop |nop |nop |MI |DI |EX |M |ER | | | | | | |
| | | | | | | |lw r1,0(r2) |MI |DI |EX |M |ER | | | | | | | |sub r4,r1,r5 |
|MI |DI |nop |EX |M |ER | | | | | |and r6,r1,r7 | | |MI |nop |DI |EX |M |ER
| | | | |or r8,r1,r9 | | | |nop |MI |DI |EX |M |ER | | | | | | | | | | | |
| | | | |
L'instruction de chargement peut envoi son résultat aux instructions and et
or, mais pas à sub, puisque cela impliquerait d'envoyer le résultat "en
remontant dans le temps ».


L'ordonnancement du compil