Cours "Architecture des Systèmes Multi-Processeurs"

TP3 : Architecture interne du contrôleur de cache

(pirouz.bazargan-sabet@…)

A. Objectifs

On analyse dans ce TP l'architecture interne d'un contrôleur de cache L1 contenant un cache instruction et un cache de données. Les deux caches sont indépendants, mais partagent le même port d'accès au PIBUS. On rappelle que dans un cache associatif par ensembles, l'ensemble de toutes les lignes de cache est partitionné en NSET familles suivant la valeur du champs SET de l'adresse. Chaque famille se voit attribué un ensemble de NWAY cases équivalentes. Pour une famille identifiée par un numéro de SET, on différencie les cases par un numéro de WAY. Le nombre total de cases est donc égal à NSET * NWAY. Toutes les lignes d'une même famille sont en compétition pour les NWAY cases attribuées à la famille. Dans un cache à correspondance directe, on a NWAY = 1, et une ligne de cache ne peut donc être rangée que dans une seule case du cache. Dans un cache totalement associatif, n'importe quelle ligne de cache peut être rangée dans n'importe quelle case, on a donc une seule famille et NSET = 1.

L'adresse 32 bits se découpe de la façon suivante :

TAG

SET

BYTE

• Le champ BYTE désigne un octet dans une ligne
• Le champ SET définit un numéro de famille
• Le champ TAG identifie une ligne particulière dans une famille

La stratégie d'écriture en mémoire est une stratégie « write-through » : Toute requête d'écriture émise par le processeur se traduit par une écriture immédiate en mémoire (dès que le contrôleur du cache peut accéder au bus). Le cache n'est mis à jour que si l'adresse correspond à une donnée présente dans le cache. Un tampon d'écritures postées permet d'éviter de geler le processeur lors des instructions d'écriture (instructions de type sw ou sb), tant qu'il n'y a pas un trop grand nombre d'écritures consécutives.

B. Architecture matérielle

L'architecture du système considéré dans ce TP est identique à celle du TP2. Elle comporte donc un seul processeur programmable MIPS32 avec ses caches, une mémoire RAM, une mémoire ROM, et un terminal TTY. Créez un répertoire de travail tp3, et recopiez dans ce répertoire les deux fichiers tp2_top.cpp et tp2.desc déjà utilisés dans le TP2.

On utilise dans ce TP3 deux caches à correspondance directe, possédant chacun une capacité de 128 octets, et des lignes de cache d'une largeur de 4 mots de 32 bits. Commencez donc par modifier les valeurs des paramètres définissant les caractéristiques des caches dans le fichier tp2_top.cpp puis générez le simulateur.

C. Application logicielle

L'archive attachment:multi_tp3.tgz​ contient les fichiers dont vous aurez besoin: vous trouverez dans le répertoire soft le fichier main.s (programme utilisateur en assembleur), le fichier reset.s (code de boot), les fichiers seg.ld, sys.ld et app.ld (permettant de contrôler l'édition de liens), le fichier config.h, et un fichier Makefile permettant de lancer la génération du code binaire. Décompressez cette archive dans le répertoire tp3.

Le programme exécuté dans le TP2 était écrit en langage C. Dans ce TP3, le programme principal contenu dans le fichier main.s est écrit en assembleur pour faciliter le contrôle des valeurs des adresses du code et des données.

Ce programme réalise l'addition vectorielle : C = A + B. Les 3 vecteurs A, B et C possèdent 20 composantes chacun. Ces vecteurs sont représentés en mémoire par des tableaux d'entiers. Avant d'entrer dans la boucle qui effectue l'addition, on charge l'adresse de l'élément A[0] dans le registre $8.

Vérifiez que les adresses des segments définies dans le fichier seg.ld (pour le logiciel) sont cohérentes avec les valeurs définies dans le fichier tp2_top.cpp (pour le matériel).

Ouvrez le fichier main.s pour répondre aux questions suivantes:

