wiki:AS6-TME-B3

INDEX

  2. A. Questions de cours
  3. B. Exercices
    1. B.1. Remplissage des cases de cache
    2. B.2. Cas de collision de lignes
  4. C. Travaux pratiques
    1. C.1. Calcul du taux de MISS dans le cache d'instructions
    2. C.2. Analyse de trace
    3. C.3. Mesure du taux de MISS
    4. C.4. Optimisation du code pour minimiser le taux de MISS

DOCS → [Config] [MIPS U] [MIPS K] [​markdown] [CR.md]
COURS → [1 (+code) (+outils)] [2] [3] [4] [5] [6] [7] [8] [9]
TME → [1] [2] [3] [4] [5] [6] [7] [8] [9]
CODE → [gcc + soc] [1] [2] [3] [4] [5] [6] [7] [8] [9]

3 - Cache L1 à correspondance directe - principes

Vous pouvez lire les slides de cours pour voir les détails, mais voici le résumé des principes en quelques lignes.

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 temporelle des applications logicielles. En effet, il est fort probable que, 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 qu’elle 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 (parce que la propriété de localité spatiale est moins grande si on est trop loin l'adresse lue). Un Segment d'adresse aligné signifie que l'adresse du premier octet du segment est un 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. À 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 range dans des cases de caches. Attention case de cache et ligne de cache ne sont pas synonymes. Une ligne de cache est un contenu alors qu'une case de cache est un contenant. À 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éfinisse directement le numéro de la case. Ce choix est celui des 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 cases, 3 bits s'il y a 8 cases, [...], 10 bits s'il y a 1024 cases, etc.).

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 2n = nombre de cases de cache.

Le but de cette première séance sur les caches est de répondre à trois questions :

  • Comment les caches se remplissent en fonction de la position des instructions et des données en mémoire (leurs adresses) et en fonction de la taille des caches.
  • Comment calculer le taux de miss du cache instruction lors de l'exécution d'une boucle d'instructions
  • Comment calculer le taux de miss du cache de données de l'usage de donnée par les instructions de leur position en mémoire

A. Questions de cours

  1. Que signifie bus système ?
  2. À quoi sert l'arbitre du bus système ?
  3. Qu'est un contrôleur mémoire ?
  4. La "localité spatiale" et la "localité temporelle" sont deux propriétés des programmes, que représentent-elles ?
  5. Où sont placés les caches ?
  6. Peut-on avoir plusieurs niveaux de cache ?
  7. Que signifient "caches séparés" et "cache unifié" ?
  8. Quelle est la répartition des types d'instructions dans un programme ?
  9. Pourquoi les lectures sont bloquantes et les écritures sont non bloquantes ?
  10. Qu'est un taux de MISS et quels sont les taux normaux ?
  11. Qu'est-ce qu'une "ligne de cache" ?
  12. Qu'est-ce qu'une "case de cache" ?
  13. Que veut dire cache à correspondance directe ?
  14. Que sont un numéro de ligne, un tag, un index et un offset de cache ?
  15. Qu'est-ce que le tampon d'écriture ?
  16. Quel est le principal inconvénient des caches à correspondance directe ?

B. Exercices

B.1. Remplissage des cases de cache

Vous avez le corrigé de l'exercice, mais nous vous conseillons vraiment de ne pas le regarder avant d'avoir vraiment essayé de répondre aux questions, parce que vous aurez ce genre d'exercice à l'examen et ce sera sans document.

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) ?

Considérons la séquence d'instructions suivante dont la première instruction est stockée à l'adresse loop = 0x00000010 : 

    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)
    Instruction Adresse de ligne Index Offset
























  • Complétez le tableau suivant en précisant si le chargement de l'instruction est un échec ou un succès.
    Instruction Échec ou 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 2e itération de la boucle.

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 ?
    Validité Adresse de ligne Donnée 1 Donnée 0
    0
    0
    0
    0

B.2. Cas de collision de lignes

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.
  • 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) : 
    for (i = 0; i < 4096; i++) {
    S = S + X[i] + Y[i];
}
  • Si l'on suppose que le tableau Y est maintenant rangé à l'adresse 0x00014020, calculez le nouveau taux d'échecs.

C. Travaux pratiques

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, plus précisément l'étude du taux de miss de cache L1 en fonction du programme exécuté.

On a choisi des lignes de cache de 16 octets et des caches de très 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 (sous-entendu correspondance directe entre le numéro de ligne de cache et le numéro de case de cache). 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 s'il est absent.

