ALMO TP n°5 - Mémoires Cache

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. Nous allons pour cela exécuter sur la plateforme matérielle que vous connaissez déjà (voir figure ci-contre) une application écrite en C et compilée avec GCC.

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 simul_almo_generic, 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 dans votre répertoire de travail, les fichiers source spécifiques pour ce TP5 :

$ cp -r /Infos/lmd/2019/licence/ue/LU3IN004-2019oct/sesi-almo/soft/tp05/sujet   ./tp05
$ cd tp05

Ce répertoire contient tous les fichiers nécessaires à la génération des codes binaires, dont un fichier Makefile permettant de générer automatiquement les deux exécutables, sys.bin et app.bin. Dans un premier temps vous utiliserez sans modifications le fichier fourni main.c.

• Ouvrez le fichier main.c et expliquez ce que fait la fonction main() ?

• Lancez l'exécution du Makefile, puis examinez le code assembleur correspondant à l'application logicielle (app.bin.txt). 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 ?

• En éditant le fichier app.bin.txt, déterminez, pour chaque instruction de la boucle de calcul, à quelle ligne de cache cette instruction appartient. On regroupera les 51 instructions du corps de boucle par groupe de 4 (puisqu'une ligne de cache contient 4 instructions).

Attention, la première instruction de la boucle de calcul ne correspond pas à un début de ligne de cache. Il faut donc considérer 13 lignes de caches pour couvrir les 51 instructions du corps de boucle.

• 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.

• É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.

2. Analyse de trace

Vous allez maintenant tenter de valider ce calcul du taux de MISS par la simulation. Commencez par lancer le simulateur simul_almo_generic en spécifiant les deux arguments suivants sur la ligne de commande :

• -NICACHE 8 : définit le nombre de cases du cache L1 d'instructions (ici, 8 cases).
• -NDCACHE 8 : définit le nombre de cases du cache L1 de données (ici, 8 cases).

• Lancez donc la simulation avec la commande suivante :

  $ simul_almo_generic -SYS sys.bin -APP app.bin -NICACHE 8 -NDCACHE 8
  

Vous devriez voir les résultats s'afficher dans la fenêtre du TTY. 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_file, pour obtenir un fichier trace_file permettant de visualiser le contenu des caches au cours du temps. Les fichiers de trace étant très volumineux, on limitera à 5000 le nombre de cycles simulés en utilisant l'option -NCYCLES 5000.

• Relancez donc la simulation avec la commande suivante :

  $ simul_almo_generic -SYS sys.bin -APP app.bin -NICACHE 8 -NDCACHE 8  -TRACE trace_file -NCYCLES 5000
  

Une fois la simulation terminée, ouvrez dans deux fenêtres différentes le fichier de trace trace_file, contenant les états successifs des caches, et le fichier app.bin.txt 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 main() ?
• À 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?

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_file. Le fichier stats_file 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),
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 (colonne 3 / colonne 2),
7. Le taux de MISS sur le cache de données (colonne 5 / colonne 4),
8. Le CPI, qui est le nombre moyen de cycles par instruction (colonne 1 / colonne 2).

• Relancez donc la simulation avec la commande suivante :

  $ simul_almo_generic -SYS sys.bin -APP app.bin -NICACHE 8 -NDCACHE 8  -STATS stats_file -NCYCLES 100000
  

À l'aide de l'outil 'gnuplot', 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_file' using 1:6

Note : cette commande signifie que vous souhaitez afficher la courbe où la colonne n°1 du fichier stats_file (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 ?

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, main_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 (app.bin.txt), 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).

• Relancez la simulation pour 100000 cycles, en changeant le nom du fichier de statistiques :

$ simul_almo_generic -SYS sys.bin -APP app.bin -NCYCLES 100000  -STATS nomiss_stats -NICACHE 8 -NDCACHE 8

• À 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 :

plot 'stats_file' using 1:6
replot 'nomiss_stats' using 1:6

• Comment expliquez-vous l'évolution du taux de MISS pour cette nouvelle version de l'application ?