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


Ignore:
Timestamp:
Mar 19, 2022, 2:02:05 PM (3 years ago)
Author:
franck
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • AS6-TME-B4

    v1 v2  
     1[[PageOutline]]
     2{{{#!html
     3<h1><font size=+2> Cache L1 à correspondance directe - performance</font></h1>
     4}}}
     5
    16{{{#!protected
    2 {{{#!html
    3 <h1><font size=+3> Partie TD</font></h1>
    4 }}}
    5 
    6 {{{#!html
    7 <h1><font size=+2> Remplissage des caches </font></h1>
    8 }}}
    9 
     7= A. Questions de cours
     8
     91. Question ?
     10{{{#!protected
     11'''
     12* réponse
     13'''
     14}}}
     15
     16= B. Influence des mémoires cache sur les performances
    1017
    1118== Préambule ==
    1219
    13 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.
    14 
    15 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).
    16 
    17 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.
    18 
    19 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.).
    20 
    21 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.
    22 
    23 == Exercice ==
    24 
    25 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).
    26 
    27 ''Rappel : toutes les adresses émises par le processeur sont des adresses octets, et les adresses sont codées sur 32 bits.''
    28 
    29 * Dites comment le contrôleur du cache interprète une adresse :
    30  * quel est le nombre de bits de l'index ?
    31  * quel est le nombre de bits du déplacement (''offset'') ?
    32  * quel est le nombre de bits de l'étiquette (''tag'') ?
    33 
    34 {{{
    35 #!protected
    36 
    37 * Nombre de bits de l'index : log2 (capacité du cache / largeur de la ligne) = log2  (8/2) =  2.
    38 * Nombre de bits du déplacement : log2 (nombre d'octets dans la ligne de cache) = log2 (2*4)= 3.
    39 * Nombre de bits de l'étiquette : taille totale de l'adresse - taille de l'index - taille de l'offset = 32 - 2 - 3 = 27.
    40 
    41 Il faut dire aux étudiants qu'ils auront besoin de ces formules pour l'examen !
    42 }}}
    43 
    44 Considérons la séquence d'instructions suivante dont la première instruction est stockée à l'adresse `loop = 0x00000010` :
    45 
    46 {{{
    47 #!asm
    48     loop:
    49         lw      $8,  0($16)
    50         lw      $9,  4($16)
    51         addu    $10, $8,  $9
    52         sw      $10, 512($16)
    53         addiu   $16, $16, 8
    54         bne     $16, $12, loop
    55 }}}
    56 
    57 * 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)
    58 
    59 {{{#!table width="50%"
    60 ||= Instruction =||= Adresse de ligne =||= Index =||= Offset =||
    61 || [[BR]] || [[BR]] || [[BR]] || [[BR]] ||
    62 || [[BR]] || [[BR]] || [[BR]] || [[BR]] ||
    63 || [[BR]] || [[BR]] || [[BR]] || [[BR]] ||
    64 || [[BR]] || [[BR]] || [[BR]] || [[BR]] ||
    65 || [[BR]] || [[BR]] || [[BR]] || [[BR]] ||
    66 || [[BR]] || [[BR]] || [[BR]] || [[BR]] ||
    67 }}}
    68 
    69 {{{
    70 #!protected
    71 
    72 ||= Instruction      =||= Adresse de ligne   =||= Index   =||= Déplacement   =||
    73 || lw $8, 0($16)      ||  10  ||   0b10 ||        0b000 ||
    74 || lw $9, 4($16)      ||  10  ||   0b10 ||        0b100 ||
    75 || addu $10, $8, $9   ||  18  ||   0b11 ||        0b000 ||
    76 || sw $10, 512($16)   ||  18  ||   0b11 ||        0b100 ||
    77 || addiu $16, $16, 8  ||  20  ||   0b00 ||        0b000 ||
    78 || bne $16, $12, loop ||  20  ||   0b00 ||        0b100 ||
    79 }}}
    80 
    81 * Complétez le tableau suivant en précisant si le chargement de l'instruction est un échec ou un succès.
    82 
    83 {{{#!table width="50%"
    84 ||= Instruction =||= Échec ou succès =||
    85 || [[BR]] || [[BR]] ||
    86 || [[BR]] || [[BR]] ||
    87 || [[BR]] || [[BR]] ||
    88 || [[BR]] || [[BR]] ||
    89 || [[BR]] || [[BR]] ||
    90 || [[BR]] || [[BR]] ||
    91 }}}
    92 
    93 {{{
    94 #!protected
    95 ||= Instruction      =||= Échec ou succès =||
    96 || lw $8, 0($16)      ||            échec  ||
    97 || lw $9, 4($16)      ||            succès ||
    98 || addu $10, $8, $9   ||            échec  ||
    99 || sw $10, 512($16)   ||            succès ||
    100 || addiu $16, $16, 8  ||            échec  ||
    101 || bne $16, $12, loop ||            succès ||
    102 }}}
    103 
    104 * 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.
    105 
    106 {{{
    107 #!protected
    108 
    109 ||= Instruction      =||= Échec ou succès =||
    110 || lw $8, 0($16)      ||            succès ||
    111 || lw $9, 4($16)      ||            succès ||
    112 || addu $10, $8, $9   ||            succès ||
    113 || sw $10, 512($16)   ||            succès ||
    114 || addiu $16, $16, 8  ||            succès ||
    115 || bne $16, $12, loop ||            succès ||
    116 }}}
    117 
    118 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).
    119 
    120 * 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 ?
    121 
    122 {{{#!table width="50%"
    123 ||= Validité =||= Adresse de ligne =||= Donnée 1 =||= Donnée 0 =||
    124 || 0 || || || ||
    125 || 0 || || || ||
    126 || 0 || || || ||
    127 || 0 || || || ||
    128 }}}
    129 
    130 {{{
    131 #!protected
    132 
    133 0x00000110 = 0...0 0001 0001 0000,,2,, : index = 2, déplacement = 0.
    134 
    135 * À la fin de la première itération :
    136 
    137 ||= Validité =||= Adresse de ligne =||= Donnée 1 =||= Donnée 0 =||
    138 || 0 || || || ||
    139 || 0 || || || ||
    140 || 1 || 0x110 || 0x00000001 || 0x00000000 ||
    141 || 0 || || || ||
    142 
    143 * À la fin de la deuxième itération :
    144 
    145 ||= Validité =||= Adresse de ligne =||= Donnée 1 =||= Donnée 0 =||
    146 || 0 || || || ||
    147 || 0 || || || ||
    148 || 1 || 0x110 || 0x00000001 || 0x00000000 ||
    149 || 1 || 0x118 || 0x00000003 || 0x00000002 ||
    150 
    151 * À la fin de la troisième itération :
    152 
    153 ||= Validité =||= Adresse de ligne =||= Donnée 1 =||= Donnée 0 =||
    154 || 1 || 0x120 || 0x00000005 || 0x00000004 ||
    155 || 0 || || || ||
    156 || 1 || 0x110 || 0x00000001 || 0x00000000 ||
    157 || 1 || 0x118 || 0x00000003 || 0x00000002 ||
    158 
    159 }}}
    160 
    161 {{{#!comment
    162 
    163 == Exercice 2 ==
    164 
    165 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.
    166 
    167 Soit deux tableaux de 4096 entiers (un entier équivaut à 32 bits), implantés en mémoire aux adresses suivantes :
    168 
    169 * `X` : `0x00010000`
    170 * `Y` : `0x00014000`
    171 
    172 * 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.
    173 
    174 {{{
    175 #!protected
    176 
    177 * Nombre de bits de l'index : log2 (taille du cache / taille de la ligne) = log2  (8192/32) = 8.
    178  * il y a 256 lignes dans le cache.
    179 * Nombre de bits du déplacement : log2 (nombre d'octets dans ligne de cache) = log2 (32)= 5.
    180 
    181 * Mot n°0 : déplacement = `00000`
    182 * Case n°3 : index = `00000011`
    183 
    184 * Dans le tableau `X` :
    185  * `0x10060` (X![24])
    186  * `0x12060` (X![2072])
    187 * Dans le tableau `Y` :
    188  * `0x14060` (Y![24])
    189  * `0x16060` (Y![2072])
    190 
    191 }}}
    192 
    193 * 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) :
    194 
    195 {{{
    196 #!c
    197     for (i = 0; i < 4096; i++) {
    198         S = S + X[i] + Y[i];
    199     }
    200 }}}
    201 
    202 {{{
    203 #!protected
    204 
    205 * Nombre d'accès : 2 * N (2 accès par itération).
    206 * Nombre d'échecs : à chaque accès, car X[i] et Y[i] sont en compétition pour la même case du cache.
    207 * Taux d'échecs = Nombre d'échecs / Nombre d'accès = 1.
    208 }}}
    209 
    210 * Si l'on suppose que le tableau `Y` est maintenant rangé à l'adresse `0x00014020`, calculez le nouveau taux d'échecs.
    211 
    212 {{{
    213 #!protected
    214 
    215 * Nombre d'accès : 2 * N
    216 * Nombre d'échecs : à chaque nouvelle ligne, c'est-à-dire tous les 8 accès = 2 * N / 8
    217 * Taux d'échecs = Nombre d'échecs / Nombre d'accès = 0.125.
    218 
    219 Le tableau `Y` a en fait été décalé d'une ligne de cache : on a fait du "padding" (bourrage).
    220 }}}
    221 
    222 }}}
    223 
    224 [[BR]]
    225 = 2) Influence des mémoires cache sur les performances
    226 
    227 == Préambule ==
    228 
    22920On 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).
    23021
    … …  
    23526''Note : ces valeurs moyennes dépendent évidemment des programmes exécutés, et les valeurs proposées ci-dessous sont fournies à titre d'exemple.''
    23627
    237 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.
     28Comme illustré ci-contre, on s'intéresse à une plateforme matérielle comportant un processeur `MIPS32`, possédant deux 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.
    23829
    23930En 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.
    … …  
    27465Voyons qu'elles sont les étapes:
    275661. Le cache L1 doit déclencher une lecture sur le bus système → 4 cycles
    276 2. Le cache L2 doit lire la ligne (C'est un cache, il faut tenir compte qu'il peut aussi faire MISS) → 20 cycles
     672. Le cache L2 doit lire la ligne (c'est un cache, il faut tenir compte qu'il peut aussi faire MISS) → 20 cycles
    277683. La ligne doit être transférée sur le bus entre le cache L2 et le cache L1 →  4 cycles
    278694. Le cache L1 doit mettre à jour la case recevant la ligne → 2 cycles
    … …  
    30293}}}
    30394
    304 '''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'') ?
     95'''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'') ?
    30596
    30697{{{
    … …  
    309100}}}
    310101
    311 '''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é)
    312 
    313 {{{
    314 #!protected
    315 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.
     102'''Question''': Faut-il traiter comme un cas particulier les situations où le processeur é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é)
     103
     104{{{
     105#!protected
     106Puisque 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 d'instructions et fait également MISS sur le cache de données.
    316107}}}
    317108
    … …  
    371162}}}
    372163
    373 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.
     164Ce 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.
    374165
    375166* Allez dans le répertoire `8_cache_miss``
    … …  
    379170#!protected
    380171
    381 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`.
     172La 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`.
    382173}}}
    383174
    … …  
    390181#!protected
    391182* La boucle commence à l'instruction `lw v0,24(sp)` et se termine à l'instruction `nop` qui suit l'instruction `bnez v0, kinit+0x50`.
    392 * 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'').
     183* 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'').
    393184* 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.
    394185}}}
    395186
    396 * 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).
     187* 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).
    397188
    398189* 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.
    … …  
    4982891ere 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.
    499290
    500 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%.
     291Ité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%.
    501292}}}
    502293