Pour ce TP, vous utiliserez le simulateur almo1.x, qui peut produire des fichiers d'instrumentation permettant de suivre l'évolution des caches L1 au cours du temps. Commencez par recopier le code du tp3 dans votre répertoire de travail (l'archive est accessible dans l'INDEX en haut de cette page). 

tp3
├── Makefile
└── src
    ├── harch.c
    ├── harch.h
    ├── hcpu.S
    ├── hcpu.h
    ├── kernel.ld
    ├── kinit.c
    ├── klibc.c
    └── klibc.h

C.1. Calcul du taux de MISS dans le cache d'instructions

Ce répertoire tp3 contient 1 répertoire. Il va permettre de voir l'évolution des miss de cache. Tous les fichiers nécessaires à la génération du code binaire kernel.x se trouvent dans le fichier src, le fichier Makefile permet de générer l'exécutable et les fichiers de trace. 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 tp3

  1. Ouvrez le fichier src/kinit.c et expliquez ce que fait la fonction kinit() dans le cadre de ce TP ?
  2. 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 ?
  3. 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).
  4. 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.
  5. É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.

C.2. Analyse de trace

Vous allez maintenant tenter de valider ce calcul du taux de MISS par la simulation. Dans le fichier Makefile, vous pouvez voir de nouvelles règles : cachetrace et cachestats qui lancent le simulateur en lui demandant d'afficher les états successifs des caches et des statistiques. Elles imposent aussi 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

Pour observer précisément le comportement des caches, le simulateur dispose donc d'une option d'instrumentation -TRACE cache.txt qui produit le fichier cache.txt permettant de visualiser le contenu des caches instructions et data au cours du temps. Les fichiers de trace du cache étant très volumineux, on a limité à 5000 le nombre de cycles simulés en utilisant l'option -NCYCLES 5000.

Vous pouvez ouvrir le fichier Makefile pour voir la commande du simulateur avec ces options. La règle cachetrace du Makefile lance le simulateur avec le mode TRACE afin d'obtenir la trace de remplissage du cache, mais également avec le mode DEBUG que vous connaissez déjà afin de générer la trace d'exécution du programme. Comprenez bien que ce sont deux traces du même programme, mais de nature très différente.

A titre d'illustration, si vous exécutez la commande : make cachetrace, voici ce que vous pouvez observer au tout début des fichiers trace0.s et cache.txt, relativement à l'exécution de la première instruction du code de boot :

trace0.s 

K    12:     <boot> ------------------------------------------------------- ./src/hcpu.S
K    12:     0xbfc00000 0x3c1d8040  lui sp,0x8040
K    13:     0xbfc00004 0x27bd0000  addiu   sp,sp,0
K    14:     0xbfc00008 0x3c1a8000  lui k0,0x8000
K    15:     0xbfc0000c 0x275a0210  addiu   k0,k0,528
K    26:     0xbfc00010 0x03400008  jr  k0
K    27:     0xbfc00014 0x00000000  nop
K    37:     <kinit> ------------------------------------------------------ ./src/kinit.c
K    37:     0x80000210 0x27bdffa0      addiu   sp,sp,-96
[...]

cache.txt 

*****************************  cycle 10       INSTRUCTION
 V / way 0 / set 0 / @ = BFC00000 / 275A0210 3C1A8000 27BD0000 3C1D8040
   / way 0 / set 1 / @ = 00000010 / 00000000 00000000 00000000 00000000
   / way 0 / set 2 / @ = 00000020 / 00000000 00000000 00000000 00000000
   / way 0 / set 3 / @ = 00000030 / 00000000 00000000 00000000 00000000
   / way 0 / set 4 / @ = 00000040 / 00000000 00000000 00000000 00000000
   / way 0 / set 5 / @ = 00000050 / 00000000 00000000 00000000 00000000
   / way 0 / set 6 / @ = 00000060 / 00000000 00000000 00000000 00000000
   / way 0 / set 7 / @ = 00000070 / 00000000 00000000 00000000 00000000
[...]

