Les mémoires de l’ordinateur

Cette conférence aborde les mémoires de l’ordinateur, en particulier le principe de hiérarchie mémoire et le fonctionnement des mémoires caches. Elle s’inscrit dans un cours d’architecture des machines, visant à expliquer comment les différents types de mémoire interagissent pour optimiser les performances d’un système informatique.

Les mémoires de l’ordinateur : notions fondamentales

Une mémoire est un composant électronique capable de stocker temporairement des informations. Elle se caractérise par sa capacité, c’est-à-dire le volume global d’informations qu’elle peut contenir (exprimé en bits), et par son temps d’accès, qui correspond à l’intervalle entre la demande de lecture ou d’écriture et la disponibilité de la donnée.

Dans un ordinateur, plusieurs niveaux de mémoire coexistent, organisés selon une hiérarchie mémoire :

• Registres : capacité de quelques dizaines de bits (32 ou 64 bits), temps d’accès d’environ 1 nanoseconde.
• Mémoires caches : capacité en kilo-octets, temps d’accès autour de 5 nanosecondes.
• Mémoire centrale : capacité en gigaoctets, temps d’accès d’environ 10 nanosecondes.
• Mémoires de masse : capacité de centaines de gigaoctets, temps d’accès de l’ordre de 5 millisecondes.

Les mémoires internes sont volatiles, tandis que les mémoires de stockage sont permanentes. Par exemple, les barrettes mémoire (SIMM, DIMM) sont volatiles, alors que les plateaux magnétiques sont permanents.

Types de mémoire

On distingue plusieurs types de mémoire :

• Mémoires vives (RAM) : accessibles en lecture et écriture, volatiles, composées de DRAM (Dynamic RAM) et SRAM (Static RAM). La DRAM est dynamique, peu coûteuse, constituée d’une cellule mémoire par bit formée d’un transistor et d’un condensateur, nécessitant un rafraîchissement périodique (environ 1000 fois par seconde). Le temps d’accès varie de 60 ns (DRAM) à 10 ns (SDRAM). La SRAM est statique, plus coûteuse et encombrante, utilisée pour les caches, avec un temps d’accès d’environ 10 ns. Une cellule SRAM est constituée de 4 à 6 transistors.
• Mémoires mortes (ROM) : accessibles uniquement en lecture, non volatiles, avec un temps d’accès d’environ 150 ns. Une fois l’information enregistrée, elle ne peut pas ou difficilement être modifiée. La ROM contient notamment l’amorce (boot) de l’ordinateur.
• Mémoires flash : compromis entre RAM et ROM, accessibles en lecture et écriture, non volatiles, avec un temps d’accès plus élevé que la RAM.

Hiérarchie mémoire et rôle des caches

La hiérarchie mémoire repose sur un compromis entre vitesse, coût et capacité. Les registres sont les plus rapides et les plus coûteux par bit, mais ont une capacité très limitée. La mémoire centrale est plus lente, moins coûteuse, mais avec une capacité beaucoup plus grande.

La mémoire cache est une mémoire intermédiaire placée entre le processeur et la mémoire centrale. Son 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) et vise à réduire le temps d’accès moyen aux données.

Fonctionnement de la mémoire cache : principe de localité

Le fonctionnement des caches repose sur le principe de localité :

• Localité temporelle : si une donnée d’adresse A est accédée à un instant t, il est très probable qu’elle soit de nouveau accédée aux instants t+1, t+2, etc. La donnée est donc remontée dans le cache pour minimiser les temps d’accès ultérieurs.
• Localité spatiale : si une donnée d’adresse A est accédée à un instant t, il est probable que les données voisines (adresses proches) soient également accédées peu après. Ainsi, la donnée A et ses voisines sont chargées dans le cache.

Par exemple, lors d’une boucle de programme, les instructions suivantes sont souvent situées à des adresses proches et sont donc chargées dans le cache pour accélérer leur exécution.

Lecture et écriture dans la mémoire cache

Lecture

Lorsqu’une instruction de lecture est lancée pour une adresse A :

• Si l’adresse A est présente dans le cache, l’information est directement chargée dans le processeur (succès).
• Sinon (défaut de cache), le bloc contenant A et ses adresses voisines est chargé depuis la mémoire centrale dans le cache, puis l’information est transmise au processeur.

Écriture

Lors d’une écriture à l’adresse A :

• Si A est présent dans le cache, la donnée est modifiée dans le cache.
• Sinon, la modification est effectuée directement en mémoire principale.

Deux politiques d’écriture sont utilisées :

• Write Through (écriture immédiate) : l’écriture en mémoire centrale est effectuée simultanément avec celle dans le cache. Cette méthode garantit une cohérence maximale mais engendre un coût plus élevé.
• Write Back (écriture différée) : l’écriture en mémoire centrale est différée et réalisée uniquement lorsque l’entrée du cache doit être remplacée. Cette méthode réduit le coût des écritures mais diminue la cohérence, car la mémoire centrale peut ne pas refléter immédiatement les modifications.

Un bit de modification (dirty bit) dans chaque entrée de cache indique si la ligne a été modifiée (1) ou non (0), ce qui guide la politique d’écriture différée.

Performances de la mémoire cache

Soient :

• h : probabilité de succès (hit) dans le cache
• Tc : temps d’accès au cache
• Tm : temps de lecture d’un bloc en mémoire centrale
• Td : temps d’accès à un mot en mémoire centrale

Le temps effectif d’accès Teff est donné par la formule :

