80
Caches 1 Référence à un mot Xn dans le cache Mémoir e Centra le UC X4 X1 Xn-2 Xn-1 X5 X3

Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Embed Size (px)

Citation preview

Page 1: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 1

Référence à un mot Xn dans le cache

MémoireCentraleMémoireCentraleUCUC

X4

X1

Xn-2

Xn-1

X5

X3

X4

X1

Xn-2

Xn-1

X5

X3

Page 2: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 2

Référence à un mot Xn dans le cache

MémoireCentraleMémoireCentraleUCUC

X4

X1

Xn-2

Xn-1

X5

X3

X4

X1

Xn-2

Xn-1

X5

X3

UC veut faire référence à Xn

1

Xn

Page 3: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 3

Référence à un mot Xn dans le cache

Recherche de Xn dans le cache

MémoireCentraleMémoireCentraleUCUC

X4

X1

Xn-2

Xn-1

X5

X3

X4

X1

Xn-2

Xn-1

X5

X3

2

Xn

Page 4: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 4

Référence à un mot Xn dans le cache

Recherche de Xn dans le cache

MémoireCentraleMémoireCentraleUCUC

X4

X1

Xn-2

Xn-1

X5

X3

X4

X1

Xn-2

Xn-1

X5

X3

Xn

Défau

t de

cach

e

2

Page 5: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 5

Référence à un mot Xn dans le cache

Extraction de Xn dans la mémoireInsertion dans le cache

MémoireCentraleMémoireCentraleUCUC

X4

X1

Xn-2

Xn-1

X5

Xn

X3

X4

X1

Xn-2

Xn-1

X5

Xn

X3

3

Page 6: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 6

Bilan : Référence à un mot Xn

X4

X1

Xn-2

Xn-1

X5

Xn

X3

Après la référence à Xn

X4

X1

Xn-2

Xn-1

X5

X3

Avant la référence à Xn

Page 7: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 7

Questions à résoudre

• Question 1 : Où placer un bloc?

• Question 2 : Comment un bloc est-il trouvé ?

• Question 3 : Quel bloc remplacé lors d’un défaut ?

• Question 4 : Comment sont traités les écritures?

Page 8: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 8

Question 1 :

Où placer un bloc?

• Caches à correspondances directes

• Caches totalement associatifs

• Caches associatifs par ensemble

Page 9: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 9

Les caches à correspondance directe

Le moyen le plus simple est d’assigner un emplacement unique dans le cache. Cet emplacement est fonction du mot en mémoire.

La correspondance est la suivante : numéro de bloc modulo le nombre de blocs dans le cache

Cette structure du cache est dite à correspondance directe.

adresse

Rappel : Modulo n = reste de la division par n

Page 10: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 10

Cache à correspondance directe 8 entrées

MémoireCentraleMémoireCentraleUCUC

Exemple :

Page 11: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 11

Cache à correspondance directe 8 entrées

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

AdresseDonnéeAdresse Donnée

?

Page 12: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 12

Cache à correspondance directe 8 entrées

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

1 mod 8 = 1

Page 13: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 13

Cache à correspondance directe 8 entrées

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

Page 14: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 14

Cache à correspondance directe 8 entrées

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

Aux 4 adresses 00001, 01001, 10001, 11001

correspond la même entrée d’index (adresse dans le cache)

001 du cache

Aux 4 adresses 00001, 01001, 10001, 11001

correspond la même entrée d’index (adresse dans le cache)

001 du cache

Page 15: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 15

Cache à correspondance directe 8 entrées

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

Page 16: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 16

Cache à correspondance directe 8 entrées

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

PROBLEME :

Un emplacement dans le cache peut appartenir à plusieurs emplacements mémoire.Comment savoir si la donnée correspond au mot demandé ?

PROBLEME :

Un emplacement dans le cache peut appartenir à plusieurs emplacements mémoire.Comment savoir si la donnée correspond au mot demandé ?

