Changes between Version 1 and Version 2 of TracRevision


Ignore:
Timestamp:
Nov 2, 2020, 4:09:36 PM (4 years ago)
Author:
meunier
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • TracRevision

    v1 v2  
    22= M1 SESI – Architecture des Processeurs et Optimisation =
    33
    4 = TD2 – Pipeline MIPS =
    5 
    6 Ce TD se focalise sur les points suivants :
    7 * Le schéma d'exécution des instructions dans la réalisation pipeline du Mips
    8 * La dépendance de données dans le pipeline
    9 * Le problème des branchements dans le pipeline
    10 * Évaluation du nombre cycles nécessaires pour l'exécution d'un code, CPI, CPI-utile
    11 
     4= TD3 – Pipeline, Superpipeline, Optimisation de codes =
    125
    136= Exercice 1 : =
    147
    15 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.
     8La fonction `GetListLength` calcule le nombre d'éléments d'une liste. Un élément d'une liste est une structure de donnée appelée `chain`. Une structure `chain` est composée de deux pointeurs (un pointeur est un mot de 4 octets qui contient l'adresse d'un autre objet). Le premier pointeur donne l'adresse de la structure `chain` suivante. Le deuxième pointeur donne l'adresse de la donnée.
     9{{{
     10#!c
     11struct chain {
     12    struct chain * NEXT;
     13    void * DATA;
     14};
     15
     16int GetListLength (struct chain * pt) {
     17    int i = 0;
     18    while (pt != NULL) {
     19        i++;
     20        pt = pt->NEXT;
     21    }
     22    return i;
     23}
     24}}}
     25
     26Ecrire en assembleur Mips-32 la boucle principale de `GetListLength`. On suppose que `R4` contient l'adresse de la liste (pt).
     27
     28Analyser l'exécution de la boucle à l'aide d'un schéma simplifié.
    1629
    1730
    1831'''''Solution 1 :'''''
    19 
    20 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.
    21 
    22 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q1.svg)]]
    23 
    24 '''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.
    25 
    26 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).
     32{{{
     33#!asm
     34Loop :
     35    Lw    r4 , 0 (r4)
     36    Bne   r4 , r0 , loop
     37    Addi  r2 , r2 , 1
     38}}}
     39
     40[[Image(htdocs:/corrige/Seance4/S4_corrige_Q1.svg)]]
     41
     42
    2743
    2844= Exercice 2 : =
    2945
    30 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.
    31 
    32 
    33 '''''Solution 2 :'''''
    34 
    35 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).
    36 
    37 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q2.svg)]]
    38 
    39 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).
    40 
    41 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
    42 
    43 {{{
    44     @_de_l'instruction_de_branchement + 4 + Imd * 4
    45 }}}
    46 
    47 Il faut remarquer que, dans ce calcul, le + 4 a déjà été effectué par l'instruction qui précède le branchement.
     46On considère un programme de traitement d'images. Une image est composée d'un ensemble de pixels organisés sous forme d'un tableau. Pour une image en 'niveaux de gris', chaque pixel est codé sur un octet. La valeur 0 représente la couleur noire, la valeur 255 la couleur blanche. Les valeurs comprises entre 0 et 255 représentent les différentes nuances de gris. Une fonction de traitement d'images consiste à appliquer un certain algorithme à un tableau de pixels. On considère le programme suivant.
     47{{{
     48#!asm
     49loop:
     50    Lbu   r8 , 0(r4)        ; lire un pixel
     51    Addu  r8 , r8 , r5
     52    Lbu   r9 , 0(r8)        ; lire f(pixel)
     53    Sb    r9 , 0(r4)
     54
     55    Addiu r4 , r4 , 1
     56    Bne   r4 , r10, loop
     57}}}
     58
     59À l'entrée de la boucle, le registre `R4` contient l'adresse du tableau de pixels (l'image à traiter). Le registre `R10` contient l'adresse de la fin de l'image. Le registre `R5` contient l'adresse d'un tableau F de 256 octets. Ce tableau représente une fonction `f(x)` avec `0 <= x <= 255` et `0 <= f(x) <= 255`. Ce programme permet d'appliquer la fonction `f(x)` à chaque pixel de l'image. Si `x` est la valeur d'un pixel, celle-ci est remplacée par `f(x)`.
     60Par exemple, si `f(x) = 255 - x`, l'application de ce programme à une image permet d'obtenir l'image négative.
     61
     62''a - Modifier le programme pour qu'il soit exécutable sur le Mips-32.''
     63
     64
     65'''''Solution 2-a :'''''
     66
     67Il faut un delayed slot après chaque branchement
     68{{{
     69#!asm
     70loop:
     71    Lbu   r8 , 0(r4)        ; lire un pixel
     72    Addu  r8 , r8 , r5
     73    Lbu   r9 , 0(r8)        ; lire f(pixel)
     74    Sb    r9 , 0(r4)
     75
     76    Addiu r4 , r4 , 1
     77    Bne   r4 , r10, loop
     78    Nop
     79}}}
     80
     81
     82''b - Analyser, à l'aide d'un schéma simplifié, l'exécution de ce programme dans le Mips. Calculer le nombre de cycles pour effectuer une itération.''
     83
     84
     85'''''Solution 2-b :'''''
     86
     87[[Image(htdocs:/corrige/Seance4/S4_corrige_Q2_b_1.svg)]]
     88
     89[[Image(htdocs:/corrige/Seance4/S4_corrige_Q2_b_2.svg)]]
     90
     91
     92Il faut 10 cycles par itération soit :
     93CPI = 10/7 cycles/inst -- CPI-utile = 10/6 cycles/inst
     94
     95
     96''c - Optimiser le code en changeant l'ordre des instructions de manière à obtenir un CPI et un CPI-utile de 1''
     97
     98
     99'''''Solution 2-c :'''''
     100
     101Au total, il y a 4 cycles perdus :
     102 * 1 cycle de gel entre le premier `Lbu` et le `Addu`
     103 * 1 cycle de gel entre le second `Lbu` et le `Sb`
     104 * 1 cycle de gel entre le `Addiu` et le `Bne`
     105 * 1 cycle de `Nop`
     106
     107
     108Par ailleurs, les 4 premières instructions sont dépendantes et on ne peut pas modifier leur ordre. Les deux dernières instructions sont dépendantes. L'idée est de remonter le `Addiu` après le premier `Lbu` et de descendre le `Sb` à la place du delayed slot.
     109
     110{{{
     111#!asm
     112loop:
     113    Lbu   r8 ,  0(r4)        ; lire un pixel
     114    Addiu r4 , r4 , 1
     115    Addu  r8 , r8 , r5
     116    Lbu   r9 ,  0(r8)        ; lire f(pixel)
     117
     118    Bne   r4 , r10, loop
     119    Sb    r9 , -1(r4)
     120}}}
     121
     122Il faut 6 cycles par itération soit CPI = CPI-utile = 1 cycle/inst
     123
     124
     125''d - Optimiser le code en utilisant la technique du "pipeline logiciel". Calculer le nombre de cycles par itération.''
     126
     127
     128'''''Solution 2-d :'''''
     129
     130On peut décomposer le traitement d'un pixel en trois étapes : lecture du pixel (le premier `Lbu`), calcul de la valeur de la fonction (`Addu` et le second `Lbu`), sauvegarde du pixel (`Sb`).
     131
     132A chaque itération de la boucle, l'idée est de traiter trois pixels : pour le pixel `i`, on fait la lecture, pour le pixel `i-1` on fait le calcul et pour le pixel `i-2` on sauvegarde.
     133{{{
     134#!asm
     135loop:
     136    Sb    r11, -2(r4)        ; sauvegarde de pixel i-2
     137    Addu  r9 , r8 , r5
     138    Lbu   r11,  0(r9)        ; lire f(pixel i-1)
     139    Lbu   r8 ,  0(r4)        ; lire le pixel i
     140
     141    Addiu r4 , r4 , 1
     142    Bne   r4 , r10, loop
     143    Nop
     144}}}
     145
     146Maintenant, on peut réordonner ce code pour éviter les cycles perdus. Il faut déplacer le dernier `Lbu` dans le delayed slot et remonter le `Addiu` avant le premier `Lbu`.
     147{{{
     148#!asm
     149loop:
     150    Sb    r11, -2(r4)        ; sauvegarde de pixel i-2
     151    Addu  r9 , r8 , r5
     152    Addiu r4 , r4 , 1
     153    Lbu   r11,  0(r9)        ; lire f(pixel i-1)
     154
     155    Bne   r4 , r10, loop
     156    Lbu   r8, -1(r4)        ; lire le pixel i
     157}}}
     158
     159Il faut 6 cycles par itération soit CPI = CPI-utile = 1 cycle/inst.
     160
    48161
    49162
    50163= Exercice 3 : =
    51164
    52 On considère une nouvelle instruction de branchement conditionnel : l'instruction `BEQPI` (Branch if equal and post increment).
    53 {{{
    54     Beqpi    rs, rt, Label
    55 }}}
    56 
    57 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é.
    58 
    59 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.
    60 
    61 
    62 '''''Solution 3 :'''''
    63 
    64 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q3.svg)]]
    65 
    66 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.
     165On considère un processeur RISC pipeline, appelé '''PROC'''. '''PROC''' a le même jeu d'instructions que le Mips-32. PROC a un pipeline à 7 étages : `IF1`, `IF2`, `DEC`, `EXE`, `MM1`, `MM2`, `WBK`.
     166
     167Au début de l'étage '''`IF1`''', l'adresse de l'instruction est envoyée à la mémoire et l'instruction correspondante est récupérée à la fin du cycle '''`IF2`'''. De la même manière, l'accès à la mémoire de données se déroule en deux cycles. Comme dans Mips-32, le calcul de l'adresse d'instruction s'effectue dans '''`DEC`'''. De même, les étages '''`EXE`''' et '''`WBK`''' ressemblent aux étages '''`EXE`''' et '''`WBK`''' du Mips.
     168
     169''a - Montrer, à l'aide d'un schéma détaillé, l'exécution de l'instruction '''`SW`''' dans '''PROC'''.''
     170
     171
     172'''''Solution 3-a :'''''
     173
     174Dans PROC les accès mémoire se font en deux cycles. Cela veut dire que le système mémoire est lui-même en pipeline pour pouvoir traiter une nouvelle demande à chaque cycle. Dans le cycle WBK, à chaque cycle on écrit dans le banc de registres. Lorsque l'instruction ne nécessite pas de sauvegarder un résultat dans un registre, on écrit dans le registre 0.
     175
     176[[Image(htdocs:/corrige/Seance4/S4_corrige_Q3_a.svg)]]
     177
     178
     179
     180'''PROC''' contient tous les bypass qui arrivent dans les étages '''`DEC`''' et '''`EXE`'''. On souhaite étudier l'impact de la mise en place d'un bypass dans l'étage '''`MM1`''' sur la performance du processeur. On considère donc deux versions de '''PROC'''.
     181
     182Dans '''PROC1''', il n'y a pas de bypass entre l'étage '''`MM2`''' de l'instruction `i` et l'étage '''`MM1`''' de l'instruction `i+2`. La période de l'horloge est de 2 ns pour '''PROC1'''.
     183Dans '''PROC2''', il y a un bypass entre l'étage '''`MM2`''' de l'instruction `i` et l'étage '''`MM1`''' de l'instruction `i+2`. La période de l'horloge est de 2,1 ns pour '''PROC2'''.
     184
     185''b - Expliquer pourquoi la période de l'horloge est plus longue dans '''PROC2''' ?''
     186
     187
     188'''''Solution 3-b :'''''
     189
     190Dans un processeur pipeline, le temps de cycle est souvent déterminé par le temps d'accès à la mémoire. En effet, l'accès à la mémoire se trouve souvent sur le chemin critique du processeur (l'opération la plus longue). Dans PROC, l'accès à la mémoire s'effectue en deux cycles. Si l'on place un bypass dans les cycles d'accès à la mémoire, il y a une très forte probabilité d'aggraver le chemin critique du processeur et donc de ralentir le temps de cycle.
     191
     192
     193Pour comparer la performance des 2 versions de '''PROC''', on considère le code de l'exercice 2.
     194
     195''c - Modifier le code du programme pour qu'il soit exécutable sur '''PROC'''.''
     196
     197
     198'''''Solution 3-c :'''''
     199
     200Dans '''PROC''', l'adresse de l'instruction est calculée dans le cycle '''`DEC`''', c'est-à-dire le troisième cycle du pipeline. Il y a donc 2 delayed slots dans ce processeur. La manière la plus simple de rendre le code exécutable est de remplir les delayed slots avec des `Nop`.
     201{{{
     202#!asm
     203loop:
     204    Lbu   r8, 0(r4)        ; lire un pixel
     205    Addu  r8 , r8, r5
     206    Lbu   r9 , 0(r8)       ; lire f(pixel)
     207    Sb    r9 , 0(r4)
     208
     209    Addiu r4 , r4 , 1
     210    Bne   r4 , r10, loop
     211    Nop
     212    Nop
     213}}}
     214
     215
     216''d - Analyser, à l'aide d'un schéma simplifié, l'exécution de ce code dans '''PROC1'''. Combien de cycles sont nécessaires pour l'exécution d'une itération de la boucle ? Calculer le CPI et le CPI-utile. Combien dure (en seconde) le traitement d'une image de 1024 pixels ?''
     217
     218
     219'''''Solution 3-d :'''''
     220
     221On a les dépendances de données suivantes :
     222 * entre `Lbu` et `Addu`  (2 cycles de gel et bypass MM2-EXE)
     223 * entre `Addu` et `Lbu`  (bypass EXE-EXE)
     224 * entre `Lbu` et `Sb`    (2 cycles de gel et bypass MM2-EXE)
     225 * entre `Addiu` et `Bne` (1 cycle de gel et bypass EXE-DEC)
     226
     227[[Image(htdocs:/corrige/Seance4/S4_corrige_Q3_d.svg)]]
     228
     229En tout, il faut donc 13 cycles pour exécuter une itération de la boucle.
     230
     231CPI = 13/8 cycles/instruction -- CPI-utile = 13/6 cycles/instruction
     232
     233Pour une image de 1024 pixels il faut 13 x 1024 = 13312 cycles soit 13312 x 2 = 26624 ns
     234
     235
     236''e - Analyser, à l'aide d'un schéma simplifié, l'exécution de ce code dans '''PROC2'''. Combien de cycles sont nécessaires pour l'exécution d'une itération de la boucle. Calculer le CPI et le CPI-utile. Combien dure (en seconde) le traitement d'une image de 1024 pixels ?''
     237
     238
     239
     240'''''Solution 3-e :'''''
     241
     242On a les dépendances de données suivantes :
     243 * entre `Lbu` et `Addu`  (2 cycles de gel et bypass MM2-EXE)
     244 * entre `Addu` et `Lbu`  (bypass EXE-EXE)
     245 * entre `Lbu` et `Sb`    (1 cycle de gel et bypass MM2-MM1)
     246 * entre `Addiu` et `Bne` (1 cycle de gel et bypass EXE-DEC)
     247
     248[[Image(htdocs:/corrige/Seance4/S4_corrige_Q3_e.svg)]]
     249
     250En tout, il faut donc 12 cycles pour exécuter une itération de la boucle.
     251
     252CPI = 12/8 cycles/instruction -- CPI-utile = 12/6 cycles/instruction
     253
     254Pour une image de 1024 pixels il faut 12 x 1024 = 12288 cycles soit 12288 x 2.1 = 25804.8 ns
     255
     256La mise en place du bypass permet de gagner un cycle dans le traitement (gain de 1/13). En contrepartie on perd 5% sur le temps de cycle. On aboutit donc globalement à une accélération dans le traitement de l'image.
     257
     258
     259''f - Pour '''PROC1''', réordonner le code afin d'éviter au maximum les cycles perdus. Combien de cycles sont maintenant nécessaires pour l'exécution d'une itération de la boucle. Calculer le CPI et le CPI-utile. Combien dure (en seconde) le traitement d'une image de 1024 pixels ?''
     260
     261
     262'''''Solution 3-f :'''''
     263
     264Il y a en tout 7 cycles perdus (5 cycles de gel et 2 de `Nop`). Les 4 premières instructions sont dépendantes. On ne peut donc pas changer leur ordre. La seule instruction que l'on peut réordonner est la deuxième `Addiu`. Elle peut être placée entre le premier `Lbu` et `Addiu` pour combler un cycle de gel. On peut aussi placer le `Sb` dans le deuxième delayed slot pour l'écarter du `Lbu`.
     265{{{
     266#!asm
     267loop:
     268    lbu   r8 , 0(r4)        ; lire un pixel
     269    addiu r4 , r4 , 1
     270    addu  r8 , r8 , r5
     271    lbu   r9 , 0(r8)        ; lire f(pixel)
     272
     273    bne   r4 , r10, loop
     274    nop
     275    sb    r9 , -1(r4)
     276}}}
     277
     278On a les dépendances de données suivantes :
     279 * entre `Lbu` et `Addu` (1 cycle de gel et bypass MM2-EXE)
     280 * entre `Addu` et `Lbu` (bypass EXE-EXE)
     281 * entre `Lbu` et `Sb`  (bypass MM2-EXE)
     282 * entre `Addiu` et `Bne` (bypass MM2-DEC)
     283
     284[[Image(htdocs:/corrige/Seance4/S4_corrige_Q3_f.svg)]]
     285
     286En tout, il faut donc 8 cycles pour exécuter une itération de la boucle.
     287
     288CPI = 8/7 cycles/instruction -- CPI-utile = 8/6 cycles/instruction
     289
     290Pour une image de 1024 pixels il faut 8 x 1024 = 8192 cycles soit 8192 x 2 = 16384 ns.
     291
     292
     293''g - Pour '''PROC2''', réordonner le code afin d'éviter au maximum les cycles perdus. Combien de cycles sont maintenant nécessaires pour l'exécution d'une itération de la boucle. Calculer le CPI et le CPI-utile. Combien dure (en seconde) le traitement d'une image de 1024 pixels ?''
     294
     295
     296
     297'''''Solution 3-g :'''''
     298
     299Le même ordonnancement convient à '''PROC2'''. En tout, il faut donc 8 cycles pour exécuter une itération de la boucle.
     300
     301CPI = 8/7 cycles/instruction -- CPI-utile = 8/6 cycles/instruction
     302
     303Pour une image de 1024 pixels il faut 8 x 1024 = 8192 cycles soit 8192 x 2.1 = 17203.2 ns.
     304
     305Le réordonnancement a permis d'éliminer les cycles de gel entre `Lbu` et `Sb`. Le bypass entre '''`MM2`''' et '''`MM1`''' n'apporte donc aucune amélioration. Globalement le traitement est ralenti à cause de la période d'horloge.
     306
     307
     308''h - Pour améliorer la performance du traitement, on décide de dérouler une fois la boucle (traitement de 2 pixels par itération). Proposer un code optimisé pour '''PROC1'''. Combien de cycles sont maintenant nécessaires pour l'exécution d'une itération de la boucle. Calculer le CPI et le CPI-utile. Combien dure (en seconde) le traitement d'une image de 1024 pixels ?''
     309
     310
     311
     312'''''Solution 3-h :'''''
     313{{{
     314#!asm
     315loop:
     316    Lbu   r8 , 0(r4)        ; lire un pixel
     317    Lbu   r12, 1(r4)        ; lire un pixel
     318    Addiu r4 , r4 , 2
     319    Addu  r8 , r8 , r5
     320    Addu  r12, r12, r5
     321    Lbu   r9 , 0(r8)        ; lire f(pixel)
     322    Lbu   r13, 0(r12)       ; lire f(pixel)
     323
     324    Bne   r4 , r10, loop
     325    Sb    r9 , -2(r4)
     326    Sb    r13, -1(r4)
     327}}}
     328
     329Il n'y a aucun cycle perdu. En tout, il faut donc 10 cycles pour exécuter une itération de la boucle.
     330
     331CPI = 10/10 cycles/instruction -- CPI-utile = 10/10 cycles/instruction
     332
     333Pour une image de 1024 pixels il faut 512 itérations soit 10 x 512 = 5120 cycles soit 5120 x 2 = 10240 ns.
     334
     335
     336''i - Pour améliorer la performance du traitement, on décide de dérouler une fois la boucle (traitement de 2 pixels par itération). Proposer un code optimisé pour '''PROC2'''. Combien de cycles sont maintenant nécessaires pour l'exécution d'une itération de la boucle. Calculer le CPI et le CPI-utile. Combien dure (en seconde) le traitement d'une image de 1024 pixels ?''
     337
     338
     339'''''Solution 3-i :'''''
     340
     341Le même code convient à '''PROC2'''. En tout, il faut donc 10 cycles pour exécuter une itération de la boucle.
     342
     343CPI = CPI-utile = 1 cycles/instruction
     344
     345Pour une image de 1024 pixels il faut 10x 512 = 5120 cycles soit 5120 x 2.1 = 10752 ns.
     346
     347Le réordonnancement a permis d'éliminer les cycles de gel entre `Lbu` et `Sb`. Le bypass entre '''`MM2`''' et '''`MM1`''' n'apporte donc aucune amélioration. Globalement le traitement est ralenti à cause de la période d'horloge.
    67348
    68349
    … …  
    70351= Exercice 4 : =
    71352
    72 On considère une nouvelle instruction de branchement conditionnel : l'instruction BEQPD (Branch if equal and pre-decrement).
    73 {{{
    74     Beqpd    rs, rt, Label
    75 }}}
    76 
    77 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é.
    78 
    79 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.
    80 
    81 
    82 '''''Solution 4 :'''''
    83 
    84 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.
    85 
    86 
    87 
    88 = Exercice 5 : =
    89 
    90 Montrer à l’aide d’un schéma détaillé l’exécution de la suite d’instructions suivante dans le pipeline du Mips-32.
    91 {{{
    92     Add    r3 , r2 , r1
    93     Add    r3 , r3 , r1
    94 }}}
    95 
    96 Quelle est la condition du déclenchement des bypass ?
    97 
    98 
    99 '''''Solution 5 :'''''
    100 
    101 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q5.svg)]]
    102 
    103 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.
    104 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).
    105 
    106 
    107 
    108 = Exercice 6 : =
    109 
    110 Montrer à l’aide d’un schéma détaillé l’exécution de la suite d’instructions suivante dans le pipeline du Mips-32.
    111 {{{
    112     Add    r0 , r2 , r1
    113     Add    r3 , r0 , r1
    114 }}}
    115 Donner l'expression exacte de la condition du déclenchement des bypass ?
    116 
    117 
    118 '''''Solution 6 :'''''
    119 
    120 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.
    121 
    122 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q6_a.svg)]]
    123 
    124 Le schéma détaillé correspond à l'exécution de 2 instructions d'addition.
    125 
    126 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q6_b.svg)]]
    127 
    128 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.
    129 
    130 
    131 
    132 = Exercice 7 : =
    133 
    134 Montrer à l’aide d’un schéma détaillé l’exécution de la suite d’instructions suivante dans le pipeline du Mips-32.
    135 {{{
    136     Lw    r3 , 0 (r2)
    137     Add   r3 , r3 , r1
    138 }}}
    139 
    140 
    141 '''''Solution 7 :'''''
    142 
    143 Il y a une dépendance de données entre ces deux instructions qui provoque un cycle de gel (stall).
    144 
    145 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q7.svg)]]
    146 
    147 
    148 
    149 = Exercice 8 : =
    150 
    151 Analyser l’exécution de la suite d’instructions suivante dans le processeur Mips-32 à l’aide d’un schéma simplifié.
    152 {{{
    153 #!asm
    154     Addiu  r2 , r0 , 4
    155     Lui    r3 , 0x000c
    156     Add    r2 , r2 , r2
    157     Ori    r3 , r3 , 0x4568
    158     Lw     r2 , 0(r3)
    159     Lbu    r2 , 0(r2)
    160     Ori    r2 , r2 , 0x0001
    161     Bltzal r2 , suite
    162     Addu   r0 , r0 , r0
    163 suite:
    164     Jr     r31
    165     Addu   r31, r31, -8
    166 }}}
    167 
    168 
    169 '''''Solution 8 :'''''
    170 
    171 Le schéma suivant montre les dépendances de données dans ce code.
    172 
    173 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q8_a.svg)]]
    174 
    175 
    176 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q8_b.svg)]]
    177 
    178 
    179 
    180    
    181 = Exercice 9 : =
    182 
    183 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.
    184 
    185 
    186 '''''Solution 9 :'''''
    187 
    188 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).
    189 
    190 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q9_a.svg)]]
    191 
    192 Exemple (bypass sur RS) :
    193 {{{
    194     Add    r3 , r2 , r1
    195     Add    r3 , r3 , r4
    196 }}}
    197 
    198 Exemple (bypass sur RT) :
    199 {{{
    200     Add    r3 , r2 , r1
    201     Add    r3 , r4 , r3
    202 }}}
    203 
    204 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`.
    205 
    206 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q9_b.svg)]]
    207 
    208 Exemple (bypass sur RS) :
    209 {{{
    210     Add    r3 , r2 , r1
    211     ... (une instruction quelconque)
    212     Beq    r3 , r4 , Suite
    213 }}}
    214 
    215 Exemple (bypass sur RT) :
    216 {{{
    217     Add    r3 , r2 , r1
    218     ... (une instruction quelconque)
    219     Beq    r4 , r3 , Suite
    220 }}}
    221 
    222 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`.
    223 
    224 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q9_c.svg)]]
    225 
    226 Exemple (bypass sur RS) :
    227 {{{
    228     Lw    r3 , 0 (r2)
    229     ... (une instruction quelconque)
    230     Add    r5 , r3 , r4
    231 }}}
    232 
    233 Exemple (bypass sur RT) :
    234 {{{
    235     Lw    r3 , 0 (r2)
    236     ... (une instruction quelconque)
    237     Add    r5 , r4 , r3
    238 }}}
    239 
    240 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).
    241 
    242 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q9_d.svg)]]
    243 
    244 Exemple (bypass sur RS) :
    245 {{{
    246     Add    r3 , r2 , r1
    247     ... (une instruction quelconque)
    248     ... (une instruction quelconque)
    249     Add    r5 , r3 , r4
    250 }}}
    251 
    252 Exemple (bypass sur RT) :
    253 {{{
    254     Add    r3 , r2 , r1
    255     ... (une instruction quelconque)
    256     ... (une instruction quelconque)
    257     Add    r5 , r4 , r3
    258 }}}
    259 
    260 
    261 
    262 = Exercice 10 : =
    263 
    264 La fonction strlen calcule le nombre de caractères :
    265 {{{
    266 #!c
    267 unsigned int strlen (char * str) {
    268    unsigned int i = 0;
    269    while (str [i] != '\0') {
    270       i++;
    271    }
    272    return (i);
    273 }
    274 }}}
    275 
    276 Différents codes assembleur peuvent être produits pour cette fonction pour un processeur non-pipeline :
    277 
    278 1ère version :
    279 {{{
    280 #!asm
    281 _strlen:
    282     Addiu    r29, r29, -1*4
    283     Addu     r2, r0 , r0    ; initialisation
    284 _strlen_loop:
    285     Lb       r9 , 0(r4)     ; lire 1 caractere
    286     Beq      r9 , r0 , _strlen_end_loop    ; fin de chaine ?
    287     Addiu    r4 , r4 , 1    ; caractere suivant
    288     Addiu    r2 , r2 , 1    ; caractere suivant
    289     J        _strlen_loop   ; boucle
    290 
    291 _strlen_end_loop:
    292     Addiu    r29, r29, 1*4
    293     Jr       r31
    294 }}}
    295 
    296 2ème version :
    297 {{{
    298 #!asm
    299 _strlen:
    300     Addiu    r29, r29, -1*4
    301     Addiu    r2, r0 , -1    ; initialisation
    302 _strlen_loop:
    303     Lb       r9 , 0(r4)     ; lire 1 caractere
    304     Addiu    r4 , r4 , 1    ; caractere suivant
    305     Addiu    r2 , r2 , 1    ; caractere suivant
    306     Bne      r9 , r0 , _strlen_loop    ; fin de chaine ?
    307 
    308     Addiu    r29, r29, 1*4
    309     Jr       r31
    310 }}}
    311 
    312 3ème version :
    313 {{{
    314 #!asm
    315 _strlen:
    316     Addiu    r29, r29, -1*4
    317     Addiu    r8, r4 ,  1    ; sauvegarde adresse debut
    318 _strlen_loop:
    319     Lb       r9 , 0(r4)     ; lire 1 caractere (octet)
    320     Addiu    r4 , r4 , 1    ; caractere suivant
    321     Bne      r9 , r0 , _strlen_loop    ; fin de chaine ?
    322     Subu     r2 , r4 , r8    ; calculer nbr de carac
    323 
    324     Addiu    r29, r29, 1*4
    325     Jr       r31
    326 }}}
    327 
    328 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.
    329 
    330 
    331 '''''Solution 10 :'''''
    332 
    333 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.
    334 
    335 1ère version :
    336 {{{
    337 #!asm
    338 _strlen:
    339     Addiu    r29, r29, -1*4
    340     Addu     r2, r0 , r0    ; initialisation
    341 _strlen_loop:
    342     Lb       r9 , 0(r4)     ; lire 1 caractere
    343     Beq      r9 , r0 , _strlen_end_loop    ; fin de chaine ?
    344     Nop
    345     Addiu    r4 , r4 , 1    ; caractere suivant
    346     Addiu    r2 , r2 , 1    ; caractere suivant
    347     J        _strlen_loop   ; boucle
    348     Nop
    349 
    350     Addiu    r29, r29, 1*4
    351     Jr       r31
    352     Nop
    353 }}}
    354 
    355 2ème version :
    356 {{{
    357 #!asm
    358 _strlen:
    359     Addiu    r29, r29, -1*4
    360     Addiu    r2, r0 , -1    ; initialisation
    361 _strlen_loop:
    362     Lb       r9 , 0(r4)     ; lire 1 caractere
    363     Addiu    r4 , r4 , 1    ; caractere suivant
    364     Addiu    r2 , r2 , 1    ; caractere suivant
    365     Bne      r9 , r0 , _strlen_loop    ; fin de chaine ?
    366     Nop
    367 
    368     Addiu    r29, r29, 1*4
    369     Jr       r31
    370     Nop
    371 }}}
    372 
    373 3ème version :
    374 {{{
    375 #!asm
    376 _strlen:
    377     Addiu    r29, r29, -1*4
    378     Addiu    r8, r4 ,  1    ; sauvegarde adresse debut
    379 _strlen_loop:
    380     Lb       r9 , 0(r4)     ; lire 1 caractere (octet)
    381     Addiu    r4 , r4 , 1    ; caractere suivant
    382     Bne      r9 , r0 , _strlen_loop    ; fin de chaine ?
    383     Nop
    384     Subu     r2 , r4 , r8    ; calculer nbr de carac
    385 
    386     Addiu    r29, r29, 1*4
    387     Jr       r31
    388     Nop
    389 }}}
    390 
    391 
    392 Analyser l'exécution de la boucle sur le processeur Mips à l'aide d'un schéma simplifié.
    393 
    394 
    395 '''''Solution 10 :'''''
    396 
    397 1ère version :
    398 
    399 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q10_1_a.svg)]]
    400 
    401 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q10_1_b.svg)]]
    402 
    403 2ème version :
    404 
    405 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q10_2_a.svg)]]
    406 
    407 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q10_2_b.svg)]]
    408 
    409 3ème version :
    410 
    411 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q10_3_a.svg)]]
    412 
    413 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q10_3_b.svg)]]
    414 
    415    
    416 
    417 Calculer le nombre de cycles nécessaires à l'exécution d'une itération de la boucle.
    418 
    419 
    420 '''''Solution 10 :'''''
    421 
    422  * 1ère version : 9 cycles par itération
    423  * 2ème version : 5 cycles par itération
    424  * 3ème version : 5 cycles par itération
    425 
    426 
    427 
    428 Calculer le CPI et le CPI-utile de la boucle.
    429 
    430 
    431 '''''Solution 10 :'''''
    432 
    433  * 1ère version : CPI = 9/7 cycles/inst  --  CPI-utile = 9/5 cycles/inst
    434  * 2ème version : CPI = 5/5 cycles/inst  --  CPI-utile = 5/4 cycles/inst
    435  * 3ème version : CPI = 5/4 cycles/inst  --  CPI-utile = 5/3 cycles/inst
    436 
    437 
    438 
    439 
    440 = Exercice 11 :  =
    441 
    442 La fonction strupper transforme une chaîne de caractères en majuscules :
    443 {{{
    444 #!c
    445 char * strupper (char * src) {
    446    int i = 0;
    447    while (src[i] != '\0') {
    448       if ((src[i] >= 'a') && (src[i] <= 'z')) {
    449          src[i] = src[i] - 'a' + 'A'
    450       }
    451       i++;
    452    }
    453    return src;
    454 }
    455 }}}
    456 
    457 La compilation de cette fonction pour un processeur non-pipeline a produit le code suivant:
    458 {{{
    459 #!asm
    460 _strupper:
    461     Addiu    r29, r29, -1*4
    462 
    463     Addu    r2 , r0 , r4     ; valeur de retour
    464     Addiu   r11, r0 , 'a'    ; pour la comparaison
    465     Addiu   r12, r0 , 'z'    ; pour la comparaison
    466 
    467 _strupper_loop:
    468     Lb      r8 , 0(r4)       ; lire src[i]
    469     Slt     r9 , r8 , r11    ; src[i] < 'a'
    470     Slt     r10, r12, r8     ; 'z'    < src[i]
    471     Or      r10, r10, r9     ; et des 2 conditions
    472     Bne     r10, r0 , _strupper_endif    ; si 1 des 2 cond vraie
    473     Addiu   r8 , r8 , 'A'-'a'; transformer en majuscule
    474     Sb      r8 , 0(r4)
    475 
    476 _strupper_endif:
    477     Addiu   r4 , r4 , 1      ; caractère suivant
    478     Bne     r8 , r0 , _strupper_loop
    479 
    480     Addiu   r29, r29, 1*4
    481     Jr      r31
    482 }}}
    483 
    484 Transformer ce code de telle façon qu'il puisse être exécuté sur le processeur Mips pipeline à 5 étages.
    485 
    486 
    487 '''''Solution 11 :'''''
    488 
    489 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.
    490 
    491 {{{
    492 #!asm
    493 __strupper:
    494     Addiu    r29, r29, -1*4
    495 
    496     Addu    r2 , r0 , r4     ; valeur de retour
    497     Addiu   r11, r0 , 'a'    ; pour la comparaison
    498     Addiu   r12, r0 , 'z'    ; pour la comparaison
    499 
    500 _strupper_loop:
    501     Lb      r8 , 0(r4)       ; lire src[i]
    502     Slt     r9 , r8 , r11    ; src[i] < 'a'
    503     Slt     r10, r12, r8     ; 'z'    < src[i]
    504     Or      r10, r10, r9     ; et des 2 conditions
    505     Bne     r10, r0 , _strupper_endif    ; si 1 des 2 cond vraie
    506     Nop
    507     Addiu   r8 , r8 , 'A'-'a'; transformer en majuscule
    508     Sb      r8 , 0(r4)
    509 
    510 _strupper_endif:
    511     Addiu   r4 , r4 , 1      ; caractère suivant
    512     Bne     r8 , r0 , _strupper_loop
    513     Nop
    514 
    515     Addiu   r29, r29, 1*4
    516     Jr      r31
    517     Nop
    518 }}}
    519 
    520 
    521 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.
    522 
    523 
    524 '''''Solution 11 :'''''
    525 
    526 Attention, il y a une dépendance entre le dernier `Addiu` et le `Lb` de l'itération suivante.
    527 
    528 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q11_a.svg)]]
    529 
    530 Cas où le `if` réussit :
    531 
    532 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q11_b.svg)]]
    533 
    534 Cas où le `if` échoue :
    535 
    536 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q11_c.svg)]]
    537 
    538 
    539 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.
    540 
    541 
    542 '''''Solution 11 :'''''
    543 
    544 Il faut 13 cycles pour une itération si le `if` réussit
    545 
    546 
    547 Calculer le nombre de cycles nécessaires à l'exécution d'une itération de la boucle dans le cas ou le `if` échoue.
    548 
    549 
    550 '''''Solution 11 :'''''
    551 
    552 Il faut 11 cycles pour une itération si le `if` échoue.
    553 
    554 
    555 Sachant que 30% des caractères sont minuscules calculer le CPI et le CPI-utile de la boucle.
    556 
    557 
    558 '''''Solution 11 :'''''
    559 
    560 CPI = 1.208 cycle/instruction
    561 
    562 CPI_utile = 1.526 cycle/instruction utile
    563 
    564 
    565    
    566 = Exercice 12 : =
    567 
    568 La fonction suivante calcule le PGCD de deux nombres positifs non nuls :
    569 {{{
    570 #!c
    571 unsigned int pgcd (unsigned int a, unsigned int b) {
    572    while (a != b) {
    573       if (a < b) {
    574           b = b - a;
    575       }
    576       else {
    577           a = a - b;
    578       }
    579    }
    580    return a;
    581 }
    582 }}}
    583 
    584 La compilation de cette fonction pour un processeur non-pipeline a produit le code suivant:
    585 {{{
    586 #!asm
    587 _pgcd:
    588     Beq     r4 , r5 , _pgcd_end
    589 
    590 _pgcd_loop:
    591     Sltu    r8 , r4 , r5    ; a < b
    592     Beq     r8 , r0 , _pgcd_else
    593     Subu    r5 , r5 , r4
    594     J       _pgcd_endif
    595 
    596 _pgcd_else:
    597     Subu    r4 , r4 , r5
    598 _pgcd_endif:
    599     Bne     r4 , r5 , _pgcd_loop
    600 
    601 _pgcd_end:
    602     Add     r2 , r4 , r0    ; valeur de retour
    603     Jr      r31
    604 }}}
    605 
    606 Transformer ce code de telle façon qu'il puisse être exécuté sur le processeur Mips pipeline à 5 étages.
    607 
    608 
    609 '''''Solution 12 :'''''
    610 
    611 Il suffit d'ajouter une instruction NOP après chaque branchement.
    612 {{{
    613 #!asm
    614 _pgcd:
    615     Beq     r4 , r5 , _pgcd_end
    616     Nop
    617 
    618 _pgcd_loop:
    619     Sltu    r8 , r4 , r5    ; a < b
    620     Beq     r8 , r0 , _pgcd_else
    621     Nop
    622     Subu    r5 , r5 , r4
    623     J       _pgcd_endif
    624     Nop
    625 
    626 _pgcd_else:
    627     Subu    r4 , r4 , r5
    628 _pgcd_endif:
    629     Bne     r4 , r5 , _pgcd_loop
    630     Nop
    631 
    632 _pgcd_end:
    633     Add     r2 , r4 , r0    ; valeur de retour
    634     Jr      r31
    635     Nop
    636 }}}
    637 
    638 
    639 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.
    640 
    641 
    642 '''''Solution 12 :'''''
    643 
    644 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q12_a.svg)]]
    645 
    646 Cas où le `if` réussit :
    647 
    648 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q12_b.svg)]]
    649 
    650 Cas où le `if` échoue :
    651 
    652 [[Image(htdocs:/corrige/Seance3/S3_corrige_Q12_c.svg)]]
    653 
    654 
    655 
    656 
    657 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.
    658 
    659 
    660 '''''Solution 12 :'''''
    661 
    662 Il faut 9 cycles pour une itération si le `if` réussit.
    663 
    664 
    665 Calculer le nombre de cycles nécessaires à l'exécution d'une itération de la boucle dans le cas ou le `if` échoue.
    666 
    667 
    668 '''''Solution 12 :'''''
    669 
    670 Il faut 8 cycles pour une itération si le `if` échoue.
    671 
    672 
    673 Sachant que dans un cas sur deux le `if` échoue, calculer le CPI et le CPI-utile de la boucle.
    674 
    675 
    676 '''''Solution 12 :'''''
    677 
    678 CPI = 1.214 cycle/instrution
    679 
    680 CPI_utile = 1.889 cycle/instrution utile
    681 
    682 
     353On considère le processeur pipeline P9. Il a le même jeu d'instructions que le Mips. Il est construit autour d'un pipeline à 9 étages :
     354
     355`IF1, IF2, DEC1, DEC2, EXE1, EXE2, MEM1, MEM2, WBK`
     356
     357Le découpage en étages de ce pipeline a été obtenu à partir du pipeline du processeur Mips. Chacun des étages `IFC`, `DEC`, `EXE` et `MEM` a été divisé en deux étages. Le calcul de l'adresse de l'instruction suivante s'achève dans l'étage `DEC2`.
     358
     359On souhaite étudier le fonctionnement de ce processeur. Le code suivant est la boucle principale d'une fonction qui calcule la valeur absolue des éléments d'un tableau d'entiers. A l'entrée de la boucle `R4` contient l'adresse du tableau, le registre `R9` contient l'adresse de la fin du tableau.
     360{{{
     361#!asm
     362loop:
     363    Lw    r8 , 0(r4)        ; lire un élément
     364    Bgez  r8 , _endif
     365    Sub   r8 , r0 , r8      ; calculer l'opposé
     366    Sw    r8, 0(r4)
     367
     368_endif:
     369    Addiu r4 , r4 , 4
     370    Bne   r4 , r9 , loop
     371}}}
     372
     373''a - Le découpage du pipeline en 9 étages a-t-il un impact sur le compilateur ?''
     374
     375'''''Solution 4-a :'''''
     376
     377Oui. Dans le processeur P9, le calcul de l'adresse de l'instruction suivante se fait dans le cycle '''`DEC2`''' (4ème cycle du pipeline). Il y a donc 3 delayed slot après chaque branchement dans cette réalisation. Le compilateur doit en tenir compte pour générer le code et pour effectuer les optimisations.
     378
     379
     380''b - Dans le processeur Mips, il existe des dépendances de données d'ordre 1, 2 et 3. Dans P9 quelles sont les dépendances de données ?''
     381
     382
     383'''''Solution 4-b :'''''
     384
     385Dans le processeur P9, il y a des dépendances de données d'ordre 1 à 6. En effet, le cycle `DEC1` (où s'effectue la lecture du banc de registres) de l'instruction `i+7` s'effectue après le cycle `WBK` de l'instruction `i`.
     386
     387[[Image(htdocs:/corrige/Seance4/S4_corrige_Q4_b.svg)]]
     388
     389
     390''c - Quels sont les bypass nécessaires à l'exécution des instructions dans ce P9 ? Illustrer pour chaque bypass son utilisation à l'aide d'un exemple d'une suite d'instructions.''
     391
     392
     393'''''Solution 4-c :'''''
     394
     395 * 1 bypass de la sortie de `EXE2` vers `EXE2` (ordre 1) : sur `RT`
     396{{{
     397    Add  r7 , r1 , r2
     398    Sw   r7 , 0(r3)
     399}}}
     400
     401 * 2 bypass de la sortie de `EXE2` vers `EXE1` (ordre 2) : un sur `RS` et un sur `RT`
     402{{{
     403    Add  r7 , r1 , r2         Add  r8 , r1 , r2
     404    ...                       ...
     405    Add  r9 , r7 , r8         Add  r9 , r7 , r8
     406}}}
     407
     408 * 1 bypass de la sortie de `MEM2` vers `EXE2` (ordre 3) : sur `RT`
     409{{{
     410    Lw   r7 , 0(r1)
     411    ...
     412    ...
     413    Sw   r7 , 0(r3)
     414}}}
     415
     416 * 2 bypass de la sortie de `EXE2` vers `DEC2` (ordre 3) : un sur `RS` et un sur `RT`
     417ou
     418 * 2 bypass de la sortie de `MEM1` vers `EXE1` (ordre 3) : un sur `RS` et un sur `RT`
     419{{{
     420    Add  r7 , r1 , r2         Add  r8 , r1 , r2
     421    ...                       ...
     422    ...                       ...
     423    Add  r9 , r7 , r8         Add  r9 , r7 , r8
     424}}}
     425
     426 * 2 bypass de la sortie de `EXE2` vers `DEC1` (ordre 4) : un sur `RS` et un sur `RT`
     427{{{
     428    Add  r7 , r1 , r2         Add  r8 , r1 , r2
     429    ...                       ...
     430    ...                       ...
     431    ...                       ...
     432    Beq  r7 , r8 , suite      Beq  r7 , r8 , suite
     433}}}
     434
     435 * 2 bypass de la sortie de `MEM2` vers `EXE1` (ordre 4) : un sur `RS` et un sur `RT`
     436{{{
     437    Lw   r7 , 0(r1)           Lw   r8 , 0(r1)
     438    ...                       ...
     439    ...                       ...
     440    ...                       ...
     441    Add  r9 , r7 , r8         Add  r9 , r7 , r8
     442}}}
     443
     444 * 2 bypass de la sortie de `MEM1` vers `DEC1` (ordre 5) : un sur `RS` et un sur `RT`
     445{{{
     446    Add  r7 , r1 , r2         Add  r8 , r1 , r2
     447    ...                       ...
     448    ...                       ...
     449    ...                       ...
     450    ...                       ...
     451    Beq  r7 , r8 , suite      Beq  r7 , r8 , suite
     452}}}
     453
     454 * 2 bypass de la sortie de `MEM2` vers `DEC2` (ordre 5) : un sur `RS` et un sur `RT`
     455{{{
     456    Lw   r7 , 0(r1)           Lw   r8 , 0(r1)
     457    ...                       ...
     458    ...                       ...
     459    ...                       ...
     460    ...                       ...
     461    Add  r9 , r7 , r8         Add  r9 , r7 , r8
     462}}}
     463
     464 * 2 bypass de la sortie de `MEM2` vers `DEC1` (ordre 6) : un sur `RS` et un sur `RT`
     465{{{
     466    Add  r7 , r1 , r2         Add  r8 , r1 , r2
     467    ...                       ...
     468    ...                       ...
     469    ...                       ...
     470    ...                       ...
     471    ...                       ...
     472    Add  r9 , r7 , r8         Add  r9 , r7 , r8
     473}}}
     474
     475Au total il y a 16 bypass.
     476
     477
     478''d - Quelles sont les situations qui provoquent des cycles de gel ? Illustrer chaque cas à l'aide d'un exemple d'une suite d'instructions.''
     479
     480
     481'''''Solution 4-d :'''''
     482
     483Toutes les dépendances qui ne peuvent pas être résolues par un bypass provoquent des cycles de gel.
     484
     485 * dépendance d'ordre 1 sur `RS` ou sur `RT` (autre que les Store)
     486{{{
     487    Add  r7 , r1 , r2
     488    Add  r9 , r8 , r7
     489}}}
     490
     491 * dépendance d'ordre 2 sur `RS` ou sur `RT` lorsque la valeur est produite par le cycle `MEM2` ou lorsque l'opérande est consommé dans le cycle `DEC1`.
     492{{{
     493    Add  r7 , r1 , r2         Lw   r7 , 0(r1)
     494    ...                       ...
     495    Beq  r7 , r8 , suite      Add  r9 , r7 , r8
     496}}}
     497
     498 * dépendance d'ordre 3 sur `RS` ou sur `RT` lorsque la valeur est produite par le cycle `MEM2` ou lorsque l'opérande est consommé dans le cycle `DEC1`.
     499{{{
     500    Add  r7 , r1 , r2         Lw    r7 , 0(r1)
     501    ...                       ...
     502    ...                       ...
     503    Beq  r7 , r8 , suite      Add    r9 , r7 , r8
     504}}}
     505
     506 * dépendance d'ordre 4 sur `RS` ou sur `RT` lorsque la valeur est produite par le cycle `MEM2` et consommée dans le cycle `DEC1`.
     507{{{
     508    Lw   r7 , 0(r1)
     509    ...
     510    ...
     511    ...
     512    Beq  r7 , r8 , suite
     513}}}
     514
     515 * dépendance d'ordre 5 sur `RS` ou sur `RT` lorsque la valeur est produite par le cycle `MEM2` et consommée dans le cycle `DEC1`.
     516{{{
     517    Lw   r7 , 0(r1)
     518    ...
     519    ...
     520    ...
     521    ...
     522    Beq  r7 , r8 , suite
     523}}}
     524
     525
     526''e - Modifier le code de la boucle pour qu'il soit exécutable sur le processeur P9.''
     527
     528
     529'''''Solution 4-e :'''''
     530
     531La manière la plus simple est de remplir les delayed slots avec des `Nop`.
     532{{{
     533#!asm
     534loop:
     535    Lw    r8 , 0(r4)        ; lire un élément
     536    Bgez  r8 , _endif
     537    Nop
     538    Nop
     539    Nop
     540    Sub   r8 , r0 , r8      ; calculer l'opposé
     541    Sw    r8 , 0(r4)
     542
     543_endif:
     544    Addiu r4 , r4 , 4
     545    Bne   r4 , r9 , loop
     546    Nop
     547    Nop
     548    Nop
     549}}}
     550
     551
     552''f - Analyser l'exécution d'une itération de la boucle à l'aide d'un schéma simplifié.''
     553
     554
     555'''''Solution 4-f :'''''
     556
     557On a les dépendances de données suivantes :
     558 * entre le `Lw` et le `Bgez`   (5 cycles de gel)
     559 * entre le `Sub` et le `Sw`    (pas de cycle de gel)
     560 * entre le `Addiu` et le `Bne` (3 cycles de gel)
     561
     562[[Image(htdocs:/corrige/Seance4/S4_corrige_Q4_f.svg)]]
     563
     564
     565
     566''g - Calculer le CPI et le CPI-utile en supposant que 50% des nombres sont négatifs.''
     567
     568
     569'''''Solution 4-g :'''''
     570
     571Il faut 20 cycles pour une itération si le branchement échoue et 18 cycles s'il réussit. D'où :
     572
     573CPI = (20*0.5 + 18*0.5)/(12*0.5 + 10*0.5) = 1.73 cycles/inst
     574
     575CPI-utile = (20*0.5 + 18*0.5)/(6*0.5 + 4*0.5) = 3.8 cycles/inst-utile
     576
     577
     578
     579
     580''h - Réordonner ce code de manière à éviter au maximum les cycles perdus.''
     581
     582
     583'''''Solution 4-h :'''''
     584
     585On peut déplacer le Addiu entre le `Lw` et le `Bgez`.
     586{{{
     587#!asm
     588loop:
     589    Lw    r8 , 0(r4)        ; lire un élément
     590    Addiu r4 , r4 , 4
     591    Bgez  r8 , _endif
     592    Nop
     593    Nop
     594    Nop
     595    Sub   r8 , r0 , r8      ; calculer l'opposé
     596    Sw    r8 , -4(r4)
     597
     598_endif:
     599    Bne   r4 , r9 , loop
     600    Nop
     601    Nop
     602    Nop
     603}}}
     604
     605Il faut maintenant 16 cycles par itération si le branchement échoue et 14 cycles s'il réussit.
     606
     607
     608''i - Optimiser ce code à l'aide de la technique "software pipeline".''
     609
     610
     611'''''Solution 4-i :'''''
     612
     613A première vue, on peut décomposer le traitement d'un élément du tableau en deux étapes : la lecture et le test et le rangement. On peut alors réorganiser le code de manière à traiter deux éléments dans une itération : la lecture de l'élément `i` et le rangement de l'élément `i-1`.
     614{{{
     615#!asm
     616loop:
     617    Bgez  r8 , _endif
     618    Nop
     619    Nop
     620    Nop
     621    Sub   r10, r0 , r8  ; calculer l'opposé (elem i-1)
     622    Sw    r10, -4(r4)
     623
     624_endif:
     625    Lw    r8 , 0(r4)    ; lire un élément (elem i)
     626    Addiu r4 , r4 , 4
     627    Bne   r4 , r9 , loop
     628    Nop
     629    Nop
     630    Nop
     631}}}
     632
     633On peut maintenant réordonner ce code. Il faut écarter le `Addiu` et le `Bne`. On peut par exemple placer le `Addiu` avant le `Bgez`. Par contre, il vaut mieux ne pas placer le `Lw` dans les delayed slot du `Bne`. En effet, on a une dépendance entre le `Lw` et le `Bgez` de l’itération suivante. Pour que cette dépendance ne crée pas de cycle de gel, il faut au moins une distance de 6.
     634{{{
     635#!asm
     636loop:
     637    Addiu r4 , r4 , 4
     638    Bgez  r8 , _endif
     639    Nop
     640    Nop
     641    Nop
     642    Sub   r10, r0 , r8   ; calculer l'opposé (elem i-1)
     643    Sw    r10, -8(r4)
     644
     645_endif:
     646    Lw    r8 , -4(r4)    ; lire un élément (elem i)
     647    Bne   r4 , r9 , loop
     648    Nop
     649    Nop
     650    Nop
     651}}}
     652
     653Il faut maintenant 12 cycles pour une itération si le branchement échoue et 10 cycles s'il réussit.
     654
     655Une autre idée consiste à sortir le `Sub` de la partie du code exécutée de manière conditionnelle (on exécute le `Sub` dans tous les cas, et on ne fait le `Sw` que si le branchement échoue). On peut gagner alors 1 cycle en déplaçant le Sub dans le dernier delayed Slot du `Bgez`.
     656
     657Il faut maintenant 11 cycles pour une itération si le branchement échoue et 10 cycles s'il réussit.
     658{{{
     659#!asm
     660loop:
     661    Addiu r4 , r4 , 4
     662    Bgez  r8 , _endif
     663    Nop
     664    Nop
     665    Sub   r10, r0 , r8    ; calculer l'opposé (elem i-1)
     666    Sw    r10, -8(r4)
     667
     668_endif:
     669    Lw    r8 , -4(r4)    ; lire un élément (elem i)
     670    Bne   r4 , r9 , loop
     671    Nop
     672    Nop
     673    Nop
     674}}}
     675
     676Autre solution :
     677{{{
     678#!asm
     679loop:
     680    Bgez  r8 , _endif
     681    Addiu r4 , r4 , 4
     682    Sub   r10, r0 , r8      ; calculer l'opposé
     683    Lw    r8 , -4(r4)       ; lire un élément
     684
     685    Sw    r10, -8(r4)
     686
     687_endif:
     688    Bne   r4 , r9 , loop
     689    Nop
     690    Nop
     691    Nop
     692}}}
     693Avec cette solution on a 9 cycles que le branchement réussisse ou non.
     694
     695
     696
     697
     698''j - Le temps de cycle du processeur P9 est égal à 0,6 fois le temps de cycle du processeur Mips. Comparer le temps nécessaire à l'exécution d'une itération de la boucle entre le Mips et P9. Quelle conclusion en tirez-vous ?''
     699
     700
     701'''''Solution 4-j :'''''
     702
     703Si l'on considère le code original, dans P9, il faut 20 cycles pour l'exécuter. Dans le Mips, il faut 11 cycles si le branchement échoue et 9 cycles s'il réussit.
     704{{{
     705#!asm
     706loop:
     707    Lw    r8 , 0(r4)    ; lire un élément
     708    Bgez  r8 , _endif
     709    Nop
     710    Sub   r8 , r0 , r8  ; calculer l'opposé
     711    Sw    r8 , 0(r4)
     712
     713_endif:
     714    Addiu r4 , r4 , 4
     715    Bne   r4 , r9 , loop
     716    Nop
     717}}}
     718
     719Ainsi, par rapport au Mips, l'exécution du code sans optimisation dans le P9 prend (20*0.5 + 18*0.5)*0.6/(11*0.5 + 9*0.5) = 1.14 fois plus de temps.
     720
     721Si l'on optimise le code dans le Mips :
     722{{{
     723#!asm
     724loop:
     725    Bgez  r8 , _endif
     726    Addiu r4 , r4 , 4
     727    Sw    r10, -8(r4)
     728
     729_endif:
     730    Lw    r8 , -4(r4)     ; lire un élément
     731    Bne   r4 , r6 , loop
     732    Sub   r10 , r0 , r8   ; calculer l'opposé
     733}}}
     734
     735et si on considère la meilleure optimisation obtenue dans P9, l'exécution dans P9 prend (11*0.5 + 10*0.5)*0.6/(6*0.5+5*0.5) = 1.15 fois plus de temps.
     736
     737Même si la fréquence de fonctionnement de P9 est plus élevée que celle du Mips, globalement, sur ce code, le traitement est ralenti. Cela est dû au grand nombre de delayed slots dans P9 et au fait que la boucle étant très court, il n'y a pas beaucoup d'occasion d'ordonnancement. Sans doute en déroulant la boucle, on peut obtenir de meilleurs résultats.