Question C1 : Quelle est l'adresse de la première instruction de la fonction main ? Quelle est l'adresse de la première instruction de la boucle (instruction correspondant à l'étiquette loop) ?

Question C2 : Quelle sont les adresses de base des trois tableaux A, B, C ?

Question C3 : Pourquoi l'instruction sw est-elle placée après l'instruction bne (test de fin de boucle) ?

Question C4 : Quel est le nombre de cycles nécessaires pour exécuter une itération de la boucle, dans l'hypothèse ou toutes les instructions et toutes les données sont dans le cache (pas de MISS).

D. Fonctionnement du cache instruction

On va maintenant analyser le comportement du cache instruction. Plus précisément, nous allons essayer de prévoir l'évolution du contenu du cache pendant l'exécution du programme.

Question D1 : Sur combien de bits sont codés les trois champs BYTE, SET, et TAG d'une adresse 32 bits ? Quelles sont leurs valeurs pour l'adresse 0x00400000 (correspondant à la première instruction du programme ?

Question D2 : Représentez dans le tableau ci-dessous le contenu du cache instruction à la fin de la première itération de la boucle. Quelles instructions ont déclenché un MISS sur le cache instruction pour atteindre cet état ?

TAG	V	WORD3	WORD2	WORD1	WORD0
	0
	0
	0
	0
	0
	0
	0
	0

Pour les 4 colonnes de droite, chaque case du tableau contient un mot de 32 bits.

Question D3 : Quel est le contenu du cache instruction à la fin de la 20e itération ? Calculez approximativement le taux de MISS lors de l'exécution complête du programme (on ne prend pas en compte ce qui se passe pendant la séquence de boot et pendant l'affichage du message).

On s'intéresse maintenant à l'automate qui contrôle le cache instructions. Le traitement d'un MISS instruction nécessite la coopération entre deux automates : Lorsque l'automate ICACHE_FSM détecte une condition de MISS, ou une adresse non cachable, il fait appel à l'automate PIBUS_FSM pour effectuer la transaction sur le PIBUS en respectant le protocole du PIBUS.

En cas de MISS, l'automate ICACHE_FSM stocke l'adresse de la ligne manquante dans un registre, puis entre dans l'état MISS_SELECT pour sélectionner la case où sera stockée la ligne manquante, puis entre dans l'état MISS_WAIT, où il attend que l'automate PIBUS_FSM aie terminé d'écrire tous les mots de la ligne manquante dans le registre tampon. Pour finir, l'automate ICACHE_FSM met à jour le cache instruction dans l'état MISS_UPDT, puis retourne dans l'état IDLE. Cet automate est capable de traiter des requêtes de lecture d'instructions non cachables (etats UNC_WAIT et UNC_GO), et doit également reporter au processeur les éventuelles erreurs d'adressage signalées par l'automate PIBUS_FSM (état ERROR).

Question D4 : Pour quel type de cache l'état MISS_SELECT est-il indispensable ?

Question D5 : Complétez le graphe de l'automate ICACHE_FSM ci-dessous, en attachant à chaque transition sa condition de franchissement. Les conditions de transition dépendent des signaux Booléens suivants :

• IREQ : le processeur emet une requête instruction,
• IUNC : l'adresse correspond à un segment non caché,
• IMISS : le cache instruction fait MISS,
• VALID : l'automate PIBUS signale que la réponse est disponible,
• ERROR : l'automate PIBUS signale que la réponse correspond à une erreur.

Question D6 : Dans quel état est forcé cet automate lors de l'activation du signal RESETN? Quel doit être l'autre effet du signal RESETN sur le cache instruction ?

Remarque : Il n'est pas interdit de consulter le modèle de simulation contenu dans le fichier pibus_mips32_xcache.cpp pour faire du reverse engineering et essayer d'en extraire la structure des automates. On rappelle que ces modèles sont rangés dans le répertoire :

/users/outil/soc/soclib-lip6/pibus

E. Fonctionnement du cache de données

On va maintenant analyser le comportement du cache de données.

Il n'y a aucune lecture de donnée (aucune instruction lw ou lb) dans le code de boot contenu dans le fichier reset.s. Le cache de données est donc initialement « vide » (c'est à dire que les 8 cases ont un contenu « non valide »).

Question E1 : Quelles sont les valeurs des trois champs BYTE, SET, et TAG pour les adresses des éléments A[0] et B[0] des deux tableaux ? Donnez le contenu du cache de données à la fin de la première itération de la boucle, en précisant quelles instructions entraînent un MISS sur le cache de données et donc un gel du processeur.

