Mémoires: disposition, cache, virtuelle



- Organisation de la mémoire principale en modules et planches
- Hiérarchie à deux niveaux
- Mémoire cache
- Mémoire virtuelle
- Le système de mémoire dans un ordinateur

Planches et modules de mémoire :

Pour faire des grandes mémoires on utilise plusieurs puces.
La mémoire peut être sur des planches séparés (SIMM, DIMM...) ou directement sur la planche mère du système.
Un module (ou une banque de mémoire) peut être formé de plusieurs planches.
La mémoire système peut contenir plusieurs modules.

Modules: (pages 334 à 336)
- satisfait le protocole d'interface avec le processeur (on peut mettre un seul module), qui peut n'avoir aucun lien avec le protocol pour les puces mémoires.
- on peut ajouter des modules pour avoir plus de mémoire
- peut contenir le circuit de refraîchissement pour la DRAM


Formation de mémoire avec mots plus larges :   (pages 330,331)

Pour former des mémoires plus larges, on met plusieurs puces en parallèle ayant en entrée les mêmes signaux (adresse, "select" et lecture/écriture).  Chaque mémoire contient une partie du mot, et on met les parties ensemble pour former le mot complet. (Figure 7.18)


Formation de mémoire avec plus de mots :   (section 7.3.2)

Pour former une mémoire qui contient plus de mots, on met plusieurs puces ayant en entrée la même adresse et le même signal de lecture/écriture mais un "select" différent.  Les données qui vont à chaque puce sont les mêmes (un seul bus passe par toutes les puces).  Le "select" est généré par un ou plusieurs décodeurs. (Figures 7.19, 7.20)


Organisation de mémoires multi-modules :   (pages 336 à 340)

Il y a deux façons d'organiser les modules:  (figure 7.24, page 338)

- Séquentiel :  le premier module contient les petites adresses, le deuxième module contient les adresses plus grosses...  Chaque module reçoit les bits de poids faibles de l'adresse comme adresse, et les bits de poids forts de l'adresse servent comme sélection de module.  Ce type permet de changer la taille de la mémoire facilement (en ajoutant ou en enlevant des modules).

- Entrelacé :  le premier mot est dans l'adresse 0 du premier module, le deuxième mot est dans l'adresse 0 du deuxième module...  puis, lorsqu'on a passé tous les module, on place les mots à l'adresse 1 de chaque module, puis à l'adresse2...  Chaque module reçoit les bits de poids forts de l'adresse comme adresse, et les bits de poids faibles de l'adresse servent comme sélection de module.  Ce type permet des accès séquentiels plus rapides (les modules font la recherche de mots consécutifs en mémoire).


Exemple de temps d'accès :   (page 342)

Regardons pourquoi une mémoire avec temps d'accès de 70 ns ne donne pas nécessairement un système de mémoire pouvant faire des accès à tous les 70 ns.  Pour la simplicité, on va utiliser de la mémoire SRAM.

