Une mémoire cache ou antémémoire est, en informatique, une mémoire qui enregistre temporairement des copies de données provenant d'une source, afin de diminuer le temps d'un nouvel accès (en lecture) d'un matériel informatique (en général, un processeur) à ces données. Le principe du cache est également utilisable en écriture, et existe alors en trois modes possibles : write-through, write-back et write-around.

La mémoire cache, plus rapide et plus proche du matériel informatique qui demande la donnée, est plus petite - en raison de ses performances et donc de son coût - que la mémoire pour laquelle elle sert d'intermédiaire. Commercialement, la notion de cache est apparue sur le mainframe IBM 360/85 en 1968.

Des mécanismes de mémoires cache peuvent être placés entre tous producteurs et consommateurs de données fonctionnant de façon asynchrone, par exemple processeur et mémoire vive, réseau et espace applicatif, disque dur et mémoire vive, etc.

Techniquement, il est avantageux de gérer séparément les données non modifiables (illustrations d'un site distant, section de code d'un programme) et celles qui sont modifiables (formulaire, sections de données, etc.). Les processeurs ont par exemple le plus souvent des caches séparés pour le code et les données.

Sa rapidité nécessaire rend la mémoire cache coûteuse, et pour cette raison limitée. Dans le cas des microprocesseurs, taille et performance de ces caches, externes ou internes, peuvent très fortement influencer la vitesse de traitement des programmes. Il est possible de le mesurer par inhibition totale ou partielle du cache, ou par changement de sa taille s'il est externe.

Dans le cas des caches internes, la place utilisée par les transistors du cache dans le wafer conditionne son coût de fabrication. La mémoire cache est d'autant plus utile que l'algorithme à exécuter demande des accès répétitifs à de petites zones de mémoire :

section de code qui se répète (boucle), callbacks en programmation objet etc.

Quand le processeur est capable de prédire grosso modo ses besoins futurs en données, il peut alimenter à l'avance le cache, ce qui se nomme du prefetch.

Dénomination

Mémoire cache est la même expression que celle utilisée en anglais, à savoir cache memory, qui a remplacé « slave-memory », donné par son inventeur Maurice Vincent Wilkes en 1965. L'Académie française propose plutôt le terme antémémoire.

La différence entre mémoire cache et mémoire tampon réside dans le fait que la mémoire cache duplique l'information, tandis que le tampon peut exprimer l'idée d'une salle d'attente, sans impliquer nécessairement de duplication. Le cache buffer (tampon de cache) du disque ou disk cache (cache de disque) est à la fois un tampon où transite l'information et une mémoire cache qui recopie sous forme électronique les données stockées dans le disque sous forme magnétique.

La différence essentielle entre les caches disque et mémoire est que l'on dispose de très peu de temps dans le second cas pour déterminer où ranger ce que l'on cache. Lorsqu'on cache un disque, on peut choisir avec soin où placer chaque information en fonction des caractéristiques des pages. L'antémémoire des IBM 370, n'ayant droit qu'à un cycle mineur pour prendre sa décision, utilise arbitrairement les bits de poids faible de l'adresse mémoire comme adresse du cadre de page associé. Il revient alors au compilateur d'éviter de son mieux les collisions potentielles.

Voir Algorithme LRU.

Fonctionnement

Le cache contient une copie des données originelles lorsqu'elles sont coûteuses (en termes de temps d'accès) à récupérer ou à calculer par rapport au temps d'accès au cache. Une fois les données stockées dans le cache, on les y accède directement plutôt qu'en les récupérant ou en les recalculant, ce qui diminue le temps d'accès moyen.

Le processus fonctionne ainsi :

l'élément demandeur (microprocesseur) demande une information ;

le cache vérifie s'il possède cette information. S'il la possède, il la retransmet à l'élément demandeur – on parle alors de succès de cache (cache hit en anglais). S'il ne la possède pas, il la demande à l'élément fournisseur (mémoire principale par exemple) – on parle alors de défaut de cache (cache miss) ;

l'élément fournisseur traite la demande et renvoie la réponse au cache ;

le cache la stocke pour utilisation ultérieure et la retransmet à l'élément demandeur au besoin.

Si les mémoires cache permettent d'accroître les performances, c'est en partie grâce à deux principes qui ont été découverts à la suite d'études sur le comportement des programmes informatiques :

le principe de localité spatiale qui indique que l'accès à une donnée située à une adresse X va probablement être suivi d'un accès à une zone très proche de X. C'est évidemment vrai dans le cas d'instructions exécutées en séquence, et plus vrai encore pour les boucles courtes.

