1

ARCHITECTURE EVOLUEE DES ORDINATEURS

HIERARCHIE MEMOIRE
Mme Kadri & Mlle Haichour
{n_kadri , a_haichour}@esi.dz
Ecole nationale Supérieure d’Informatique (ESI)

2019-2020
 2

Objectifs du chapitre
• Définir la hiérarchie mémoire
• Décrire le fonctionnement de la mémoire cache
• Evaluer l’effet d’une mémoire cache sur la performance globale
• Connaitre les différentes techniques de conception des mémoires
caches
• Comparer les différentes techniques de conception des mémoires
caches
• Lister les techniques utilisées pour améliorer la performance de la
mémoire cache
 3

Contenu du chapitre
• Introduction
• Définition de la hiérarchie mémoire
• Fonctionnement de la mémoire cache
• Effet de la mémoire cache sur la performance
• Techniques de conception de la mémoire cache
• Techniques d’amélioration de la performance de la mémoire cache
• Synthèse et conclusion
 4

Contenu du chapitre
• Introduction
• Définition de la hiérarchie mémoire
• Fonctionnement de la mémoire cache
• Effet de la mémoire cache sur la performance
• Techniques de conception de la mémoire cache
• Techniques d’amélioration de la performance de la mémoire cache
• Synthèse et conclusion
 5

Introduction (Evolution des performances)

• Vitesse du processeur évolue beaucoup plus
vite que la vitesse de la mémoire

• Les vitesses d'accès aux données n'arrivent

plus à satisfaire les besoins en termes de
données des processeurs

 Ecart de performances entre processeur et

mémoire que les architectes d'ordinateurs
essayent de combler

Performances comparées des processeurs et des mémoires -

Patterson and Hennessy 2012
 6

Introduction (Caractéristiques d’une mémoire)

• Point de vue utilisateur

▫ Capacité

▫ Performance : temps d’accès; temps de cycle mémoire; taux de transfert

 7

Introduction (Caractéristiques d’une mémoire)

• Capacité
▫ Nombre (quantité) de données que peut contenir une mémoire

• Temps d’accès / Latence

▫ Temps nécessaire pour effectuer une lecture ou une écriture
Commande de lecture

Donnée stable sur le bus

Temps d’accès en lecture

 8

Introduction (Caractéristiques d’une mémoire)

• Temps de cycle mémoire
▫ Temps minimal entre deux accès successifs à la mémoire
▫ Concept appliqué aux mémoires à accès aléatoire
Temps_Cycle = Temps d'accès + Temps d’attente avant de pouvoir effectuer une seconde opération

• Taux de transfert
▫ Taux avec lequel les données sont transférées vers ou hors de la mémoire
▫ Cas des mémoires à accès aléatoire
Taux de transfert  1
Temps _ Cycle
 9

Introduction (Caractéristiques d’une mémoire)

• Débit / Bande passante
▫ Volume (quantité) de données échangé par unité de temps
▫ Obtenu en multipliant le taux de transfert par la largeur du bus de données
 10

Introduction (Caractéristiques d’une mémoire)

• Besoin
▫ Capacités mémoires plus importantes
▫ Mémoires présentant des temps d’accès plus courts
▫ Mémoires présentant des coûts de revient raisonnables

• Dilemme
▫ De plus grandes capacités impliquent des temps d’accès plus élevés
▫ Des temps d’accès plus courts impliquent un plus grand coût par bit
 11

Introduction (Caractéristiques d’une mémoire)

• Compromis
▫ Capacité
▫ Vitesse
▫ Coût

• Solution
▫ Ne pas se baser sur un composant ou une technologie mémoire uniques
▫ Utiliser une hiérarchie mémoire
 12

Contenu du chapitre
• Introduction
• Définition de la hiérarchie mémoire
• Fonctionnement de la mémoire cache
• Effet de la mémoire cache sur la performance
• Techniques de conception de la mémoire cache
• Techniques d’amélioration de la performance de la mémoire cache
• Synthèse et conclusion
 13

Hiérarchie mémoire
• Types de mémoires

Registres Disque
Mémoire Mémoire dur
Processeur cache centrale

Taille 500 Bytes 8 MB 16 GB 250 GB

Temps d’accès 500 ps 10-15 ns 50-100 ns 3-4 ms

 14

