| Version 1 (modified by , 6 years ago) ( diff ) |
|---|
M1 SESI – Architecture des Processeurs et Optimisation
TD2 – Pipeline MIPS
Ce TD se focalise sur les points suivants :
- Le schéma d'exécution des instructions dans la réalisation pipeline du Mips
- La dépendance de données dans le pipeline
- Le problème des branchements dans le pipeline
- Évaluation du nombre cycles nécessaires pour l'exécution d'un code, CPI, CPI-utile
Exercice 1 :
Montrer à l'aide d'un schéma détaillé l'exécution de l'instruction SLLV rd, rt, rs (Shift Left Logic Variable) dans le pipeline du Mips-32.
Solution 1 :
Le schéma détaillé présente l'évolution de l'instruction à chaque étage du pipeline (représentation utilisée en cours). L'axe horizontal est l'axe du temps découpé en cycles d'horloge (chaque trait vertical représente un front montant d'horloge). On ne représente que les ressources matérielles (registres, signaux, parties combinatoires) qui interviennent dans l'exécution de l'instruction et qui présentent un intérêt pour la compréhension de l'exécution.
Remarque importante : Sur une même ligne, on représente l'évolution d'un matériel donné au cours du temps. Ainsi, il faut réserver une ligne pour chaque registre représenté. Il ne faut pas faire figurer sur une même ligne deux registres différents.
Chaque ressource matérielle appartient à un cycle du pipeline (le cycle dans lequel elle est modifiée). Elle porte un nom suffixé par une lettre qui indique le cycle du pipeline auquel elle appartient. Par exemple, le registre qui reçoit l'instruction lue depuis la mémoire s'appelle I_RI : les deux lettres du suffixe indiquent qu'il s'agit d'un registre (R) et qu'il appartient au cycle IFC (la dernière lettre I).
Exercice 2 :
Montrer à l’aide d’un schéma détaillé l’exécution de l’instruction BLTZAL rs, label (Branch if Less Than Zero And Link) dans le pipeline du Mips-32.
Solution 2 :
Il s'agit d'une instruction de branchement conditionnel à un sous-programme. L'adresse de retour est sauvegardée dans le registre R31. Il faut noter que la sauvegarde s'effectue dans tous les cas (que le branchement réussisse ou non).
L'adresse de retour est l'adresse de l'instruction de branchement + 8 (à cause du delayed slot qui s'exécute avant l'exécution de l'instruction cible du branchement).
On utilise deux additionneurs pour accélérer le calcul de l'adresse. On calcule les deux adresses possibles et on choisit après en fonction du résultat de la condition de branchement. L'adresse de branchement est
@_de_l'instruction_de_branchement + 4 + Imd * 4
Il faut remarquer que, dans ce calcul, le + 4 a déjà été effectué par l'instruction qui précède le branchement.
Exercice 3 :
On considère une nouvelle instruction de branchement conditionnel : l'instruction BEQPI (Branch if equal and post increment).
Beqpi rs, rt, Label
Il s'agit d'une instruction de format I. Cette instruction réalise l'opération suivante. Comme pour BEQ, le contenu de RS est comparé au contenu de RT. En cas d'égalité, on se branche à l'instruction portant l'étiquette Label, sinon le branchement échoue et on continue en séquence. De plus, une fois le test effectué, le contenu de RT est incrémenté.
Le schéma d'exécution du pipeline du Mips convient-il à l'exécution de cette instruction ? Si oui, proposer un schéma détaillé montrant l'exécution de cette instruction. Si non, expliquer pourquoi.
Solution 3 :
Cette instruction peut être exécutée dans le pipeline du Mips puisque l'incrémentation de RT s'effectue après l'évaluation de la condition de branchement. Cette incrémentation peut être prise en charge par le cycle EXE. Puis, la mise à jour de RT s'effectue naturellement dans le cycle WBK en sélectionnant RT comme registre destinataire.
Exercice 4 :
On considère une nouvelle instruction de branchement conditionnel : l'instruction BEQPD (Branch if equal and pre-decrement).
Beqpd rs, rt, Label
Il s'agit d'une instruction de format I. Cette instruction réalise l'opération suivante. Comme pour BEQ, le contenu de RS est comparé au contenu de RT. En cas d'égalité, on se branche à l'instruction portant l'étiquette Label, sinon le branchement échoue et on continue en séquence. En plus, avant d'effectuer le test, le contenu de RT est decrémenté.
Le schéma d'exécution du pipeline du Mips convient-il à l'exécution de cette instruction ? Si oui, proposer un schéma détaillé montrant l'exécution de cette instruction. Si non, expliquer pourquoi.
Solution 4 :
Cette instruction ne peut pas être exécutée dans le pipeline du Mips. En effet, avant d'évaluer la condition de branchement, il faut décrémenter RT. Cette action doit donc s'effectuer dans le cycle DEC puisque c'est dans ce cycle que s'effectue le calcul de l'adresse cible du branchement. Or, il est clair que l'ensemble de ces opérations (lecture des opérandes, décrémentation de RT puis, évaluation de la condition de branchement) nécessite un temps bien supérieur au temps de cycle si l'on considère comme référence pour la période d'horloge, le temps nécessaire à l'exécution de l'étage EXE (un calcul - typiquement une addition - et un multiplexeur pour sélectionner le résultat parmi tous les résultats calculés par les différents opérateurs). Ainsi, l'exécution de cette instruction dans le pipeline du MIPS aboutirait à un pipeline fortement déséquilibré ce qui est contraire aux règles de conception des pipelines.
Exercice 5 :
Montrer à l’aide d’un schéma détaillé l’exécution de la suite d’instructions suivante dans le pipeline du Mips-32.
Add r3 , r2 , r1
Add r3 , r3 , r1
Quelle est la condition du déclenchement des bypass ?
Solution 5 :
On remarque une dépendance de données entre ces deux instructions (sur RS). Cette dépendance est résolue grâce à un bypass entre la sortie de l'étage EXE de la première instruction et le début de l'étage EXE de la seconde.
Le multiplexeur qui se trouve avant l'additionneur est le bypass. Il se déclenche lorsque le numéro du registre RS de l'instruction courante (I_RD) est identique au numéro du registre RD de l'instruction précédente (I_RE).
Exercice 6 :
Montrer à l’aide d’un schéma détaillé l’exécution de la suite d’instructions suivante dans le pipeline du Mips-32.
Add r0 , r2 , r1
Add r3 , r0 , r1
Donner l'expression exacte de la condition du déclenchement des bypass ?
Solution 6 :
A première vue on pourrait penser qu'il y a une dépendance de données entre ces deux instructions. Cependant, ce n'est pas le cas car la première instruction écrit dans le registre R0 (en fait, cette instruction ne fait rien). Autrement dit, il ne faut pas activer le bypass. Le schéma simplifié est le suivant.
Le schéma détaillé correspond à l'exécution de 2 instructions d'addition.
On peut donc dire que le bypass se déclenche si le numéro du registre RS de l'instruction courante (I_RD) est identique au numéro du registre RD de l'instruction précédente (I_RE) et qu'il ne s'agit pas du numéro 0. Il faut ajouter à cette condition : il faut que l'instruction précédente écrive dans le registre RD et que l'instruction courante ait besoin du registre RS.
Exercice 7 :
Montrer à l’aide d’un schéma détaillé l’exécution de la suite d’instructions suivante dans le pipeline du Mips-32.
Lw r3 , 0 (r2)
Add r3 , r3 , r1
Solution 7 :
Il y a une dépendance de données entre ces deux instructions qui provoque un cycle de gel (stall).
Exercice 8 :
Analyser l’exécution de la suite d’instructions suivante dans le processeur Mips-32 à l’aide d’un schéma simplifié.
Addiu r2 , r0 , 4
Lui r3 , 0x000c
Add r2 , r2 , r2
Ori r3 , r3 , 0x4568
Lw r2 , 0(r3)
Lbu r2 , 0(r2)
Ori r2 , r2 , 0x0001
Bltzal r2 , suite
Addu r0 , r0 , r0
suite:
Jr r31
Addu r31, r31, -8
Solution 8 :
Le schéma suivant montre les dépendances de données dans ce code.
Exercice 9 :
La réalisation du processeur Mips-32 nécessite la mise en œuvre de 8 bypass (raccourcis). Pour chacun de ces bypass, proposer un exemple de suite d'instructions qui illustre la nécessité de ce bypass.
Solution 9 :
Il existe deux bypass (un sur RS et un sur RT) entre la sortie de l'étage EXE et le début de l'étage EXE. Ces bypass résolvent les dépendances de données d'ordre 1 (entre une instruction et l'instruction qui la précède).
Exemple (bypass sur RS) :
Add r3 , r2 , r1
Add r3 , r3 , r4
Exemple (bypass sur RT) :
Add r3 , r2 , r1
Add r3 , r4 , r3
Il existe deux bypass (un sur RS et un sur RT) entre la sortie de l'étage EXE et le début de l'étage DEC. Ces bypass résolvent les dépendances de données d'ordre 2 (entre une instruction et la deuxième instruction qui la précède). Ces bypass sont nécessaires lorsque l'opérande (RS ou RT) est consommé dans le cycle DEC.
Exemple (bypass sur RS) :
Add r3 , r2 , r1
... (une instruction quelconque)
Beq r3 , r4 , Suite
Exemple (bypass sur RT) :
Add r3 , r2 , r1
... (une instruction quelconque)
Beq r4 , r3 , Suite
Il existe deux bypass (un sur RS et un sur RT) entre la sortie de l'étage MEM et le début de l'étage EXE. Ces bypass résolvent les dépendances de données d'ordre 2 (entre une instruction et la deuxième instruction qui la précède). Ces bypass sont nécessaires lorsque l'opérande (RS ou RT) est produit par le cycle MEM.
Exemple (bypass sur RS) :
Lw r3 , 0 (r2)
... (une instruction quelconque)
Add r5 , r3 , r4
Exemple (bypass sur RT) :
Lw r3 , 0 (r2)
... (une instruction quelconque)
Add r5 , r4 , r3
Il existe deux bypass (un sur RS et un sur RT) entre la sortie de l'étage MEM et le début de l'étage DEC. Ces bypass résolvent les dépendances de données d'ordre 3 (entre une instruction et la troisième instruction qui la précède).
Exemple (bypass sur RS) :
Add r3 , r2 , r1
... (une instruction quelconque)
... (une instruction quelconque)
Add r5 , r3 , r4
Exemple (bypass sur RT) :
Add r3 , r2 , r1
... (une instruction quelconque)
... (une instruction quelconque)
Add r5 , r4 , r3
Exercice 10 :
La fonction strlen calcule le nombre de caractères :
unsigned int strlen (char * str) {
unsigned int i = 0;
while (str [i] != '\0') {
i++;
}
return (i);
}
Différents codes assembleur peuvent être produits pour cette fonction pour un processeur non-pipeline :
1ère version :
_strlen:
Addiu r29, r29, -1*4
Addu r2, r0 , r0 ; initialisation
_strlen_loop:
Lb r9 , 0(r4) ; lire 1 caractere
Beq r9 , r0 , _strlen_end_loop ; fin de chaine ?
Addiu r4 , r4 , 1 ; caractere suivant
Addiu r2 , r2 , 1 ; caractere suivant
J _strlen_loop ; boucle
_strlen_end_loop:
Addiu r29, r29, 1*4
Jr r31
2ème version :
_strlen:
Addiu r29, r29, -1*4
Addiu r2, r0 , -1 ; initialisation
_strlen_loop:
Lb r9 , 0(r4) ; lire 1 caractere
Addiu r4 , r4 , 1 ; caractere suivant
Addiu r2 , r2 , 1 ; caractere suivant
Bne r9 , r0 , _strlen_loop ; fin de chaine ?
Addiu r29, r29, 1*4
Jr r31
3ème version :
_strlen:
Addiu r29, r29, -1*4
Addiu r8, r4 , 1 ; sauvegarde adresse debut
_strlen_loop:
Lb r9 , 0(r4) ; lire 1 caractere (octet)
Addiu r4 , r4 , 1 ; caractere suivant
Bne r9 , r0 , _strlen_loop ; fin de chaine ?
Subu r2 , r4 , r8 ; calculer nbr de carac
Addiu r29, r29, 1*4
Jr r31
Pour chacune des trois versions, transformer le code de telle façon qu'il puisse être exécuté sur le processeur Mips pipeline à 5 étages.
Solution 10 :
Dans le processeur Mips, l'instruction qui suit un branchement est exécutée dans tous les cas. Pour tenir compte de cette particularité, sans perturber le code généré par le compilateur, il suffit d'ajouter une instruction NOP après chaque branchement.
1ère version :
_strlen:
Addiu r29, r29, -1*4
Addu r2, r0 , r0 ; initialisation
_strlen_loop:
Lb r9 , 0(r4) ; lire 1 caractere
Beq r9 , r0 , _strlen_end_loop ; fin de chaine ?
Nop
Addiu r4 , r4 , 1 ; caractere suivant
Addiu r2 , r2 , 1 ; caractere suivant
J _strlen_loop ; boucle
Nop
Addiu r29, r29, 1*4
Jr r31
Nop
2ème version :
_strlen:
Addiu r29, r29, -1*4
Addiu r2, r0 , -1 ; initialisation
_strlen_loop:
Lb r9 , 0(r4) ; lire 1 caractere
Addiu r4 , r4 , 1 ; caractere suivant
Addiu r2 , r2 , 1 ; caractere suivant
Bne r9 , r0 , _strlen_loop ; fin de chaine ?
Nop
Addiu r29, r29, 1*4
Jr r31
Nop
3ème version :
_strlen:
Addiu r29, r29, -1*4
Addiu r8, r4 , 1 ; sauvegarde adresse debut
_strlen_loop:
Lb r9 , 0(r4) ; lire 1 caractere (octet)
Addiu r4 , r4 , 1 ; caractere suivant
Bne r9 , r0 , _strlen_loop ; fin de chaine ?
Nop
Subu r2 , r4 , r8 ; calculer nbr de carac
Addiu r29, r29, 1*4
Jr r31
Nop
Analyser l'exécution de la boucle sur le processeur Mips à l'aide d'un schéma simplifié.
Solution 10 :
1ère version :
2ème version :
3ème version :
Calculer le nombre de cycles nécessaires à l'exécution d'une itération de la boucle.
Solution 10 :
- 1ère version : 9 cycles par itération
- 2ème version : 5 cycles par itération
- 3ème version : 5 cycles par itération
Calculer le CPI et le CPI-utile de la boucle.
Solution 10 :
- 1ère version : CPI = 9/7 cycles/inst -- CPI-utile = 9/5 cycles/inst
- 2ème version : CPI = 5/5 cycles/inst -- CPI-utile = 5/4 cycles/inst
- 3ème version : CPI = 5/4 cycles/inst -- CPI-utile = 5/3 cycles/inst
Exercice 11 :
La fonction strupper transforme une chaîne de caractères en majuscules :
char * strupper (char * src) {
int i = 0;
while (src[i] != '\0') {
if ((src[i] >= 'a') && (src[i] <= 'z')) {
src[i] = src[i] - 'a' + 'A'
}
i++;
}
return src;
}
La compilation de cette fonction pour un processeur non-pipeline a produit le code suivant:
_strupper:
Addiu r29, r29, -1*4
Addu r2 , r0 , r4 ; valeur de retour
Addiu r11, r0 , 'a' ; pour la comparaison
Addiu r12, r0 , 'z' ; pour la comparaison
_strupper_loop:
Lb r8 , 0(r4) ; lire src[i]
Slt r9 , r8 , r11 ; src[i] < 'a'
Slt r10, r12, r8 ; 'z' < src[i]
Or r10, r10, r9 ; et des 2 conditions
Bne r10, r0 , _strupper_endif ; si 1 des 2 cond vraie
Addiu r8 , r8 , 'A'-'a'; transformer en majuscule
Sb r8 , 0(r4)
_strupper_endif:
Addiu r4 , r4 , 1 ; caractère suivant
Bne r8 , r0 , _strupper_loop
Addiu r29, r29, 1*4
Jr r31
Transformer ce code de telle façon qu'il puisse être exécuté sur le processeur Mips pipeline à 5 étages.
Solution 11 :
Dans le processeur Mips, l'instruction qui suit un branchement est exécutée dans tous les cas. Pour tenir compte de cette particularité, sans perturber le code généré par le compilateur, il suffit d'ajouter une instruction NOP après chaque branchement.
__strupper:
Addiu r29, r29, -1*4
Addu r2 , r0 , r4 ; valeur de retour
Addiu r11, r0 , 'a' ; pour la comparaison
Addiu r12, r0 , 'z' ; pour la comparaison
_strupper_loop:
Lb r8 , 0(r4) ; lire src[i]
Slt r9 , r8 , r11 ; src[i] < 'a'
Slt r10, r12, r8 ; 'z' < src[i]
Or r10, r10, r9 ; et des 2 conditions
Bne r10, r0 , _strupper_endif ; si 1 des 2 cond vraie
Nop
Addiu r8 , r8 , 'A'-'a'; transformer en majuscule
Sb r8 , 0(r4)
_strupper_endif:
Addiu r4 , r4 , 1 ; caractère suivant
Bne r8 , r0 , _strupper_loop
Nop
Addiu r29, r29, 1*4
Jr r31
Nop
Analyser l'exécution de la boucle sur le processeur Mips à l'aide d'un schéma simplifié dans le cas où le if (du code source) réussit, puis dans le cas où le if échoue.
Solution 11 :
Attention, il y a une dépendance entre le dernier Addiu et le Lb de l'itération suivante.
Cas où le if réussit :
Cas où le if échoue :
Calculer le nombre de cycles nécessaires à l'exécution d'une itération de la boucle dans le cas ou le if réussit.
Solution 11 :
Il faut 13 cycles pour une itération si le if réussit
Calculer le nombre de cycles nécessaires à l'exécution d'une itération de la boucle dans le cas ou le if échoue.
Solution 11 :
Il faut 11 cycles pour une itération si le if échoue.
Sachant que 30% des caractères sont minuscules calculer le CPI et le CPI-utile de la boucle.
Solution 11 :
CPI = 1.208 cycle/instruction
CPI_utile = 1.526 cycle/instruction utile
Exercice 12 :
La fonction suivante calcule le PGCD de deux nombres positifs non nuls :
unsigned int pgcd (unsigned int a, unsigned int b) {
while (a != b) {
if (a < b) {
b = b - a;
}
else {
a = a - b;
}
}
return a;
}
La compilation de cette fonction pour un processeur non-pipeline a produit le code suivant:
_pgcd:
Beq r4 , r5 , _pgcd_end
_pgcd_loop:
Sltu r8 , r4 , r5 ; a < b
Beq r8 , r0 , _pgcd_else
Subu r5 , r5 , r4
J _pgcd_endif
_pgcd_else:
Subu r4 , r4 , r5
_pgcd_endif:
Bne r4 , r5 , _pgcd_loop
_pgcd_end:
Add r2 , r4 , r0 ; valeur de retour
Jr r31
Transformer ce code de telle façon qu'il puisse être exécuté sur le processeur Mips pipeline à 5 étages.
Solution 12 :
Il suffit d'ajouter une instruction NOP après chaque branchement.
_pgcd:
Beq r4 , r5 , _pgcd_end
Nop
_pgcd_loop:
Sltu r8 , r4 , r5 ; a < b
Beq r8 , r0 , _pgcd_else
Nop
Subu r5 , r5 , r4
J _pgcd_endif
Nop
_pgcd_else:
Subu r4 , r4 , r5
_pgcd_endif:
Bne r4 , r5 , _pgcd_loop
Nop
_pgcd_end:
Add r2 , r4 , r0 ; valeur de retour
Jr r31
Nop
Analyser l'exécution de la boucle sur le processeur Mips à l'aide d'un schéma simplifié, dans le cas où le if (du code source) réussit, puis dans le cas où le if échoue.
Solution 12 :
Cas où le if réussit :
Cas où le if échoue :
Calculer le nombre de cycles nécessaires à l'exécution d'une itération de la boucle dans le cas ou le if réussit.
Solution 12 :
Il faut 9 cycles pour une itération si le if réussit.
Calculer le nombre de cycles nécessaires à l'exécution d'une itération de la boucle dans le cas ou le if échoue.
Solution 12 :
Il faut 8 cycles pour une itération si le if échoue.
Sachant que dans un cas sur deux le if échoue, calculer le CPI et le CPI-utile de la boucle.
Solution 12 :
CPI = 1.214 cycle/instrution
CPI_utile = 1.889 cycle/instrution utile
