Mémoire cache
N° line Tag Mémoire Cache Mémoire Centrale
0 Block 1 @0 Mot mémoire
1 Block 2 @1
2 Block 3 @2 Block 1
(K mots)
J Block M
Taille line = K mots
Block M
Tag=étiquette (K mots)
@ 𝒏
Taille mot 108
(Ex : 2 octets)
Mémoire cache
Mapping function
The cache size is much smaller than La taille du cache est beaucoup plus petite que la taille de la mémoire. Il
the memory size.
faut définir une stratégie de copie des blocs de données dans le cache. Cette
A strategy for copying data blocks
into the cache must be defined. méthode s'appelle le mapping.
This method is called mapping.
109
Mémoire cache
Mapping functions
Correspondance directe (direct mapped cache) : le bloc m de la mémoire principale
peut se retrouver seulement dans la line j = m % M de la mémoire cache, sachant que
M est le nombre de lines de la mémoire cache
Correspondance totalement associatif (fully associative cache) : chaque bloc mémoire
peut être placé dans n'importe quel bloc du cache
Correspondance associative par ensemble (set associative cache) : séparation de la
mémoire cache en groupes de blocs et associativité complète dans un groupe, c.à.d. le
bloc m de la mémoire principale peut se retrouver dans n'importe quel bloc du groupe
g = m % v de la mémoire cache, sachant que v est le nombre total de groupes de blocs
dans la mémoire cache
110
Mémoire cache
Mapping functions
Correspondance directe (direct mapped cache) : le bloc m de la mémoire principale
peut se retrouver seulement dans la line j = m % M de la mémoire cache, sachant que
M est le nombre de lines de la mémoire cache
j=m%M Mem Centrale
j : N° line
m : N° block Tag Mem Cache Block 0
M : Nombre lines 0 Line 0 Block 1
j = (m % 4) 1 Line 1
j(0) = (0 % 4)= 0 Block 2
j(1) = (1 % 4)= 1
2 Line 2
j(2) = (2 % 4)= 2 3 Line 3 Block 3
j(3) = (3 % 4)= 3
j(4) = (4 % 4)= 0
Block 4
j(5) = (5 % 4)= 1 Block 5
j(6) = (6 % 4)= 2 j(7) = (7 % 4)= 3 j(8) = (8 % 4)= 0 111
Instant t (Etat Init: L0 contient B2) (Inconvénient direct cache)
Instant t+1
accès W1 accès W7
C W1 W2 W3 B0 C W1 W2 W3 B0
L0 B2 L0
P L1 W4 W5 W6 B1 P W4 W5 W6 B1
L1
U W7 W8 W9 B2 U W7 W8 W9 B2
Instant t+2 Instant t+3
accès W3 accès W7
C W1 W2 W3 B0 C W1 W2 W3 B0
L0 L0
P L1 W4 W5 W6 B1 P W4 W5 W6 B1
L1
U W7 W8 W9 B2 U W7 W8 W9 B2
Instant t+4 Instant t+5
accès W2 accès W9
C W1 W2 W3 B0 C W1 W2 W3 B0
L0 L0
P L1 W4 W5 W6 B1 P L1 W4 W5 W6 B1
U W7 W8 W9 B2 U W7 W8 W9 B2
112
Mémoire cache
Mapping function
L’accès à la mémoire cache (Cas cache directe)
s+w
Tag Line offset
s-r r w
Taille adresse mémoire = s+w
Partie offset = w (déplacement (offset) à l’intérieur du bloc)
Partie Line = r
Partie Tag = s-r
113
Mémoire cache
• offset (w bits)
• Permet de choisir un mot à l’intérieur d’un bloc.
• Taille d’un bloc = 2^w mots
• Line (r bits)
• Indique quelle ligne du cache doit être utilisée.
• Nombre de lignes cache = 2^r
• Tag (s − r bits)
• Sert à vérifier si le bloc présent dans la ligne est bien le bon.
• Taille du tag = s − r bits
114
Mémoire cache
• Taille mémoire centrale
• MC mots
• Car : s bits → numéro du bloc
• w bits → (déplacement (offset) à l’intérieur du bloc)
• Nombre de mots par bloc
•
• Nombre de blocs en mémoire centrale
•
115
Mémoire cache
• Nombre de lignes en cache
•
• Taille du cache
•
• (car chaque ligne contient un bloc de mots)
• Taille du tag
• bits
116
Mémoire cache
Mapping function
L’accès à la mémoire cache (Cas cache directe)
s+w
Tag Line offset
s-r r w
Nombre mots mémoire (Taille mémoire centrale ‘’MC’’) = ( )
Nombre mots par block (Taille block, Taille line)=
Nombre blocks dans MC = =
Nombre de lines dans cache =
Taille mémoire cache =
Taille tag =
117
Mémoire cache
Mapping function
L’accès à la mémoire cache (Cas cache directe)
Mémoire Centrale
Adresse
Tag index offset W1
Mémoire Cache W2
Tag W1 W3
B1
W2 W4
L1
W3
W4
CMP ×
Tag W6
W7
L3 W10
W8
× W9 W11
Hit B5
W12
W13
Miss 118
Mémoire cache
Mapping functions
Correspondance totalement associatif (fully associative cache) : chaque bloc mémoire
peut être placé dans n'importe quelle line du cache
Mem Centrale
Mem Cache Block 0
0 Line 0 Block 1
1 Line 1
2 Line 2 Block 2
3 Line 3 Block 3
Block 4
Block 5
119
Mémoire cache
Mapping functions
L’accès à la mémoire cache (Cas cache totalement associatif )
s+w
Tag Offset
s w
Nombre mots par block = (car taille bloc=taille line)
Taille tag =
120
Mémoire cache
Mapping function
L’accès à la mémoire cache (Cas cache totalement associatif )
Mémoire Centrale
Adresse
Tag W W1
Mémoire Cache W2
Tag W3
B1
L1 W4
CMP ×
Tag
L3 W10
W11
Hit × B5
W12
W13
Miss 121
Mémoire cache
Mapping functions
Correspondance associative par ensemble (set associative cache) : séparation de la mémoire
cache en groupes de blocs et associativité complète dans un groupe, c.à.d. le bloc m de la
mémoire principale peut se retrouver dans n'importe quel bloc du groupe g = m % v de la
mémoire cache, sachant que V est le nombre total de groupes de blocs dans la mémoire cache
Combinaison entre Directe & Associatif functions
Divise le cache en V ensembles, et chaque ensemble g contient un certain
nombre de lines k
Un block mémoire peut être stocké dans n’importe quelle line d’un ensemble
spécifique (unique)
Si un groupe contient K-lines, on parle de K-way set associative cache (La
plupart des ordinateurs d’aujourd’hui utilisent le cache 2-way ou 4-way) 122
Mémoire cache
Mapping functions
Divise le cache en V ensembles, et chaque ensemble g contient un certain nombre de
lines k
Un block mémoire peut être stocké dans n’importe quel line d’un ensemble
spécifique (g = m % V)
Tag Mem Cache Mem Centrale
g0, k lines Block 0
g1, k lines Block 1
Block 2
g2, k lines
g4, k lines Block 4
Block M 123
Mémoire cache
Mapping function
L’accès à la mémoire cache (Cas cache associatif par ensemble)
s+w
Tag Index(Ensemble) Offset
s-d d w
Nombre mots par block (Taille block, Taille line)=
Nombre de lignes dans ensemble = k (k-way: selon les archis actuelles k=2 ou 4)
Nombre d’ensembles = V =
Nombre de lines dans cache = k * V = k * (nb lignes par groupes * nb total groupe)
Taille cache = k* ( ) mots (nb lines total * taille une line)
124
Taille Tag = s – d
Mémoire cache
Mapping function
L’accès à la mémoire cache (Cas cache associatif par ensemble)
Mémoire Centrale
Adresse
Tag IE Offset W1
Mémoire Cache W2
Tag W3
B1
Tag W4
g1
Tag
Tag
CMP ×
Tag
Tag
g3 W10
Tag
Tag W11
Hit × B5
W12
W13
Miss 125
Mémoire cache
Techniques de remplacement
Si le cache est plein et que le processeur a besoin d’un bloc qui n’est pas dans le cache,
il faut remplacer l’un des blocs du cache. Diverses stratégies sont employées,
principalement :
Choisir le bloc le moins récemment utilisé (LRU pour Least Recently Used) * Use bit
in Set associative // or separate list in fully associative *
Choisir le plus ancien bloc du cache (FIFO pour First In First Out)
Choisir le bloc le moins fréquemment utilisé (LFU pour Least Frequently Used) //
Dans LFU algorithme, on utilise un compteur
Choisir un bloc candidat de manière aléatoire (Random)
Dans un cache à accès direct le problème ne se pose évidemment pas. En
revanche dans les caches associatifs, ou associatifs par ensemble, une
stratégie doit être mise en œuvre 126
127
128
129
130