Mémoire cache
composant électronique chargée d’accélérer la lecture de données en les conservant de manière transparante De Wikipédia, l'encyclopédie libre
composant électronique chargée d’accélérer la lecture de données en les conservant de manière transparante De Wikipédia, l'encyclopédie libre
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 accès ultérieur (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[1].
| Type |
|---|
| Usage |
|---|
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, 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é 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 :
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.
Mémoire cache est la même expression que celle utilisée en anglais, à savoir cache memory[2], qui a remplacé « slave-memory », donné par son inventeur Maurice Vincent Wilkes en 1965. La Commission d'enrichissement de la langue française propose d'utiliser plutôt le terme « antémémoire »[3].
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.
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 y accède directement par le cache 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 :
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 :
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[4] mentionne un écart de performances d'un facteur 8 à 10 pour des matrices dont la plus petite dimension est 50.
On trouve une zone de cache :
Dans les microprocesseurs, on différencie plusieurs niveaux de caches, souvent au nombre de trois :
Ces derniers caches peuvent être situés dedans ou hors du microprocesseur.
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;
Il existe trois types de défauts de cache en système monoprocesseur et quatre dans les environnements multiprocesseurs. Il s'agit de :
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 :
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 :
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 s kibioctets. La mémoire cache contient donc 2 × 10s+13 bits (1 kio = 210 octets et 1 octet = 23 bits). Sachant qu'une ligne est de 256 bits soit 28 bits, nous déduisons qu'il y a 2s+5 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 232 octets, soit 235 bits. L'index étant de s+5 bits, il faut distinguer 222-s é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.
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 entrées 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 :
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 :
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.
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 :
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 (dit aussi politique de remplacement ou politique d'éviction) 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 :
La politique LRU peut paraître la plus naturelle, car elle favorise les éléments les plus récemment utilisés donc a priori ceux qui sont en cours d'utilisation fréquente, mais elle a pu paraître difficile à réaliser efficacement en matériel, d'où l'existence de politiques « pseudo-LRU ».
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 :
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).
Un cache logiciel permet à une application d'éviter de répéter des appels de méthodes coûteux en stockant le résultat d'un appel en mémoire. Les appels de méthodes peuvent être coûteux en temps parce qu'ils réalisent des entrées-sorties réseau ou disque ou bien coûteux en termes de calculs, dans ce cas la mémoïsation peut être utilisée.
Voici une liste de logiciels ou librairies permettant d'implémenter un cache logiciel:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
