| 1 | | |
| 2 | | = M1 SESI – Architecture des Processeurs et Optimisation = |
| 3 | | |
| 4 | | = TD3 – Pipeline, Superpipeline, Optimisation de codes = |
| 5 | | |
| 6 | | = Exercice 1 : = |
| 7 | | |
| 8 | | La 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 |
| 11 | | struct chain { |
| 12 | | struct chain * NEXT; |
| 13 | | void * DATA; |
| 14 | | }; |
| 15 | | |
| 16 | | int 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 | | |
| 26 | | Ecrire en assembleur Mips-32 la boucle principale de `GetListLength`. On suppose que `R4` contient l'adresse de la liste (pt). |
| 27 | | |
| 28 | | Analyser l'exécution de la boucle à l'aide d'un schéma simplifié. |
| 29 | | |
| 30 | | |
| 31 | | '''''Solution 1 :''''' |
| 32 | | {{{ |
| 33 | | #!asm |
| 34 | | Loop : |
| 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 | | |
| 43 | | |
| 44 | | = Exercice 2 : = |
| 45 | | |
| 46 | | On 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 |
| 49 | | loop: |
| 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)`. |
| 60 | | Par 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 | | |
| 67 | | Il faut un delayed slot après chaque branchement |
| 68 | | {{{ |
| 69 | | #!asm |
| 70 | | loop: |
| 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 | | |
| 92 | | Il faut 10 cycles par itération soit : |
| 93 | | CPI = 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 | | |
| 101 | | Au 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 | | |
| 108 | | Par 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 |
| 112 | | loop: |
| 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 | | |
| 122 | | Il 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 | | |
| 130 | | On 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 | | |
| 132 | | A 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 |
| 135 | | loop: |
| 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 | | |
| 146 | | Maintenant, 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 |
| 149 | | loop: |
| 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 | | |
| 159 | | Il faut 6 cycles par itération soit CPI = CPI-utile = 1 cycle/inst. |
| 160 | | |
| 161 | | |
| 162 | | |
| 163 | | = Exercice 3 : = |
| 164 | | |
| 165 | | On 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 | | |
| 167 | | Au 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 | | |
| 174 | | Dans 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 | | |
| 182 | | Dans '''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'''. |
| 183 | | Dans '''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 | | |
| 190 | | Dans 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 | | |
| 193 | | Pour 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 | | |
| 200 | | Dans '''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 |
| 203 | | loop: |
| 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 | | |
| 221 | | On 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 | | |
| 229 | | En tout, il faut donc 13 cycles pour exécuter une itération de la boucle. |
| 230 | | |
| 231 | | CPI = 13/8 cycles/instruction -- CPI-utile = 13/6 cycles/instruction |
| 232 | | |
| 233 | | Pour 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 | | |
| 242 | | On 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 | | |
| 250 | | En tout, il faut donc 12 cycles pour exécuter une itération de la boucle. |
| 251 | | |
| 252 | | CPI = 12/8 cycles/instruction -- CPI-utile = 12/6 cycles/instruction |
| 253 | | |
| 254 | | Pour une image de 1024 pixels il faut 12 x 1024 = 12288 cycles soit 12288 x 2.1 = 25804.8 ns |
| 255 | | |
| 256 | | La 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 | | |
| 264 | | Il 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 |
| 267 | | loop: |
| 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 | | |
| 278 | | On 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 | | |
| 286 | | En tout, il faut donc 8 cycles pour exécuter une itération de la boucle. |
| 287 | | |
| 288 | | CPI = 8/7 cycles/instruction -- CPI-utile = 8/6 cycles/instruction |
| 289 | | |
| 290 | | Pour 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 | | |
| 299 | | Le même ordonnancement convient à '''PROC2'''. En tout, il faut donc 8 cycles pour exécuter une itération de la boucle. |
| 300 | | |
| 301 | | CPI = 8/7 cycles/instruction -- CPI-utile = 8/6 cycles/instruction |
| 302 | | |
| 303 | | Pour une image de 1024 pixels il faut 8 x 1024 = 8192 cycles soit 8192 x 2.1 = 17203.2 ns. |
| 304 | | |
| 305 | | Le 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 |
| 315 | | loop: |
| 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 | | |
| 329 | | Il n'y a aucun cycle perdu. En tout, il faut donc 10 cycles pour exécuter une itération de la boucle. |
| 330 | | |
| 331 | | CPI = 10/10 cycles/instruction -- CPI-utile = 10/10 cycles/instruction |
| 332 | | |
| 333 | | Pour 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 | | |
| 341 | | Le même code convient à '''PROC2'''. En tout, il faut donc 10 cycles pour exécuter une itération de la boucle. |
| 342 | | |
| 343 | | CPI = CPI-utile = 1 cycles/instruction |
| 344 | | |
| 345 | | Pour une image de 1024 pixels il faut 10x 512 = 5120 cycles soit 5120 x 2.1 = 10752 ns. |
| 346 | | |
| 347 | | Le 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. |
| 348 | | |
| 349 | | |
| 350 | | |
| 351 | | = Exercice 4 : = |
| 352 | | |
| 353 | | On 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 | | |
| 357 | | Le 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 | | |
| 359 | | On 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 |
| 362 | | loop: |
| 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 | | |
| 377 | | Oui. 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 | | |
| 385 | | Dans 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` |
| 417 | | ou |
| 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 | | |
| 475 | | Au 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 | | |
| 483 | | Toutes 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 | | |
| 531 | | La manière la plus simple est de remplir les delayed slots avec des `Nop`. |
| 532 | | {{{ |
| 533 | | #!asm |
| 534 | | loop: |
| 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 | | |
| 557 | | On 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 | | |
| 571 | | Il faut 20 cycles pour une itération si le branchement échoue et 18 cycles s'il réussit. D'où : |
| 572 | | |
| 573 | | CPI = (20*0.5 + 18*0.5)/(12*0.5 + 10*0.5) = 1.73 cycles/inst |
| 574 | | |
| 575 | | CPI-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 | | |
| 585 | | On peut déplacer le Addiu entre le `Lw` et le `Bgez`. |
| 586 | | {{{ |
| 587 | | #!asm |
| 588 | | loop: |
| 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 | | |
| 605 | | Il 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 | | |
| 613 | | A 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 |
| 616 | | loop: |
| 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 | | |
| 633 | | On 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 |
| 636 | | loop: |
| 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 | | |
| 653 | | Il faut maintenant 12 cycles pour une itération si le branchement échoue et 10 cycles s'il réussit. |
| 654 | | |
| 655 | | Une 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 | | |
| 657 | | Il faut maintenant 11 cycles pour une itération si le branchement échoue et 10 cycles s'il réussit. |
| 658 | | {{{ |
| 659 | | #!asm |
| 660 | | loop: |
| 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 | | |
| 676 | | Autre solution : |
| 677 | | {{{ |
| 678 | | #!asm |
| 679 | | loop: |
| 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 | | }}} |
| 693 | | Avec 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 | | |
| 703 | | Si 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 |
| 706 | | loop: |
| 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 | | |
| 719 | | Ainsi, 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 | | |
| 721 | | Si l'on optimise le code dans le Mips : |
| 722 | | {{{ |
| 723 | | #!asm |
| 724 | | loop: |
| 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 | | |
| 735 | | et 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 | | |
| 737 | | Mê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. |