On voit que la première instruction lui sp,0x8040 a le code binaire 0x3c1d8040 et que cette instruction a été rangé dans le mot 0 (à gauche) dans la case 0 du cache (c'est le numéro de set). Lors de la lecture de cette instruction, les 3 autres instructions de la même ligne ont aussi été chargée.
Le fichier cache.txt représente l'état, ici au cycle 10, des 8 cases du cache. La case d'index 0 (notée ici set 0) est valide V, c'est-à-dire qu'elle contient la ligne de l'espace d'adressage dont l'adresse du premier octet est BFC00000 (on n'indique pas le numéro de ligne, mais l'adresse de ligne par souci de lisibilité, si ce n'est pas clair pour vous, demandez-moi ou relisez le cours).
Le numéro de way c'est pour les caches n-way-set-associative, qui permettent d'avoir plusieurs ways (c'est-à-dire plusieurs cases) possibles pour chaque ligne. En fait, un cache direct-mapped est un cache 1-way-set-associative.
Notez aussi, qu'au cycle 10 la ligne est déjà dans le cache, mais que l'instruction n'est exécutée que 2 cycles plus tard.

  1. Commencez par lancer la simulation normalement avec la commande : make exec

    Vous devriez voir les résultats s'afficher dans la fenêtre du TTY, avec la date à laquelle le programme 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.
    A quelle numéro de cycles s'affiche le message EXIT
  2. Relancez le simulateur pour avoir l'histoire du cache avec make tracecache:

    Une fois la simulation terminée, ouvrez dans 4 fenêtres différentes (1) le fichier source src/kinit.c ; (2) le fichier kernel.x.s contenant le code désassemblé ; (3) le fichier de trace d'exécution du processeur trace0.txt contenant la séquence des instructions exécutées par le MIPS au cours du temps et, enfin (4) le fichier de trace du cache cache.txt contenant les états successifs des caches data et instruction au cours du temps.
    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 du corps de la boucle de calcul ? (on peut la repérer parce la boucle de calcul fait beaucoup de fois la même chose)
    • À 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 ? Et à quelle cycle cette première instruction est ré-exécutée pour la seconde itération ?
    • Quelle est la durée (en nombre de cycles) de la première itération?
    • À quel cycle est-elle ré-exécutée à la troisième itération?
    • Quelle est la durée des itérations suivantes?

C.3. Mesure du taux de MISS

Pour mesurer le taux de MISS sur le cache instruction, nous allons activer l'option d'instrumentation -STATS stats.txt du simulateur de la machine almo1.X. Cette option permet de produire un fichier nommé stats.txt. Ce fichier stats.txt contient des informations statistiques de comportement du cache. Pour ce faire, le simulateur relève à intervalles réguliers (tous les 10 cycles) différents compteurs du simulateur permettant de caractériser l'activité des caches L1.

  • 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),
    2. Le nombre d'instructions exécutées depuis le démarrage de la machine,
    3. Le nombre de MISS sur le cache d'instructions depuis le démarrage de la machine,
    4. Le nombre de lectures de données depuis le démarrage de la machine,
    5. Le nombre de MISS sur le cache de données depuis le démarrage de la machine,
    6. Le taux de MISS sur le cache d'instructions,
    7. Le taux de MISS sur le cache de données,
    8. Le CPI, qui est le nombre moyen de cycles par instruction.

Relancez la simulation avec la commande shell suivante : make cachestats
Vous pouvez ouvrir le fichier Makefile pour voir comment est appliquée l'option STATS au simulateur.
À l'aide de l'outil 'gnuplot' (s'il n'est pas installé sur votre machine personnelle, vous devrez l'installer), 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 : 

$ gnuplot

Une fois dans ce logiciel (indiqué par l'invite de commande 'gnuplot> '), vous pouvez entrer la commande : 

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.
Attention : les valeurs mesurées sont des moyennes cumulées depuis le début de la simulation...

  1. Comment expliquez-vous l'évolution du taux de MISS au cours du temps ?

C.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 kinit.c actuel dans un autre fichier (par exemple, kinit_orig.c) afin de garder une sauvegarde du fichier original. Puis, ouvrez le fichier kinit.c et modifiez la fonction kinit() 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).
  • Éditez 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
  • Enfin, à l'aide de gnuplot, affichez sur le même graphique les résultats des exercices C.3. et C.4., afin de les comparer. Pour cela, entrez les deux commandes suivantes : 
    plot 'stats.txt' using 1:6
replot 'stats_nomiss.txt' using 1:6
  1. Comment expliquez-vous l'évolution du taux de MISS pour cette nouvelle version de l'application ?
Last modified 9 months ago Last modified on Feb 13, 2024, 8:11:05 PM