Hiérarchie mémoire
• Principe de la hiérarchie mémoire
▫ Processeur n’a jamais besoin de toutes les données au même moment et
de la même façon
▫ Règle générale des programmes : 90% du temps d’exécution est passé dans
10% du code (cas courant)  Principe de localité
 15

Hiérarchie mémoire
• Principe de la hiérarchie mémoire
▫ Principe de localité : Passé proche prédit le futur proche

▫ Localité temporelle : Les emplacements accédés récemment sont

susceptibles d'être accédés dans le futur proche

▫ Localité spatiale : Les éléments dont les adresses sont proches ont
tendance à être accéder dans des temps proches (nature séquentielle des
programmes)
 16

Hiérarchie mémoire
• Principe de la hiérarchie mémoire
▫ Conserver les éléments les plus utilisés dans les mémoires les plus rapides
Rendre le cas courant plus rapide  améliorer les performances

 Mémoires de faible capacité mais très rapides pour les éléments les
plus utilisés
Mémoires de grande capacité mais très lentes pour les éléments les
moins utilisés
 17

Hiérarchie mémoire
• Principe de la hiérarchie mémoire
▫ Plusieurs couches de mémoires de différents types
▫ Mémoires rapides, de petite taille, plus coûteuses, plus proches du
processeur
▫ Mémoires moins rapides, moins coûteuses, de plus grande capacité, plus
éloignées du processeur
 18

Hiérarchie mémoire
• Principe de la hiérarchie mémoire

Mémoire secondaire

Mémoire centrale

Cache
Registres
Taille Taille

Processeur
Temps d’accès Temps d’accès
Coût Coût
 19

Hiérarchie mémoire
• Principe de la hiérarchie mémoire

Niveau 1 2 3 4
Mémoire
Nom Registres Cache Mémoire centrale
secondaire
Taille typique < 1 KB 32 KB-8 MB < 512 GB > 1 TB
Temps d'accès (ns) 0.15-0.30 0.5-15 30-200 5,000,000
100,000-
Débit MB/sec 10,000-40,000 5000-20,000 50-500
1,000,000
Caractéristiques d'une hiérarchie mémoire moyenne pour un PC de base -
Patterson and Hennessy 2012
 20

Hiérarchie mémoire
• Principe de la hiérarchie mémoire

Mémoire secondaire

Mémoire centrale

Cache
Registres
Taille Taille

Processeur
Temps d’accès Temps d’accès
Coût Coût
 21

Contenu du chapitre
• Introduction
• Définition de la hiérarchie mémoire
• Fonctionnement de la mémoire cache
• Effet de la mémoire cache sur la performance
• Techniques de conception de la mémoire cache
• Techniques d’amélioration de la performance de la mémoire cache
• Synthèse et conclusion
 22

Fonctionnement de la mémoire cache

Mémoire Mémoire
Processeur
cache centrale
Transfert Transfert
par mot par bloc
 23

Fonctionnement de la mémoire cache

Mémoire cache

@ existe
@ NON
dans le
cache
Processeur OUI
Donnée Transférer
donnée à
l’UC @
Chercher Mémoire
un bloc centrale
Stocker Donnée
bloc dans dans la MC
le cache et
HIT transférer
donnée à
MISS l’UC
 24

Fonctionnement de la mémoire cache

MC
@0
cache Bloc mémoire
@K-1
@K
L0 TAG Ligne mémoire
L1 @2K-1

Lm-1
@0 … @K-1

@2n-1

Ligne Mémoire cache = Bloc Mémoire centrale (K mots)

 25

Fonctionnement de la mémoire cache

Buffer d'adresses
Adresses

(@, Données, CTL)

Système Bus
Contrôle Contrôle
Processeur Cache

Buffer de données
Données
 26

Contenu du chapitre
• Introduction
• Définition de la hiérarchie mémoire
• Fonctionnement de la mémoire cache
• Effet de la mémoire cache sur la performance
• Techniques de conception de la mémoire cache
• Techniques d’amélioration de la performance de la mémoire cache
• Synthèse et conclusion
 27

Effet de la mémoire cache sur la performance

• Temps d’exécution d’un programme

Temps _ Pgme  (NI CPI )Temps _ Cycle

Nombre Total de cycles

Temps _ Pgme  (Cycles_UC  Cycles_ Mémoire)Temps _ Cycle

 28

Effet de la mémoire cache sur la performance

• Cycles mémoire

