Changes between Initial Version and Version 1 of AS6-TME-B4

Timestamp:

Mar 7, 2022, 1:26:33 PM (3 years ago)

Author:

franck

Comment:

--

AS6-TME-B4

@@ +1 @@
+{{{#!protected
+{{{#!html
+<h1><font size=+3> Partie TD</font></h1>
+}}}
+
+{{{#!html
+<h1><font size=+2> Remplissage des caches </font></h1>
+}}}
+
+
+== Préambule ==
+
+Dans un ordinateur (un SoC), l'accès à la mémoire principale par le, ou les, processeur(s) est souvent coûteux en nombre de cycles d'horloge, car la mémoire principale est souvent située en dehors du SoC. Pour améliorer les performances, on place des ''mémoires'', petites mais très rapides, entre le processeur et la mémoire.
+
+Ces mémoires, nommées ''cache'', contiennent les données ou les instructions récemment utilisées par le processeur. Les ''caches'' ne contiennent que des copies de données ou d'instructions de la mémoire principale. L'efficacité des ''caches'' est liée aux propriétés de localité spatiale et temporelles des applications logicielles. En effet, il est fort probable qu'après avoir accédé à une certaine adresse mémoire `X`, l'application accède à nouveau à l'adresse `X` dans un futur proche (localité temporelle) ou accède à une autre adresse mémoire proche de `X` (localité spatiale).
+
+Un cache lit la mémoire par ''ligne de cache''. Une ''ligne de cache'' est un segment d'adresse aligné dans l'espace d'adressage dont la taille est une puissance de 2 en mots. Une ligne de cache peut faire 2 mots, 4 mots, 8 mots voire 16 mots mais rarement plus. Un segment aligné signifie que l'adresse du premier octet est multiple de la taille du segment. Pour le MIPS, les mots font 4 octets, si les lignes de cache font 2 mots alors les lignes commencent à des adresses multiples de 8. Les lignes sont numérotées. Pour savoir à quelle ligne appartient un octet quelconque de l'espace d'adressage de la mémoire, il suffit de diviser l'adresse de l'octet par la taille d'une ligne. A titre d'exemple, pour des lignes de 8 octets, les octets de 0 à 7 sont dans la ligne n°0, les octets de 8 à 15 sont dans la ligne 1, etc.
+
+Le cache lit des **''lignes de caches''** et les rangent dans des **''cases de caches''**. Une ligne de cache est un contenu alors qu'une case de cache est un contenant. A chaque fois qu'un composant cache lit une ligne de cache en mémoire, il doit la ranger dans l'une de ces cases. Le choix le plus simple est que ce soit le numéro de la ligne qui définissent directement le numéro de la case. Ce choix définit les caches à correspondance directe : un numéro de ligne impose un numéro de case. Le nombre de cases d'un cache est toujours une puissance de 2 (2 cases, 4 cases, 8 cases, [...], 1024 cases, etc), ainsi un numéro de cases est toujours défini par un nombre entier de bits (1 bit s'il y a 2 cases, 2 bits s'il y a 4 case, 3 bits s'il y a 8 cases, [...], 10 bits s'il y a 1024 casses, ect.). 
+
+Nous allons étudier les mémoires cache à ''correspondance directe'' pour lesquels le numéro de la case de cache est simplement défini par le n bits de poids faible du numéro de ligne de cache, avec 2^n^ = nombre de cases de cache.
+
+== Exercice ==
+
+Soit un processeur `MIPS32` associé à un cache d'instructions et à un cache de données séparés. Les deux caches ont une capacité de stockage de 32 octets et sont à ''correspondance directe''. La largeur d'une ligne de cache est de 8 octets (soit 2 mots).
+
+''Rappel : toutes les adresses émises par le processeur sont des adresses octets, et les adresses sont codées sur 32 bits.''
+
+* Dites comment le contrôleur du cache interprète une adresse :
+ * quel est le nombre de bits de l'index ?
+ * quel est le nombre de bits du déplacement (''offset'') ?
+ * quel est le nombre de bits de l'étiquette (''tag'') ?
+
+{{{
+#!protected
+
+* Nombre de bits de l'index : log2 (capacité du cache / largeur de la ligne) = log2  (8/2) =  2.
+* Nombre de bits du déplacement : log2 (nombre d'octets dans la ligne de cache) = log2 (2*4)= 3.
+* Nombre de bits de l'étiquette : taille totale de l'adresse - taille de l'index - taille de l'offset = 32 - 2 - 3 = 27.
+
+Il faut dire aux étudiants qu'ils auront besoin de ces formules pour l'examen !
+}}}
+
+Considérons la séquence d'instructions suivante dont la première instruction est stockée à l'adresse `loop = 0x00000010` :
+
+{{{
+#!asm
+    loop:
+        lw      $8,  0($16)
+        lw      $9,  4($16)
+        addu    $10, $8,  $9
+        sw      $10, 512($16)
+        addiu   $16, $16, 8
+        bne     $16, $12, loop
+}}}
+
+* Pour chacune des instructions de cette séquence, donnez les valeurs (en base 2) du numéro de ligne, index et déplacement de l'adresse de l'instruction, en complétant la table suivante : (Pour ne pas avoir à faire de calcul à la place du numéro de ligne, vous indiquerez l'adresse du premier octet de la ligne, que nous appellerons Adresse de ligne)
+
+{{{#!table width="50%"
+||= Instruction =||= Adresse de ligne =||= Index =||= Offset =||
+|| [[BR]] || [[BR]] || [[BR]] || [[BR]] ||
+|| [[BR]] || [[BR]] || [[BR]] || [[BR]] ||
+|| [[BR]] || [[BR]] || [[BR]] || [[BR]] ||
+|| [[BR]] || [[BR]] || [[BR]] || [[BR]] ||
+|| [[BR]] || [[BR]] || [[BR]] || [[BR]] ||
+|| [[BR]] || [[BR]] || [[BR]] || [[BR]] ||
+}}}
+
+{{{
+#!protected
+
+||= Instruction      =||= Adresse de ligne   =||= Index   =||= Déplacement   =||
+|| lw $8, 0($16)      ||  10  ||   0b10 ||        0b000 ||
+|| lw $9, 4($16)      ||  10  ||   0b10 ||        0b100 ||
+|| addu $10, $8, $9   ||  18  ||   0b11 ||        0b000 ||
+|| sw $10, 512($16)   ||  18  ||   0b11 ||        0b100 ||
+|| addiu $16, $16, 8  ||  20  ||   0b00 ||        0b000 ||
+|| bne $16, $12, loop ||  20  ||   0b00 ||        0b100 ||
+}}}
+
+* Complétez le tableau suivant en précisant si le chargement de l'instruction est un échec ou un succès.
+
+{{{#!table width="50%"
+||= Instruction =||= Échec ou succès =||
+|| [[BR]] || [[BR]] ||
+|| [[BR]] || [[BR]] ||
+|| [[BR]] || [[BR]] ||
+|| [[BR]] || [[BR]] ||
+|| [[BR]] || [[BR]] ||
+|| [[BR]] || [[BR]] ||
+}}}
+
+{{{
+#!protected
+||= Instruction      =||= Échec ou succès =||
+|| lw $8, 0($16)      ||            échec  ||
+|| lw $9, 4($16)      ||            succès ||
+|| addu $10, $8, $9   ||            échec  ||
+|| sw $10, 512($16)   ||            succès ||
+|| addiu $16, $16, 8  ||            échec  ||
+|| bne $16, $12, loop ||            succès ||
+}}}
+
+* Considérez une deuxième itération de la séquence d'instructions précédente (la condition de branchement `bne` est vérifiée et donc l'instruction située à l'adresse `0x00000010` est de nouveau exécutée). Modifiez le tableau précédent pour la 2ème itération de la boucle.
+
+{{{
+#!protected
+
+||= Instruction      =||= Échec ou succès =||
+|| lw $8, 0($16)      ||            succès ||
+|| lw $9, 4($16)      ||            succès ||
+|| addu $10, $8, $9   ||            succès ||
+|| sw $10, 512($16)   ||            succès ||
+|| addiu $16, $16, 8  ||            succès ||
+|| bne $16, $12, loop ||            succès ||
+}}}
+
+Considérons maintenant les lectures de données générées par la séquence d'instructions précédente. On suppose que le registre `$16` contient la valeur `0x00000110`, qui est l'adresse de base d'un tableau d'entiers Tab[] dont les valeurs ont été initialisées telles que  `Tab[i] = i`. Au démarrage de la boucle, le cache de données est supposé vide (ce qui signifie que les 4 lignes sont marquées invalides).
+
+* Complétez le tableau ci-dessous pour décrire le contenu du cache de données à la fin de la première itération de la boucle ? À la fin de la deuxième itération ? À la fin de la troisième ?
+
+{{{#!table width="50%"
+||= Validité =||= Adresse de ligne =||= Donnée 1 =||= Donnée 0 =||
+|| 0 || || || ||
+|| 0 || || || ||
+|| 0 || || || ||
+|| 0 || || || ||
+}}}
+
+{{{
+#!protected
+
+0x00000110 = 0...0 0001 0001 0000,,2,, : index = 2, déplacement = 0.
+
+* À la fin de la première itération :
+
+||= Validité =||= Adresse de ligne =||= Donnée 1 =||= Donnée 0 =||
+|| 0 || || || ||
+|| 0 || || || ||
+|| 1 || 0x110 || 0x00000001 || 0x00000000 ||
+|| 0 || || || ||
+
+* À la fin de la deuxième itération :
+
+||= Validité =||= Adresse de ligne =||= Donnée 1 =||= Donnée 0 =||
+|| 0 || || || ||
+|| 0 || || || ||
+|| 1 || 0x110 || 0x00000001 || 0x00000000 ||
+|| 1 || 0x118 || 0x00000003 || 0x00000002 ||
+
+* À la fin de la troisième itération :
+
+||= Validité =||= Adresse de ligne =||= Donnée 1 =||= Donnée 0 =||
+|| 1 || 0x120 || 0x00000005 || 0x00000004 ||
+|| 0 || || || ||
+|| 1 || 0x110 || 0x00000001 || 0x00000000 ||
+|| 1 || 0x118 || 0x00000003 || 0x00000002 ||
+
+}}}
+
+{{{#!comment
+
+== Exercice 2 ==
+
+On considère maintenant un processeur `MIPS32` possédant un cache de données à correspondance directe de 8 kibi octets organisé en lignes de 32 octets.
+
+Soit deux tableaux de 4096 entiers (un entier équivaut à 32 bits), implantés en mémoire aux adresses suivantes :
+
+* `X` : `0x00010000`
+* `Y` : `0x00014000`
+
+* Donnez les éléments des tableaux `X` et `Y` qui peuvent occuper le mot n°0 de la case n°3 du cache de données.
+
+{{{
+#!protected
+
+* Nombre de bits de l'index : log2 (taille du cache / taille de la ligne) = log2  (8192/32) = 8.
+ * il y a 256 lignes dans le cache.
+* Nombre de bits du déplacement : log2 (nombre d'octets dans ligne de cache) = log2 (32)= 5.
+
+* Mot n°0 : déplacement = `00000`
+* Case n°3 : index = `00000011`
+
+* Dans le tableau `X` :
+ * `0x10060` (X![24])
+ * `0x12060` (X![2072])
+* Dans le tableau `Y` :
+ * `0x14060` (Y![24])
+ * `0x16060` (Y![2072])
+
+}}}
+
+* Calculez le taux d'échecs dans le cache de données pour la boucle suivante (on suppose que la variable scalaire `S` est contenue dans un registre - donc jamais d'échec de cache lors de sa lecture) :
+
+{{{
+#!c
+    for (i = 0; i < 4096; i++) {
+        S = S + X[i] + Y[i];
+    }
+}}}
+
+{{{
+#!protected
+
+* Nombre d'accès : 2 * N (2 accès par itération).
+* Nombre d'échecs : à chaque accès, car X[i] et Y[i] sont en compétition pour la même case du cache.
+* Taux d'échecs = Nombre d'échecs / Nombre d'accès = 1.
+}}}
+
+* Si l'on suppose que le tableau `Y` est maintenant rangé à l'adresse `0x00014020`, calculez le nouveau taux d'échecs.
+
+{{{
+#!protected
+
+* Nombre d'accès : 2 * N
+* Nombre d'échecs : à chaque nouvelle ligne, c'est-à-dire tous les 8 accès = 2 * N / 8
+* Taux d'échecs = Nombre d'échecs / Nombre d'accès = 0.125.
+
+Le tableau `Y` a en fait été décalé d'une ligne de cache : on a fait du "padding" (bourrage).
+}}}
+
+}}}
+
+[[BR]]
+= 2) Influence des mémoires cache sur les performances
+
+== Préambule ==
+
+On cherche à évaluer l'influence des mémoires caches sur les performances du système. Pour évaluer la performance, on utilise comme mesure le nombre moyen de ''Cycles Par Instruction'' (CPI). 
+
+Dans un système mémoire ''parfait'', le taux de ''HIT'' est de 100% sur le cache d'instructions comme sur le cache de données : c'est-à-dire que toutes les requêtes de lecture du processeur vers la mémoire sont satisfaites immédiatement. Mais dans un système mémoire ''réel'', la capacité de stockage limitée des caches (cache d'instructions et cache de données) a pour effet de dégrader la performance : certaines requêtes de lecture font ''MISS'' (échec de cache), et le processeur est gelé pendant plusieurs cycles en attendant que la ligne de cache manquante soit lue en mémoire par le contrôleur du cache. Ces cycles de gel du processeur augmentent évidemment la valeur du nombre moyen de cycles par instruction (CPI). 
+
+Cette augmentation du CPI dépend évidemment du ''taux de MISS'' (proportion de requêtes du processeur qui font MISS), mais dépend également du ''coût du MISS'' (nombre moyen de cycles de gel pour rapatrier la ligne de cache manquante en cas de gel). En cas de MISS sur un cache L1, cache de 1^er^ niveau, le nombre de cycles de gel peut être très élevé (plusieurs centaines de cycles), s'il faut aller chercher la ligne de cache dans la mémoire externe. Le cache L2, ou cache de 2^ème^ niveau, joue le rôle d'un "accélérateur", qui permet de limiter le coût du MISS. Dans tous les calculs de ce TD, nous allons raisonner sur des valeurs moyennes.
+
+''Note : ces valeurs moyennes dépendent évidemment des programmes exécutés, et les valeurs proposées ci-dessous sont fournies à titre d'exemple.''
+
+Comme illustré ci-contre, on s'intéresse à une plateforme matérielle comportant un processeur `MIPS32`, possédant deux caches caches L1 séparés, pour les instructions et pour les données. Le cache de données suit une politique d'écriture ''write-through'' (toute requête d'écriture provenant du processeur est enregistrée dans un tampon d'écritures postées, puis transmise vers la mémoire). Compte-tenu de la taille des caches L1 et des applications exécutées, on observe que le taux de MISS moyen est de 4% sur le cache L1 d'instructions et de 8% sur le cache L1 des données.
+
+En cas de MISS sur un cache L1, le contrôleur du cache L1 s'adresse au cache L2, par l'intermédiaire d'un bus système de largeur 32 bits. On suppose que le processeur, les 2 caches L1, la ROM de démarrage, le bus système et le cache L2 sont intégrés sur la même puce, et fonctionnent à la même fréquence d'horloge. La largeur d'une ligne de cache est de 16 octets (soit 4 mots de 32 bits). En cas de MISS sur le cache L2, le contrôleur du cache L2 doit chercher la ligne de cache manquante dans la mémoire principale, qui est une mémoire externe à la puce.
+
+== 1. Système mémoire parfait ==
+
+On suppose que, pour le programme exécuté, on a mesuré les fréquences suivantes pour les différents types d'instruction exécutées par le processeur `MIPS32` :
+
+* opérations entre registres : 55%
+* branchements : 25%
+* lecture de données : 10%
+* écriture de données : 10%
+
+Le processeur `MIPS32` est un processeur ''RISC'' à architecture ''pipe-line''. Il est donc capable de démarrer l'exécution d'une instruction à chaque cycle, ce qui correspond en principe à un CPI de 1 cycle/instruction. Malheureusement, même avec un système mémoire parfait (pas de MISS sur les caches), la valeur du CPI est supérieure à 1, car certaines instructions ont une durée supérieure
+à un cycle : 
+* lorsque le processeur exécute une instruction de branchement, la durée effective de l'instruction est de 2 cycles au lieu de 1 cycle, que le branchement réussisse ou non.
+* lorsqu'une instruction de lecture de donnée en mémoire est suivie par une instruction qui utilise la donnée lue par la première (on dit qu'il y a une dépendance de donnée entre les 2 instructions), la durée effective de l'instruction de lecture est de 2 cycles au lieu de 1 cycle.[[BR]]
+'''Question''': Calculez la valeur '''CPI0''' (correspondant à un système mémoire ''parfait'') en supposant que 50% des instructions de lecture de donnée sont en dépendance avec l'instruction suivante.
+
+{{{
+#!protected
+Il faut faire une somme pondérée :
+
+CPI =     (0.55 * 1)    instructions entre registres \\
+           + (0.25 * 2)    instructions de branchement \\
+           + (0.10 * ((0.5 * 1) + (0.5 * 2)))    instructions de lecture de données \\
+           + (0.10 * 1)    instructions d'écriture 
+
+CPI = 1.3 cycle/instruction.
+
+Même avec un système mémoire ''parfait'', le processeur MIPS32 est "gelé"  23% du temps à cause des dépendances de données ou de contrôle.
+}}}
+
+== 2. Estimation du coût du MISS ==
+
+Lorsqu'une requête de lecture du processeur fait MISS sur un des deux caches L1, le processeur est gelé. Le contrôleur du cache L1 doit alors effectuer une transaction sur le bus système pour accéder au cache L2 pour récupérer la ligne. 
+Le temps nécessaire à récupérer la ligne manquante définit le **coût d'un MISS**. 
+Voyons qu'elles sont les étapes:
+1. Le cache L1 doit déclencher une lecture sur le bus système → 4 cycles 
+2. Le cache L2 doit lire la ligne (C'est un cache, il faut tenir compte qu'il peut aussi faire MISS) → 20 cycles
+3. La ligne doit être transférée sur le bus entre le cache L2 et le cache L1 →  4 cycles
+4. Le cache L1 doit mettre à jour la case recevant la ligne → 2 cycles
+
+En tenant compte des hypothèses précédentes, le coût moyen d'un MISS sur le cache L1 est donc de 30 cycles.
+On cherche à évaluer l'augmentation du CPI causée par les MISS sur le cache d'instructions. On note ''DCPI_ins'' cet accroissement. Puis à évaluer l'augmentation du CPI causée par les MISS sur le cache de données. On note ''DCPI_data'' cet accroissement.
+
+'''Question''': Calculez la valeur de ''DCPI_ins'', en utilisant le taux de MISS défini dans l'énoncé, et le coût du MISS de 30 cycles.
+
+{{{
+#!protected
+
+Toute instruction exécutée doit être lue dans le cache L1 d'instruction. Quatre instructions sur 100 font MISS et vont entraîner un gel du processeur pendant 32 cycles.
+
+Par conséquent :
+* DCPI_ins = 0.04 * 30 = 1.2 cycles.
+}}}
+
+'''Question''': Calculez la valeur de ''DCPI_data'', en utilisant le taux de MISS défini dans l'énoncé et le coût du MISS de 30 cycles.
+{{{
+#!protected
+
+Seulement 10% des instructions exécutées sont des instructions de lecture, et 8% de ces instructions font MISS et vont entraîner un gel du processeur pendant 32 cycles.
+
+Par conséquent :
+* DCPI_data = 0.1 * 0.08 * 30 = 0.24 cycle.
+}}}
+
+'''Question''': Sachant que 10% des instructions sont des écritures, expliquez pourquoi les écritures n'entraînent pas d'augmentation directe du CPI, bien que toute écriture entraîne un accès au bus système (politique ''write-through'') ?
+
+{{{
+#!protected
+Puisqu'on dispose d'un tampon d'écritures postées, le processeur n'est que très rarement gelé lorsqu'il exécute une instruction d'écriture. Cette écriture sera effectuée plus tard par l'automate contrôleur du cache, lorsque le bus sera disponible, et tout se passe comme si les écritures étaient exécutées en 1 cycle.
+}}}
+
+'''Question''': Faut-il traiter comme un cas particulier les situations où le processeurs émet simultanément (i.e. au même cycle) des requêtes d'instructions et de données qui font à la fois MISS sur le cache d'instructions et MISS sur le cache de données ? (cela est possible si l'on suppose un processeur pipeliné)
+
+{{{
+#!protected
+Puisque que le bus système n'effectue qu'une seule transaction à la fois, le processeur est gelé pendant deux fois 32 cycles lorsque la même instruction fait MISS sur le cache de d'instructions et fait également MISS sur le cache de données.
+}}}
+
+'''Question''': Quelle est finalement la valeur du nombre moyen de cycles par instruction ?
+
+{{{
+#!protected
+Tous les couts de MISS doivent donc être cumulés. Par conséquent :
+* CPI = CPI0 + DCPI_ins + DCPI_data = 1.3 + 1.2 + 0.24 = 2.74 cycles/instruction.
+}}}
+
+{{{#!html
+<h1><font size=+3> Partie TP</font></h1>
+}}}
+
+{{{#!html
+<h1><font size=+2> A) Étude du taux de miss en fonction du programme exécuté </font></h1>
+}}}
+
+== Préambule ==
+
+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. 
+
+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.
+
+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.
+
+== 1. Calcul du taux de MISS dans le cache d'instructions ==
+
+Commencez par recopier [htdocs:files/tp3.tgz tp3] dans votre répertoire de travail.
+
+{{{
+tp3
+├── 8_cache_miss
+│   ├── Makefile
+│   └── src
+│       ├── harch.c
+│       ├── harch.h
+│       ├── hcpu.S
+│       ├── hcpu.h
+│       ├── kernel.ld
+│       ├── kinit.c
+│       ├── klibc.c
+│       └── klibc.h
+└── 9_cache_perf
+    ├── Makefile
+    └── src
+        ├── harch.c
+        ├── harch.h
+        ├── hcpu.S
+        ├── hcpu.h
+        ├── jpeg.h
+        ├── kernel.ld
+        ├── kinit.c
+        ├── klibc.c
+        └── klibc.h
+}}}
+
+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 performance 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.
+
+* Allez dans le répertoire `8_cache_miss``
+* Ouvrez le fichier `src/kinit.c` et expliquez ce que fait, ici, la fonction `kinit()` ?
+
+{{{
+#!protected
+
+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és sur le terminal grâce à une troisième boucle `for`.
+}}}
+
+* 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`).
+ * Combien d'instructions sont exécutées à chaque itération de cette boucle ?
+ * Toutes les instructions de la boucle de calcul peuvent-elles être simultanément stockées dans le cache ?
+ * Que pouvez-vous en conclure ?
+
+{{{
+#!protected
+* La boucle commence à l'instruction `lw v0,24(sp)` et se termine à l'instruction `nop` qui suit l'instruction `bnez v0, kinit+0x50`.
+* 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ée à cause de l'effet retardé du branchement (`delayed slot` dû à l'architecture ''pipeline'').
+* 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.
+}}}
+
+* Vous allez renommer le fichier `kernel.x.s` en `kernel.myx.s` et y ajouter des commentaires (ce renommage permets 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 instruction par 4 (puisqu'une ligne de cache contient 4 instructions). 
+
+* 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. 
+
+{{{
+#!protected
+
+
+{{{
+004012dc <main>:
+  ...
+  401320:       1440fff5        bnez    v0,4012f8 <main+0x1c>
+  401324:       00000000        nop
+  401328:       afc00014        sw      zero,20(s8)
+  40132c:       081004fc        j       4013f0 <main+0x114>
+
+  # ligne de cache (ci-dessous) : case n°3
+  401330:       00000000        nop
+  401334:       8fc20018        lw      v0,24(s8)
+  401338:       afc20018        sw      v0,24(s8)
+  40133c:       8fc2001c        lw      v0,28(s8)
+  
+  # ligne de cache (ci-dessous) : case n°4
+  401340:       24420001        addiu   v0,v0,1
+  401344:       afc2001c        sw      v0,28(s8)
+  401348:       8fc20020        lw      v0,32(s8)
+  40134c:       24420002        addiu   v0,v0,2
+  
+  # ligne de cache (ci-dessous) : case n°5
+  401350:       afc20020        sw      v0,32(s8)
+  401354:       8fc20024        lw      v0,36(s8)
+  401358:       24420003        addiu   v0,v0,3
+  40135c:       afc20024        sw      v0,36(s8)
+
+  # ligne de cache (ci-dessous) : case n°6
+  401360:       8fc20028        lw      v0,40(s8)
+  401364:       24420004        addiu   v0,v0,4
+  401368:       afc20028        sw      v0,40(s8)
+  40136c:       8fc2002c        lw      v0,44(s8)
+
+  # ligne de cache (ci-dessous) : case n°7
+  401370:       24420005        addiu   v0,v0,5
+  401374:       afc2002c        sw      v0,44(s8)
+  401378:       8fc20030        lw      v0,48(s8)
+  40137c:       24420006        addiu   v0,v0,6
+
+  # ligne de cache (ci-dessous) : case n°0
+  401380:       afc20030        sw      v0,48(s8)
+  401384:       8fc20034        lw      v0,52(s8)
+  401388:       24420007        addiu   v0,v0,7
+  40138c:       afc20034        sw      v0,52(s8)
+
+  # ligne de cache (ci-dessous) : case n°1
+  401390:       8fc20038        lw      v0,56(s8)
+  401394:       24420008        addiu   v0,v0,8
+  401398:       afc20038        sw      v0,56(s8)
+  40139c:       8fc2003c        lw      v0,60(s8)
+
+  # ligne de cache (ci-dessous) : case n°2
+  4013a0:       24420009        addiu   v0,v0,9
+  4013a4:       afc2003c        sw      v0,60(s8)
+  4013a8:       8fc20040        lw      v0,64(s8)
+  4013ac:       2442000a        addiu   v0,v0,10
+
+  # ligne de cache (ci-dessous) : case n°3
+  4013b0:       afc20040        sw      v0,64(s8)
+  4013b4:       8fc20044        lw      v0,68(s8)
+  4013b8:       2442000b        addiu   v0,v0,11
+  4013bc:       afc20044        sw      v0,68(s8)
+
+  # ligne de cache (ci-dessous) : case n°4
+  4013c0:       8fc20048        lw      v0,72(s8)
+  4013c4:       2442000c        addiu   v0,v0,12
+  4013c8:       afc20048        sw      v0,72(s8)
+  4013cc:       8fc2004c        lw      v0,76(s8)
+
+  # ligne de cache (ci-dessous) : case n°5
+  4013d0:       2442000d        addiu   v0,v0,13
+  4013d4:       afc2004c        sw      v0,76(s8)
+  4013d8:       8fc20050        lw      v0,80(s8)
+  4013dc:       2442000e        addiu   v0,v0,14
+
+  # ligne de cache (ci-dessous) : case n°6
+  4013e0:       afc20050        sw      v0,80(s8)
+  4013e4:       8fc20014        lw      v0,20(s8)
+  4013e8:       24420001        addiu   v0,v0,1
+  4013ec:       afc20014        sw      v0,20(s8)
+ 
+  # ligne de cache (ci-dessous) : case n°7
+  4013f0:       8fc20014        lw      v0,20(s8)
+  4013f4:       2c4203e8        sltiu   v0,v0,1000
+  4013f8:       1440ffce        bnez    v0,401334 <main+0x58>
+  4013fc:       00000000        nop
+  ...
+}}}
+}}}
+
+* É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.
+
+{{{
+#!protected
+
+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.
+
+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. A 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%.
+}}}
+
+== 2. Analyse de trace ==
+
+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 :
+
+* -NICACHELEN : nombre de mots par case dans le cache instruction 
+* -NDCACHELEN : nombre de mots par case dans le cache data
+* -NICACHESET : nombre de cases dans le cache instruction
+* -NDCACHESET : nombre de cases dans le cache data
+
+* Lancez donc la simulation avec la commande suivante : `make cache`
+
+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.
+
+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`.
+ 
+* Relancez donc la simulation avec la commande suivante : `make cachetrace`\\(vous pouvez ouvrir le fichier `Makefile` pour voir la commande du simulateur).
+
+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.
+
+* À quel cycle est chargée dans le cache d'instructions la première instruction de la fonction `kinit()` ?
+* À quel cycle est chargée la  première ligne de cache contenant des instructions de la boucle de calcul ?
+* À quel cycle cette première ligne est-elle évincée par le chargement d'une autre ligne de cache ?
+* À quel cycle cette première ligne est-elle rechargée pour exécuter la deuxième itération de la boucle ?
+* A quel cycle est-elle rechargée pour exécuter la troisième itération?
+* Quelle est la durée (en nombre de cycles) de la première itération? 
+* Quelle est la durée des itérations suivantes? 
+
+{{{
+#!protected
+* 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.
+* 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.
+* Elle est évincée au cycle 572 pour stocker d'autres instructions situées vers la fin de la boucle.
+* Elle est rechargée pour la deuxième itération au cycle 666.
+
+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.
+}}}
+
+== 3. Mesure du taux de MISS ==
+
+Pour mesurer le taux de MISS sur le cache instruction, on peut activer l'option d'instrumentation `-STATS stats.txt`.
+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 :
+
+1. Le nombre de cycles simulés depuis le démarrage de la machine (incrément de 10 à chaque ligne),
+1. Le nombre d'instructions exécutées depuis le démarrage de la machine,
+1. Le nombre de MISS sur le cache d'instructions depuis le démarrage de la machine,
+1. Le nombre de lectures de données depuis le démarrage de la machine,
+1. Le nombre de MISS sur le cache de données depuis le démarrage de la machine,
+1. Le taux de MISS sur le cache d'instructions,
+1. Le taux de MISS sur le cache de données,
+1. Le CPI, qui est le nombre moyen de cycles par instruction.
+
+* Relancez donc la simulation avec la commande suivante : `make cachestats`\\(vous pouvez ouvrir le fichier `Makefile` pour voir la commande du simulateur).
+
+À 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 :
+
+{{{
+#!bash
+$ gnuplot
+}}}
+
+* Une fois dans ce logiciel (indiqué par l'invite de commande `'gnuplot> '`), vous pouvez entrer la commande :
+
+{{{
+#!bash
+plot 'stats.txt' using 1:6
+}}}
+
+''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.''
+
+* Comment expliquez-vous l'évolution du taux de MISS au cours du temps ?
+
+{{{
+#!protected
+Attention: les valeurs mesurées sont des moyennes cumulées depuis le début de la simulation...
+
+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).
+}}}
+
+== 4. Optimisation du code pour minimiser le taux de MISS ==
+
+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.
+
+* 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.
+
+* É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).
+
+* Editez le fichier `Makefile` pour que la simulation avec statistique produise le fichier `stats_nomiss.txt`.
+
+* Relancez la simulation pour 100000 cycles, en changeant le nom du fichier de statistiques : `make cachestat`
+
+* À 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 :
+
+{{{
+#!bash
+plot 'stats.txt' using 1:6
+replot 'stats_nomiss.txt' using 1:6
+}}}
+
+* Comment expliquez-vous l'évolution du taux de MISS pour cette nouvelle version de l'application ?
+
+{{{
+#!protected
+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.
+}}}
+
+
+{{{#!html
+<h1><font size=+2> B) mesures de performance du processeur en fonction de la taille des caches</font></h1>
+}}}
+
+
+== Préambule ==
+
+Le but de cette seconde partie du TP est de vérifier expérimentalement l'évolution de la performance du processeur (mesurée en CPI) en fonction de la taille des cache. Vous allez faire varier les capacités des caches L1 d'instructions et données, et vous allez mesurer la durée d'exécution d'une application logicielle un peu plus complexe que la précédente. La largeur des lignes des deux caches est fixée à 16 octets (soit 4 mots). Vous ferez donc varier la capacité des deux caches, en faisant varier le nombre de cases. Le code est dans le répertoire `9_cache_perf`.
+
+=== Logiciel ===
+
+L'application logicielle proposée pour ce TP effectue un calcul de traitement d'image appelé ''transformation cosinus inverse'' (IDCT). Cette transformation est une variante de la ''transformée de Fourier'' à deux dimensions. L'application traite une image en découpant cette image en blocs de (8 * 8) pixels. Elle est écrite en langage C, et vous pouvez trouver son contenu dans le fichier `main.c`. Il n'est pas indispensable de comprendre en détail l'algorithme IDCT pour faire ce TP.
+
+=== Matériel ===
+
+Comme vous l'avez constaté au TP précédent, le simulateur `almo1.x` permet de faire varier la capacité des caches L1, grâce à deux arguments à passer sur la ligne de commande :
+* `-NICACHESET`, qui spécifie le nombre de cases du cache d'instructions,
+* `-NDCACHESET`, qui spécifie le nombre de cases du cache de données.
+
+ ''Attention : les valeurs que l'on peut donner pour ces deux arguments doivent être des puissances de 2.''
+
+En utilisant l'argument `-STATS` sur la ligne de commande, vous pouvez obtenir les statistiques sur les taux de MISS et le CPI.
+
+Le simulateur `almo1.x` permet de rediriger la sortie texte vers un fichier plutôt que de l'afficher sur le terminal TTY, comme habituellement). Pour cela, avant de lancer la simulation, il faut entrer la commande :
+
+{{{
+#!bash
+$ export SOCLIB_TTY=FILES
+}}}
+
+Pour revenir à l'affichage dans une fenêtre TTY, taper la commande :
+
+{{{
+#!bash
+$ export SOCLIB_TTY=TTY
+}}}
+
+== 1. Caches de faible capacité ==
+
+* Vous allez compiler le code et lancez le simulateur avec des caches L1 (instructions et données) dont la capacité est d'une seule ligne de cache (une seule case), en activant la génération des statistiques. Chaque cache a donc une capacité de 16 octets. Notez au passage comment changer le comportement des commandes en changeant la valeur des variables du Makefile.
+
+{{{
+#!bash
+$ make cachestat NICACHESET=1 NDCACHESET=1
+}}}
+
+* Quel est le CPI (nombre moyen de ''Cycles Par Instruction'') pour ces tailles de cache ?
+* Quel est le temps d'exécution de l'application (en nombre de cycles) ?
+
+* Relancez la simulation en doublant la capacité des caches à 32 octets (2 cases). Que constatez vous concernant le temps d'exécution et le CPI ?
+
+ ''Attention : pour ne pas biaiser la mesure, il faut relever la valeur du CPI dans le fichier `stats` à la date où l'application se termine (ni avant, ni après).''
+
+== 2. Caches de capacité "normale" ==
+
+* Faites varier la taille du cache d'instructions de 4 à 1024 cases par puissance de 2, et notez à chaque fois le CPI et le temps de calcul obtenus. Vous utiliserez comme taille de cache de données `NDCACHESET=1024` (cache de 16 kibi octets).
+
+* Faites varier la taille du cache de données de 1 à 1024 cases par puissance de 2, et notez à chaque fois le CPI et le temps de calcul obtenus. Vous utiliserez comme taille de cache d'instructions `NICACHESET=1024` (cache de 16 kibi octets).
+
+* Pour cette application logicielle, quelles tailles de caches pensez-vous qu'il faille choisir pour obtenir (approximativement) les taux de MISS correspondant aux hypothèses vues en TD ?
+
+== 3. Caches désactivés ==
+
+* Relancez l'exécution du simulateur en désactivant les deux caches, c'est-à-dire en utilisant les valeurs : `NICACHESET=0` et `NDCACHE =0`.
+ * Quelle est la durée d'exécution du programme ?
+ * Quelle est la valeur du CPI ?
+
+== 4. Représentation graphique ==
+
+* En reprenant vos résultats de l'exercice 2, créez un fichier texte dans lequel vous mettrez à chaque ligne le nombre de lignes du cache d'instructions et la valeur du CPI que vous avez obtenue pour ce nombre. Le format d'une ligne de ce fichier doit être le suivant :
+
+{{{
+...
+NB_LIGNES_ICACHE CPI
+NB_LIGNES_ICACHE CPI
+NB_LIGNES_ICACHE CPI
+...
+}}}
+
+* Utilisez l'outil `gnuplot` pour visualiser la courbe représentant l'évolution du CPI en fonction de la taille du cache d'instructions.
+
+* Refaites la même opération pour le cache de données, afin de générer la courbe représentant l'évolution du CPI en fonction de la taille du cache de données.