| Version 1 (modified by , 4 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