TAG	V	WORD3	WORD2	WORD1	WORD0
	0
	0
	0
	0
	0
	0
	0
	0

Pour les 4 colonnes de droite, chaque case du tableau contient un mot de 32 bits.

Question E2 : Calculez le taux de MISS sur le cache de données pour l'exécution complête des 20 itérations de cette boucle. Donnez le contenu du cache de données à la fin de la 20e itération de la boucle.

L'automate contrôleur du cache de données est très semblable à l'automate contrôleur du cache instructions. Il faut ajouter les deux états permettant de traiter les écritures: l'état WRITE_UPDT correspond à la mise à jour du cache en cas d'écriture qui fait HIT dans le cache. L'état WRITE_REQ correspond à l'enregistrement de la requête d'écriture dans le tampon d'écritures.

Question E3 : Complétez le graphe de cet automate, en attachant à chaque transition sa condition de franchissement. Ces conditions dépendent des signaux Booléens suivants :

• DREQ : le processeur emet une requête de donnée,
• WRITE : il s'agit d'une requête d'écriture,
• DMISS : le cache de donnée fait MISS,
• DUNC : l'adresse correspond à un segment non caché,
• WOK : le write buffer n'est pas plein,
• VALID : l'automate PIBUS signale que la réponse est disponible..
• ERROR : l'automate PIBUS signale que la réponse correspond à une erreur.

Notez que les transitions sortantes de l'état WRITE_REQ ne sont pas représentées sur le graphe ci-dessous. Ces transitions sont traitées dans la question suivante.

Pour pouvoir traiter efficacement les rafales d'écritures, les requêtes du processeur sont prises en compte de la même façon dans l'état IDLE et dans l'état WRITE_REQ. Ceci qui signifie que les états successeurs de l'état WRITE_REQ sont les mêmes que les états successeurs de l'état IDLE.

Question E4 : Les expressions booléennes associées aux transitions de sortie de l'état WRITE_REQ sont très proches des expressions booléennes associées aux transitions de sortie de l'état IDLE. Quelle est la différence?

F. Accès au PIBUS

L'automate PIBUS_FSM peut être considéré comme un serveur qui répond aux requêtes de trois clients, qui sont l'automate ICACHE_FSM, l'automate DCACHE_FSM et le tampon d'écriture postées WBUF. Il peut générer six types de de transactions sur le bus correspondant aux six événements suivants (l'instruction d'écriture conditionnelle SC est utilisée pour la synchronisation, et sera analysée dans la suite du cours) :

1. Le tampon WBUF est non-vide, et demande une transaction de type WRITE (écriture d'un mot).
2. l'automate DCACHE_FSM demande une transaction de type SC (écriture conditionnelle d'un mot)).
3. l'automate DCACHE_FSM demande une transaction de type DUNC (lecture d'un mot non cachable).
4. l'automate DCACHE_FSM demande une transaction de type DMISS (lecture d'une ligne de cache).
5. l'automate ICACHE_FSM demande une transaction de type IUNC (lecture d'un mot non cachable).
6. l'automate ICACHE_FSM demande une transaction de type IMISS (lecture d'une ligne de cache).

Plusieurs conditions pouvant ëtre simultanément vraies, il faut définir une priorité. La numérotation ci-dessus définit un ordre de priorité fixe décroissante.

Question F1 : Pourquoi les écritures ont-elles la priorité la plus élevée ? Quel est l'inconvénient de ce choix ?

Question F2 : Quel est le mécanisme utilisé par les deux automates ICACHE_FSM et DCACHE_FSM pour transmettre une requête de lecture vers l'automate PIBUS_FSM ? Comment le serveur signale-t-il aux clients que la requête a été prise en compte ? Dans le cas d'une requête de lecture, comment le serveur signale-t-il au client que les données sont disponibles ?

Question F3 : Pourquoi l'automate PIBUS_FSM n'a-t-il pas besoin de signaler qu'une requête d'écriture transmise par le tampon d'écritures postées s'est effectivement terminée ? Quelle est l'utilité de la réponse dans le cas d'une transaction d'écriture ?