Page 17: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 17

Cache à correspondance directe 8 entrées

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

Réponse :

Une Étiquette permet de savoir si le mot demandé est dans le cache

DonnéeEtiquette

Page 18: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 18

Cache à correspondance directe 8 entrées

UCUC

000

001

010

011

100

101

110

111 11001

11101

10001

10101

01001

01101

00001

00101

Index Etiquette donnée

00

01

Page 19: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 19

Question 1 :

• Où placer un bloc?

Caches à correspondance directe

• Caches totalement associatifs

Caches associatifs par ensemble

Page 20: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 20

Les caches totalement associatifs

Si un bloc peut être placé n’importe où dans le cache, celui ci est totalement associatif.

Page 21: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 21

Les caches totalement associatifs

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

?

Page 22: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 22

Les caches totalement associatifs

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

Page 23: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 23

Question 1 :

• Où placer un bloc?

Caches à correspondance directe

Caches totalement associatifs

• Caches associatifs par ensemble

Page 24: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 24

Caches associatif par ensemble

Si un bloc peut être placé dans un ensemble restreint de places dans le cache, le cache est dit associatif par ensemble de blocs. Un ensemble est un groupe de blocs dans le cache.

Un bloc est d’abord affecté à un ensemble, puis placé n’importe où dans l’ensemble.

numéro de l’ensemble =

numéro de bloc (=adresse) modulo le nombre d’ensembles dans le cache

Page 25: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 25

Cache associatif par ensemble de 2

UCUC

11001

11101

10001

10101

01001

01101

00001

00101Et D Et D

0

1

2

3

Ensembles

Page 26: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 26

Cache associatif par ensemble de 2

UCUC

11001

11101

10001

10101

01001

01101

00001

00101

17 mod 4 = 1

Et D Et D

0

1

2

3

Page 27: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 27

Alors quel cache est à utiliser ?

• Augmenter le degré d’associativité présente généralement l’avantage de diminuer le taux de défaut. (Voir TD)

• Mais cela a tendance à augmenter le coût et le temps d’accès.

Page 28: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 28

But du cours

Question 1 : Où placer un bloc?

• Question 2 : Comment un bloc est-il trouvé ?

Question 3 : Quel bloc remplacé lors d’un défaut ?

Question 4 : Comment sont traités les écritures?

Page 29: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 29

Organisation de la mémoire principale

0 1 2 3

4 5 6 7

8 9 10 11

0

4

8

Adresse du mot Adresse de l’octet

Rappels :

Page 30: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 30

Organisation de la mémoire principale

4 5 6 7

Adresse du mot Adresse de l’octet

0 1 2 3

4 5 6 7

8 9 10 11

MémoireMémoire

CacheCache

Transfert du mot de 32 bits

Pour me déplacer dans le bloc il faut 2 bits d’adresse

0

4

8

Page 31: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 31

Comment trouver un bloc ?

Réponse :Quelle est la relation de l’adresse UC avec le cache ?

N° ensemble Déplacement dans le bloc

Cache associatif par ensemble de bloc

Etiquette Déplacement dans le bloc

Cache direct

Etiquette

Taille =Log2(blocCache)-1

Index

Remarque : en augmentant d’un facteur de deux l’associativité on diminue de 1 bit la taille de l’index.

Page 32: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 32

Exemple : Cache à correspondance directe

Validité Etiquette donnéeIndex 0

12..................10221023

Succès

Page 33: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 33

UC veut la donnée qui est à l’adresse :

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Etiquette Index

Validité Etiquette donnéeIndex 0

12..................10221023

Adresse d’octet

32

UCUC

Page 34: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 34

L’index sélectionne une entrée du cache :

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Etiquette Index

Validité Etiquette donnéeIndex 0

12..................10221023

Adresse d’octet

32

UCUC

Page 35: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 35

Compare l’étiquette

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Etiquette Index