Cycles_ Mémoire  Nbre _ MISS  Pénalité _ MISS

Cycles_ Mémoire  NI  Nbre _ Accès _ Mémoire Nbre _ MISS  Pénalité _ MISS

NI Nbre _ Accès_Mémoire

Cycles_ Mémoire  NI Taux _ Accès_MémoireTaux _ MISS  Pénalité _ MISS

 29

Effet de la mémoire cache sur la performance

• Exemple
Soit un processeur avec les paramètres suivants :
▫ CPI = 1 lorsqu’il y a HIT
▫ Les accès mémoires (LOAD, STORE) représentent 50% des instructions
▫ Pénalité_MISS = 25 cycles
▫ Taux_MISS = 2%

Déterminer l’accélération du processeur obtenue si toutes les

instructions d’accès à la mémoire réalisent des HIT
 30

Effet de la mémoire cache sur la performance

• Exemple
Soit un processeur avec les paramètres suivants :
▫ CPI = 1 lorsqu’il y a HIT
▫ Les accès mémoires (LOAD, STORE) représentent 50% des instructions
▫ Pénalité_MISS = 25 cycles
▫ Taux_MISS = 2%

On détermine en premier le Temps_Pgme sans MISS et avec MISS

On les compare par la suite afin de trouver l’accélération
 31

Effet de la mémoire cache sur la performance

• Exemple
Cas 1 : HIT toujours
Temps_Pgme_HIT = (Cycles_UC + Cycles_Mémoire) x Temps_Cycle
= NI x CPI x Temps_Cycle = NI x Temps_Cycle

Cas 2 : avec MISS

Temps_Pgme_MISS = (Cycles_UC + Cycles_Mémoire) x Temps_Cycle

Cycles_Mémoire = NI x (1 + 0.5) x 0.02 x 25 = 0.75 x NI

Temps_Pgme_MISS = (NI x 1 + 0.75 x NI) x Temps_Cycle

= 1.75 x NI x Temps_Cycle
 32

Effet de la mémoire cache sur la performance

• Exemple
Temps_Pgme_HIT = NI x Temps_Cycle
Temps_Pgme_MISS = 1.75 x NI x Temps_Cycle

Accélération = Temps_Pgme_MISS / Temps_Pgme_HIT = 1.75

Le processeur sans MISS est 1.75 fois plus rapide que le processeur avec MISS
 33

Contenu du chapitre
• Introduction
• Définition de la hiérarchie mémoire
• Fonctionnement de la mémoire cache
• Effet de la mémoire cache sur la performance
• Techniques de conception de la mémoire cache
• Techniques d’amélioration de la performance de la mémoire cache
• Synthèse et conclusion
 34

Conception de la mémoire cache

• Différentes techniques en rapport avec :
▫ Placement et identification des blocs dans le cache
▫ Remplacement des blocs dans le cache
▫ Ecriture dans le cache
 35

Conception de la mémoire cache

• Placement des blocs dans le cache (organisation du cache)

▫ Placement direct (Direct mapping)

▫ Purement associative (Fully associative)

▫ Associative par ensemble (Set-associative)

 36

Conception de la mémoire cache

• Placement direct
▫ Chaque bloc a une location/emplacement unique qui lui est assignée pour
être rangé dans le cache
▫ Calcul de l’emplacement : Ligne = @bloc mod Nbre de lignes dans le cache
 37

Conception de la mémoire cache

• Purement associative
▫ Le bloc peut être placé n’importe où dans le cache
 38

Conception de la mémoire cache

• Associative par ensemble
▫ Le cache est organisé en ensembles
▫ Chaque ensemble est constitué de lignes
▫ Le bloc peut être placé dans un ensemble de lignes
▫ Le bloc est assigné à un ensemble unique mais peut être placé n’importe
où dans l’ensemble
▫ Calcul de l’emplacement : Ensemble = @bloc mod Nbre d’ensembles dans
le cache
 39

Conception de la mémoire cache

• Associative par ensemble
▫ Le nombre de lignes par ensembles (n) définit le type d’associativité
▫ (n-way set-associative)
n = 2 : 2-way set-associative (2 lignes/ensemble)
▫ Majorité des caches sont : placement direct / 2-way set-associative / 4-way
set-associative
 40

Conception de la mémoire cache