le principe de localité temporelle qui indique que l'accès à une zone mémoire à un instant donné a de fortes chances de se reproduire dans la suite immédiate du programme. C'est évidemment vrai dans le cas des boucles de quelques instructions seulement.

Concernant le calcul matriciel, le cache introduit en revanche de fortes dissymétries selon qu'on accède la matrice par lignes ou par colonnes, dissymétries d'autant plus importantes que la matrice est de grande taille. Un rapport du CNUCE mentionne un écart de performances d'un facteur 8 à 10 pour des matrices dont la plus petite dimension est 50.

Divers niveaux de mémoire cache

On trouve une zone de cache :

dans les disques durs ;

dans les serveurs proxy (dont les squids) ;

dans les serveurs de pages dynamiques ;

dans les mémoires gérées par les bases de données.

Dans les microprocesseurs, on différencie plusieurs niveaux de caches, souvent au nombre de trois :

Le cache de premier niveau (L1), plus rapide et plus petit (cache de données pouvant être séparé du cache d'instructions) ;

Le cache de second niveau (L2), moins rapide et plus gros ;

Le cache de troisième niveau (L3), encore moins rapide et encore plus gros ;

Ces derniers caches peuvent être situés dedans ou hors du microprocesseur.

Mémoire cache des microprocesseurs

Elle est très rapide, mais aussi très chère. Il s'agit souvent de SRAM.

La présence de mémoire cache permet d'accélérer l'exécution d'un programme. De ce fait, plus la taille de la mémoire cache est grande, plus la taille des programmes accélérés peut être élevée. Il y a cependant une limite au-delà de laquelle l'augmentation de la taille du cache ne sert plus à rien. En effet, dans les codes, il y a des branchements qui ne peuvent pas être prédits par les processeurs. À chaque branchement, la partie du code peut faire appel à une zone mémoire différente. C'est la raison pour laquelle, "l'horizon" au-delà duquel le microprocesseur ne peut voir s'il aura besoin de certaines données limite l’efficacité du cache. La taille du cache est un élément souvent utilisé par les constructeurs pour faire varier les performances d'un produit sans changer d'autres matériels. Par exemple, pour les microprocesseurs, on trouve des séries bridées (avec une taille de mémoire cache volontairement réduite), tels que les Duron chez AMD ou Celeron chez Intel, et des séries haut de gamme avec une grande mémoire cache comme les processeurs Opteron chez AMD, ou Pentium 4EE chez Intel. Autrement dit, la taille de la mémoire cache résulte d'un compromis coût/performance.

En programmation, pour profiter de l'accélération fournie par cette mémoire très rapide, il faut que les parties de programme tiennent le plus possible dans cette mémoire cache. Comme elle varie suivant les processeurs, ce rôle d'optimisation est souvent dédié au compilateur. Cela dit, un programmeur chevronné peut écrire son code d'une manière qui optimise l'utilisation du cache.

C'est le cas des boucles très courtes qui tiennent entièrement dans les caches de données et d'instruction, par exemple le calcul suivant (écrit en langage C) :

       long i;
       double s;
       s = 0.0;
       for (i = 1; i < 50000000; i++)
           s += 1.0 / i;

Définitions

Une ligne 

le plus petit élément de données qui peut être transféré entre la mémoire cache et la mémoire de niveau supérieur.

Un mot 

le plus petit élément de données qui peut être transféré entre le processeur et la mémoire cache.

Différents types de défauts de cache (miss)

Il existe trois types de défauts de cache en système monoprocesseur et quatre dans les environnements multiprocesseurs. Il s'agit de :

les défauts de cache obligatoires : ils correspondent à la première demande du processeur pour une donnée/instruction spécifique et ne peuvent être évités ;

les défauts de cache capacitifs : l'ensemble des données nécessaires au programme excèdent la taille du cache, qui ne peut donc pas contenir toutes les données nécessaires ;

les défauts de cache conflictuels : deux adresses distinctes de la mémoire de niveau supérieur sont enregistrées au même endroit dans le cache et s'évincent mutuellement, créant ainsi des défauts de cache ;

les défauts de cohérence : ils sont dus à l'invalidation de lignes de la mémoire cache afin de conserver la cohérence entre les différents caches des processeurs d'un système multi-processeurs.

La correspondance (ou mapping)

La mémoire cache ne pouvant contenir toute la mémoire principale, il faut définir une méthode indiquant à quelle adresse de la mémoire cache doit être écrite une ligne de la mémoire principale. Cette méthode s'appelle le mapping. Il existe trois types de mapping répandus dans les caches aujourd'hui :

les mémoires caches complètement associatives (fully associative cache) ;

les mémoires caches directes (direct mapped cache).

les mémoires caches N-associatives (N-way set associative cache) ;

Cache pleinement associatif (fully associative cache)

Chaque ligne de la mémoire de niveau supérieur peut être écrite à n'importe quelle adresse de la mémoire cache. Cette méthode requiert beaucoup de logique car elle donne accès à de nombreuses possibilités. Ceci explique pourquoi l'associativité complète n'est utilisée que dans les mémoires cache de petite taille (typiquement de l'ordre de quelques kibioctets). Cela donne le découpage suivant de l'adresse :

