ALMO TD n°5 - Mémoires Cache

Préambule

Dans un ordinateur, l'accès à la mémoire principale est souvent coûteux (en termes de nombre de cycles) car la mémoire principale est généralement située hors de la puce. Afin d'améliorer les performances du système, on utilise alors des mémoires cache. Ces mémoires cache, généralement placées à côté du processeur, donc sur la puce, sont elles très rapides d'accès, mais ne peuvent contenir que peu de données.

Le principe de ces mémoires cache est qu'elle contiennent les données les plus récémment utilisées par le processeur. Attention : les mémoires caches ne contiennent que des copies de données de la mémoire principale. L'efficacité des caches est liée à la propriété de localité des applications logicielles : il est fort probable qu'après avoir accédé à une certaine adresse mémoire X, le processeur accède à nouveau à l'adresse X (localité temporelle) ou accède à une autre adresse mémoire proche de X (localité spatiale).

Dans ce TD5 et dans le TP5 associé, nous étudions des mémoires cache à correspondance directe.

Exercice 1

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) des champs étiquette, index et déplacement de l'adresse de l'instruction, en complétant la table suivante :

Instruction	Étiquette	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 2ème 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é	Étiquette	Donnée 1	Donnée 0
0
0
0
0

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.

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