Mémoire centrale Mémoire cache
0 0
1 1
2 2
3 3
4 4 Le bloc 20 peut être
5 5
6 6 placé n’importe où
7 7
8
9 Purement associative
10
11 0
12 1
13 2
14 3
15 4 Le bloc 20 est placé à la
16 5
17 6 ligne 4 (20 mod 8)
18 7
19
20 Placement direct
21
22 0
Le bloc 20 peut être

SET 0
23 1
24
25
2
3
placé n’importe où dans
26 4
le set 0 (0-3)
SET 1
27 5
28
29
6
7
20 mod 2 = 0
30
31 4-way set-associative
 41

Conception de la mémoire cache

• Identification des blocs dans le cache
Mémoire centrale
TAG Mémoire cache Mot 0
Mot 1 B0
N° Bloc MC Mot 0 Mot 1 Mot 2 L0
Mot 2
N° Bloc MC Mot 0 Mot 1 Mot 2
. .
. . .
. . .
Mot 0 Mot 1 Mot 2 .
N° Bloc MC Lj

Mot 0
@ UC TAG INDEX OFFSET Mot 1 Bi
Mot 2
 42

Conception de la mémoire cache

• Identification des blocs dans le cache
@ UC TAG INDEX OFFSET

t bits k bits m bits

▫ OFFSET : 2m mots dans le bloc/ligne INDEX (bits) Degré d’associativité

▫ INDEX : 2k ensembles dans le cache 0 Purement associative
2n ensembles
▫ TAG : t bits restant de l’adresse n
n 2n lignes
 43

Conception de la mémoire cache

• Placement et identification des blocs
Technique Avantages Inconvénients

Purement Comparaison du TAG avec toutes les lignes

Remplissage maximal de la cache
Associative Complexité matérielle

Placement Accès direct à la ligne Deux blocs assignés à la même ligne ne

Direct Simple à implémenter peuvent pas être dans le cache
Associative Flexibilité de l’associativité Peut devenir complexe lorsque le nombre
par ensemble et simplicité du placement direct d’ensembles augmente
 44

Conception de la mémoire cache

• Remplacement des blocs (Quel bloc remplacer dans le cas du MISS ?)

▫ Aléatoire (RANDOM)

▫ Least Recently Used (LRU, le moins récemment utilisé)

▫ First In First Out (FIFO)

 45

Conception de la mémoire cache

• Remplacement des blocs (Quel bloc remplacer dans le cas du MISS ?)
Technique Avantages Inconvénients
Ne respecte pas la localité temporelle
Aléatoire Très simple à implémenter Une ligne peut être remplacée ensuite
demandée

Garde la trace d’utilisation des lignes du cache

LRU Utilise la localité temporelle
(complexe)
Approximation du LRU (ne reflète pas la
FIFO Plus simple à implémenter que LRU
localité temporelle)
 46

Conception de la mémoire cache

• Remplacement des blocs (Quel bloc remplacer dans le cas du MISS ?)

Associativité 2 lignes/ensemble 4 lignes/ensemble 8 lignes/ensemble

Taille LRU Aléatoire LRU Aléatoire LRU Aléatoire
16 KB 5,18 % 5,69 % 4,67 % 5,29 % 4,39 % 4,69 %
64 KB 1,88 % 2,01 % 1,54 % 1,66 % 1,39 % 1,53 %
256 KB 1,15 % 1,17 % 1,13 % 1,13 % 1,12 % 1,12 %
Exemples de taux de MISS en comparant le remplacement LRU et aléatoire,
pour différentes tailles et associativités - Patterson and Hennessy 1996
 47

Conception de la mémoire cache

• Ecriture dans le cache (En cas d’écriture, où écrire les données ?)
Ecriture d’un bloc qui n’est pas dans le cache (MISS)

▫ Ecriture allouée (Write-allocate) : Charger le bloc dans le cache et y écrire

▫ Ecriture non allouée (No-write-allocate) : Ecriture dans la mémoire centrale

seulement
 48

Conception de la mémoire cache

• Ecriture dans le cache (En cas d’écriture, où écrire les données ?)
Ecriture dans un bloc qui est dans le cache (HIT)

▫ Ecriture immédiate (Write-through) : Ecriture dans le cache et la mémoire

centrale

▫ Ecriture différée (Write-back) : Ecriture dans le cache seulement, lorsque le

bloc est remplacé, il est écrit à la mémoire
centrale
 49

Conception de la mémoire cache

