Hiérarchie mémoire

Ramenons les temps d'accès d'une machine à l'échelle humaine, en posant qu'un accès à un registre dure une seconde.

Le chapitre 5 a nommé le problème — le processeur attend la mémoire. Le voici chiffré : entre un registre et la mémoire vive, il y a le rapport d'une seconde à trois minutes. Aucune astuce de programmation ne comble un tel écart. Ce qui le comble, c'est une hiérarchie de mémoires, et un pari statistique sur la façon dont les programmes accèdent aux données.

La pyramide, et pourquoi elle existe

On voudrait une mémoire à la fois rapide, vaste et bon marché. Les trois sont incompatibles : la technologie qui va vite coûte cher au bit et consomme, donc on n'en met pas beaucoup.

La solution est de superposer plusieurs technologies, la plus rapide et la plus petite au plus près du processeur :

1        registres      ~ 1 Kio        le plus rapide, le plus cher2        cache L1       ~ 64 Kio3        cache L2       ~ 512 Kio4        cache L3       ~ 32 Mio       partagé entre les cœurs5        mémoire vive   ~ 16 Gio6        SSD / disque   ~ 1 Tio        le plus lent, le moins cher

Chaque niveau contient un sous-ensemble du niveau inférieur, et sert de tampon pour lui. L'objectif est de donner l'illusion d'une mémoire aussi vaste que le disque et presque aussi rapide que le cache. Ce n'est pas une illusion gratuite : elle repose sur une propriété observée des programmes réels.

Le principe de localité

Un programme n'accède pas à la mémoire au hasard. Il le fait suivant deux régularités, et toute la hiérarchie repose sur elles.

La localité temporelle. Une case qui vient d'être utilisée a de fortes chances de l'être à nouveau bientôt. Une variable de boucle, un compteur, l'adresse de retour d'une fonction : on y revient à chaque tour.

La localité spatiale. Si une case est utilisée, ses voisines le seront probablement. Parcourir un tableau, exécuter des instructions consécutives, lire les champs d'une structure : tous ces accès sont contigus.

Le programme du chapitre 6 en est l'illustration parfaite. Les cinq instructions du corps de la boucle sont relues à chaque tour — localité temporelle — et se suivent en mémoire — localité spatiale. Les registres $t0 et $t1 sont écrits et relus sans cesse.

De là découle la décision de conception la plus importante du cache : on ne transfère jamais un mot isolé, on transfère une ligne de 32 ou 64 octets. Puisque les voisines seront probablement demandées, autant les rapporter tout de suite — le coût dominant est celui du déplacement, pas celui de la quantité.

Comment fonctionne un cache

Le cache est un petit tableau de lignes. Le processeur demande une adresse ; s'il la trouve c'est un succès (hit), sinon un échec (miss) et il faut aller au niveau inférieur.

Pour savoir où chercher, l'adresse est découpée en trois champs, et ce découpage est exactement la somme pondérée du chapitre 1 coupée en morceaux :

1        ┌──────────────┬──────────┬──────────────┐2adresse │   étiquette  │  index   │  déplacement │3        └──────────────┴──────────┴──────────────┘4             qui ?        où ?        quel octet5                                      dans la ligne

Le déplacement désigne l'octet dans la ligne : pour une ligne de 64 octets, 6 bits. L'index désigne l'emplacement du cache où cette adresse a le droit de se trouver : pour 128 emplacements, 7 bits. L'étiquette est tout le reste, et elle est stockée avec la ligne pour savoir laquelle des nombreuses adresses possibles y réside.

Trois organisations existent, et elles se distinguent par le nombre d'emplacements où une adresse peut aller.

La correspondance directe : un seul emplacement possible, calculé par l'index. Recherche immédiate, matériel minimal — mais deux adresses de même index se chassent mutuellement, même si le reste du cache est vide. C'est le conflit, et il est spectaculaire sur les parcours dont le pas est une puissance de deux.

Le totalement associatif : n'importe quelle ligne peut aller n'importe où. Aucun conflit, mais il faut comparer l'étiquette à toutes les lignes en parallèle — trop coûteux au-delà de quelques dizaines d'entrées.

L'associatif par ensembles est le compromis universellement retenu : le cache est découpé en ensembles de $k$ lignes, l'index désigne l'ensemble, et l'adresse peut occuper n'importe laquelle des $k$ voies. Avec $k = 4$ ou 8, les conflits deviennent rares pour un coût de comparaison modeste.

