Introduction

Il existe différents types de mémoire selon leurs tailles et leurs temps d’accès :

Type de mémoire Capacité Temps d’accès
Processeurs et registres Kilo-octet 3/cycle
Cache Méga_octet quelque cycles
Mémoire RAM Giga-octet 200 cycles
Mémoire virtuelle Terra-octet 10^6 cycles

Les échanges entre les différents niveaux de mémoire se font par blocs.

Sommaire masquer
1 Introduction
1.1 Qu'est-ce que la mémoire virtuelle ?
2 Localité
3 Hiérarchie de la mémoire
3.1 Qu'est-ce que la mémoire virtuelle ?
4 Fonctionnement d'une mémoire dynamique
4.1 Organisation du processeur Pentium
5 La mémoire Cache
5.1 Les différents types de cache
5.2 Comment savoir si une ligne est présente dans le cache ?
5.3 Cache en défaut (cache Miss)
5.4 Taux d'échec
5.5 Cache à chaque niveaux

Qu'est-ce que la mémoire virtuelle ?

L’un des premiers problèmes de la mémoire que c’est quelle s’améliore beaucoup moins vite que les processeurs. Ceci fait que les processeurs ne peuvent fonctionner avec la performance souhaiter car il est limité par les différents composants qui l’entoure (notamment la mémoire).

Plus les années passe et plus

Localité

Problème : Les accès mémoire sont de plus en plus couteux en terme de temps et de rapidité.

Pour pouvoir accélérer ces accès mémoire on utiliser la localité. Il y a deux types de localité : temporelle et spatiale.

  • Localité temporelle : Si une information est manipulée par le processeur, il est très probable qu’elle sera également utilisée peu de temps après.
  • Localité spatiale : Si une information est manipulée par le processeur, il est très probable qu’une information située dans une emplacement mémoire proche sera également utilisée peu de temps après.

La localité permet d’identifier de l’information utile et de la déplacer dans un cache ( mémoire très rapide). Ceci permet de gagner de temps lorsqu’il faudra réutiliser cette information.

 

Hiérarchie de la mémoire

Il existe deux types de mémoire : statique et dynamique.

  • Mémoire Dynamique (DRAM) : Information mémorisée dans un condensateur. Lecture destructrice nécessitant une réécriture. La préservation de l’information nécessite un rafraichissement régulier. C’est utilisé comme la mémoire principale du système. DRAM veut dire Double Data Rate Synchronous DRAM. Double Data Rate veut dire que l’on écrit les données sur les fronts montants et descendants de l’horloge. Synchronous DRAM veut dire que l’on utilise une horloge pour transférer les données.
  • Mémoire Statique (SRAM) : Information mémorisée dans un latch. Temps de cycle fortement réduit donc utilisé dans les caches mémoire.

Qu'est-ce que la mémoire virtuelle ?

La mémoire virtuelle est une mémoire crée par l’ordinateur afin de copier des variables utilent aux programmes. Cette mémoire vient au secours de la mémoire RAM lorsque celle-ci est remplise. Les variables sont alors copiés de la RAM vers votre disque dur et fait des aller-retours selon si la variable est beaucoup utilisé. Le défaut de cette technique c’est qu’une fois votre variable copié sur votre disque dur elle est accessible beaucoup moins rapidement sur dans la RAM et donc ralenti votre programme.

Dans les systèmes embarqués on n’utilise pas de mémoire virtuelle.

Fonctionnement d'une mémoire dynamique

Dans la mémoire dynamique, les bits de poids fort de l’adresse sélectionne la ligne de la mémoire et les bits de poids faible de l’adresse sélectionne la colonne de la mémoire.

Voici comment lire une mémoire :

  1. Précharge du bus : Avant la lecture, on précharge les bus à la moitié de la tension d’alimentation de la mémoire (temps de précharge)
  2.  Modification du mot dans le registre : On arrête de la précharge et on sélectionne de la ligne à lire. On lit la valeur dans les amplificateurs de lecture et on mémorise dans des latches de toute la ligne de la mémoire (temps d’attente)
  3. Réécriture de la ligne : On séléctionne de la colonne et on envoi la donnée sur le bus de donnée. Enfin, on réécrit la ligne dans les cases mémoire. (temps de latence)

La lecture est destructive, c’est à dire qu’elle nécessite de réécrire les valeurs lues.

