2/16
Performance d'une mémoire cache
> On veut un temps d'accès moyen réduit ;
Chapitre 12: > Temps d'accès moyen :
T m = T s + τ E × TP
Mémoire cache Exemple :
• Accès SRAM : 10 ns ;
M. Dubacq • Accès DRAM : 70 ns ;
• Accès DRAM en mode page : 20 ns ;
IUT de Villetanneuse 2008 2009 • Taux succès : 90% ;
Temps moyen normal : 10 + 0, 1 × 70 = 17 ns
Temps moyen mode page (8 mots) : 10 + 0, 1 × (70 +
7 × 20) = 31 ns
3/16 4/16
Méthodologie de la mémoire cache Découpage d'une adresse pour identi er
> On a besoin d'informations : on va les chercher unique- > Classi er l'information : connue uniquement par son
ment à côté ; adresse ;
> Défaut de cache ramène l'information ; > Répartition en blocs : x bits de poids faibles utilisés
> Analogie : épicerie locale ; comme colonne, reste utilisée comme ligne ;
> Quand le produit demandé n'est pas là, l'épicerie la de- > Un bloc est donc identi ée par son numéro (les bits de
mande au grossiste en grande quantité et donne le pro- poids fort) ;
duit demandé ; > Découpage en champs !
> Le grossiste est plus loin, mais a plus de choix.
n x 0
numéro de page numéro de colonne
5/16 6/16
Le cache associatif Représentation d'un cache associatif
> On demande une adresse, dans un certain bloc X ; On prend 32 bits d'adresse, 64 octets/bloc, cache de 1 kio
31 5 0
> La mémoire cache contient un certain nombre de blocs, o o
N bloc=clé N octet
ainsi que l'indication de leurs numéros ; | {z }| {z } Données
X Octet
> Les blocs sont de toute façon tous aussi dans la RAM ; 16 emplacements Clé
oct. oct. oct. oct. oct. oct.
Valide 63 62 61 2 1 0
> Chacun de ces emplacements peut contenir le bloc de- =?
mandé X ou un autre ; =?
> On parcourt chacun des emplacements de blocs, et on =? X 1
regarde si on trouve X ; =?
> Si on trouve X, succès (on cherche le bon octet, et on
l'envoie) ; =?
> Sinon, échec (on trouve un bloc à éliminer, et on met X =?
à la place).
7/16 8/16
Politique de remplacement Le cache direct
> Bit « valide » décrit si le numéro du bloc correspond bien > Défaut du cache associatif : parcours de tous les empla-
à une copie de la mémoire ; cements pour trouver le bon bloc ;
> Quand il y a échec d'accès, il faut remplacer un bloc par > Cache direct : les bits de poids faible du numéro de bloc
le bloc voulu ; forment un index cache ;
> Remplacement aléatoire : un bloc au hasard est éliminé ; > Les autres bits du numéro de bloc forment la clé ;
> Remplacement LRU (least recently used) : le matériel > Un bloc ne peut aller que dans un seul emplacement ;
garde la trace des accès mémoires les plus récents, on > La clé est plus courte ;
remplace le bloc le moins utilisé récemment ;
> Deux blocs consécutifs ne sont pas dans le même em-
> Remplacement du plus vieux : le matériel garde la trace placement (car index=poids faible) ;
du bloc le plus ancien, on remplace ce bloc ;
> Choix direct du bloc à remplacer en cas d'échec (un seul
> On met le nouveau bloc à la place. bloc possible).
9/16 10/16
Cache direct Cache associatif par ensembles à n voies
32 bits d'adresse, 64 octets/bloc, cache de 1 kio > Cache associatif : beaucoup d'emplacements équiva-
31 9 5 0
lents, stratégie de remplacement et identi cation com-
clé index No octet
| {z }| {z } Données plexe ;
No bloc Octet
16 emplacements oct. oct. oct. oct. oct. oct. > Cache direct : un seul emplacement pour un bloc, stra-
Clé Valide 63 62 61 2 1 0
tégie et identi cation simple ;
0
=? 1 X 1
> Mais e et ping-pong entre blocs possible !
2 > Cache associatif par ensembles à n voies : comme cache
3
direct, mais avec le choix entre plusieurs emplacements ;
> 2 voies donnent 2 emplacements possibles pour un bloc,
14 4 voies donnent 4 emplacements...
15 > taille de l'index cache diminue si quantité totale de mé-
moire constante.
11/16 12/16
Cache associatif à 2 voies Hiérarchie de cache
2 voies, 32 bits d'adresse, 64 octets/bloc, cache de 1 kio > Politique de remplacement pour cache associatif par en-
31 8 5 0
sembles : comme cache associatif, mais l'index est xe
clé index No octet
| {z }| {z } Données (on doit jeter un bloc qui a le bon index) ;
No bloc Octet
16 emplacements oct. oct. oct. oct. oct. oct. > Évite l'e et ping-pong ;
Clé Valide 63 62 61 2 1 0
0A
> Cache direct équivalent à cache associatif par ensembles
0B
à 1 voie, et cache associatif équivalent à un cache asso-
ciatif par ensembles à k voies (k=nb blocs).
=? 1A X 1
=? 1B
> Ces méthodes de cache s'appliquent entre le cache ni-
veau 1 (sur processeur) et cache niveau 2 (externe) ;
7A
> Mais aussi entre cache niveau 2 et RAM/cache niveau 3 ;
7B > Souvent, le cache niveau 1 est divisé en cache d'instruc-
tions et cache de données ;
13/16 14/16
Cohérence de cache Écriture en cas de succès cache
> La mémoire peut parfois être modi ée indépendamment > Méthode 1 : écriture immédiate ;
du processeur (ex : contrôleur DMA) ; > écrire en même temps dans le cache et dans la mémoire ;
> Le cache n'est alors plus une copie dèle de la mémoire ; > méthode lente ;
> Dans ce cas, on invalide le bloc du cache (bit « valide » à > Méthode 2 : écriture di érée ;
0) ;
> on écrit seulement dans le cache ;
> Problème similaire dans le cas de l'écriture ;
> on retient un bit par bloc de cache pour savoir s'il a été
> On modi e la valeur dans le cache ; modi é ;
> Que doit-on faire pour la mémoire ? > quand un bloc est jeté, il doit d'abord être copié du cache
vers la mémoire ;
> réduit le tra c, mais complexe.
15/16 16/16
Écriture en cas d'échec cache Conclusion sur le cache
> Pour écrire, pas besoin de lire ; > Paramètres nombreux :
> Méthode 1 : écrire uniquement dans mémoire ; temps moyen ;
> Pas de déplacement du bloc vers le cache ; taux succès ;
taille cache ;
> taux d'échec reste élevé ;
taille bloc ;
> En cas d'écriture au même endroit, très lent (cache in- associativité (nombre de voies) ;
utile) ; stratégie de remplacement ;
> marche bien avec écriture immédiate ; écriture immédiate ou di érée ;
> Méthode 2 : écriture avec allocation ; allocation ou non sur échec en écriture ;
> taux d'échec réduit ; > Intégration dans la hiérarchie mémoire ;
> complexe et tra c intense ; > Utilisation en programmation.
> marche bien avec écriture di érée.