Un cœur moderne peut terminer plusieurs instructions par nanoseconde. La mémoire principale met de l’ordre de 60 à 100 nanosecondes pour répondre à une lecture. Si chaque chargement allait jusqu’à la DRAM, le pipeline passerait presque tout son temps bloqué.
La solution est un cache : une petite mémoire rapide placée près du cœur, qui garde des copies des données utilisées récemment. Cela fonctionne parce que les programmes sont prévisibles d’une façon bien précise — ils réutilisent ce qu’ils viennent d’utiliser, et ils touchent des données voisines de celles qu’ils viennent de toucher.
La hiérarchie mémoire
Aucune technologie n’est à la fois grande et rapide, alors les ordinateurs en empilent plusieurs :
| Niveau | Taille typique | Latence typique |
|---|---|---|
| registres | quelques centaines d’octets | comprise dans l’instruction |
| cache L1 (par cœur) | 32–64 Ko | ~4–5 cycles |
| cache L2 (par cœur) | 0,5–2 Mo | ~12–16 cycles |
| cache L3 (partagé) | 8–100+ Mo | ~40–70 cycles |
| mémoire principale (DRAM) | 8–512 Go | ~60–100 ns (des centaines de cycles) |
| SSD | 0,5–8 To | quelques dizaines de µs |
| disque dur | 1–30 To | ~5–10 ms |
Ce sont des ordres de grandeur pour un CPU de bureau ou de serveur du milieu des années 2020, pas des valeurs exactes. En descendant le tableau, chaque niveau est plus grand, moins cher par octet et plus lent. Chacun sert de cache au niveau inférieur.
La hiérarchie de Tanenbaum va des registres jusqu’aux bandes et disques optiques. L’idée n’a pas changé ; les chiffres, si.
La localité
Les caches reposent sur deux habitudes des programmes réels :
- Localité temporelle : une donnée utilisée maintenant a de bonnes chances d’être réutilisée bientôt — un compteur de boucle, le sommet de la pile, les instructions d’un corps de boucle.
- Localité spatiale : une donnée voisine de celle qu’on vient d’utiliser a de bonnes chances d’être utilisée bientôt — l’élément suivant d’un tableau, le champ suivant d’une structure, l’instruction suivante.
Un cache exploite la localité temporelle en gardant les données récemment utilisées, et la localité spatiale en chargeant plus que ce qui a été demandé.
Les lignes de cache
La mémoire est découpée en blocs de taille fixe appelés lignes — 64 octets sur tous les x86 actuels et la plupart des cœurs ARM. Le cache ne contient jamais un octet isolé. Lors d’un défaut (miss), il charge toute la ligne qui contient l’adresse. Lors d’un succès (hit), la donnée est déjà là.
La démo ci-dessous exécute une boucle qui additionne 64 int consécutifs (256 octets), et rejoue chaque accès aux données dans un cache à lignes de 64 octets :
Loading emulator…
Chaque carré de la bande est un accès. Seuls 4 sur 64 échouent — un par ligne — et les 60 autres réussissent : 93,75 %. Le premier défaut sur chaque ligne est obligatoire (compulsory) : personne n’avait encore touché cette ligne, aucun cache ne pouvait l’avoir.
Réglez maintenant line sur 16 octets : 16 défauts. Réglez-la sur 4 octets, un int par ligne, et chaque accès échoue. La localité spatiale ne rapporte que parce que la ligne est plus grande que ce qu’on demande.
Où va une ligne ?
Un cache de S ensembles (sets) et W voies (ways) contient S × W lignes. Chaque adresse est découpée en trois champs :
| étiquette (tag) | index d’ensemble | décalage |
|---|---|---|
| tout le reste | l’ensemble où chercher | l’octet dans la ligne |
Avec des lignes de 64 octets, le décalage occupe les 6 bits de poids faible. Avec 64 ensembles, les 6 bits suivants choisissent l’ensemble. Le reste est l’étiquette, rangée à côté de la ligne pour que le cache puisse vérifier laquelle des nombreuses lignes possibles il contient réellement.
À chaque accès, le cache prend l’index d’ensemble, compare l’étiquette aux W lignes de cet ensemble — toutes à la fois, en parallèle — et signale un succès si l’une correspond.
- Correspondance directe (W = 1) : chaque ligne n’a qu’un seul emplacement possible. La recherche est rapide et simple, mais deux lignes qui partagent un index d’ensemble s’évincent mutuellement.
- Associatif par ensembles à W voies : chaque ligne peut aller dans n’importe lequel des W emplacements de son ensemble.
- Totalement associatif (S = 1) : n’importe quelle ligne peut aller n’importe où, au prix d’une comparaison avec toutes les étiquettes.
Un cache de données L1 courant fait 64 ensembles × 8 voies × 64 octets = 32 Ko. Le livre de Tanenbaum note qu’une associativité au-delà de quatre voies était inhabituelle. Ce n’est plus vrai : les caches de données L1 actuels ont 8 à 12 voies, et les caches L3 12 à 16 voies ou plus.
Les défauts de conflit
Ici, deux tableaux sont placés à exactement 128 octets l’un de l’autre, et la boucle lit alternativement a[i] et b[i]. Le cache est à correspondance directe : 8 ensembles × 1 voie × 16 octets = 128 octets.
Loading emulator…
Chaque accès échoue. a[i] et b[i] sont à 128 octets l’un de l’autre, la taille du cache entier : ils tombent dans le même ensemble et s’évincent sans cesse. Le programme n’utilise que 4 lignes et le cache a 8 emplacements : la place n’est pas le problème, c’est la correspondance. Ce sont des défauts de conflit, en rouge.
Réglez ways sur 2. Chaque ensemble contient alors les deux lignes, et après les quatre défauts obligatoires, tout réussit. Voilà ce qu’apporte l’associativité.
Défauts de capacité et écritures
Quand les données ne tiennent tout simplement pas, même un placement parfait n’y peut rien. Cette boucle ajoute 1 à chaque élément d’un tableau de 256 octets, deux fois, à travers un cache de 128 octets :
Loading emulator…
add DWORD PTR [...], 1 lit la valeur puis la réécrit : chaque élément coûte deux accès, une lecture, puis une écriture qui réussit toujours. Quand la seconde passe commence, le début du tableau a été évincé depuis longtemps : ses défauts sont des défauts de capacité, en bleu — même un cache totalement associatif de 128 octets échouerait.
Regardez aussi write-backs. Ce cache est en write-back (écriture différée) : une écriture ne met à jour que la ligne en cache et la marque modifiée (dirty, D dans le tableau). La ligne ne retourne en mémoire qu’au moment de son éviction. Ici, toutes les lignes sont modifiées, donc chaque éviction est une réécriture.
Réglez sets sur 16. Le cache fait alors 256 octets, le tableau entier tient, et la seconde passe réussit à chaque fois.
Ces trois sortes de défauts — obligatoires, de capacité, de conflit — sont la façon habituelle d’expliquer pourquoi un programme rate le cache. Elles suggèrent aussi les remèdes : des lignes plus grandes ou du préchargement pour les défauts obligatoires, un cache plus grand ou un ensemble de travail plus petit pour les défauts de capacité, plus de voies ou une autre disposition des données pour les défauts de conflit.
L’ordre des accès compte
Mêmes données, même travail, ordre différent. Un tableau C int m[8][8] est rangé ligne après ligne. Le sommer ligne par ligne parcourt la mémoire dans l’ordre. Le sommer colonne par colonne saute de 32 octets à chaque pas.
Loading emulator…
Loading emulator…
La première version réussit 75 % du temps. La seconde échoue à chaque accès : chaque colonne touche 8 lignes différentes, le cache en contient 4, et quand la colonne suivante revient sur une ligne, elle a disparu. Sur du vrai matériel, avec des tableaux de plusieurs mégaoctets, la même différence rend la boucle par colonnes plusieurs fois plus lente. Les instructions sont identiques ; seul l’ordre des accès mémoire a changé.
Les écritures
Chaque écriture pose deux questions :
- Écriture réussie : mettre à jour la mémoire tout de suite (write-through, écriture immédiate), ou seulement à l’éviction de la ligne (write-back) ? L’écriture immédiate est plus simple et garde la mémoire à jour, mais elle envoie chaque rangement au niveau suivant. Les CPU actuels utilisent le write-back pour leurs caches de données.
- Écriture ratée : charger d’abord la ligne dans le cache (write-allocate), ou envoyer l’écriture directement au niveau suivant ? Les caches write-back allouent presque toujours, comme la démo : le prochain accès à cette ligne a alors de bonnes chances de réussir.
Le remplacement
Quand un ensemble est plein, un défaut doit évincer l’une de ses lignes. Le choix idéal serait la ligne dont on aura besoin le plus tard, mais le matériel ne voit pas l’avenir. LRU (least recently used) évince la ligne restée le plus longtemps sans être touchée, en pariant sur la localité temporelle. C’est ce que font les démos.
Un vrai LRU devient coûteux avec beaucoup de voies, car l’ordre doit être mis à jour à chaque accès. Les vrais caches utilisent des approximations moins chères, comme le pseudo-LRU en arbre, ou des politiques plus adaptatives qui évitent qu’un seul grand parcours chasse tout ce qui était utile.
Le temps d’accès effectif
Avec un temps d’accès au cache c, un temps d’accès mémoire m et un taux de succès h, le temps d’accès moyen vaut :
c + (1 − h) × m
Avec c = 4 cycles et m = 300 cycles :
- h = 95 % : 4 + 0,05 × 300 = 19 cycles ;
- h = 99 % : 4 + 0,01 × 300 = 7 cycles.
Quatre points de taux de succès rendent la mémoire presque trois fois plus rapide en apparence. C’est pourquoi un petit changement dans l’ordre des accès, comme l’exemple lignes/colonnes, peut autant changer la vitesse d’un programme.
Les hiérarchies de cache réelles
- L1 séparé. Chaque cœur a un cache L1 d’instructions et un cache L1 de données : une lecture d’instruction et un chargement ne sont jamais en concurrence. C’est le cache séparé du chapitre fetch–decode–execute.
- L2 privé par cœur, unifié (code et données).
- L3 partagé entre tous les cœurs de la puce.
- L’inclusion varie. Certaines conceptions gardent dans le L3 une copie de chaque ligne du L1/L2 (cache inclusif). D’autres non : le L3 des Zen d’AMD est rempli surtout par les lignes évincées du L2 (un cache de victimes), et les puces serveur récentes d’Intel utilisent un L3 non inclusif.
- Des préchargeurs matériels observent le flux d’accès et chargent des lignes avant qu’on les demande — la ligne suivante, ou l’élément suivant d’un pas régulier. Ils transforment beaucoup de défauts obligatoires en succès.
- Quand plusieurs cœurs mettent en cache les mêmes données, les caches doivent aussi rester cohérents. C’est un sujet pour le chapitre sur les multicœurs.
Sous Linux, lscpu --caches ou getconf -a | grep CACHE liste la taille, l’associativité et la taille de ligne des caches de votre machine, et perf stat -e cache-misses ./prog compte les défauts lors d’une vraie exécution.
À retenir
- La hiérarchie mémoire échange taille contre vitesse : registres, L1, L2, L3, DRAM, stockage.
- Les caches fonctionnent grâce à la localité temporelle et spatiale, et déplacent les données par lignes, en général de 64 octets.
- Une adresse se découpe en étiquette, index d’ensemble et décalage. L’associativité décide du nombre d’emplacements possibles pour une ligne.
- Les défauts sont obligatoires, de capacité ou de conflit. L’ordre des accès et la disposition des données peuvent changer radicalement le taux de succès.
- Les caches de données sont en write-back et write-allocate, et remplacent les lignes par LRU ou une approximation.
- Le temps d’accès moyen vaut c + (1 − h)m : quelques points de taux de succès comptent beaucoup.