On va maintenant voir le nombre de cycle que prends l’utilisation d’une mémoire :

  • Temps de précharge : 12-15 cycles
  • Temps d’attente : 12-15 cycles
  • Temps de latence : 10-12 cycles

L’écriture dans une mémoire prends donc environ 40 cycles, ce qui est beaucoup. On essaie donc de limiter l’accès à la mémoire ou bien de mettre la donnée dans des caches si on veut y accéder rapidement.

  • Mémoire burst mode

Les mémoires dynamique fonctionnent avec accès en rafale (burst mode) : Lors de la lecture d’une donnée,  on envoi les données environnantes dans la ligne, sans relecture de la ligne. L’ensemble est géré par un contrôleur mémoire qui est intégré au processeur.

Organisation du processeur Pentium

On va maintenant voir le fonctionnement du processeur pentium :

NorthBridge : Assure les entreés/sorties rapides, notamment ceux de la mémoire et graphique.

SouthBridge : Assure les entrées/sorties plus lente. Comprend un contrôleur PCI  et des contrôleurs de périphériques (SATA, USB, Ethernet).

La mémoire Cache

La mémoire cache a été crée pour augmenter la rapidité de l’utilisation de la mémoire. La mémoire cache es plus petite que la mémoire RAM et se trouve au plus proche du processeur afin de limiter le temps de transition.

Voici comment marche un cache : 

On cherche d’abord si la donnée est présente dans le cache

  • Si la donnée est dans le cache, on envoie la donnée dans le processeur avec temps d’accès limité.
  • Si la donnée n’est pas dans le cache, on lit la ligne contenant la donnée en mémoire et on la copie dans le cache et on envoie la donnée au processeur.

Les différents types de cache

cache à correspondance directe (direct map) : ligne à un emplacement unique dépendant de son adresse.


Un des problèmes du cache à correspondance direct est qu’il ne faut pas de lignes différentes avec les même poids faibles d’adresse.

 

Cache associatif : ligne à un emplacement quelconque. Ceci évite que des lignes avec les mêmes poids faibles d’adresse ne s’écrasent mutuellement, mais nécessite une recherche complexe.

 

Cache associatif par ensemble (set associative) : ligne à un emplacement quelconque dans un bloc déterminé par l’adresse. Bon compromis car l’ensemble fait quelques lignes.

Comment savoir si une ligne est présente dans le cache ?

Déplacement : adresse de l’octet dans la ligne
Index : La position de la ligne dans le cache
Etiquette : les poids forts identifient la ligne de cache

Si on insère une nouvelle ligne dans le cache, il faut en supprimer une.

  • Si le cache est associatif, comment choisir la ligne à supprimer ?

Pour cela il y a on va voir différentes manières de faire :
— On supprime la moins fréquemment utilisée (least frequentlu used LFU)
—  On supprime la moins récemment utilisée (least recently used LRU)

Pour cela on va voir le pseudo LRU :

1bit-PLRU : A chaque accès, on indique avec un bit si la ligne est dans la partie haute ou basse de l’ensemble. En cas d’échec, prendre une ligne aléatoire de l’autre partie

bit-pLRU :  On associe à chaque ligne un bit d’état. A chaque accès à la ligne, le bit est mis à 1.
En cas d’échec on remplace une des lignes dont le bit d’état est à 0.
— S’il en a plusieurs, on en choisit une (aléatoirement, celle avec le plus petit index, …) et on met son bit d’état à 1.
— S’il n’y a qu’une ligne dont le bit d’état est à 0, on la choisit et on complémente tous les bits d’état

 

 

Cache à écriture simultanée (write-through) : On écrit simultanément dans le cache et la mémoire pour assurer la cohérence des information. Le problème du cache à écriture simultané est l’encombrement du bus.

Cache à réécriture (write-back) : Lors d’une écriture en cache, on marque la ligne comme modifiée. La deuxième étape et de réécrire la ligne en mémoire. On réécrit seulement si la ligne est supprimée du cache ou si elle a été modifiée. Le cache à réécriture est plus complexe, mais charge moins le bus.

Cache en défaut (cache Miss)

Write allocate  : Lors d’une écriture, on crée une entrée pour la ligne dans le cache. Nécessite une lecture de la ligne, mais plus efficace en cas d’écritures successives dans la même ligne.
No-write allocate : La donnée est directement envoyée à la mémoire. On n’alloue une ligne que sur une lecture.

 