On veut faire une lecture dans la mémoire.  Pour ça il faut (avec des temps possibles):
- Charger le bus d'adresse (activation + temps de propagation sur le bus):  50 ns
- Faire la sélection de la planche: 20 ns
- Délais de propagation de la sélection: 30 ns
- Sélection de la puce: 20ns
(Temps total de propagation de l'adresse: 120 ns)
- Faire la lecture dans la puce mémoire: 70 ns
- Temps de propagation des données sur la planche: 30 ns
- Temps de propagation des données sur le bus, jusqu'au processeur: 50 ns

Le temps d'accès total est donc de 270 ns.

Si on met une seule planche, très près du processeur, on sauve 50 ns de sélection et le 100 ns de délais sera beaucoup réduit.  La vitesse réelle de la mémoire dépend donc de son emplacement.


Hierarchie de mémoires :   (section 7.4)

L'objectif est d'avoir une grande mémoire, rapide, à faible coût.  Ici on présente une hierarchie à deux niveaux:
-  Une mémoire primaire petite et rapide (coût relativement élevé pour la taille, mais elle est petite alors...)
-  Une mémoire secondaire grande et lente (coût beaucoup plus bas)
La hierarchie peut être:
Cache - Mémoire principale :  on met une cache pour accélérer les accès mémoire.
-  Mémoire principale - Disque : (Mémoire virtuelle) on utilise le disque pour avoir une grande mémoire pas chère.

La méthode: copier des parties de la grande mémoire lente dans la petite mémoire rapide.
Pourquoi ça fonctionne:  la localité d'accès, temporelle et spaciale. L'ensemble de travail ("working set") change lentement à cause des "localités".

Le transfert entre les deux niveaux se fait par blocs :
-  Entre le CPU et la cache :  quelques octets.
-  Entre la cache et la mémoire pricipale :  bloc de 16 à 64 octets.
-  Entre la mémoire et le disque :  page de 1kB à 4kB.

La même donnée ne se trouve pas à la même adresse dans les deux niveaux, il faut donc une traduction (figure 7.28, page 345).
La traduction peut se faire selon le système:  (figure 7.29)
Paginé :  les bits de poids forts de l'adresse système sont utilisés comme indice dans une table qui donne les bits de poids forts de l'adresse primaire, et les bits de poids faibles sont les mêmes.
Segmenté :  les bits de poids forts de l'adresse système sont utilisés comme indice dans une table qui donne une adresse de base à laquelle on additionne les bits de poids faibles pour obtenir l'adresse primaire.

Terminologie:
Succès d'accès: le mot a été trouvé au niveau demandé.
Défaut d'accès: le mot n'est pas dans le niveau demandé, if faut faire une recherche dans un niveau supérieur.
Taux de succès (h): nombre de succès d'accès / nombre total d'accès
Taux de défauts = 1-h
tp = temps d'accès à la mémoire primaire;  ts = temps d'accès à la mémoire secondaire
Temp d'accès effectif = h tp + (1-h) ts
Défaut de page ("page fault"): défaut d'accès dans une mémoire virtuelle (le mot ne se trouve pas en mémoire principale).
Pagination sur demande: les pages sont transférées du disque à la mémoire seulement lorsqu'un mot est demandé par le processeur; par opposition à la prépagination (le programme dit quelles pages il aura besoin).
Décisions de placement et de remplacement (ou politique de remplacement): quand on copie un bloc d'un niveau supérieur, il faut choisir où on le met dans le niveau présent (quelles données on remplace).


Cache :   (section 7.5)

La cache est une mémoire rapide entre le CPU et la mémoire principale (figure 7.30). (C'est une hierarchie de mémoires)
Lors de la conception il faut choisir:
-  Procédure de traduction d'adresses
-  Taille des blocs
-  Placement:  direct, associatif ou une combinaison (associatif par ensembles)
-  Politique de remplacement:  FIFO, LRU, aléatoire, ...
-  En cas de défaut:  accès au travers (direct) à la mémoire ou attendre la copie
-  Écriture immédiate ("write through") ou écriture au remplacement

Ces mécanismes sont implantés en matériel à cause de la vitesse demandée.

Cache associative: (pages 350 à 352)
Dans une cache associative, on peut mettre n'importe quel bloc à n'importe endroit. (figure 7.31)  On met un "tag" sur chaque bloc dans la cache  pour dire d`où il vient (quelle était sont adresse dans la mémoire principale).  Lorsqu'on fait une lecture dans la cache, on regarde tous les "tags" pour voir si la donnée s'y trouve.  (figure 7.32)

Avantage: le plus flexible.
Inconvénient: pour que la recherche soit rapide, il faut un gros circuit (ou peu de blocs).

Cache à associativité directe ("direct-mapped"): (pages 352 à 354)
Chaque bloc a un seul endroit possible dans la cache. (figure 7.33)  On met un "tag" sur chaque bloc dans la cache pour dire lequel, de l'ensemble possible, se trouve à cet endroit.  Il n'y a plus vraiment de recheche à faire; on regarde à un seul endroit et on vérifie si le "tag" est le bon pour savoir si c'est le bon bloc. (figure 7.34)

Avantage: simple (petit circuit)
Inconvénient: peu flexible (ne peut pas avoir une "bonne" politique de remplacement)

Cache associative par ensembles: (pages 354 à 356)
C'est un compromis entre l'associativité complète et le "direct-mapped".  Chaque bloc a un seul ensemble possible dans la cache, mais il peut se trouver à n'importe quel endroit dans l'ensemble. (figure 7.35)

Un exemple: la cache sur le Pentium
Caches séparées instructions/données.
Chaqu'une est 8k associative par ensembles de 2 blocs:
-  8kB = 213 octets
-  les blocs (lignes) sont de 32B = 25 octets
-  il y a donc 213 / 25 / 2 = 27 = 128 groupes
-  les adresses sont de 32 bits, donc le tag est de 32 - 5 - 7 = 20 bits

Un autre: la cache sur le PowerPC 601
Cache unifié (instructions et données).
32kB en 64 groupes de 8 blocs (cache associative par ensembles), chaque bloc étant 16 mots (organisés en 2 secteurs de 8 mots) de 4 octets.
La mise-à-jours se fait en 2 cycles d'horloge, 4 mots sont transférés par cycle.
Écriture sur remplacement, mais peut aussi être programmée pour écriture immédiate ou inhiber la cache.
Utilise la politique de remplacement LRU.
 

Politiques de lecture et d'écriture:

Sur succès d'accès:
-  Écriture immédiate ("write through") :  mise-à-jour de la mémoire et de la cache en même temps.
-  Écriture au remplacement ("write back") :  écriture du bloc lorsqu'on l'enlève de la cache.  Dans la cache, il y a un bit pour indiquer si le bloc a été modifié ou non (bit sale ou "dirty bit").

Sur défaut d'accès:
-  Lecture
        -  Accès au travers :  mise-à-jour du bloc de la cache avec le transert du mot au CPU en même temps.
        -  Accès avec attente :  commence par faire la mise-à-jour de la cache, puis on relance la lecture.
-  Écriture
        -  Allouer avant d'écrire ("write allocate") :  met le bloc dans la cache avant de faire l'écriture.
        -  Écrire sans allouer ("write-no allocate") :  écrit directement en mémoire sans charger dans la cache.
 

Politique de remplacement:

Associativité directe :  pas besoin de politique.

Associativité complète ou par ensemble :
FIFO (First In First Out) :  Pour chaque ensemble on garde un pointeur qui dit quel bloc sera remplacé.  Lorsqu'on remplace un bloc, on incrémente le pointeur (en revenant au premier bloc quand on dépasse le dernier).  [ Peu utilisé. ]
LRU (Least Recently Used) :  Chaque bloc a un compteur.  Lorsqu'on fait un accès dans un bloc, on incrémente les compteurs des blocs ayant des comptes plus petits, puis on met le compte du bloc accèdé à zéro.  Lors d'un remplacement, c'est le bloc qui a le plus haut compte qui est pris.
Remplacement aléatoire :  Remplace un bloc au hasard (avec générateur pseudo-aléatoire).  Même si cette méthode est simple, elle fonctionne assez bien.
 

Performance d'une cache:

C'est une hierarchie de mémoire donc:  Temp d'accès effectif = h tcache + (1-h) tmémoire
Comme toujours, l'accélération ("speedup") = Temps sans cache / Temps avec cache


Mémoire virtuelle :   (section 7.6)

Une nouvelle hierarchie de mémoires, pour augmenter la taille de la mémoire (mais cette mémoire est beaucoup plus lente).
Voir Figure 7.37 page 359.  (la puce du processeur contient en général le CPU, le MMU et une partie de la cache)

MMU (Memory Management Unit) :  s'occupe de la gestion de l'espace mémoire et de la traduction de l'adresse virtuelle vers l'adresse physique.
L'adresse effective calculée par le processeur est une adresse logique dans un espace virtuel qui est en général plus grand que l'espace physique.  Lorsqu'on fait un accès à cette adresse, le MMU fait une traduction vers l'adresse physique en mémoire principale de l'ordinateur, si elle s'y trouve, sinon il génère un défaut de page.  La routine de défaut de page s'occupe d'aller chercher les données sur le disque et modifier la table de traduction.
La cache peut voir soit les adresses virtuelles soit les adresses physiques (qui est plus courant).

Exemple du PowerPC 601   (pages 368, 369)
- Le CPU génère des adresses logiques sont de 32 bits
- L'adresse logique est traduite par le MMU en une adresse virtuelle de 52 bits (16 bits directement de l'adresse et 24 bits venant d'une table de traduction), qui est ensuite traduite en une adresse physique de 32 bits.
 

Avantages de la mémoire virtuelle
-  L'écriture de programmes est plus facile (l'espace d'adresses est assez grand)
-  Pas besoin de recouvrement ("overlay")
-  Pas de fragmentation du programme (pas de fragmentation externe)
-  Beacoup de mémoire pour pas chère (les disques sont beacoup moins chères que la RAM).
-  Contrôle d'accès (vérification des privilèges).  Ceci peut aussi être fait par un système de mémoire segmenté, sans nécessairement avoir de mémoire virtuelle.  Ça permet de protéger le système contre des bogues dans les programmes, ou contre des attaques intentionnelles.

Incovenient de la mémoire virtuelle
Les programmes avec faible localité ont des mauvaises performances (surtout s'ils utilisent plus que la mémoire physique).  En fait c'est la même chose que pour la cache, sauf qu'ici le disque est vraiment lent, surtout si les accès sont fait de manière aléatoire.  Il faut donc programmer en tenant compte de la présence de mémoire virtuelle (et pour faire des programmes très rapides, il faut aussi tenir compte de la présence d'une cache).
 

Types de traduction d'adresses

Mémoire segmentée :  pages 360-362 (Figures 7.38, 7.39, 4.40)
Un registre contient le numéro de segment et les accès mémoires sont fait relativement à la base du segment (il peut y avoir plusieurs registres de segment, par exemple un pour le code, un pour les données et un pour la pile).
Lorsqu'un accès est fait, le MMU prend l'adresse et additionne l'adresse de base du segment.  Il vérifie aussi que l'adresse est plus petite que la borne supérieure du segment (génère un "bound exception" si elle est à l'extérieur).  Il peut aussi y avoir une vérification des droits du processus par rapport à ce segment (droit d'écrire, de lire, ou d'exécuter les données qui se trouvent dans le segment).
Peut causer de la fragmentation externe :  de la mémoire est perdue entre les segments.

Exemple du Intel 8086 :
- adresse logique de 16 bits, avec registre de segment de 16 bits
- adresse physique de 20 bits, qui est = adresse logique + 16 * registre de segment
- 4 registres de segments (Code, Data, Stack et Extra)
C'est utilisé pour augmenter l'espace d'adresses.  On a une adresse physique de 20 bits en ayant seulement des registres de 16 bits (le 8086 est 16 bits).
Ce système de segmentation existe aussi sur le Pentium, mais il a aussi un autre système de segmentation (plus complet, avec tailles de segments et vérification des droits d'accès).  Par dessus le système de segmentation, le Pentium a aussi un système de pagination.

Mémoire paginée :  pages 362-365 (Figures 7.41, 7.42)
La mémoire (virtuelle et physique) est découpée en pages, chaque page virtuelle peut être associée avec n'importe quelle page physique.  Une page virtuelle peut aussi être associée à aucune page physique, dans ce cas le MMU génère un défaut de page si elle est accèdée.

Traduction avec table de pages à un niveau :  Figure 7.42
Peut être vu comme une cache complètement associative mais avec une grosse table pour dire quelles adresses se trouvent dans quel bloc, plutot que de faire plein de comparaisons.

On peut utiliser plusieurs niveaux en découpant l'adresse virtuelle en plusieurs parties, chaque partie étant un indice dans une table.  On fait un arbre de table, les bits de poids forts de l'adresse servent pour sélectionner l'embranchement dans la racine de l'arbre, puis on prend les prochains pour l'embranchement suivant...  Ceci sert à réduire la taille de la table.

La traduction est faite pour chaque accès mémoire, donc il faut que ce soit rapide.  Faire la lecture dans une grosse table en mémoire est beaucoup trop lent.  On utilise donc un genre de cache pour la table de traduction: TLB (Translation Lookaside Buffer) (pages 366, 367, Figure 7.43)
 

Sommaire des opérations de hiérarchie  (Section 7.6.2, Figure 7.44)


Le système de mémoire :   (section 7.7)

Voir figure 7.46.

Nous avons vu une hierarchie de mémoire :  CPU - cache - mémoire principale - disque.

La cache fait une genstion transparente des accès mémoires, mais entre la mémoire principale et le disque le lien est différent :  la copie n'est pas faite par la mémoire pricipale, elle est ordonnée par le CPU.  En général on utilise un contrôleur de disque qui avec DMA (Direct Memory Access), c'est-à-dire qu'il peut écrire en mémoire sans passer par le CPU, mais c'est quand-même le CPU qui donne la permission d'écrire dans un certain bloc mémoire.  Le DMA doit avoir un lien avec la cache pour lui dire que certaines données sont modifiées.

Sur plusieurs machines, certaines adresses physiques sont associées aux entrées/sorties.  Quand le processeur fait un accès à ces adresses, ce n'est pas la mémoire qui est accèdée mais un périférique qui peut donner des données différentes à chaque fois qu'on fait une lecture, même si elle est à la même adresse.  Il faut donc une méthode pour empècher la cache d'intercepter les accès vers ces adresses (soit en écriture, en lecture, ou les deux).



Présentation en classe (.PDF)