• Ecriture dans le cache (En cas d’écriture, où écrire les données ?)
Technique Avantages Inconvénients

Facile à implémenter
Accès à la MC à chaque écriture
Ecriture immédiate La MC a la version la plus récente des
(ralentissement)
données (cohérence des données)

Ecriture multiples dans le bloc requièrent

une seule écriture dans la MC La MC peut ne pas avoir la version la plus
Ecriture différée
Minimise les accès MC récente des données
Les écritures se font à la vitesse du cache
 50

Conception de la mémoire cache

• Causes du MISS

▫ Défaut à froid : Cache pas encore remplie

▫ Défaut conflictuel : Des blocs qui sont assignés aux mêmes lignes et qui ne
peuvent pas être ensembles dans le cache

▫ Défaut de capacité : Un programme qui utilise un ensemble de blocs qui

dépasse la taille du cache
 51

Conception de la mémoire cache

• Exemple de simulation
 52

Contenu du chapitre
• Introduction.
• Définition de la hiérarchie mémoire
• Fonctionnement de la mémoire cache
• Effet de la mémoire cache sur la performance
• Techniques de conception de la mémoire cache
• Techniques d’amélioration de la performance de la mémoire cache
• Synthèse et conclusion
 53

Amélioration de la performance de la cache

• Performance de la mémoire cache
▫ Temps d’accès
Temps _ Accès _ Moyen Temps _ HIT Taux _ MISS  Pénalité _ MISS

▫ Améliorer la performance signifie :

Réduire Temps_HIT
Réduire Taux_MISS
Réduire pénalité_MISS
 54

Amélioration de la performance de la cache

• Performance de la mémoire cache
▫ Temps d’accès
Temps _ Accès _ Moyen Temps _ HIT Taux _ MISS  Pénalité _ MISS

▫ Améliorer la performance signifie :

Réduire Temps_HIT (Taille de la cache)
Réduire Taux_MISS
Réduire pénalité_MISS
 55

Amélioration de la performance de la cache

• Réduire Taux_MISS
▫ Taille de ligne plus élevée
▫ Taille du cache plus grande
▫ Plus d’associativité

Patterson and Hennessy 2012

 56

Amélioration de la performance de la cache

• Réduire Pénalité_MISS
▫ Utilisation de plusieurs niveaux de cache
Exemple (Effet de plusieurs niveaux sur la performance de la cache)

Cache L1 : Temps d’accès = 1 cycle, Taux_MISS = 10%

Cache L2 : Temps d’accès = 10 cycles, Taux_MISS = 2%
Mémoire centrale : Temps d’accès = 80 cycles

Calculer le temps moyen d’accès mémoire avec L1 seulement et avec L1

et L2
 57

Amélioration de la performance de la cache

• Réduire Pénalité_MISS
▫ Utilisation de plusieurs niveaux de cache
Exemple (Effet de plusieurs niveaux sur la performance de la cache)

Cache L1 : Temps_accès = 1 cycle, Taux_MISS = 10%

Cache L2 : Temps_accès = 10 cycles, Taux_MISS = 2%
Mémoire centrale : Temps_accès = 80 cycles

1. L1 seulement
Temps_Accès_Moyen = 1 + 0.1 x 80 = 9 cycles
2. L1 et L2
Temps_Accès_Moyen = 1 + 0.1 x (10 + 0.02 x 80) = 1 + 1 + 0.16 = 2.16 cycles
 58

Amélioration de la performance de la cache

• Réduire Pénalité_MISS
▫ Utilisation de plusieurs niveaux de cache
Cache externe
L3
Cache interne
L1 & L2
Registres
Taille Taille
Temps d’accès Temps d’accès

Processeur
Coût Coût
 59

Amélioration de la performance de la cache

• Réduire Pénalité_MISS
▫ Utilisation de plusieurs niveaux de cache

Processeur

L1 L2 L3
SRAM DRAM SRAM
 60

Contenu du chapitre
• Introduction.
• Définition de la hiérarchie mémoire
• Fonctionnement de la mémoire cache
• Effet de la mémoire cache sur la performance
• Techniques de conception de la mémoire cache
• Techniques d’amélioration de la performance de la mémoire cache
• Synthèse et conclusion
 61

Synthèse et conclusion
• Hiérarchie mémoire
• Mémoire cache
• Performance de la mémoire cache
• Conception de la mémoire cache
• Amélioration du temps d’accès au cache