Mesurer, et les deux politiques

Le taux de succès $t$ est la proportion d'accès trouvés dans le cache. Le temps d'accès moyen s'en déduit :

Le calcul réserve une surprise, et c'est le point à retenir du chapitre. Avec un cache à 1 ns et une mémoire à 60 ns : à 95 % de succès, on obtient 3,95 ns ; à 99 %, 1,59 ns. Passer de 95 % à 99 % divise le temps moyen par 2,5, alors que le taux ne progresse que de quatre points. C'est parce que le terme d'échec est pondéré par un coût soixante fois supérieur — raison pour laquelle on parle plutôt du taux d'échec que du taux de succès : c'est lui qui pilote la performance.

Deux politiques restent à fixer.

Le remplacement : quelle ligne évincer quand l'ensemble est plein ? LRU (least recently used), qui sacrifie la moins récemment utilisée, est le choix naturel — c'est un pari direct sur la localité temporelle. Le cours de systèmes reprendra exactement cette question au chapitre 6, pour les pages en mémoire.

L'écriture : que faire quand le processeur écrit ? En écriture immédiate (write-through), on écrit dans le cache et dans la mémoire à la fois — simple, cohérent, lent. En écriture différée (write-back), on n'écrit que dans le cache, on marque la ligne « sale », et on ne recopie en mémoire qu'à son éviction — rapide, mais il faut gérer la cohérence, question qui devient épineuse dès qu'il y a plusieurs cœurs partageant des données.

ROM, SRAM, DRAM

Trois technologies, trois rôles, et les distinguer évite bien des confusions.

La ROM est non volatile : elle survit à la coupure de courant. Elle contient le micrologiciel qui démarre la machine — le processeur, au premier front d'horloge, va chercher son instruction à une adresse fixe qui pointe dans la ROM. Ses variantes modernes, EEPROM et mémoire flash, se réécrivent, ce qui permet les mises à jour de micrologiciel et fonde les SSD.

La SRAM stocke chaque bit dans une bascule — celle du chapitre 4, six transistors. Elle est rapide et tient son état tant qu'elle est alimentée, mais elle est encombrante et chère. C'est la mémoire des caches et des registres.

La DRAM stocke chaque bit dans un condensateur, avec un seul transistor. D'où sa densité, donc son prix bas au gigaoctet, donc son emploi comme mémoire principale. Mais le condensateur se décharge : il faut le rafraîchir toutes les quelques dizaines de millisecondes, en relisant et réécrivant chaque ligne. Ce rafraîchissement coûte du temps et de l'énergie, et c'est la raison de fond pour laquelle la DRAM est plus lente que la SRAM.

Toutes deux sont volatiles : contenu perdu à l'extinction. C'est ce qui rend nécessaire le système de fichiers du chapitre 7 du cours de systèmes.

Un mot de mémoire virtuelle

Le même raisonnement se rejoue un cran plus bas, entre la mémoire vive et le disque, et il porte alors le nom de mémoire virtuelle.

Chaque programme manipule des adresses logiques, qu'un composant matériel — l'unité de gestion mémoire — traduit en adresses physiques. La mémoire est découpée en pages de 4 Kio, et toutes les pages n'ont pas besoin d'être en mémoire vive : les autres attendent sur le disque, et le matériel signale un défaut de page quand on touche l'une d'elles.

Les analogies avec le cache sont exactes, terme à terme : la page est la ligne, le défaut de page est l'échec, l'algorithme de remplacement est le LRU, et la localité est ce qui rend le tout viable. Seuls les ordres de grandeur changent — et ils changent tellement, un facteur cent mille sur le coût de l'échec, que la gestion passe du matériel au logiciel. C'est pourquoi la mémoire virtuelle est traitée en détail par le cours de systèmes d'exploitation, chapitre 6, et seulement introduite ici.

À vous

L'exercice construit un simulateur de cache : découpage d'adresse en étiquette, index et déplacement, puis comptage des succès et des échecs sur une trace d'accès.