Cache à correspondance préétablie (direct-mapped cache)

Chaque ligne de la mémoire principale ne peut être enregistrée qu'à une seule adresse de la mémoire cache, par exemple associée au modulo de son adresse. Cela crée de nombreux défauts de cache si le programme accède à des données en collision sur les mêmes adresses de la mémoire cache. La sélection de la ligne où la donnée sera enregistrée est habituellement obtenue par: Ligne = Adresse mod Nombre de lignes.

Une ligne de cache est partagée par de nombreuses adresses de la mémoire de niveau supérieur. Il nous faut donc un moyen de savoir quelle donnée est actuellement dans le cache. Cette information est donnée par le tag, qui est une information supplémentaire stockée dans le cache. L'index correspond à la ligne où est enregistrée la donnée. En outre, le contrôleur de la mémoire cache doit savoir si une adresse donnée contient une donnée ou non. Un bit additionnel (appelé bit de validité) est chargé de cette information.

Prenons l'exemple d'une adresse de 32 bits donnant accès à une mémoire adressable par octet, d'une taille de ligne de 256 bits et d'une mémoire cache de 2 kibioctets. La mémoire cache contient donc 2 bits (1 kio = 2 octets et 1 octet = 2 bits). Sachant qu'une ligne est de 256 bits soit 2 bits, nous déduisons qu'il y a 2 lignes stockables en mémoire cache. Par conséquent, l'index est de s+5 bits.

L'adresse de 32 bits permet d'accéder à une mémoire de 2 octets, soit 2 bits. L'index étant de s+5 bits, il faut distinguer 2 éléments de la mémoire principale par ligne de cache. Le tag est donc de 22-s bits.

De plus, une ligne a une taille de 256 bits soit 32 octets. La mémoire étant adressable par octet, cela implique un offset de 5 bits. L'offset est le décalage à l'intérieur d'une ligne pour accéder à un octet particulier. Ces calculs donnent le découpage de l'adresse suivant pour une mémoire cache mappée directement :

Le mapping direct est une stratégie simple mais peu efficace car elle crée de nombreux défauts de cache conflictuels. Une solution est de permettre à une adresse de la mémoire principale d'être enregistrée à un nombre limité d'adresses de la mémoire cache. Cette solution est présentée dans la section suivante.

N-way set associative cache

N-way set associative cache

Il s'agit d'un compromis entre le "mapping" direct et complètement associatif essayant d'allier la simplicité de l'un et l'efficacité de l'autre.

La mémoire cache est divisée en ensembles (sets) de N lignes de cache. Un ensemble est représenté sur la figure ci-jointe par l'union des rectangles rouges. Une ligne de la mémoire de niveau supérieur est affectée à un ensemble, elle peut par conséquent être écrite dans n'importe laquelle des voies i.e. des N lignes de l'ensemble. Ceci permet d'éviter de nombreux défauts de cache conflictuels. À l'intérieur d'un ensemble, le mapping est Direct Mapped, alors que le mapping des N Sets est Full Associative. En général, la sélection de l'ensemble est effectuée par : Ensemble = Adresse mémoire mod (Nombre d'ensembles).

Reprenons l'exemple de la section précédente (mémoire cache de kibioctets) mais constitué de voies. Le nombre de voies est en effet toujours une puissance de 2 afin d'obtenir un découpage simple de l'adresse mémoire. La mémoire cache contient donc bits par voie. Sachant qu'une ligne représente 256 bits, il y a donc lignes par ensemble. L'index est donc de s-n+5 bits.

