| 145 | | |
| 146 | | |
| 147 | | == Préambule == |
| 148 | | |
| 149 | | Ce TP a pour but l'observation (en simulation) du fonctionnement des mémoires caches, et des mouvements de données entre les caches et la mémoire principale. |
| 150 | | |
| 151 | | On a choisi des lignes de cache de 16 octets et des caches de faible capacité : chaque cache (cache d'instructions et cache de données) possède une capacité de 128 octets (soit 8 cases, pouvant contenir chacune une ligne de cache de 16 octets). Les deux caches du processeur sont à ''correspondance directe''. On ne s'intéresse pas dans ce TP au fonctionnement du cache L2, qui peut être vu comme un accélérateur d'accès à la mémoire externe : grâce au cache L2, un accès à la mémoire, en cas de MISS sur un cache L1 va coûter en moyenne quelques dizaines de cycles au lieu de quelques centaines de cycles. |
| 152 | | |
| 153 | | Pour ce TP, vous utiliserez le simulateur `almo1.x`, qui peut produire des fichiers d'instrumentation permettant de suivre l'évolution des caches au cours du temps. |
| 154 | | |
| 155 | | == 1. Calcul du taux de MISS dans le cache d'instructions == |
| 156 | | |
| 157 | | Commencez par recopier [attachments:s5.tgz tp5] dans votre répertoire de travail. |
| 158 | | |
| 159 | | {{{ |
| 160 | | s5 |
| 161 | | ├── Makefile |
| 162 | | └── src |
| 163 | | ├── harch.c |
| 164 | | ├── harch.h |
| 165 | | ├── hcpu.S |
| 166 | | ├── hcpu.h |
| 167 | | ├── jpeg.h |
| 168 | | ├── kernel.ld |
| 169 | | ├── kinit.c |
| 170 | | ├── klibc.c |
| 171 | | └── klibc.h |
| 172 | | }}} |
| 173 | | |
| 174 | | Ce répertoire tp3 contient 2 répertoires. Le premier `8_cache_miss` va permettre de voir l'évolution des miss, le second `9_cache_perf` sera vu plus loin pour l'évolution des performances en fonction de la taille de cache. Pour les deux répertoires, il y a tous les fichiers nécessaires à la génération du code binaire `kernel.x`, dont un fichier `Makefile` permettant de le générer automatiquement. Ces fichiers représentent une version minimaliste du système (vu au tp1), il n'y a presque rien, mais le but est d'analyser le comportement des caches, donc moins il y a de code à exécuter avant la fonction que vous allez analyser, mieux c'est. Dans un premier temps vous utiliserez le code sans modification. |
| 175 | | |
| 176 | | * Allez dans le répertoire `8_cache_miss`` |
| 177 | | * Ouvrez le fichier `src/kinit.c` et expliquez ce que fait, ici, la fonction `kinit()` ? |
| 178 | | |
| 179 | | {{{ |
| 180 | | #!protected |
| 181 | | |
| 182 | | La fonction `kinit()` déclare un tableau de 20 entiers. Les valeurs sont initialisées dans une première boucle `for`, puis une seconde boucle `for` est exécutée 1000 fois. À chaque itération de cette seconde boucle, chaque élément du tableau est incrémenté d'une valeur égale à son indice de tableau. Finalement, les valeurs finales des 20 éléments du tableau sont affichées sur le terminal grâce à une troisième boucle `for`. |
| 183 | | }}} |
| 184 | | |
| 185 | | * Lancez l'exécution du `Makefile` (make compil), puis examinez le code assembleur correspondant à l'application logicielle (`kernel.x.s`). Déterminez les adresses de début et de fin de la boucle de calcul (seconde boucle `for`). |
| 186 | | * Combien d'instructions sont exécutées à chaque itération de cette boucle ? |
| 187 | | * Toutes les instructions de la boucle de calcul peuvent-elles être simultanément stockées dans le cache ? |
| 188 | | * Que pouvez-vous en conclure ? |
| 189 | | |
| 190 | | {{{ |
| 191 | | #!protected |
| 192 | | * La boucle commence à l'instruction `lw v0,24(sp)` et se termine à l'instruction `nop` qui suit l'instruction `bnez v0, kinit+0x50`. |
| 193 | | * Cette boucle exécute 51 instructions à chaque itération. Si les étudiants posent la question, on peut expliquer que l'instruction `nop` qui suit le branchement est toujours exécuté à cause de l'effet retardé du branchement (`delayed slot` dû à l'architecture ''pipeline''). |
| 194 | | * Comme le cache ne peut contenir que 32 instructions au max (8 cases contenant chacune 4 instructions), la boucle ne tient pas entièrement dans le cache. Il y aura donc des MISS et des évincements à chaque itération dans la boucle. |
| 195 | | }}} |
| 196 | | |
| 197 | | * Vous allez renommer le fichier `kernel.x.s` en `kernel.myx.s` et y ajouter des commentaires (ce renommage permet de ne pas perdre vos commentaires lors du `make clean`), déterminez, pour chaque instruction de la boucle de calcul, dans quelle case du cache sera rangée la ligne de cache à laquelle cette instruction appartient. La boucle for fait 51 instructions, vous devez grouper les instructions par 4 (puisqu'une ligne de cache contient 4 instructions). |
| 198 | | |
| 199 | | * En analysant la valeur du champ ''index'' de l'adresse, calculez pour chacune de ces 13 lignes de cache, dans quelle case du cache elle va être stockée. |
| 200 | | |
| 201 | | {{{ |
| 202 | | #!protected |
| 203 | | |
| 204 | | |
| 205 | | {{{ |
| 206 | | 004012dc <main>: |
| 207 | | ... |
| 208 | | 401320: 1440fff5 bnez v0,4012f8 <main+0x1c> |
| 209 | | 401324: 00000000 nop |
| 210 | | 401328: afc00014 sw zero,20(s8) |
| 211 | | 40132c: 081004fc j 4013f0 <main+0x114> |
| 212 | | |
| 213 | | # ligne de cache (ci-dessous) : case n°3 |
| 214 | | 401330: 00000000 nop |
| 215 | | 401334: 8fc20018 lw v0,24(s8) |
| 216 | | 401338: afc20018 sw v0,24(s8) |
| 217 | | 40133c: 8fc2001c lw v0,28(s8) |
| 218 | | |
| 219 | | # ligne de cache (ci-dessous) : case n°4 |
| 220 | | 401340: 24420001 addiu v0,v0,1 |
| 221 | | 401344: afc2001c sw v0,28(s8) |
| 222 | | 401348: 8fc20020 lw v0,32(s8) |
| 223 | | 40134c: 24420002 addiu v0,v0,2 |
| 224 | | |
| 225 | | # ligne de cache (ci-dessous) : case n°5 |
| 226 | | 401350: afc20020 sw v0,32(s8) |
| 227 | | 401354: 8fc20024 lw v0,36(s8) |
| 228 | | 401358: 24420003 addiu v0,v0,3 |
| 229 | | 40135c: afc20024 sw v0,36(s8) |
| 230 | | |
| 231 | | # ligne de cache (ci-dessous) : case n°6 |
| 232 | | 401360: 8fc20028 lw v0,40(s8) |
| 233 | | 401364: 24420004 addiu v0,v0,4 |
| 234 | | 401368: afc20028 sw v0,40(s8) |
| 235 | | 40136c: 8fc2002c lw v0,44(s8) |
| 236 | | |
| 237 | | # ligne de cache (ci-dessous) : case n°7 |
| 238 | | 401370: 24420005 addiu v0,v0,5 |
| 239 | | 401374: afc2002c sw v0,44(s8) |
| 240 | | 401378: 8fc20030 lw v0,48(s8) |
| 241 | | 40137c: 24420006 addiu v0,v0,6 |
| 242 | | |
| 243 | | # ligne de cache (ci-dessous) : case n°0 |
| 244 | | 401380: afc20030 sw v0,48(s8) |
| 245 | | 401384: 8fc20034 lw v0,52(s8) |
| 246 | | 401388: 24420007 addiu v0,v0,7 |
| 247 | | 40138c: afc20034 sw v0,52(s8) |
| 248 | | |
| 249 | | # ligne de cache (ci-dessous) : case n°1 |
| 250 | | 401390: 8fc20038 lw v0,56(s8) |
| 251 | | 401394: 24420008 addiu v0,v0,8 |
| 252 | | 401398: afc20038 sw v0,56(s8) |
| 253 | | 40139c: 8fc2003c lw v0,60(s8) |
| 254 | | |
| 255 | | # ligne de cache (ci-dessous) : case n°2 |
| 256 | | 4013a0: 24420009 addiu v0,v0,9 |
| 257 | | 4013a4: afc2003c sw v0,60(s8) |
| 258 | | 4013a8: 8fc20040 lw v0,64(s8) |
| 259 | | 4013ac: 2442000a addiu v0,v0,10 |
| 260 | | |
| 261 | | # ligne de cache (ci-dessous) : case n°3 |
| 262 | | 4013b0: afc20040 sw v0,64(s8) |
| 263 | | 4013b4: 8fc20044 lw v0,68(s8) |
| 264 | | 4013b8: 2442000b addiu v0,v0,11 |
| 265 | | 4013bc: afc20044 sw v0,68(s8) |
| 266 | | |
| 267 | | # ligne de cache (ci-dessous) : case n°4 |
| 268 | | 4013c0: 8fc20048 lw v0,72(s8) |
| 269 | | 4013c4: 2442000c addiu v0,v0,12 |
| 270 | | 4013c8: afc20048 sw v0,72(s8) |
| 271 | | 4013cc: 8fc2004c lw v0,76(s8) |
| 272 | | |
| 273 | | # ligne de cache (ci-dessous) : case n°5 |
| 274 | | 4013d0: 2442000d addiu v0,v0,13 |
| 275 | | 4013d4: afc2004c sw v0,76(s8) |
| 276 | | 4013d8: 8fc20050 lw v0,80(s8) |
| 277 | | 4013dc: 2442000e addiu v0,v0,14 |
| 278 | | |
| 279 | | # ligne de cache (ci-dessous) : case n°6 |
| 280 | | 4013e0: afc20050 sw v0,80(s8) |
| 281 | | 4013e4: 8fc20014 lw v0,20(s8) |
| 282 | | 4013e8: 24420001 addiu v0,v0,1 |
| 283 | | 4013ec: afc20014 sw v0,20(s8) |
| 284 | | |
| 285 | | # ligne de cache (ci-dessous) : case n°7 |
| 286 | | 4013f0: 8fc20014 lw v0,20(s8) |
| 287 | | 4013f4: 2c4203e8 sltiu v0,v0,1000 |
| 288 | | 4013f8: 1440ffce bnez v0,401334 <main+0x58> |
| 289 | | 4013fc: 00000000 nop |
| 290 | | ... |
| 291 | | }}} |
| 292 | | }}} |
| 293 | | |
| 294 | | * Évaluez le nombre de MISS instruction lors de l'exécution de la première itération ? Lors de la deuxième itération ? En déduire une valeur estimée du ''taux de MISS'' moyen après 1000 itérations. |
| 295 | | |
| 296 | | {{{ |
| 297 | | #!protected |
| 298 | | |
| 299 | | 1ere itération : En exécutant la boucle `for` la première fois, le processeur va provoquer le chargement de 13 lignes de caches aux index successifs suivants : 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2. Il y a donc 13 MISS lors de la 1ere itération. |
| 300 | | |
| 301 | | Itérations suivantes : Au début de la 2e itération, les instructions contenues dans les cases 3, 4, 5, 6, 7 font MISS, car elles ont été écrasées. Les instructions contenues dans les cases 0, 1, 2 ne font pas MISS. À la fin de l'itération, les instructions contenues dans les cases 3, 4, 5, 6, 7 font de nouveau MISS. On a donc 10 MISS pour 51 instructions lors de la 2e itération, et il en va de même pour les itérations suivantes. Ceci correspond à un taux de MISS de 10/51, légèrement inférieur à 20%. |
| 302 | | }}} |
| 303 | | |
| 304 | | == 2. Analyse de trace == |
| 305 | | |
| 306 | | Vous allez maintenant tenter de valider ce calcul du taux de MISS par la simulation. En éditant le fichier `Makefile`, vous pouvez voir la règle `cache` qui lance le simulateur en imposant les caractéristiques du cache : |
| 307 | | |
| 308 | | * -NICACHELEN : nombre de mots par case dans le cache instruction |
| 309 | | * -NDCACHELEN : nombre de mots par case dans le cache data |
| 310 | | * -NICACHESET : nombre de cases dans le cache instruction |
| 311 | | * -NDCACHESET : nombre de cases dans le cache data |
| 312 | | |
| 313 | | * Lancez donc la simulation avec la commande suivante : `make cache` |
| 314 | | |
| 315 | | Vous devriez voir les résultats s'afficher dans la fenêtre du TTY, avec la date à laquelle il est arrivé au `exit()`. Pour arrêter le simulateur, il faut taper le caractère `ctrl + c` dans la fenêtre du terminal où a été lancée la simulation. |
| 316 | | |
| 317 | | Pour observer précisément le comportement des caches, il faut relancer le simulateur en activant l'option d'instrumentation `-TRACE trace.txt`, pour obtenir un fichier `trace.txt` permettant de visualiser le contenu des caches au cours du temps. Les fichiers de trace étant très volumineux, on limite à 5000 le nombre de cycles simulés en utilisant l'option `-NCYCLES 5000`. |
| 318 | | |
| 319 | | * Relancez donc la simulation avec la commande suivante : `make cachetrace`\\(vous pouvez ouvrir le fichier `Makefile` pour voir la commande du simulateur). |
| 320 | | |
| 321 | | Une fois la simulation terminée, ouvrez dans deux fenêtres différentes le fichier de trace `trace.txt`, contenant les états successifs des caches, et le fichier `kernel.x.s` contenant le code désassemblé, puis observez le remplissage progressif des deux caches au fur et à mesure de l'exécution de l'application. |
| 322 | | |
| 323 | | * À quel cycle est chargée dans le cache d'instructions la première instruction de la fonction `kinit()` ? |
| 324 | | * À quel cycle est chargée la première ligne de cache contenant des instructions de la boucle de calcul ? |
| 325 | | * À quel cycle cette première ligne est-elle évincée par le chargement d'une autre ligne de cache ? |
| 326 | | * À quel cycle cette première ligne est-elle rechargée pour exécuter la deuxième itération de la boucle ? |
| 327 | | * A quel cycle est-elle rechargée pour exécuter la troisième itération? |
| 328 | | * Quelle est la durée (en nombre de cycles) de la première itération? |
| 329 | | * Quelle est la durée des itérations suivantes? |
| 330 | | |
| 331 | | {{{ |
| 332 | | #!protected |
| 333 | | * La première ligne de cache correspondant aux instructions de la fonction `main()` est copiée dans la case n°0 du cache au cycle 58. |
| 334 | | * La première ligne de cache correspondant aux premières instructions de la boucle est copiée dans la case n°6 du cache au cycle 388. |
| 335 | | * Elle est évincée au cycle 572 pour stocker d'autres instructions situées vers la fin de la boucle. |
| 336 | | * Elle est rechargée pour la deuxième itération au cycle 666. |
| 337 | | |
| 338 | | Il s'est donc écoulé (666 - 388) = 278 cycles entre deux itérations. Cela signifie qu'il faut 278 cycles pour exécuter 50 instructions, soit presque 6 cycles par instruction. |
| 339 | | }}} |
| 340 | | |
| 341 | | == 3. Mesure du taux de MISS == |
| 342 | | |
| 343 | | Pour mesurer le taux de MISS sur le cache instruction, on peut activer l'option d'instrumentation `-STATS stats.txt`. |
| 344 | | Le fichier `stats.txt` contient des informations statistiques. Plus précisément, le simulateur relève à intervalles réguliers (tous les 10 cycles) différents compteurs permettant de caractériser l'activité des caches. Chaque ligne de ce fichier de statistiques contient 8 valeurs : |
| 345 | | |
| 346 | | 1. Le nombre de cycles simulés depuis le démarrage de la machine (incrément de 10 à chaque ligne), |
| 347 | | 1. Le nombre d'instructions exécutées depuis le démarrage de la machine, |
| 348 | | 1. Le nombre de MISS sur le cache d'instructions depuis le démarrage de la machine, |
| 349 | | 1. Le nombre de lectures de données depuis le démarrage de la machine, |
| 350 | | 1. Le nombre de MISS sur le cache de données depuis le démarrage de la machine, |
| 351 | | 1. Le taux de MISS sur le cache d'instructions, |
| 352 | | 1. Le taux de MISS sur le cache de données, |
| 353 | | 1. Le CPI, qui est le nombre moyen de cycles par instruction. |
| 354 | | |
| 355 | | * Relancez donc la simulation avec la commande suivante : `make cachestats`\\(vous pouvez ouvrir le fichier `Makefile` pour voir la commande du simulateur). |
| 356 | | |
| 357 | | À l'aide de l'outil `'gnuplot'` (s'il n'est pas installé sur votre machine personnelle, vous devrez l'intaller), c'est un logiciel de visualisation de courbes, vous allez afficher l'évolution du taux de MISS sur le cache d'instructions au cours du temps. Pour cela, lancez la commande : |
| 358 | | |
| 359 | | {{{ |
| 360 | | #!bash |
| 361 | | $ gnuplot |
| 362 | | }}} |
| 363 | | |
| 364 | | * Une fois dans ce logiciel (indiqué par l'invite de commande `'gnuplot> '`), vous pouvez entrer la commande : |
| 365 | | |
| 366 | | {{{ |
| 367 | | #!bash |
| 368 | | plot 'stats.txt' using 1:6 |
| 369 | | }}} |
| 370 | | |
| 371 | | ''Note : cette commande signifie que vous souhaitez afficher la courbe où la colonne n°1 du fichier `stats.txt` (le nombre de cycles écoulés) est en abscisse et la colonne n°6 (le taux de MISS sur le cache d'instructions) est en ordonnée.'' |
| 372 | | |
| 373 | | * Comment expliquez-vous l'évolution du taux de MISS au cours du temps ? |
| 374 | | |
| 375 | | {{{ |
| 376 | | #!protected |
| 377 | | Attention: les valeurs mesurées sont des moyennes cumulées depuis le début de la simulation... |
| 378 | | |
| 379 | | Au début le cache est vide, et il n'y a que des MISS. Puis le cache d'instructions est rempli avec le code de `reset`, puis avec le code du `main`, et enfin avec le code de la boucle. Le taux de MISS dans le cache remonte pour se rapprocher de 20% car 5 des 8 lignes de cache font systématiquement MISS pendant l'exécution de la boucle (10 MISS pour 51 instructions lues dans le cache). |
| 380 | | }}} |
| 381 | | |
| 382 | | == 4. Optimisation du code pour minimiser le taux de MISS == |
| 383 | | |
| 384 | | Pour minimiser le taux de MISS, il faut modifier l'application logicielle pour que les 1000 itérations de la boucle de calcul puissent s'exécuter sans MISS sur le cache d'instructions. Pour cela, on peut remplacer les 15 lignes calculant les 15 nouvelles valeurs du tableau par une boucle `for` interne portant sur l'index dans le tableau, de façon à obtenir un code plus compact, qui tienne entièrement dans le cache. |
| 385 | | |
| 386 | | * Copiez le fichier `main.c` actuel dans un autre fichier (par exemple, `kinit_orig.c`) afin de garder une sauvegarde du fichier original. Puis, ouvrez le fichier `main.c` et modifiez la fonction `main()` comme indiqué ci-dessus. |
| 387 | | |
| 388 | | * Éditez le fichier exécutable de l'application logicielle (`kernel.x.s`), et vérifiez que votre nouvelle boucle de calcul a bien une longueur inférieure à 32 instructions (afin d'être contenue entièrement dans le cache). |
| 389 | | |
| 390 | | * Editez le fichier `Makefile` pour que la simulation avec statistique produise le fichier `stats_nomiss.txt`. |
| 391 | | |
| 392 | | * Relancez la simulation pour 100000 cycles, en changeant le nom du fichier de statistiques : `make cachestat` |
| 393 | | |
| 394 | | * À l'aide de `gnuplot`, affichez sur le même graphique les résultats des exercices 1 et 2, afin de les comparer. Pour cela, entrez les deux commandes suivantes : |
| 395 | | |
| 396 | | {{{ |
| 397 | | #!bash |
| 398 | | plot 'stats.txt' using 1:6 |
| 399 | | replot 'stats_nomiss.txt' using 1:6 |
| 400 | | }}} |
| 401 | | |
| 402 | | * Comment expliquez-vous l'évolution du taux de MISS pour cette nouvelle version de l'application ? |
| 403 | | |
| 404 | | {{{ |
| 405 | | #!protected |
| 406 | | Au début, le comportement des deux versions de l'application est identique. Vers les cycles 300/400, le cache est complètement chargé. Quand le processeur commence à exécuter la boucle de calcul, les deux courbes commencent à diverger, puisque la courbe verte correspond au cas où toutes les instructions de la boucle tiennent dans le cache : le taux de MISS instruction est nul. |
| 407 | | }}} |
| 408 | | |
| 409 | | |
| 410 | | {{{#!html |
| 411 | | <h1><font size=+2> B) mesures de performance du processeur en fonction de la taille des caches</font></h1> |
| 412 | | }}} |
