TD Caches
Alors que caches, mémoires virtuelle peuvent initialement sembler très différents,
ils reposent sur les deux mêmes principes de localité et peuvent être compris ...
part of the document
seur, la mémoire la plus lente et la moins coûteuse étant placée à un niveau inférieur.
Les performances étant la raison principale de l'utilisation d'une hiérarchie de mémoires, la vitesse des succès (si la valeur demandée par le processeur est dans le niveau supérieur) et des défauts est importante.
Le coût d'un défaut est le temps nécessaire pour remplacer un bloc (élément d'information) du niveau supérieur au niveau inférieur. Puisque le nombre total de cycles passés dans un programme est la somme des cycles processeur et des cycles d'attente mémoire, le système mémoire a une influence significative sur le temps d'exécution du programme.
Alors que caches, mémoires virtuelle peuvent initialement sembler très différents, ils reposent sur les deux mêmes principes de localité et peuvent être compris en observant comment ils répondent aux quatre questions suivantes :
Où peut être placé un bloc ?
Comment un bloc est-il trouvé ?
Quel bloc est remplacé lors dun défaut ?
Comment sont traitées les écritures ?
Rappels sur le cache
Le cache (notre bureau) est le nom qui a été choisi pour représenter le niveau de la hiérarchie mémoire situé entre l'U.C. et la mémoire principale. Aujourd'hui, le terme est aussi utilisé pour faire référence à tout espace de stockage qui est géré dans le but de tirer parti de la localité des accès. Le cache le plus simple est le cache à correspondance direct avec bloc d'un mot.
Dans un tel cache, les succès comme les défauts sont simples, car un mot ne peut aller qu'à un seul emplacement et il y a une étiquette distincte pour chaque mot. La cohérence entre le cache et la mémoire (les valeurs contenues doivent être identiques) est conservée par la méthode de l'écriture simultanée. Pour tirer partie de la localité spatiale, un cache doit avoir une taille de bloc de plus d'un mot.
L'utilisation d'un bloc plus grand réduit le taux de défauts et améliore lefficacité du cache en diminuant dans le cache l'espace de stockage pour les étiquettes par rapport à l'espace de stockage pour les données (létiquette est utilisée par plusieurs mots). Mais l'augmentation de la taille du bloc peut aussi augmenter le coût de défaut si l'on n'augmente pas le débit de la mémoire principale pour transférer les blocs de cache plus facilement (technique d'entrelacement, ou mémoire plus large).
Où peut-on placer un bloc.
Dans un cache à correspondance directe, l'emplacement du bloc est donné par : numéro de bloc modulo nombre de blocs dans le cache. Dans un cache associatif, le placement peut être n'importe où.
EXERCICES
Ex SEQ Ex \* ARABIC 1
Remplir le contenu dun cache de huit mots à correspondance directe (table 2) après les series de requettes suivante : 22,26,22,26,16,4,16,4,16,18,26,18. Le processeur demande des adresses sur 5 bits. On complétera tout dabord, le tableau des actions à mener après chaque référence. Commenter lefficacité du cache directe. Donner une serie de référence éfficace.
Table1 :
Adresse
de référenceadresse
binaireSuccès
ou défautBloc du
cache assigné2226222616416182618
Table 2 :
IndexVEtiquetteDonnéennnnnnnn
Ex SEQ Ex \* ARABIC 2
Donner le schéma du cache à correspondance directe correspondant au format de ladresse suivant :
etiquetteIndexadresse octet31 8 7 2 1
Ex SEQ Ex \* ARABIC 3
Donner le nombre de bits nécessaire à un cache de 2n mots.
Ex SEQ Ex \* ARABIC 4
Donner le schéma dun cache qui contient 16K blocs avec un mot par bloc.
Ex SEQ Ex \* ARABIC 5
Quel est le nombre total de bits requis pour un cache de 64 Ko de données (32 bits)?
Ex SEQ Ex \* ARABIC 6
donner le schéma dun cache à corespondance directe de 64 Ko utilisant des blocs de quatre mots (16 octets).
Ex SEQ Ex \* ARABIC 7
Considéros un cache à 64 blocs et une taille de bloc de 16 octets. A quel numéro de bloc ladresse en octets 1200 correspond-elle ?
Ex SEQ Ex \* ARABIC 8
On dispose de Trois caches, chacun deux possédant quatre blocs de un mot. Un des caches est totalement associatif, le second est associatif par ensemble de deux blocs et le troisième est à correspondance directe. En suposant que la politique de remplacement est celle du bloc le moins récemment utilisé, déterminer le nombre de défauts pour chaque organisation de cache à partir de la séquence dadresse de blocs suivante : 0,8,0,6,8.
Ex SEQ Ex \* ARABIC 9
On considère pour les cinq exercices la même séquence de références à des adresses de mots : 1, 4, 8, 5 , 20, 17, 19, 56, 9, 9, 11, 4, 43, 5, 6, 9, 17. Il est demandé de détailler les contenus des caches après chaque défaut.
Ex SEQ Ex \* ARABIC 10
En supposant un cache à correspondance directe initialement vide avec 16 blocs de un mot, déterminer si chaque référence de la liste conduit à un succès ou à un défaut et donner le contenu final du cache.
Ex SEQ Ex \* ARABIC 11
Indiquer les succès, les dédauts et le contenu final du cache pour un cache à correspondance directe avec des blocs de quatre mots et une taille totale de 16 mots.
Indiquer les succès, les dédauts et le contenu final du cache pour un cache associatif par ensembles de deuc blocs avec des blocs de un mot et une taille totale de 16 mots. On supposera une politique de remplacment LRU.
Ex SEQ Ex \* ARABIC 12
Indiquer les succès, les dédauts et le contenu final du cache pour un cache totalement associatif avec des blocs de un mot et une taille totale de 16 mots. On supposera une politique de remplacmenet LRU.
Ex SEQ Ex \* ARABIC 13
Indiquer les succès, les dédauts et le contenu final du cache pour un cache totalement associatif avec des blocs de quatre mots et une taille totale de 16 mots. On supposera une politique de remplacmenet LRU.
solution SEQ solution_ \* ARABIC 1
Adresse
de référenceadresse
binaireSuccès
ou défautBloc du
cache assigné2210110d1102611010d0102210110s1102611010s0101610000d000400100d1001610000s0001810010d0102611010d0101810010d010
IndexVEtiquetteDonnée000n001n010n011n100n101n110o10m(10110)111nIndexVEtiquetteDonnée000n001n010o11m(11010)011n100n101n110o10m(10110)111nIndexVEtiquetteDonnée000o10m(10000)001n010o11m(11010)011n100n101n110o10m(10110)111nIndexVEtiquetteDonnée000o10m(10000)001n010o11m(11010)011n100ooom(oo100)101n110o10m(10110)111nIndexVEtiquetteDonnée000o10m(10000)001n010o10m(10010)011n100ooom(oo100)101n110o10m(10110)111nIndexVEtiquetteDonnée000o10m(10000)001n010o11m(11010)011n100ooom(oo100)101n110o10m(10110)111n
IndexVEtiquetteDonnée000o10m(10000)001n010o10m(10010)011n100ooom(oo100)101n110o10m(10110)111n
solution SEQ solution_ \* ARABIC 2
solution SEQ solution_ \* ARABIC 3
nb bits=nb bits taille de l'adresse *nb bits taille données.
-> largueur du champ d'étiquette : 32-(n+2) {n=n bits ppour l'indexe} et 2 bits pour adresser en octet.
-> nombre total de bits :
2n*(taille bloc+taille étiquette +taille de champ de validité)
= 2n*(32+32-n-2+1)
solution SEQ solution_ \* ARABIC 4
Ceci signifie que lindex a 14 bits et que létiquette contient 16 bits.
solution SEQ solution_ \* ARABIC 5
On sait que 64 Ko représente 16K mots, cest à dire 214 mots. La taille totale du cache est donc de
214*(32+(32-1-2)+1)= 214*49=784Kbits
Soit presque 100ko pour un cache de 64Ko. Pour ce cache le nombre total de bits dans le cache est presque 1,5 fois plus important que ce qui est nécessqire pourle stockage des données uniquement.
solution SEQ solution_ \* ARABIC 6
Le champ étiquette a 16 bits de large et le champ Index 12 bits, tandis quun champ de 2 bits (bits 3 -2) est utilisé pour indexer le bloc et sélectionner le mot à extraire du bloc en utilisant un multiplexeur 4 pour 1.
solution SEQ solution_ \* ARABIC 7
Avec 16 octets par bloc, ladresse en octets 1200 est ladresse de bloc 1200/16=75 ce qui correspond au numéro de bloc de cache (75 modulo 64)=11.
Autre solution :
Par les adresses :
Chercher la valeur de ladresse 1200 en binaire rechercher la valeur de lindex, (valeur aà parite du 4 bits).
solution SEQ solution_ \* ARABIC 8
Voit livre.
Les caches PAGE 6
