Changes between Initial Version and Version 1 of TracRevision

Timestamp:

Oct 19, 2020, 1:30:40 PM (4 years ago)

Author:

meunier

Comment:

--

TracRevision

@@ +1 @@
+
+= 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.
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q1.svg)]]
+
+'''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).
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q2.svg)]]
+
+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 :'''''
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q3.svg)]]
+
+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 :'''''
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q5.svg)]]
+
+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.
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q6_a.svg)]]
+
+Le schéma détaillé correspond à l'exécution de 2 instructions d'addition.
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q6_b.svg)]]
+
+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).
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q7.svg)]]
+
+
+
+= Exercice 8 : =
+
+Analyser l’exécution de la suite d’instructions suivante dans le processeur Mips-32 à l’aide d’un schéma simplifié.
+{{{
+#!asm
+    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.
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q8_a.svg)]]
+
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q8_b.svg)]]
+
+
+
+    
+= 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).
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q9_a.svg)]]
+
+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`.
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q9_b.svg)]]
+
+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`.
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q9_c.svg)]]
+
+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).
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q9_d.svg)]]
+
+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 :
+{{{
+#!c
+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 :
+{{{
+#!asm
+_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 :
+{{{
+#!asm
+_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 :
+{{{
+#!asm
+_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 :
+{{{
+#!asm
+_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 :
+{{{
+#!asm
+_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 :
+{{{
+#!asm
+_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 :
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q10_1_a.svg)]]
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q10_1_b.svg)]]
+
+2ème version :
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q10_2_a.svg)]]
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q10_2_b.svg)]]
+
+3ème version :
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q10_3_a.svg)]]
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q10_3_b.svg)]]
+
+    
+
+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 :
+{{{
+#!c
+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:
+{{{
+#!asm
+_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.
+
+{{{
+#!asm
+__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.
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q11_a.svg)]]
+
+Cas où le `if` réussit :
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q11_b.svg)]]
+
+Cas où le `if` échoue :
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q11_c.svg)]]
+
+
+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 :
+{{{
+#!c
+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:
+{{{
+#!asm
+_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.
+{{{
+#!asm
+_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 :'''''
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q12_a.svg)]]
+
+Cas où le `if` réussit :
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q12_b.svg)]]
+
+Cas où le `if` échoue :
+
+[[Image(htdocs:/corrige/Seance3/S3_corrige_Q12_c.svg)]]
+
+
+
+
+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
+
+