Les mémoires de l’ordinateur
Le principe de hiérarchie mémoire : les caches
Architecture des machines 2006-2007
Joëlle Delacroix
1
Les mémoires de l’ordinateur
• Une « mémoire » est un composant électronique
capable de stocker temporairement des informations.
• Une mémoire est caractérisée par :
• Sa capacité, représentant le volume global d'informations (en
bits) que la mémoire peut stocker (par exemple 1 Goctets, soit
230 octets, soit 230 * 8 bits.
• Son temps d'accès, correspondant à l'intervalle de temps entre
la demande de lecture/écriture et la disponibilité de la donnée.
• L’ordinateur contient différents niveaux de mémoire,
organisés selon une hiérarchie mémoire.
Architecture des machines 2006-2007
Joëlle Delacroix
2
Les mémoires de l’ordinateur
• L’ordinateur contient différents niveaux de mémoire,
organisés selon une hiérarchie mémoire.
REGISTRES
N bits (32, 64)
1 nanoseconde
Mémoires Caches
Koctets
5 nanosecondes
Mémoires Centrales
Goctets
10 nanosecondes
Mémoires de masse
100 - 200 Goctets
5 millisecondes
Architecture des machines 2006-2007
Joëlle Delacroix
3
Les mémoires de l’ordinateur
Mémoires internes : mémoires volatiles
Mémoires de stockage :
mémoires permanentes
Barrettes mémoire
SIMM, DIMM…
Plateaux magnétiques
REGISTRES
N bits (32, 64)
1 nanoseconde
Mémoires Caches
Koctets
5 nanosecondes
Mémoires Centrales
Goctets
10 nanosecondes
Mémoires de masse
100 - 200 Goctets
5 millisecondes
Architecture des machines 2006-2007
Joëlle Delacroix
4
Les différents types de mémoire
• Mémoires vives : RAM (Random Access Memory)
(cid:190) Mémoire accessible en lecture et écriture
(cid:190) Mémoire volatile interne.
(cid:190) Compose la mémoire centrale et les caches
(cid:190) DRAM (Dynamic RAM) et SRAM (Static RAM) (60 à 5 ns)
• Mémoires mortes : ROM (Read Only Memory)
(cid:190) Mémoire accessible en lecture (150 ns)
(cid:190) Mémoire non volatile interne.
(cid:190) une fois l'information enregistrée, celle-ci ne peut pas (ou
difficilement) être modifiée.
• Mémoires flash : compromis entre les deux types de mémoire
(cid:190) Mémoire accessible en lecture et écriture
(cid:190) Mémoire non volatile.
(cid:190) Temps d’accès plus important que la RAM
Architecture des machines 2006-2007
Joëlle Delacroix
5
Les différents types de mémoire
Mémoires vives : RAM (Random Access Memory)
• DRAM : mémoire dynamique. Peu couteuses, elles
composent la mémoire centrale de l’ordinateur.
• 1 cellule mémoire mémorise un bit et est constituée par un
transistor et un condensateur
(cid:41) le condensateur se décharge dans le temps. Il convient de
recharger chaque cellule périodiquement (1000 fois / s) : le
rafraichissement de la mémoire.
• Se présente sous la forme de barrette DIMM (Dual Inline Memory
Module).
• Temps d’accès : 60 ns (DRAM) à 10 ns (SDRAM)
Architecture des machines 2006-2007
Joëlle Delacroix
6
Les différents types de mémoire
Mémoires vives : RAM (Random Access Memory)
• SRAM : mémoire statique. Plus couteuses et
les caches du
encombrantes, elles composent
processeur.
• 1 cellule mémoire mémorise un bit et est constituée par 4 à 6
transistors (circuit de type bascule)
• Temps d’accès : 10 ns
Architecture des machines 2006-2007
Joëlle Delacroix
7
Les différents types de mémoire
Contient les informations manipulées
couramment par le processeur
registre
Mémoire
SR A M
Mémoire
DR A M
Mémoire
ROM
Contient les informations
Les plus récemment
accédées par le processeur
(cid:198) Un sous ensemble de la
DRAM
Mémoire Vive, volatile
(lecture/écriture)
Contient le code et les
données
des programmes
exécutés par le
processeur
Mémoire Morte non
volatile (lecture)
Contient l’amorce (boot)
de l’ordinateur
Architecture des machines 2006-2007
Joëlle Delacroix
8
Processeur
Adressage de la mémoire centrale
Cellule mémoire mémorisant 1 bit
e
s
s
e
r
d
A
s
e
é
n
n
o
D
s
e
d
n
a
m
m
o
C
B u s
n
o
i
t
c
e
l
e
S
Tampon d’entrées/Sorties
Architecture des machines 2006-2007
Joëlle Delacroix
9
Bus adresse
0 1 0
Mémoire centrale : écriture
Bus de commandes
0
1
0
1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0
0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 1
1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0
0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1
1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0
1 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0
1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0
0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1
1- Sélection
2-Bus(données)
3- Ecriture
Architecture des machines 2006-2007
Joëlle Delacroix
10
Adresses mémoire
0
1
2
3
4
5
6
7
Bus
données
Bus adresse
0 1 0
Mémoire centrale : écriture
Bus de commandes
1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0
0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 1
1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0
0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1
1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0
1 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0
1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0
0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1
0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1
1- Sélection
2-Bus(données)
3- Ecriture
Architecture des machines 2006-2007
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
Adresses mémoire
0
1
2
3
4
5
6
7
Bus
données
Joëlle Delacroix
11
Bus adresse
0 1 0
0
1
0
1- Sélection
2-Bus(données)
3- Ecriture
Architecture des machines 2006-2007
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
Mémoire centrale : écriture
Bus de commandes
1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0
0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 1
0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1
0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1
1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0
1 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0
1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0
0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1
0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1
Adresses mémoire
0
1
2
3
4
5
6
7
Bus
données
Joëlle Delacroix
12
Les différents types de mémoire
Adressage d’une puce mémoire
Mémoire RAM (brochage)
Alimentation
s
e
é
n
n
o
D
Read
Write
Sélection
M
A
R
Vcc
D0
D1
D2
D3
D4
D5
D6
D7
R
W
S
A0
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
A11
s
e
s
s
e
r
d
A
Architecture des machines 2006-2007
Joëlle Delacroix
13
Les différents types de mémoire
Adressage d’une puce mémoire
Architecture des machines 2006-2007
Joëlle Delacroix
14
Les mémoires de l’ordinateur
Le principe de hiérarchie mémoire : les caches
Principe de la hiérarchie de mémoire,
fonctionnement des caches
Architecture des machines 2006-2007
Joëlle Delacroix
15
Hiérarchie Mémoire
vitesse
cout
Le plus élevé
capacité La plus petite
6-35 ns
70 - 120 ns
Le moins élevé
La plus grande
Processeur
Registres
Mémoire
Cache
Mémoire
centrale
Bus
Local
SRAM
DRAM
Bus
La mémoire cache est
une mémoire
intermédiaire placée
entre le processeur et la
mémoire centrale dont le
temps d'accès est de 4 à
20 fois inférieur à celui
de la mémoire centrale.
Elle comporte un
nombre fini d’entrées ( n
mots mémoire)
Architecture des machines 2006-2007
Joëlle Delacroix
16
Mémoire cache : principe
La stratégie suivie s'appuie sur le principe de localité
Processeur
Registres
Mémoire
Cache
info
b
Mémoire
Centrale
info
a
Bus
Local
SRAM
?
1
DRAM
2
?
1. L'info cherchée est-elle
dans le cache ?
OUI / Succès (a) : ramener l'info
dans le processeur
NON / Défaut (2) : chercher l'info
Publicité
dans la mémoire centrale
2. L'info est-elle en mémoire
centrale ?
OUI / Succès (b) : ramener l'info
dans le cache , puis dans le
processeur (a)
NON / Défaut
Architecture des machines 2006-2007
Joëlle Delacroix
17
Mémoire cache
Principe de localité
• Localité temporelle : si une donnée d'adresse A est
accédée à un temps t, la probabilité qu'elle soit de
nouveau accédée aux temps t+1, t+2 est très forte.
(cid:41) La donnée est remontée dans le cache pour minimiser les
temps d'accès suivants
I1
I2
I3
I4
I5
I6
loop :
fin :
load Im R1 5
add Im R2 3
add Im R1 -1
JMPZ Fin
JMP Loop
store D R2 10
Localité temporelle
Premier accès aux instructions
I2, I3, I4, I5 (cid:198) en MC
Les 4 accès suivants s’effectuent
à partir du cache
Architecture des machines 2006-2007
Joëlle Delacroix
18
Mémoire cache
Principe de localité
• Localité spatiale : si une donnée d'adresse A est accédée à
un temps t, la probabilité que les données d'adresses
voisines soient accédées aux temps t+1, t+2 est très forte.
(cid:41) La donnée d'adresse A et également les données d'adresse voisines
sont remontées dans le cache pour minimiser les temps d'accès
suivants
I1
I2
I3
I4
I5
I6
loop :
fin :
load Im R1 5
add Im R2 3
add Im R1 -1
JMPZ Fin
JMP Loop
store D R2 10
Localité spatiale
Premier accès à l’instruction I1
(cid:198) en MC
Les accès à I2, I3, I4, I5, I6 s’effectuent
à partir du cache
Architecture des machines 2006-2007
Joëlle Delacroix
19
Processeur
Registres
Mémoire
Cache
Mémoire
Centrale
Mémoire cache
Le cache en
lecture
A
A+4
A+8
A+12
A + 16
Bus
Local
SRAM
DRAM
Bus
Si (A) présent Alors Charger processeur avec (A)
Lecture
Load D R1 A
FinSi
Sinon
FinSi
Charger cache avec (A) et ses voisines
Charger processeur avec (A)
Architecture des machines 2006-2007
Joëlle Delacroix
20
Processeur
Registres
Mémoire
Cache
Mémoire
Centrale
Mémoire cache
Le cache en
lecture
A
A+4
A+8
A+12
A + 16
Bus
Local
(A)
SRAM
DRAM
Bus
Si (A) présent Alors Charger processeur avec (A)
Lecture
Load D R1 A
FinSi
Sinon
FinSi
Charger cache avec (A) et ses voisines
Charger processeur avec (A)
Architecture des machines 2006-2007
Joëlle Delacroix
21
Processeur
Registres
Mémoire
Cache
Mémoire
Centrale
Mémoire cache
Le cache en
lecture
A
A+4
A+8
A+12
A +16
Bus
Local
A
A+4
A+8
A+12
A + 16
SRAM
Bus
DRAM
Si (A) présent Alors Charger processeur avec (A)
Lecture
Load D R1 A
FinSi
Sinon
FinSi
Charger cache avec (A) et ses voisines
Charger processeur avec (A)
Architecture des machines 2006-2007
Joëlle Delacroix
22
Processeur
Registres
Mémoire
Cache
Mémoire
Centrale
Mémoire cache
Le cache en
écriture
Bus
Local
DRAM
SRAM
Bus
Ecriture
Store D R1 A
Si (A) présente Alors Modifier (A) dans le cache
Modifier (A) en mémoire principale
Sinon Modifier (A) en mémoire principale
Write Through
Write Back
FinSi
Architecture des machines 2006-2007
Joëlle Delacroix
23
Processeur
Registres
Mémoire
Cache
Mémoire
Centrale
Bus
Local
Mémoire cache
Le cache en
écriture
A
A+4
A+8
A+12
A + 16
SRAM
DRAM
Bus
Ecrire (R1) dans A
Ecriture
Store D R1 A
Si (A) présente Alors Modifier (A) dans le cache
Modifier (A) en mémoire principale
Sinon Modifier (A) en mémoire principale
Write Through
Write Back
FinSi
Architecture des machines 2006-2007
Joëlle Delacroix
24
Processeur
Registres
Mémoire
Cache
Mémoire
Centrale
Bus
Local
16(cid:198)10
(A)
16
Ecrire (R1)
dans A
R1
10
DRAM
SRAM
Bus
Ecriture
Store D R1 A
Mémoire cache
Le cache en
écriture
A
A+4
A+8
A+12
A+ 16
Si (A) présente Alors Modifier (A) dans le cache
Modifier (A) en mémoire principale
Sinon Modifier (A) en mémoire principale
Write Through
Write Back
FinSi
Architecture des machines 2006-2007
Joëlle Delacroix
25
Processeur
Registres
Mémoire
Cache
Mémoire
Centrale
Bus
Local
Ecrire (R1)
dans A
R1
10
10
(A)
16
SRAM
DRAM
Bus
DMA
UE
Imprimer (A)
Mémoire cache
Le cache en
écriture
A
A+4
A+8
A+12
A +16
Le contenu du cache
pour (A) est différent de
la MC
(cid:198) Un autre dispositif tel
que un DMA accédant
à (A) ne voit pas la
valeur modifiée
(cid:198) Politique de
modification de la MC
Architecture des machines 2006-2007
Joëlle Delacroix
26
Processeur
Registres
Mémoire
Cache
Mémoire
Centrale
Mémoire cache
Le cache en
écriture
Bus
Local
16(cid:198)10
(A)
16(cid:198)10
A
A+4
A+8
A+12
A + 16
SRAM
DRAM
Bus
Ecrire (R1)
dans A
Ecrire (R1)
dans A
R1
10
Ecriture
Store D R1 A
Si (A) présente Alors Modifier (A) dans le cache
Modifier (A) en mémoire principale
Architecture des machines 2006-2007
Joëlle Delacroix
Write Through
(écriture
Immédiate)
L’écriture en
mémoire
centrale est
effectuée en
même temps
que dans le
cache
(cid:198) Cohérence
maximale
(cid:198) Coût plus
élevé d’une
écriture
27
Processeur
Registres
Mémoire
Cache
Mémoire
Centrale
Mémoire cache
Le cache en
écriture
Bus
Local
16(cid:198)10
(A)
16
Ecrire (R1)
dans A
R1
10
SRAM
DRAM
Bus
A
A+4
A+8
A+12
A + 16
Ecriture
Store D R1 A
Si (A) présente Alors Modifier (A) dans le cache
Modifier (A) en mémoire principale
Write Back
(écriture différée)
L’écriture en
mémoire centrale
est effectuée plus
tard lorsque
l’entrée du cache
doit être
remplacée
(cid:198) Cohérence
moindre
(cid:198) Coût moins
élevé d’une
écriture
Architecture des machines 2006-2007
Joëlle Delacroix
28
Processeur
Registres
Mémoire
Cache
Bus
Local
A (10)
A+4
A+8
A+12
A + 16
SRAM
Mémoire
Centrale
16(cid:198) 10
B
B+4
B+8
B+12
B + 16
A
A+4
A+8
A+12
A + 16
Bus
DRAM
Ecrire l’entrée du cache modifiée
Publicité
dans A
R1
10
Ecriture
Load D R2 B
Mémoire cache
Le cache en
écriture
Write Back
(écriture différée)
L’écriture en
mémoire centrale
est effectuée plus
tard lorsque
l’entrée du cache
doit être
remplacée
(cid:198) Cohérence
moindre
(cid:198) Coût moins
élevé d’une
écriture
Il y a défaut au niveau du cache. Le mot B et ses voisins
doivent être chargés dans le cache.
Ils remplacent le mot A et ses voisins.
La modification de (A) est recopiée en mémoire centrale
Architecture des machines 2006-2007
Joëlle Delacroix
29
Mémoire cache
Performances
Soient
h, la probabilité de succès
Tc le temps d’accès au cache
Tm, le temps de lecture d’un bloc de mots en mémoire centrale
Td, le temps d’accès à un mot en mémoire centrale
alors Teff, le temps effectif pour accéder à une information
Teff = h × Tc + (1 – h) × (Tm + Tc)
h
0,9
0,8
Architecture des machines 2006-2007
0,7
Tc
(cycle)
Tm
(cycle)
Td
(cycle)
Teff
1
1
1
20
20
20
5
5
5
Joëlle Delacroix
3
5
7
30
Mémoire cache
Architecture de caches
Puce processeur
UC
registres
Cache
données
Cache
instructions
Niveau L1
Niveau L2
Cache
unifié
Mémoire
centrale
Bus interne
Architecture des machines 2006-2007
Back side bus
500 Mhz
Joëlle Delacroix
Front side bus
100 Mhz
31
Les mémoires de l’ordinateur
Le principe de hiérarchie mémoire : les caches
Les structures de caches
Puce processeur
UC
registres
Cache
données
Cache
instructions
Niveau L1
Niveau L2
Cache
unifié
Architecture des machines 2006-2007
Joëlle Delacroix
32
Mémoire cache : structure
• La recherche d’un mot dans le cache s’effectue à partir de son
adresse en mémoire centrale.
• Un cache est caractérisé :
(cid:41) sa capacité
Nombre d’entrées * taille du bloc de données
128 * 16 octets
(cid:41) son organisation
– Cache associatif
– Cache direct
– Cache mixte
Architecture des machines 2006-2007
Joëlle Delacroix
33
Mémoire cache : structure
• Les blocs d’octets
chargés dans les entrées
du cache (ligne du
cache) sont alignés,
c’est-à-dire que l’adresse
du premier octet du bloc
est toujours un multiple
de la taille du bloc en
octet.
• Exemple : blocs de 16
octets; adresse de 6 bits
Bloc 0
Bloc 1
Bloc 2
Bloc 3
000000 - 001111
010000 - 011111
100000 - 101111
110000 - 111111
Architecture des machines 2006-2007
Joëlle Delacroix
34
Mémoire cache : structure
0000
0001
0010
0100
0101
0110
1000
1001
1010
1100
1101
1110
0011
0111
1011
1111
Bloc 0
000000 - 001111
Bloc 1
010000 - 011111
Numéro de l’octet dans le bloc
Bloc 2
100000 - 101111
Etiquette du bloc
Bloc 3
110000 - 111111
Architecture des machines 2006-2007
Joëlle Delacroix
35
Mémoire cache : structure
cache
• Trois types de cache :
(cid:41) associatif : un bloc de mots de la
mémoire centrale est placé dans
n'importe quelle entrée (ligne) libre
du cache
(cid:41) à correspondance directe : l'entrée
(ligne) du cache occupée par un
bloc de mots est fonction de
l'adresse en mémoire centrale de ce
bloc.
(cid:41) mixte
Répertoire :
Contient l’étiquette du bloc
présent dans l’entrée du cache
Donnée utiles
Contient le bloc de mots
(n octets)
Architecture des machines 2006-2007
Joëlle Delacroix
36
Les mémoires de l’ordinateur
Le principe de hiérarchie mémoire : les caches
Les structures de caches
Cache associatif
Puce processeur
Niveau L2
Cache
unifié
UC
registres
Cache
données
Cache
instructions
Niveau L1
Architecture des machines 2006-2007
Joëlle Delacroix
37
Cache associatif
• Un bloc de mots de la mémoire centrale est placé
dans n'importe quelle entrée libre du cache
(cid:41) si le cache est plein, il faut libérer une entrée
Algorithme de remplacement de ligne
Architecture des machines 2006-2007
Joëlle Delacroix
38
Cache purement associatif (lecture)
Adresse mémoire
Etiquette n°octet
Répertoire
Comparateurs
Mémoire utile
contenant les
Mots :
Instructions
ou
données
octet
trouvé
Si Répertoire contient Etiquette Alors bloc de mots trouvé
Charger le processeur avec ligne[n°octet]
Sinon Si Répertoire plein Alors
Algorithme de remplacement
de ligne
Remplir la ligne choisie
Charger le processeur avec
ligne[n°octet]
Sinon Remplir une ligne libre
Charger le processeur avec
ligne [n°octet]
FinSi
Architecture des machines 2006-2007
Joëlle Delacroix
39
FinSi
Load D R1 3D16
00111101
0
1
2
3
4
5
6
7
Chaque bloc contient 8 octets (cid:198) 3 bits de poids faible pour les désigner
L’étiquette est formée des 5 bits de poids fort
Mémoire centrale
a b c d e f g h
00
08
10
30
38
E8
F0
F8
Si répertoire contient 00111 Alors Charger f dans processeur
Sinon Si répertoire plein Alors Remplacement ligne
Cache purement associatif : Lecture
Architecture des machines 2006-2007
Remplir ligne
Charger f dans processeur
Sinon Remplir une ligne
Charger f dans processeur
Joëlle Delacroix
40
Load D R1 3D16
00111101
0
1
2
3
4
5
6
7
00111
a b c d e f g h
Chaque bloc contient 8 octets (cid:198) 3 bits de poids faible pour les désigner
L’étiquette est formée des 5 bits de poids fort
Mémoire centrale
a b c d e f g h
00
08
10
30
38
E8
F0
F8
Si répertoire contient 00111 Alors Charger f dans processeur
Sinon Si répertoire plein Alors Remplacement ligne
Cache purement associatif : Lecture
Architecture des machines 2006-2007
Remplir ligne
Charger f dans processeur
Sinon Remplir une ligne
Charger f dans processeur
Joëlle Delacroix
41
Load D R1 3D16
00111101
Il existe des
lignes libres
dans le cache
0
1
2
3
4
5
6
7
00000
00001
i j k l m n o p
q r s t u v w x
11111
y z a b c d e f
Chaque bloc contient 8 octets (cid:198) 3 bits de poids faible pour les désigner
L’étiquette est formée des 5 bits de poids fort
Mémoire centrale
i j k l m n o p
q r s t u v w x
a b c d e f g h
y z a b c d e f
00
08
10
30
38
E8
F0
F8
Si répertoire contient 00111 Alors Charger f dans processeur
Sinon Si répertoire plein Alors Remplacement ligne
Cache purement associatif : Lecture
Architecture des machines 2006-2007
Remplir ligne
Charger f dans processeur
Sinon Remplir une ligne
Charger f dans processeur
Joëlle Delacroix
42
Load D R1 3D16
00111101
Il existe des
lignes libres
dans le cache
0
1
2
3
4
5
6
7
00000
00111
00001
i j k l m n o p
a b c d e f g h
q r s t u v w x
11111
y z a b c d e f
Chaque bloc contient 8 octets (cid:198) 3 bits de poids faible pour les désigner
L’étiquette est formée des 5 bits de poids fort
Mémoire centrale
i j k l m n o p
q r s t u v w x
a b c d e f g h
y z a b c d e f
00
08
10
30
38
E8
F0
F8
Si répertoire contient 00111 Alors Charger f dans processeur
Sinon Si répertoire plein Alors Remplacement ligne
Cache purement associatif : Lecture
Architecture des machines 2006-2007
Remplir ligne
Charger f dans processeur
Sinon Remplir une ligne
Charger f dans processeur
Joëlle Delacroix
43
Load D R1 3D16
00111101
Il n’existe pas
de lignes libres
dans le cache
0
1
2
3
4
5
6
7
00000
00011
00001
00010
00110
11101
11111
Publicité
11110
i j k l m n o p
l r c u e k g r
q r s t u v w x
a z e r v b n e
b v e y l m n p
t i o b f l g a
y z a b c d e f
r t a b g l e ù
Chaque bloc contient 8 octets (cid:198) 3 bits de poids faible pour les désigner
L’étiquette est formée des 5 bits de poids fort
Mémoire centrale
i j k l m n o p
q r s t u v w x
a z e r v b n e
l r c u e k g r
b v e y l m n p
a b c d e f g h
00
08
10
18
30
38
E8
F0
F8
t i o b f l g a
r t a b g l e ù
y z a b c d e f
Si répertoire contient 00111 Alors Charger f dans processeur
Sinon Si répertoire plein Alors Remplacement ligne
Cache purement associatif : Lecture
Architecture des machines 2006-2007
Remplir ligne
Charger f dans processeur
Sinon Remplir une ligne
Charger f dans processeur
Joëlle Delacroix
44
Load D R1 3D16
00111101
Il n’existe pas
de lignes libres
dans le cache
On choisit une
ligne à remplacer
0
1
2
3
4
5
6
7
00000
00011
00001
00010
00110
11101
11111
00111
i j k l m n o p
l r c u e k g r
q r s t u v w x
a z e r v b n e
b v e y l m n p
t i o b f l g a
y z a b c d e f
a b c d e f g h
Chaque bloc contient 8 octets (cid:198) 3 bits de poids faible pour les désigner
L’étiquette est formée des 5 bits de poids fort
Mémoire centrale
i j k l m n o p
q r s t u v w x
a z e r v b n e
l r c u e k g r
b v e y l m n p
a b c d e f g h
00
00
08
08
10
10
18
30
38
E8
F0
F8
t i o b f l g a
r t a b g l e ù
y z a b c d e f
Si répertoire contient 00111 Alors Charger f dans processeur
Sinon Si répertoire plein Alors Remplacement ligne
Cache purement associatif : Lecture
Architecture des machines 2006-2007
Remplir ligne
Charger f dans processeur
Sinon Remplir une ligne
Charger f dans processeur
Joëlle Delacroix
45
Cache associatif
• Un bloc de mots de la mémoire centrale est placé dans
n'importe quelle entrée libre du cache
(cid:41) si le cache est plein, il faut libérer une entrée
Algorithme de remplacement de ligne
(cid:41)Aléatoire : une ligne au hasard
(cid:41)FIFO : First In First Out : la ligne remplacée est la plus
ancienne dans le cache
(cid:41)LRU : Least recently Used : la ligne remplacée est la moins
récemment accédée
(cid:41)NMRU : Not most recently Used : la ligne remplacée n’est
pas la plus récemment utilisée
Architecture des machines 2006-2007
Joëlle Delacroix
46
Cache associatif
Algorithme de remplacement de ligne
FIFO : First In First Out : la ligne remplacée est la plus ancienne dans le
cache.
Simple mais pas forcément pertinent.
Accès
(étiquette bloc)
00000 00001 00010 00100 00000 10000 00010 11000
00000 00000 00000 00000 00000 10000 10000 10000
Ligne 0
Ligne 1
Ligne 2
Ligne 3
00001 00001 00001 00001 00001 00001 11000
00010 00010 00010 00010 00010 00010
00100 00100 00100 00100 00100
Architecture des machines 2006-2007
Joëlle Delacroix
47
D D D D S
D S D
Cache associatif
Algorithme de remplacement de ligne
LRU : Least recently Used : la ligne remplacée est la moins récemment
accédée
Complexe à mettre en œuvre car nécessite de maintenir l’ordre des accès.
Accès
(étiquette bloc)
00000 00001 00010 00100 00000 10000 00010 11000
00000 00000 00000 00000 00000 00000 00000 00000
Ligne 0
Ligne 1
Ligne 2
Ligne 3
00001 00001 00001 00001 10000 10000 10000
00010 00010 00010 00010 00010 00010
00100 00100 00100 00100 11000
Architecture des machines 2006-2007
Joëlle Delacroix
48
D D D D S
D S D
Cache associatif
Algorithme de remplacement de ligne
NMRU : Not most recently Used : la ligne remplacée n’est pas la plus récemment
utilisée. La ligne remplacée est choisie aléatoirement parmi celles autres
que la ligne la plus récemment accédée.
Moins coûteux que LRU
La moins récemment accédée
LRU
NMRU
Accès
(étiquette bloc)
Ligne 0
Ligne 1
Ligne 2
Ligne 3
00000 00001 00010 00100 00000 10000
00000 10000
00000 00000 00000 00000 00000 00000
00000
00000
00001 00001 00001 00001 10000
00001
00001
00010 00010 00010 00010
00010
10000
00100 00100 00100
00100
00100
Architecture des machines 2006-2007
Joëlle Delacroix
D D D D S
D
La plus récemment accédée
49
Cache associatif
• Coûteux et « encombrants » : 1 comparateur par ligne.
• Complexe : politique de remplacement de ligne.
• Format d’une entrée de cache (répertoire)
LRU : date de dernier accès
FIFO : date de chargement
1
1
V D
Champ
remplacement
étiquette
Clé de recherche
Bit de validité
0 : la ligne ne contient pas de données valides
1 : l’entrée contient des données valides
Bit de modification (dirty bit) (cid:198) politique en écriture différée
0 : le contenu de la ligne n’ pas été modifié
1 : le contenu de la ligne a été modifié
Architecture des machines 2006-2007
Joëlle Delacroix
50
Cache associatif
LRU : date de dernier accès
FIFO : date de chargement
1
1
V D
Champ
remplacement
étiquette
Clé de recherche
Bit de validité
0 : la ligne ne contient pas de données valides
1 : l’entrée contient des données valides
Bit de modification (dirty bit) (cid:198) politique en écriture différée
0 : le contenu de la ligne n’ pas été modifié
1 : le contenu de la ligne a été modifié
Si Répertoire contient Etiquette Alors Bloc de mots trouvé
(entrée avec bit V à 1)
Charger le processeur avec ligne[n°octet]
Sinon Si Répertoire plein Alors
Algorithme de remplacement de ligne
Si (écriture différée et D = 1)
Alors écrire ligne en mémoire centrale
Finsi
Remplir la ligne choisie
Charger le processeur avec ligne[n°octet]
Sinon Remplir une ligne libre (V = 1)
Charger le processeur avec ligne [n°octet]
FinSi
FinSi
Architecture des machines 2006-2007
Joëlle Delacroix
51
Les mémoires de l’ordinateur
Le principe de hiérarchie mémoire : les caches
Les structures de caches
Cache à correspondance directe
Puce processeur
UC
registres
Cache
données
Cache
instructions
Niveau L1
Niveau L2
Cache
unifié
Architecture des machines 2006-2007
Joëlle Delacroix
52
Cache à correspondance directe
• Un bloc de mots de la mémoire centrale est placé dans une entrée
du cache qui est fonction de son adresse en mémoire centrale.
Load D R2 EF16
11101111
Load D R1 3D16
00111101
0
1
2
3
4
5
6
7
11
00
t i o b f l g a
a b c d e f g h
00
00
08
08
10
10
18
30
38
i j k l m n o p
q r s t u v w x
a z e r v b n e
l r c u e k g r
b v e y l m n p
a b c d e f g h
Chaque bloc contient 8 octets (cid:198) 3 bits de poids faible pour les désigner
Le cache contient 8 entrées (cid:198) 3 bits pour les désigner
L’étiquette est formée des 2 bits de poids fort restant
Architecture des machines 2006-2007
Joëlle Delacroix
E8
F0
F8
t i o b f l g a
r t a b g l e ù
y z a b c d e f
53
Cache à correspondance directe
• Un bloc de mots de la mémoire centrale est placé dans une entrée
du cache qui est fonction de son adresse en mémoire centrale.
Load D R2 FF16
11111111
index
Load D R1 3D16
00111101
0
1
2
3
4
5
6
7
11
t i o b f l g a
Deux (n) blocs de la
mémoire centrale
entrent dans la même
entrée du cache
(tous ceux ayant la
même valeur d’index)
La valeur d’étiquette
stockée dans la ligne
permet de connaître
quel bloc occupe la
ligne à un instant donné
Chaque bloc contient 8 octets (cid:198) 3 bits de poids faible pour les désigner
Le cache contient 8 entrées (cid:198) 3 bits pour les désigner
L’étiquette est formée des 2 bits de poids fort restant
Architecture des machines 2006-2007
Joëlle Delacroix
54
Cache à correspondance directe
Adresse mémoire
Etiquette
Index n° octet
Répertoire
contient les
étiquettes
Mémoire utile
contient les
mots :
instructions
ou
données
Octet trouvé
Si Répertoire [Index] = Etiquette Alors Bloc de mots trouvé
Charger processeur avec MemoireUtile[Index,n°octet]
Sinon Répertoire[Index] = Etiquette
Charger Ligne[Index] à partir de la mémoire centrale
Charger processeur avec MémoireUtile[Index,n°octet]
FinSi
Architecture des machines 2006-2007
Joëlle Delacroix
55
Cache à correspondance directe
Load D R1 3D16
00111101
0
1
2
3
4
5
6
7
11
00
t i o b f l g a
a b c d e f g h
00
00
08
08
10
10
18
30
38
i j k l m n o p
q r s t u v w x
a z e r v b n e
l r c u e k g r
b v e y l m n p
a b c d e f g h
E8
F0
F8
t i o b f l g a
r t a b g l e ù
y z a b c d e f
Si Répertoire [111] = 00 Alors
Bloc de mots trouvé
Charger processeur avec MemoireUtile[111,101] (f)
Sinon Répertoire[Index] = Etiquette
Charger Ligne[Index] à partir de la mémoire centrale
Charger processeur avec MémoireUtile[Index,n°octet]
FinSi
Architecture des machines 2006-2007
Joëlle Delacroix
56
Cache à correspondance directe
Load D R1 3D16