Caches séparés (split caches) : Un cache pour les instructions et un pour les données. Permet d’éviter les conflits d’accès à la mémoire dans le processeur
Cache unifié (unified cache) : Un cache unique stockant instructions et données. Permet une meilleure utilisation de la capacité du cache.

 

Taux d'échec

Il y a trois choses que l’on souhaite réduire : le taux d’échec, le temps d’accès et d’échec.

Obligatoire : Le premier échec arrive lors de la première utilisation du cache qui ne contient aucune donnée et donc donne un échec
Capacité :  taux d’échec du à une capacité trop faible et donc plus de place pour ajouter de nouvelle donnée

Conflits : Taux d’échec du à des conflits (cela n’arrive pas avec un cache totalement associatif)

Ni la capacité, ni l’associativité n’influent sur les échecs obligatoires. La capacité réduit les échecs de conflits et de capacité. L’associativé n’influence que les échecs dus à des conflits.

On peut réduire le taux d’échec en augmentant la taille des lignes ou bien en anticipant la demande des données (prefetch)


Impact de la taille des lignes

La taille des lignes est très importante dans votre cache :

  • Avoir des faibles taille de ligne donne une mauvaise utilisation de la localité spatiale. Pénalité à cause du taux d’échecs obligatoires
  • Au contraire avoir des grandes taille de ligne apporte plus de conflits. Pénalité à cause du coût du transfert de la ligne et du taux d’échecs de conflits.

Un bon compromis est entre 32/64 octets.

Réduction des échecs dus à des conflits permet d’augmenter l’associativité grâce au cache de victime.

Cache des victimes : Quand une ligne est éjectée, on la met dans un petit cache totalement associatif. Si on a a nouveau besoin de cette ligne, elle sera directement
disponible.

 

Cache à chaque niveaux

On utilise plusieurs niveaux de caches successifs pour permettre d’augmenter le  temps d’accès à la donnée.

Cache de niveau 1 : C’est le cache le plus proche du processeur. Il doit fournir des données quitte à avoir un taux d’échec un peu élevé.

Caches de niveau L2 et L3 : Plus loin du processeur, on doit donc limiter les accès mémoire pour réduire le coût d’un échec. Il sont de plus grande taille et plus sophistiqués, mais leur temps d’accès est plus important.

 
Cache L1 Cache L2 Cache L3
Objectif Cache rapide pour alimenter le processeur Réduire le temps d’échec du cache L1 et limiter au maximum les accès à la mémoire Réduire le temps d’échec du cache L1 et limiter au maximum les accès à la mé- moire
Type de cache Deux caches séparés données et instructions Cache unifié instructions/données Cache unifié instructions/données
Temps d’accès 1–5 cycles 3–20 cycles 10–40 cycles
Temps d’échec 3-15 cycles 10-40 cycles 200 cycles
Taille associativité 2×16–32 ko Faible associativité 256 ko Associativité plus importante 1Mo+ Associativité plus importante
Ecriture Écriture simultanée (pour simplifier le cache) ou réécriture Réécriture (pour limiter le trafic mémoire et la consommation) Réécriture (pour limiter le trafic mémoire et la consommation)
  • Caches L1 séparés (instructions/données)
  • Caches L2 unifiés
  • Cache L3 partagé entre les différents coeurs

Les caches L1 et L2 des différents processeurs communiquent pour assurer la cohérence mémoire.

  • Les Caches inclusifs et exclusifs

Les caches successifs peuvent être inclusifs ou exclusifs
Caches strictement inclusifs : L1 ⊂ L2 ⊂ MP
Tout ce qui est dans L1 est aussi dans L2.
Simplifie la mise en œuvre
Caches non strictement inclusifs : L1 ∩ L2 6 = ∅
L1 peut contenir une partie de L2 et réciproquement. Une ligne n’est jamais à la fois dans L1 et L2. Évite de dupliquer l’information.
Si on cherche une information dans L1 et qu’on ne la trouve pas alors on l’a copie depuis la mémoire principale.

Si on ne trouve pas une donnée dans L1 mais qu’elle se trouve dans L2 alors la donné est copié de L2 vers L1.

  • Evaluation des performances d’un cache

Il est nécessaire de prendre en compte les caches dans les évaluations de performances.
Nous supposons des caches avec un temps d’accès ta , un taux d’échec τe .
Le temps d’accès à la mémoire est tM