Les mémoires considérées ici sont adressables par octet. Par conséquent, les adresses de 32 bits donnent accès à une mémoire de bits, soit l'équivalent de lignes de mémoire cache. Ainsi, chaque ensemble de la mémoire cache contient lignes distinctes. Le tag est donc de 22-s+n bits. Le découpage de l'adresse est alors :

Caches unifiés ou caches séparés

Pour fonctionner, un processeur a besoin de données et d'instructions. Il existe donc deux solutions pour l'implémentation des mémoires cache :

le cache unifié : données et instructions sont enregistrées dans la même mémoire cache ;

les caches séparés de données et d'instructions.

Séparer données et instructions permet notamment d'augmenter la fréquence de fonctionnement du processeur, qui peut ainsi accéder simultanément à une donnée et une instruction. Cette situation est particulièrement courante pour des Load/Store. Ceci explique que le cache unifié est souvent le maillon faible du système. De plus, dans un cache unifié, une logique supplémentaire donnant la priorité aux données ou aux instructions doit être introduite, ce qui n'est pas le cas pour les caches séparés.

Là où on sait que les instructions ne sont pas modifiables par le programme (ce qui fait partie des bonnes pratiques), on pourrait en théorie se passer du dirty bit. Cependant les programmes demandant des performances élevées (pilotes de périphériques rapides, par exemple) prennent parfois des libertés à cet égard, ce qui oblige à la prudence. Tout au plus, on sait que les instructions - à la différence des données - seront rarement ou très rarement modifiées, et on peut optimiser les circuits en conséquence.

En cas de modifications des instructions par le programme, les caches séparés introduisent un problème de cohérence du cache d'instructions: le programme doit alors invalider lui-même les entrées correspondantes dans le cache d'instruction pour provoquer leur mise à jour avant d'exécuter les instructions modifiées, sans quoi une version précédente de ces instructions pourrait être prise en compte et exécutée par le processeur (voire quelque mélange imprévisible des nouvelles instructions et des anciennes).

En 2011, la solution la plus répandue est la séparation des caches, car elle permet entre autres d'appliquer des optimisations spécifiques à chaque cache en fonction de son type d'accès.

Politique d'écriture dans la mémoire de niveau supérieur

Quand une donnée se situe dans le cache, le système en possède deux copies : une dans la mémoire de niveau supérieur (disons la mémoire principale) et une dans la mémoire cache. Quand la donnée est modifiée localement, plusieurs politiques de mise à jour existent :

Écriture immédiate (write-through) 

la donnée est écrite à la fois dans le cache et dans la mémoire principale. La mémoire principale et le cache ont à tout moment une valeur identique, simplifiant ainsi de nombreux protocoles de cohérence ;

Écriture différée (write-back) 

l'information n'est écrite dans la mémoire principale que lorsque la ligne disparaît du cache (invalidée par d'autres processeurs, évincée pour écrire une autre ligne...). Cette technique est la plus répandue car elle permet d'éviter de nombreuses écritures mémoires inutiles. Pour ne pas avoir à écrire des informations qui n'ont pas été modifiées (et ainsi éviter d'encombrer inutilement le bus), chaque ligne de la mémoire cache est pourvue d'un bit indiquant la modification (bit dirty). Lorsque la ligne est modifiée dans le cache, ce bit est positionné à 1, indiquant qu'il faudra réécrire la donnée dans la mémoire principale. L'écriture différée nécessite bien entendu des précautions particulières lorsqu'on l'utilise pour des supports amovibles ("Retrait du volume en toute sécurité" avec purge - flush - du cache).

Algorithme Write-through

Algorithme Write-back

Algorithmes de remplacement des lignes de cache

Les caches associatifs de N voies et complètement associatifs impliquent le mapping de différentes lignes de la mémoire de niveau supérieur sur le même set. Ainsi, lorsque le set de lignes de la mémoire cache, où une ligne de la mémoire supérieure peut être mappée, est rempli, il faut désigner la ligne qui sera effacée au profit de la ligne nouvellement écrite. Le but de l'algorithme de remplacement des lignes de cache est de choisir cette ligne de manière optimale. Ces algorithmes doivent être implémentés en hardware pour les mémoires caches de bas niveau afin d'être les plus rapides possible et de ne pas ralentir le processeur. Cependant, ils peuvent être implémentés en software pour des caches de niveau supérieur.

La majorité des algorithmes reposent sur le principe de localité pour tenter de prévoir le futur à partir du passé. Certains des algorithmes de remplacement des lignes de mémoire cache les plus répandus sont :

aléatoires pour la simplicité de la création de l'algorithme ;

FIFO(First In First Out) pour sa simplicité de conception ;

