ALMO TD n°11 - Mémoire virtuelle

Préambule

L'objectif de ce TD est d'analyser le mécanisme général de mémoire virtuelle paginée, et plus précisément d'analyser le comportement du composant matériel MMU (Memory management Unit), chargé de la traduction entre les adresses logiques (adresses manipulées par le logiciel applicatif), et les adresses physiques (adresses utilisées par le matériel). La MMU est située entre le processeur et les caches L1.

Dans la plateforme étudiée, on suppose que les adresses virtuelles sont sur 32 bits, les adresses physiques sont également sur 32 bits et les pages ont une taille de 4 Kibi octets.

1. Principe de la mémoire virtuelle

• Qu'est-ce qu'une adresse virtuelle ? Qu'est-ce qu'une adresse physique ?

• Qu'est-ce qu'une "page virtuelle", une "page physique" ? Quelle est la capacité d'une page (en octets). Quelle est la signification des termes VPN et PPN ?

• Quelles sont les deux fonctions d'une MMU ?

• Que signifient les termes "mapping mémoire", "table de pages" et "défaut de page" ?

• Pourquoi faut-il une MMU pour les instructions et une pour les données ?

• Où les tables de pages sont-elles rangées ? Pourquoi une table de pages à un seul niveau n'est pas efficace ? Décrire le mécanisme de table de pages à deux niveaux présenté en cours. Quels sont les avantages et les inconvénients d'une telle structure à deux niveaux ?

• Quel est l'algorithme exécuté lors de la traduction d'une adresse virtuelle en adresse physique  ?

• Que doit faire le système d'exploitation en cas de défaut de page ?

• Qu'est-ce qu'une TLB ? Que contient chaque entrée d'une TLB ? Quel est l'intérêt d'une TLB ?

• Qu'est-ce qu'un MISS TLB ? Quelle en est la conséquence ?

• Dessinez le schéma général d'une hiérarchie mémoire réelle faisant intervenir le processeur, les MMU (instructions et données), les caches L1 (instructions et données), le bus système, le cache L2 et la mémoire principale.

• Décrivez le scénario complet aboutissant à un défaut de page dans l'hypothèse où le MISS TLB est directement traité par l'automate matériel de la MMU. Donnez un ordre de grandeur pour le taux de MISS TLB et pour le coût d'un MISS TLB. Même question pour un défaut de page.

2. Évaluation des performances

Dans cet exercice, on ne s'intéresse qu'aux lectures et écritures de données (on suppose que toutes les traductions d'adresses instruction font HIT dans la TLB instructions et que toutes les lectures d'instructions font HIT dans dans le cache d'instructions).

La TLB est généralement réalisée sous la forme d'un cache totalement associatif (cache pour lequel une paire VPN/PPN peut être rangée dans n'importe quelle ligne du cache) plutôt que comme un cache à correspondance directe.

Pour comprendre l'intérêt du caractère associatif, traitons le cas d'une application qui veut effectuer la somme membre à membre de deux vecteurs X et Y possédant 4096 composantes, et représentés par des tableaux d'entiers. On range le résultat dans un troisième tableau Z. Le tableau X est rangé à partir de l'adresse virtuelle 0x10000000, le tableau Y est rangé à partir de l'adresse virtuelle 0x10010000, et enfin, le tableau Z est rangé à l'adresse virtuelle 0x10020000.

Le code de traitement de l'application ressemblerait à :

    for(i = 0; i < 4096; i++)
    {
        Z[i] = X[i] + Y[i];
    }

On considère le cas suivant : la TLB peut contenir 4 paires (VPN/PPN) et le coût d'un MISS est de 100 cycles de gel du processeur, nécessaires pour ré-alimenter la TLB .

Si la TLB est réalisée comme un cache à correspondance directe, la seule entrée de la TLB qui peut contenir la valeur du PPN recherché est sélectionnée par les 2 bits de poids faible du VPN. Si la TLB est réalisée comme un cache totalement associatif, n'importe quelle paire (VPN/PPN) peut être stockée dans n'importe laquelle des 4 entrées de la TLB.

• Combien de pages (physiques ou virtuelles) occupe chacun des 3 vecteur X, Y, Z  ?

• Calculez le nombre de miss TLB observés si la TLB est réalisée comme un cache à correspondance directe. Pourquoi le cache totalement associatif est-il bien meilleur ?

On analyse maintenant plus précisément le comportement de la mémoire et on s'intéresse uniquement au fonctionnement du couple TLB des données et cache des données. La TLB des données contient 4 entrées et est totalement associative. Le cache des données est à correspondance directe, a une capacité 4KiB et chaque ligne de cache contient 4 mots de 32 bits.

• En supposant des tables de pages à deux niveaux, donner un "mapping" possible des pages virtuelles relatives aux 3 vecteurs X, Y et Z dans la mémoire physique.

On considère que les vecteurs X et Y sont maintenant dans la mémoire physique et que la table des pages est correctement initialisée (pas de défaut de page). On cherche à calculer précisément le nombre de cycles de gels introduits par les MISS TLB et par les MISS du cache L1 pour l'exécution de la boucle de traitement présentée ci-dessus. On suppose que la TLB et le cache sont initialement vides. On considère qu'un MISS TLB coûte 100 cycles de gel et qu'un MISS cache coûte 10 cycles de gel.

• Combien d'instructions de chargement mémoire lw sont exécutées par le processeur pour additionner les deux vecteurs X et Y ? Combien d'instructions vont entraîner un MISS dans le cache L1 ?

• Comment réduire le taux de MISS sur le cache L1 ? Quelle est la pénalité en nombre de cycles introduite par le cache L1 après optimisation?

• Combien d'instructions de stockage mémoire sw sont exécutées par le processeur pour stocker le résultat de la somme des deux vecteurs dans Z ?

• Combien de MISS TLB vont se produire pendant l'exécution de la boucle de calcul ? Calculez la pénalité en nombre de cycles induite par ces MISS TLB ? Calculez la pénalité totale induite par le couple MMU/Cache L1.