Organisation et politiques de cache

L'organisation du cache concerne la manière dont un cache mappe les blocs de mémoire au stockage — son placement et son associativité — ainsi que les politiques qui régissent le remplacement et les écritures, qui ensemble déterminent la fréquence des accès réussis (hits) au cache et son interaction avec la mémoire principale.

Definition

L'organisation et les politiques de cache sont les choix structurels et de gestion d'un cache — où les blocs peuvent être placés, quel bloc est évincé lors d'un échec d'accès, et comment les écritures sont propagées aux niveaux inférieurs — qui régissent son taux d'accès réussi (hit rate) et son comportement.

Scope

Ce sujet couvre la conception interne d'un cache unique : le placement direct, associatif par ensembles (set-associative) et entièrement associatif (fully associative) ; les politiques de remplacement telles que LRU (Least Recently Used) et ses approximations ; les politiques d'écriture (écriture directe ou write-through versus écriture différée ou write-back) et l'allocation d'écriture (write-allocation) ; la taille des blocs ; et la classification des échecs d'accès (misses) en obligatoires (compulsory), de capacité (capacity) et de conflit (conflict). Il exclut la cohérence multi-cache (protocoles de cohérence de cache) et la traduction d'adresses (mémoire virtuelle et pagination).

Core questions

• En quoi le placement direct, associatif par ensembles et entièrement associatif diffère-t-il en termes de coût et de comportement de conflit ?
• Quelle politique de remplacement devrait évincer un bloc lors d'un échec d'accès, et comment est-elle approximée à faible coût ?
• En quoi les politiques d'écriture directe (write-through) et d'écriture différée (write-back) diffèrent-elles en termes de trafic et de complexité ?
• Comment les échecs d'accès sont-ils classifiés, et quels changements de conception réduisent chaque type ?

Key concepts

• cache à correspondance directe
• cache associatif par ensembles
• cache entièrement associatif
• remplacement du moins récemment utilisé (LRU)
• écriture directe (write-through) vs écriture différée (write-back)
• allocation d'écriture (write-allocate)
• taille de bloc (ligne)
• échecs d'accès obligatoires, de capacité et de conflit

Key theories

Modèle des trois C pour les échecs d'accès

Les échecs d'accès au cache peuvent être catégorisés comme obligatoires (premier accès), de capacité (cache trop petit pour l'ensemble de travail) et de conflit (associativité insuffisante), un cadre qui relie chaque paramètre de conception — taille, taille de bloc, associativité — aux échecs d'accès qu'il réduit.

Mechanisms

Une adresse mémoire est divisée en champs d'étiquette (tag), d'index et de décalage (offset). L'index sélectionne un ensemble (set), l'étiquette identifie le bloc à l'intérieur de cet ensemble, et l'associativité détermine combien de blocs partagent un ensemble. Lors d'un échec d'accès, le cache récupère le bloc et en évince un autre choisi par une politique de remplacement (souvent une approximation du moins récemment utilisé ou LRU). Les écritures mettent à jour la mémoire principale immédiatement (écriture directe ou write-through) ou marquent le bloc comme "sale" (dirty) et reportent la mise à jour (écriture différée ou write-back).

Clinical relevance

L'organisation du cache régit la performance effective car les pénalités d'échec d'accès sont importantes par rapport aux accès réussis. Les programmeurs améliorent le comportement du cache grâce à l'organisation des données (data layout), au blocage (blocking) et aux motifs d'accès qui augmentent la localité, tandis que les architectes ajustent l'associativité, la taille des blocs et la politique d'écriture pour équilibrer le taux d'accès réussi par rapport à la surface, la consommation d'énergie et la bande passante.

History

Wilkes a proposé la mémoire esclave (cache) en 1965, et les caches ont été rapidement adoptés commercialement. L'étude de 1982 d'Alan Jay Smith a synthétisé des mesures approfondies des politiques de placement, de remplacement et d'écriture, établissant le vocabulaire de conception encore utilisé aujourd'hui. Le modèle des trois C a ensuite fourni une manière structurée de raisonner sur les causes et les remèdes des échecs d'accès.

Key figures

• Maurice Wilkes
• Alan Jay Smith
• John L. Hennessy
• David A. Patterson

Seminal works

• smith1982cache
• hennessy2019

Frequently asked questions

Quelle est la différence entre les caches à écriture directe (write-through) et à écriture différée (write-back) ?

Un cache à écriture directe (write-through) met à jour à la fois le cache et la mémoire principale à chaque écriture, maintenant la mémoire à jour mais générant plus de trafic. Un cache à écriture différée (write-back) met à jour uniquement le cache, marquant le bloc comme "sale" (dirty), et ne l'écrit en mémoire que lorsqu'il est évincé, réduisant ainsi le trafic au prix d'une gestion supplémentaire.

Pourquoi utiliser des caches associatifs par ensembles plutôt que des caches à correspondance directe ?

Un cache à correspondance directe n'autorise qu'un seul emplacement pour chaque bloc, de sorte que les blocs qui se mappent au même emplacement entrent en conflit. L'associativité par ensembles offre à chaque bloc plusieurs emplacements possibles au sein d'un ensemble, réduisant les échecs d'accès par conflit au prix d'un matériel de comparaison plus important et d'accès réussis légèrement plus lents.