Question F4 : Complétez le graphe de l'automate PIBUS_FSM ci-dessous, en attachant à chaque transition sa condition de franchissement. Ces conditions dépendent des signaux suivants :

• ROK : Le tampon d'écritures postées est non vide
• SC : L'automate DCACHE_FSM demande une "écriture conditionnelle"
• IUNC : L'automate ICACHE_FSM demande une instruction non cachable
• IMISS : L'automate ICACHE_FSM delande une ligne de cache instruction
• DUNC : L'automate DCACHE_FSM demande une donnée non cachable
• DMISS : L'automate DCACHE_FSM demande une ligne de cache de donnée
• GNT : Le bus est alloué au composant PIbusMips32Xcache
• LAST : un compteur initialisé dans l'état IDLE signale qu'il s'agit de la dernière adresse d'une rafale
• ACK : Réponse de la cible (3 valeurs possibles : READY, WAIT, ERROR)

Question F5 : Calculez le coût minimal du miss sur le cache instruction (nombre de cycles de gel du processeur en cas de miss). Pour cela, vous dessinerez explicitement le chronogramme décrivant pour chacun des deux automates, la succession des valeurs stockées dans les registres d'etat. Même question pour le cache de données.

Question F6 : Calculez le nombre total de cycles pour exécuter les 20 itérations de la boucle de la section C, en prenant en compte les cycles de gel dûs aux miss sur le cache instruction et sur le cache de données. En déduire la valeur du CPI (nombre moyen de cycles par instruction).

G. Expérimentation par simulation

On souhaite vérifier par la simulation (c'est-à-dire par expérimentation) les calculs effectués ci-dessus.

Vérifiez la concordance entre les adresses de base des huit segments dans le fichier tp2_top.cpp, et les valeurs définies dans le fichier seg.ld.

Vérifiez que les valeurs des paramètres des caches définies dans le fichier tp2_top.cpp correspondent à des caches à correspondance directe, d'une capacité de 128 octets chacun, avec une largeur de ligne de cache de 4 mots de 32 bits.

Vérifiez enfin que le segment « tty » est déclaré non cachable dans la Table des segments.

Générez les fichier sys.bin et app.bin en lançant le Makefile dans le répertoire soft. Vérifiez que le code généré correspond à ce que vous attendez, en particulier pour ce qui concerne le segment seg_code et le segment seg_data.

Placez-vous dans le répertoire tp3, et lancez la simulation en mode trace avec l'option -DEBUG.

L'analyse détaillée du fichier de trace vous permettra de répondre aux questions suivantes :

Question G1 : À quel cycle le processeur exécute-t-il sa première instruction ? A quel code correspond cette instruction ? Quel est le coût d'un MISS sur le cache instruction (coût du MISS = nombre de cycles de gel du processeur).

Question G2 : À quel cycle le processeur se branche-t-il au programme principal main() ?

Question G3 : Quel est le coût d'un MISS sur le cache de données ? A quel cycle le processeur termine-t-il l'exécution de la première itération de la boucle ? Quelle est la durée totale de la première itération ?

Question G4 : Quelle est la durée de la seconde itération ? Quelle est la durée de la troisième itération ? Comment expliquez-vous que le coût du MISS pour les itérations 2 et 3 soit différent du coût du MISS pour la première itération ?

Question G5 : Quel est le taux de MISS sur le cache de données à la fin de l'exécution de la boucle ? Quelle est la durée totale du programme main (sans compter le temps d'exécution de l'affichage du message final).

H. Optimisation

Pour cette application, les cycles de gel du processeur dûs aux MISS de conflit sur le cache de donnée représentent plus de 2/3 du temps d'exécution. Comment faut-il modifier les adresses des tableaux en mémoire pour minimiser le taux de MISS sur le cache de données, sans modifier l'architecture matérielle et sans modifier la structure du programme ? Recalculez la durée totale d'exécution du programme et la durée moyenne d'une itération pour cette nouvelle organisation de la mémoire, et vérifiez la justesse de vos estimations par simulation.

I. Compte-rendu

Les réponses aux questions ci-dessus doivent être rédigées sous éditeur de texte et ce compte-rendu doit être rendu au début de la séance de TP suivante. De même, le simulateur, fera l'objet d'un contrôle (par binôme) au début de la séance de TP de la semaine suivante.