Validité Etiquette donnéeIndex 0

12..................10221023

Adresse d’octet

=

UCUC

Page 36: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 36

Le mot est délivré au processeur.

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Etiquette Index

Validité Etiquette donnéeIndex 0

12..................10221023

Adresse d’octet

32

SUCCESSUCCES

UCUC

ET

Page 37: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 37

En cas de défaut

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Etiquette Index

Mémoire

Cache Défaut/succès

Donnée

Donnée

Adresse

UC

Un défaut de cache génère une suspension (ou attente), semblable aux suspension de pipeline

Page 38: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 38

Exemple : Par ensemble (256) de 4 blocs

V E DIndex

012..................253254255

V E D V E D V E D

Succès Donnée

Multiplexeur 4 par 1

4 Blocs

256 Ensembles

Page 39: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 39

Par ensemble (256) de 4 blocs

V E DIndex

012..................253254255

V E D V E D V E D

Succès Donnée

Multiplexeur 4 par 1

4 Blocs

256 Ensembles

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Adresse d’octet

UCUC

Page 40: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 40

Par ensemble (256) de 4 blocs

V E DIndex

012..................253254255

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Adresse d’octet

V E D V E D V E D

Succès Donnée

Multiplexeur 4 par 1

822

Page 41: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 41

Par ensemble (256) de 4 blocs

V E DIndex

012..................253254255

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Adresse d’octet

V E D V E D V E D

Succès Donnée

Multiplexeur 4 par 1

822

Page 42: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 42

Par ensemble (256) de 4 blocs

V E DIndex

012..................253254255

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Adresse d’octet

V E D V E D V E D

Succès Donnée

Multiplexeur 4 par 1

822

Page 43: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 43

Les étiquettes en fonction du type de caches

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Adresse d’octet

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Etiquette Index

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Adresse d’octet

Etiquette

Etiquette

Index

Totalement associatif

Associatif par ensemble de bloc

Correspondance directe

Pour des caches de même dimension :

Page 44: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 44

But du cours

• Question 1 : Où placer un bloc?

• Question 2 : Comment un bloc est-il trouvé ?

• Question 3 : Quel bloc remplacé lors d’un défaut ?

• Question 4 : Comment sont traités les écritures?

Page 45: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 45

Quel bloc remplacé lors d’un défaut ?

Il existe trois stratégies principales employées pour choisir le bloc à remplacer :

• FIFO (Pas bonne)

• Le hasard (facile à réaliser)

• Le plus ancien (LRU Least Rencently Used). Ceci utilise un corollaire de la localité temporelle.

Remarque = de LRU.

Page 46: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 46

Les défauts de caches

• Défauts obligatoires de chargement (défaut de démarrage à froid). Un bloc accédé pour la première fois n’est pas dans le cache.

• Défauts de capacité. Si le cache ne peut contenir tous les blocs nécessaires au cours de l’exécution d’un programme

• Défauts de conflits (défaut de collision). Si la stratégie de placement de bloc est associative par ensembles de blocs ou à correspondance directe, des défauts de conflit surviendront, car un bloc peut être rejeté puis récupéré si trop de blocs sont en correspondance avec le même ensemble.

Page 47: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 47

But du cours

• Question 1 : Où placer un bloc?

• Question 2 : Comment un bloc est-il trouvé ?

• Question 3 : Quel bloc remplacé lors d’un défaut ?

• Question 4 : Comment sont traités les écritures?

Page 48: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 48

Comment sont traités les écritures?

L’écriture simultanée (ou rangement simultané) :

L’information est écrite à la fois dans le bloc du cache et dans le bloc de la mémoire de niveau inférieur.

La réécriture (la recopie) :

L’information est écrite uniquement dans le bloc du cache. Le bloc modifié du cache est recopié en mémoire principale uniquement quand il est remplacé.

Page 49: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 49

Comment tirer parti de la localité spatiale ?