LRU (Least Recently Used) qui mémorise la liste des derniers éléments accédés...

Gestion d'un cache au niveau logiciel

Au-delà de ces systèmes matériels de gestion d'un cache, le terme de mémoire cache est aussi utilisé par abus de langage pour désigner tout mécanisme mis en œuvre dans un logiciel afin de permettre une réutilisation rapide de données déjà transférées auparavant.

Par exemple, tout système d'exploitation moderne possède, à l'interface entre les systèmes de fichiers et les pilotes chargés du stockage de masse, une sous-entité dont le but est de garder en mémoire vive les données récemment lues ou écrites ; cela permet d'éviter les entrées/sorties inutiles avec le stockage de masse, car celles-ci sont généralement plus lentes que celles avec la mémoire vive.

Le principe est le suivant :

lorsqu'une demande d'écriture (respectivement : de lecture) est faite au système de fichiers, celui-ci demande au système de gestion de la mémoire de marquer la zone mémoire source (respectivement : destination) avec un identifiant unique (la position des données sur le disque dur par exemple) ;

si une demande de lecture intervient par la suite, le système de fichiers n'effectue pas le transfert immédiatement, mais demande au système de gestion de la mémoire si les données ne seraient pas déjà en mémoire. Si ce n'est pas le cas, le transfert a lieu normalement. En revanche, si la réponse est positive, le transfert a lieu par une simple copie de mémoire à mémoire et le disque dur a été libéré d'un transfert inutile.

La cohérence est garantie si à tout transfert est associé un marquage des données en mémoire. Un algorithme utilisant des critères d'âge et de réutilisation des données choisit lesquelles seront prioritaires pour rester dans le cache quand celui-ci approchera de la saturation. Pour l'usage aléatoire, ce qui est toujours au moins le cas des répertoires, cet algorithme considère que ce qui a été beaucoup utilisé récemment a de plus fortes chances de l'être dans un futur proche (voir : Loi des 80/20).

高速缓存（英语：cache，英语发音：/kæʃ/ kash ，简称缓存），其原始意义是指访问速度比一般随机访问内存（RAM）快的一种RAM，通常它不像系统主内存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术。

原理

Cache一词来源于1967年的一篇电子工程期刊论文。其作者将法语词「cache」赋予“safekeeping storage”的涵义，用于电脑工程领域。 当CPU处理数据时，它会先到Cache中去寻找，如果数据因之前的操作已经读取而被暂存其中，就不需要再从随机访问内存（Main memory）中读取数据——由于CPU的运行速度一般比主内存的读取速度快，主存储器周期（访问主存储器所需要的时间）为数个时钟周期。因此若要访问主内存的话，就必须等待数个CPU周期从而造成浪费。 提供「缓存」的目的是为了让数据访问的速度适应CPU的处理速度，其基于的原理是内存中「进程执行与数据访问的局域性行为」，即一定进程执行时间和空间内，被访问的代码集中于一部分。为了充分发挥缓存的作用，不仅依靠“暂存刚刚访问过的数据”，还要使用硬件实现的指令预测与数据预取技术——尽可能把将要使用的数据预先从内存中取到缓存里。 CPU的缓存曾经是用在超级计算机上的一种高级技术，不过现今电脑上使用的的AMD或Intel微处理器都在芯片内部集成了大小不等的数据缓存和指令缓存，通称为L1缓存（L1 Cache即Level 1 On-die Cache，第一级片上高速缓冲存储器）；而比L1更大容量的L2缓存曾经被放在CPU外部（主板或者CPU接口卡上），但是现在已经成为CPU内部的标准组件；更昂贵的CPU会配备比L2缓存还要大的L3缓存（level 3 On-die Cache第三级高速缓冲存储器）。

概念的扩充

如今缓存的概念已被扩充，不仅在CPU和主内存之间有Cache，而且在内存和硬盘之间也有Cache（磁盘缓存），乃至在硬盘与网络之间也有某种意义上的Cache──称为Internet临时文档夹或网络内容缓存等。凡是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构，均可称之为Cache。

地址镜像与变换

由于主存容量远大于CPU缓存的容量，因此两者之间就必须按一定的规则对应起来。地址镜像就是指按某种规则把主存块装入缓存中。地址变换是指当按某种镜像方式把主存块装入缓存后，每次访问CPU缓存时，如何把主存的物理地址（Physical address）或虚拟地址（Virtual address）变换成CPU缓存的地址，从而访问其中的数据。

缓存置换策略