Deux expériences valent le détour, et ce sont celles du TD. La première compare la correspondance directe et l'associatif à deux voies sur un motif qui provoque des conflits. La seconde parcourt une matrice par lignes puis par colonnes : même nombre d'accès, même tableau, et un taux de succès qui s'effondre dans le second cas — c'est la localité spatiale rendue mesurable, et l'argument le plus convaincant du chapitre.

// Un cache associatif par ensembles. voies = 1 donne la correspondance
// directe, voies = nbLignes donne le totalement associatif.
function creerCache({ tailleLigne, nbLignes, voies }) {
  const ensembles = nbLignes / voies;
  const table = Array.from({ length: ensembles }, () => []);  // [etiquette, ...] par ensemble
  let succes = 0, echecs = 0;

  return {
    acceder(adresse) {
      // Découpage de l'adresse. Le déplacement dans la ligne ne sert pas à
      // localiser la ligne : on le jette en divisant.
      const numeroLigne = Math.floor(adresse / tailleLigne);
      const index = numeroLigne % ensembles;
      const etiquette = Math.floor(numeroLigne / ensembles);

      const jeu = table[index];
      const place = jeu.indexOf(etiquette);
      if (place !== -1) {
        succes++;
        // ← LRU : la ligne qu'on vient d'utiliser redevient la plus récente
        return true;
      }
      echecs++;
      jeu.push(etiquette);
      if (jeu.length > voies) jeu.shift();   // évince la plus ancienne
      return false;
    },
    bilan(nom) {
      const total = succes + echecs;
      const taux = ((succes / total) * 100).toFixed(1);
      console.log(nom.padEnd(34) + succes + " succès / " + total +
                  "  ->  " + taux + " % de succès");
      return succes / total;
    },
  };
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Le LRU est incomplet : en cas de succès, la ligne touchée doit
//    redevenir la plus récente. Sans cela, la politique est un simple FIFO.
// 2. Expérience 2 : écrivez le parcours PAR COLONNES et comparez.

const MOT = 4, LIGNE = 64, LIGNES = 64;

// Expérience 1 — deux tableaux distants d'un multiple exact de la taille du
// cache : leurs cases de même rang tombent sur le même index.
function alternance(voies) {
  const c = creerCache({ tailleLigne: LIGNE, nbLignes: LIGNES, voies });
  const A = 0, B = LIGNE * LIGNES;
  for (let tour = 0; tour < 4; tour++) {
    for (let i = 0; i < 64; i++) { c.acceder(A + i * MOT); c.acceder(B + i * MOT); }
  }
  return c.bilan("alternance, " + voies + " voie(s)");
}
alternance(1);
alternance(2);

// Expérience 2 — une matrice 64 x 64 d'entiers, rangée ligne par ligne.
const N = 64;
const adresseMatrice = (i, j) => (i * N + j) * MOT;

function parLignes() {
  const c = creerCache({ tailleLigne: LIGNE, nbLignes: LIGNES, voies: 2 });
  for (let i = 0; i < N; i++) for (let j = 0; j < N; j++) c.acceder(adresseMatrice(i, j));
  return c.bilan("matrice parcourue par lignes");
}
parLignes();
// ← écrivez parColonnes() : mêmes accès, ordre des boucles inversé

function creerCache({ tailleLigne, nbLignes, voies }) {
  const ensembles = nbLignes / voies;
  const table = Array.from({ length: ensembles }, () => []);
  let succes = 0, echecs = 0;

  return {
    acceder(adresse) {
      const numeroLigne = Math.floor(adresse / tailleLigne);
      const index = numeroLigne % ensembles;
      const etiquette = Math.floor(numeroLigne / ensembles);

      const jeu = table[index];
      const place = jeu.indexOf(etiquette);
      if (place !== -1) {
        succes++;
        // LRU : on retire la ligne de sa position et on la remet en queue,
        // qui est le bout « le plus récemment utilisé ». Sans ce geste, la
        // politique dégénère en FIFO et perd la localité temporelle.
        jeu.splice(place, 1);
        jeu.push(etiquette);
        return true;
      }
      echecs++;
      jeu.push(etiquette);
      if (jeu.length > voies) jeu.shift();
      return false;
    },
    bilan(nom) {
      const total = succes + echecs;
      const taux = ((succes / total) * 100).toFixed(1);
      console.log(nom.padEnd(34) + succes + " succès / " + total +
                  "  ->  " + taux + " % de succès");
      return succes / total;
    },
  };
}

const MOT = 4, LIGNE = 64, LIGNES = 64;

function alternance(voies) {
  const c = creerCache({ tailleLigne: LIGNE, nbLignes: LIGNES, voies });
  const A = 0, B = LIGNE * LIGNES;
  for (let tour = 0; tour < 4; tour++) {
    for (let i = 0; i < 64; i++) { c.acceder(A + i * MOT); c.acceder(B + i * MOT); }
  }
  return c.bilan("alternance, " + voies + " voie(s)");
}
alternance(1);   // conflit systématique : chaque accès chasse le précédent
alternance(2);   // deux voies suffisent à loger les deux tableaux

const N = 64;
const adresseMatrice = (i, j) => (i * N + j) * MOT;

function parLignes() {
  const c = creerCache({ tailleLigne: LIGNE, nbLignes: LIGNES, voies: 2 });
  for (let i = 0; i < N; i++) for (let j = 0; j < N; j++) c.acceder(adresseMatrice(i, j));
  return c.bilan("matrice parcourue par lignes");
}

function parColonnes() {
  const c = creerCache({ tailleLigne: LIGNE, nbLignes: LIGNES, voies: 2 });
  // Mêmes 4096 accès, dans un autre ordre. Chaque accès saute 64 mots, donc
  // change de ligne de cache : la ligne rapportée ne sert qu'une fois.
  for (let j = 0; j < N; j++) for (let i = 0; i < N; i++) c.acceder(adresseMatrice(i, j));
  return c.bilan("matrice parcourue par colonnes");
}

const a = parLignes();
const b = parColonnes();
console.log("Même tableau, mêmes accès, ordre inversé : " +
  (a / b).toFixed(1) + " fois plus de succès par lignes.");

En travaux pratiques

/* par lignes : voisins en mémoire */
for (i = 0; i < N; i++)
  for (j = 0; j < N; j++)
      somme += m[i][j];        /* 0,08 s */

/* par colonnes : un saut de N entiers à chaque accès */
for (j = 0; j < N; j++)
  for (i = 0; i < N; i++)
      somme += m[i][j];        /* 0,94 s  → 12 fois plus lent */

perf stat -e cache-misses ./parcours

par lignes   :     4 200 000 défauts de cache
par colonnes : 16 800 000 défauts de cache   (×4)

une ligne de cache fait 64 octets = 16 entiers
par lignes   : 1 défaut pour 16 éléments utilisés
par colonnes : 1 défaut pour 1 seul élément utilisé,
             les 15 autres sont chargés puis jetés

taille du tableau | ns par accès
    16 Ko       |  1,1     ← tient en L1
    64 Ko       |  1,2
   256 Ko       |  3,8     ← marche : on est passé en L2
     2 Mo       |  4,1
    16 Mo       | 14,7     ← marche : on est passé en L3
   128 Mo       | 92,3     ← marche : mémoire centrale

/* ordre i, j, k : B parcouru par COLONNES */
for (i…) for (j…) for (k…) C[i][j] += A[i][k] * B[k][j];   /* 8,2 s */

/* ordre i, k, j : B parcouru par LIGNES */
for (i…) for (k…) for (j…) C[i][j] += A[i][k] * B[k][j];   /* 2,1 s */

for (ii = 0; ii < N; ii += B)
for (kk = 0; kk < N; kk += B)
  for (jj = 0; jj < N; jj += B)
    for (i = ii; i < ii+B; i++)
      for (k = kk; k < kk+B; k++)
        for (j = jj; j < jj+B; j++)
          C[i][j] += A[i][k] * B[k][j];

B = 64 → 0,7 s   (3 blocs de 64×64 entiers ≈ 48 Ko, tiennent en L2)

Ce que la suite en fait

Le chapitre 8 termine le tour de la machine par les entrées/sorties, dont les temps sont ceux de la dernière ligne du tableau d'ouverture — d'où les interruptions et l'accès direct à la mémoire, qui existent précisément pour ne pas faire attendre le processeur.

La loi d'Amdahl y formalisera ce que le calcul du taux d'échec a déjà fait pressentir : accélérer une partie d'un système donne un gain global borné par la part que cette partie occupe. Et le pipeline montrera la dernière raison d'être du cache : sans lui, un processeur capable de terminer une instruction par cycle passerait l'essentiel de son temps arrêté.

À retenir