• Le cache que nous avons décrit jusqu’à présent ne tire pas parti de la localité spatiale dans les requêtes. En effet, chaque mot dispose de son propre bloc.

EXEMPLE

• Supposons que les adresses d’octets suivantes soient demandées par un programme :

Page 50: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 50

Exemple : 16,...,19,...,17

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

Page 51: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 51

Exemple : 16,...,19,...,17

UC16

UC16

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

1610000

Etiquette Index

Page 52: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 52

Exemple : 16,...,19,...,17

UC16

UC16

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

1610000

Etiquette Index

DEFAUT

Page 53: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 53

Exemple : 16,...,19,...,17

UC16

UC16

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

1610000

Etiquette Index

10

Page 54: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 54

Exemple : 16,...,19,...,17

UC19

UC19

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

1910011

Etiquette Index

Page 55: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 55

Exemple : 16,...,19,...,17

UC19

UC19

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

Etiquette Index

DEFAUT

1910011

Page 56: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 56

Exemple : 16,...,19,...,17

UC19

UC19

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

Etiquette Index

10

1910011

Page 57: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 57

Exemple : 16,...,19,...,17

UC17

UC17

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

Etiquette Index

10

1710001

DEFAUT

Page 58: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 58

Exemple : 16,...,19,...,17

UCUC

000

001

010

011

100

101

110

111

10

Bilan :3 défauts

Page 59: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 59

Comment diminuer les défauts :

Ce Dupont ....Dans mes bras

THE BOSS

= Augmenter la taille des blocs

Page 60: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 60

Caches à 4 mots mémoire

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

Page 61: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 61

Caches à 4 mots mémoire

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

index adresse dans le blocremarque : pas d’étiquette

2 bits3 bits

Page 62: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 62

Exemple : 16,...,19,...,17

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

index adresse dans le blocremarque : pas d’étiquette

100 00

16DEFAUT

Page 63: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 63

Exemple : 16,...,19,...,17

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

1610000

index adresse dans le blocremarque : pas d’étiquette

16 16 17 18 19

On ramène les ref :16,17,18,19

Page 64: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 64

Exemple : 16,...,19,...,17

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

1910011

index adresse dans le blocremarque : pas d’étiquette

19 16 17 18 19

succès

Page 65: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 65

Exemple : 16,...,19,...,17

UCUC

000

001

010

011

100

101

110

11111001

11101

10001

10101

01001

01101

00001

00101

1710001

index adresse dans le blocremarque : pas d’étiquette

17 16 17 18 19

succès

Page 66: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 66

Exemple : 16,...,19,...,17

• Bilan : 1 seul défaut survient pour trois références.

SUPER : JE SUIS LE MEILLEUR

Page 67: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 67

Exemple de réalisation

31 30 29 28 ...............16 15 14 13 12 11 10 9 ...4 3 2 1 0

Etiquette Index

Validité Etiqu donnée 128 bitsIndex 0

12..................254255

Adresse d’octet

32MuxMux

Adresse dans le bloc

Page 68: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 68

Exemple : 16,...,19,...,17

• Bilan : 1 seul défaut survient pour trois références.

• SUPER : JE SUIS LE MEILLEUR

DUPONT and Co

Page 69: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 69

Si nous avons les temps d’accès suivants :

1 cycle d’horloge pour envoyer l’adresse

10 cycles d’horloge pour chaque accès mémoire

1 cycle d’horloge pour envoyer un mot de donnée.

Total = 3* (1+10+1) = 36 cycles

Page 70: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 70

Exemple : 16,...,19,...,17

Reprenons les chiffres précédent :

1 cycle d’horloge pour envoyer l’adresse

10 cycles d’horloge pour chaque accès mémoire

1 cycle d’horloge pour envoyer un mot de donnée.

Total = 1+4*10+4*1 = 45 cycles

Le gain n’est pas ici énorme !!!!!.

Comment diminuer ce temps ?

Page 71: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 71