Teff = h × Tc + (1 – h) × (Tm + Tc)

Cette formule montre que plus la probabilité de succès dans le cache est élevée, plus le temps moyen d’accès est réduit.

Architecture et organisation des caches

Les caches sont souvent organisés en plusieurs niveaux :

• Niveau L1 : cache séparé pour les données et les instructions, très rapide et proche du processeur.
• Niveau L2 : cache unifié, plus grand mais plus lent que L1.
• La mémoire centrale est située après ces caches.

Structure et organisation d’un cache

Un cache est caractérisé par :

• Sa capacité : nombre d’entrées multiplié par la taille du bloc de données (par exemple 128 entrées × 16 octets).
• Son organisation, qui peut être :
• Cache associatif : un bloc de mémoire centrale peut être placé dans n’importe quelle entrée libre du cache.
• Cache à correspondance directe : chaque bloc de mémoire centrale est associé à une entrée unique du cache, déterminée par une fonction de son adresse.
• Cache mixte (associatif par blocs) : le cache est divisé en sous-ensembles appelés voies, chaque voie fonctionnant comme un cache à correspondance directe. L’index sélectionne une ligne dans toutes les voies, et l’étiquette est comparée de façon associative.

Les blocs d’octets chargés dans le cache sont alignés, c’est-à-dire que l’adresse du premier octet du bloc est toujours un multiple de la taille du bloc. Par exemple, pour des blocs de 16 octets, les adresses des blocs sont 000000-001111, 010000-011111, etc.

Cache associatif

Dans un cache associatif, un bloc de mémoire centrale peut être placé dans n’importe quelle entrée libre. Si le cache est plein, une entrée doit être libérée selon un algorithme de remplacement :

• Aléatoire : une ligne est choisie au hasard.
• FIFO (First In First Out) : la ligne la plus ancienne est remplacée.
• LRU (Least Recently Used) : la ligne la moins récemment accédée est remplacée. Cette méthode est plus complexe à mettre en œuvre car elle nécessite de maintenir un ordre des accès.
• NMRU (Not Most Recently Used) : la ligne remplacée n’est pas la plus récemment utilisée, choisie aléatoirement parmi les autres. Moins coûteux que LRU.

Chaque entrée de cache comprend un répertoire contenant :

• Une étiquette (tag) correspondant à une partie de l’adresse mémoire.
• Un bit de validité (V) indiquant si la ligne contient des données valides.
• Un bit de modification (dirty bit, D) utilisé dans la politique d’écriture différée.
• Un champ de remplacement (par exemple date de dernier accès pour LRU ou date de chargement pour FIFO).

Lorsqu’une adresse est recherchée :

• Si le répertoire contient l’étiquette correspondante avec V=1, le bloc est trouvé et la donnée est chargée dans le processeur.
• Sinon, si le cache est plein, une ligne est remplacée selon l’algorithme choisi. Si la ligne remplacée a D=1, elle est écrite en mémoire centrale avant d’être remplacée.
• Si une ligne libre existe, elle est utilisée pour charger le nouveau bloc.

Cache à correspondance directe

Dans ce type de cache, chaque bloc de mémoire centrale est associé à une entrée unique du cache, déterminée par une fonction de son adresse (l’index). Plusieurs blocs peuvent partager la même entrée (conflit), ce qui peut causer des défauts même si le cache n’est pas plein.

Le format d’une entrée est similaire à celui du cache associatif, avec un bit de validité, un bit de modification et une étiquette.

Le fonctionnement est le suivant :

• Si l’entrée indexée est valide et que l’étiquette correspond, le bloc est trouvé et la donnée est chargée.
• Sinon, si la ligne est modifiée (D=1), elle est écrite en mémoire centrale avant d’être remplacée.
• Le nouveau bloc est chargé depuis la mémoire centrale dans l’entrée indexée.

Ce cache est moins coûteux et encombrant qu’un cache associatif car il nécessite un seul comparateur, mais il est moins performant à cause des conflits de ligne.

Cache mixte (associatif par blocs)

Le cache mixte est une solution intermédiaire entre le cache associatif et le cache à correspondance directe. Le cache est divisé en plusieurs voies (par exemple 3 voies). L’index sélectionne une ligne dans toutes les voies, et l’étiquette est comparée de façon associative dans chaque voie.

Si l’étiquette est trouvée dans une voie, la donnée est chargée. Sinon, une voie est choisie pour remplacer la ligne selon un algorithme de remplacement, et la nouvelle ligne est chargée dans cette voie.

Le degré d’associativité correspond au nombre de voies du cache.

Résumé des points clés

• La mémoire d’un ordinateur est organisée en hiérarchie selon la vitesse, le coût et la capacité.
• Les caches sont des mémoires intermédiaires rapides entre le processeur et la mémoire centrale, réduisant le temps d’accès moyen.
• Le principe de localité (temporelle et spatiale) justifie l’efficacité des caches.
• Les caches fonctionnent en lecture et écriture avec des politiques spécifiques (Write Through et Write Back).
• Trois types d’organisation de cache existent : associatif, à correspondance directe et mixte.
• Les algorithmes de remplacement de ligne (FIFO, LRU, NMRU) permettent de gérer les entrées pleines dans les caches associatifs.
• Le cache à correspondance directe est simple mais sujet aux conflits, tandis que le cache associatif est plus flexible mais plus coûteux.
• Le cache mixte combine les avantages des deux précédents en divisant le cache en voies associatives.