Tirer parti de la localité spatiale

Question : De quelle manière une plus grande taille de bloc influence-t-elle les performances ?

Le taux de défauts chute lorsque nous augmentons la taille de bloc.

Attention : il faut adapter le système mémoire en conséquence.

Page 72: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 72

UC

Cache

Bus

Mémoire

UC

Cache

Bus

Mémoire

UC

Cache

Bus

BM

BM

BM

BM

Page 73: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 73

Organisation d’une mémoire entrelacée

Adresse externe a=4b

b b b b

Mot 1 Mot 2 Mot 3 Mot 4

0 1 2 34 5 6 78 9 . ..

Mém

oire entrelacée

Page 74: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 74

Encore plus compliqué :

ATTENTION (voir TD)

Le taux de défaut peut augmenter, si la taille de bloc est prise très grande par rapport à la taille du cache, car le nombre de blocs pouvant être contenus dans le cache deviendra petit, et la compétition entre ces blocs sera rude. Par conséquent un bloc sera éjecté du cache avant qu’un grand nombre de ses mots soit accédé.

Le coût du défaut croît. Car le temps nécessaire(si on ne modifie pas le système mémoire).

Page 75: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 75

Les performances des caches

• Le temps UC est divisé entre les cycles d’horloge passés par l’UC à exécuter le programme et les cycles d’horloge que l’UC passe à attendre le système mémoire.

Tps UC = (Cycles d’exécution UC + Cycles d’attente mémoire) * Tps C

Page 76: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 76

Les cycles d’attente mémoire

• Les cycles d’horloge d’attente mémoire proviennent principalement des défauts de cache.

(Une prédiction précise des performances implique généralement des simulations très détaillées du processeur et du système mémoire).

Cycles d’attente = (Nb. d’inst/programmes)mémoire *(Nb. de défauts/instruction)

*Coût défaut

Cycles d’attente = (Nb. d'accès par programme)mémoire *(taux de défaut)

*Coût défaut

Page 77: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 77

Résumé

• Où peut être placer un bloc ?

Un corresp. direct, plusieurs (associatif par ensembles), ou tout (totalement associatif) endroit.

• Comment un bloc est il trouvé ?

Indexation (correspondance direct)

Recherche limitée (associatif par ensembles)

Recherche totale (totalement associatif)• Quel bloc est remplacé lors d’un défaut ?

Généralement, soit le moins récemment utilisé, soit un bloc au hasard, de manière aléatoire.

• Comment sont traitées les écritures ?

Chaque niveau de la hiérarchie peut utiliser soit l’écriture simultanée soit la réécriture.

Page 78: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 78

Résumé

• Le défi lancé par la conception des hiérarchies de mémoires est que tout changement qui peut améliorer le taux de défauts peut aussi affecter de façon négative les performances globales.

• C’est une combinaison d'effets positifs et négatifs pour chaque paramètre de conception qui rend délicate la conception d’une hiérarchie de mémoires

Changement deConception

Augmenter la taille

Augmenter l’associativité

Augmenter la taille de bloc

Effet sur letaux de défauts

Réduit les défauts de capacité

Réduit le taux de défaut dû aux défauts de conflit

Réduit le taux de défaut pour un large éventail de tailles de bloc

Effet négatif possiblesur les performances

Peut augmenter le Tpsd’accès

Peut augmenter le temps d’accès

Peut augmenter le coût de défaut

Page 79: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 79

Caches : taille des blocs

Coût de l’échec

Tps transfert

Tps d’accès

Taille du bloc Taille du bloc

Taille du bloc

Taux d’échec

T ps d’accès

Augmenter la taille du cache indéfiniment

Page 80: Caches 1 Référence à un mot Xn dans le cache Mémoire Centrale Mémoire Centrale UC X4 X1 Xn-2 Xn-1 X5 X3 X4 X1 Xn-2 Xn-1 X5 X3

Caches 80