Fonctionnement d'un ordinateur/Les mémoires cache

Le cache est une mémoire intercalée entre la mémoire et un processeur ou un périphérique, qui est souvent fabriquée avec de la mémoire SRAM, parfois avec de l'eDRAM. Sans lui, on se croirait à l'âge de pierre tellement nos PC seraient lents ! En effet, la mémoire est lente comparée au processeur. Or, le temps mis pour accéder à la mémoire est du temps durant lequel le processeur n’exécute pas d'instruction (sauf cas particuliers impliquant un pipeline). Il a fallu trouver une solution pour diminuer ce temps d'attente, et on a décidé d'intercaler une mémoire entre le processeur et la mémoire. Comme cela, le processeur accède directement à une mémoire cache très rapide plutôt que d'accéder à une mémoire RAM qui répondra de toute façon trop tard.

L'accès au cache

Le cache contient une copie de certaines données présentes en RAM. La copie présente dans le cache est accessible bien plus rapidement que celle en RAM, le cache étant beaucoup plus rapide que la RAM. Mais seule une faible partie de ces données sont présentes dans le cache, les autres données devant être lues ou écrites dans la RAM. Une donnée est chargée dans la mémoire cache quand elles est lue ou écrite par le processeur. Le cache rapatrie alors une copie de la donnée dans le cache lors de son premier accès, et conserve cette copie. Les lectures/écritures suivantes se feront alors directement dans le cache. Évidemment, au fur et à mesure des accès, certaines données anciennes sont éliminées du cache pour faire de la place aux nouveaux entrants. Mais nous en reparlerons plus tard. Toujours est-il que le cache contient une copie des dernières données accédées par le processeur.

Principe d'une mémoire cache.

La mémoire cache est invisible pour le programmeur, qui ne peut pas déceler celles-ci dans l'assembleur. Les accès mémoire se font de la même manière avec ou sans le cache. La raison à cela est que le cache intercepte les accès mémoire et y répond s'il en a la capacité. Par exemple, si le cache intercepte une lecture à une adresse et que le contenu de cette adresse est dans le cache, le cache va outrepasser la mémoire RAM et la donnée sera envoyée par le cache au lieu d'être lue en RAM. par contre, si un accès se fait à une adresse pour laquelle le cache n'a pas la donnée, alors l'accès mémoire sera effectué par la RAM de la même manière que si le cache n'était pas là.

Accès au cache

Les succès et défauts de caches

Tout accès mémoire est intercepté par le cache, qui vérifie si la donnée demandée est présente ou non dans le cache. Si la donnée voulue est présente dans le cache, on a un succès de cache (cache hit) et on accède à la donnée depuis le cache. Sinon, c'est un défaut de cache (cache miss) et on est obligé d’accéder à la RAM. Les défauts de cache peuvent avoir plusieurs origines. Tout ce qu'il faut savoir est que lorsque le processeur accède à une donnée ou une instruction pour la première fois, il la place dans la mémoire cache car elle a de bonnes chances d'être réutilisée prochainement. La raison à cela est qu'un programme a tendance à réutiliser les instructions et données qui ont été accédées dans le passé : c'est le principe de localité temporelle. Bien évidement, cela dépend du programme, de la façon dont celui-ci est programmé et accède à ses données et du traitement qu'il fait, mais c'est souvent vrai en général.

La première cause des défauts de cache est liée à la taille du cache. À force de charger des données/instructions dans le cache, le cache fini par être trop petit pour conserver les anciennes données. Le cache doit bien finir par faire de la place en supprimant les anciennes données, qui ont peu de chances d'être réutilisées. Ces anciennes données éliminées du cache peuvent cependant être accédées plus tard. Tout prochain accès à cette donnée mènera à un cache miss. C'est ce qu'on appelle un Capacity Cache Miss, ou encore défaut de capacité. Les seules solutions pour éviter cela consistent à augmenter la taille du cache ou à optimiser le programme exécuté (voir plus bas).

Une autre raison pour un défaut est donc la suivante. Lorsqu'on exécute à une instruction ou qu'on accède à donnée pour la première fois, celle-ci n'a pas encore été chargée dans le cache. Le défaut de cache est inévitable : ce genre de cache miss s'appelle un Cold Miss, ou encore un défaut à froid. De tels défauts sont presque impossibles à éliminer, sauf à utiliser des techniques de préchargement qui chargent à l'avance des données potentiellement utiles. Ces méthodes de préchargement se basent sur le principe de localité spatiale, à savoir le fait que les programmes ont tendance à accéder à des données proches en mémoire. Pour donner un exemple, les instructions d'un programme sont placées en mémoire dans l’ordre dans lequel on les exécute : la prochaine instruction à exécuter est souvent placée juste après l'instruction en cours (sauf avec les branchements). Quand on accède à une donnée ou une instruction, le cache peut précharger les données adjacentes pour en profiter. Nous parlerons de ces techniques de préchargement dans un chapitre dédié, vers la fin du cours.

Le fonctionnement du cache, vu du processeur

Vu du processeur, le cache prend en entrée toutes les informations nécessaires pour effectuer un accès mémoire : des signaux de commande, une adresse et la donnée à écrire si besoin. Tout cela est passé en entrée du cache, celui-ci répondant aux accès mémoire via divers bits de contrôles, que le processeur peut lire à souhait. Le cache fournit aussi la donnée à lire, pour les lectures, sur une sortie, connectée directement au bus mémoire/processeur. Globalement, le cache a une capacité limitée, mais il prend en entrée des adresses complètes. Par exemple, sur un processeur 64 bits, le cache prend en entrée des adresses de 64 bits (sauf si optimisations), même si le cache en question ne fait que quelques mébioctets.

Les caches sont souvent des mémoires multiports, surtout sur les processeurs récents. Les caches simple port sont rares, mêmes s'ils existent et ont existé par le passé. les caches double port sont eux plus fréquents, et ont généralement un port d'écriture séparé du port de lecture. Mais les caches récents ont plusieurs ports de lecture/écriture et sont capables de gérer plusieurs accès mémoire simultanés.

Les données présentes dans le cache sont (pré)chargées depuis la mémoire, ce qui fait que toute donnée dans le cache est la copie d'une donnée en mémoire RAM. Le cache doit faire la correspondance entre une donnée du cache et l'adresse mémoire correspondante. Du point de vue du fonctionnement, on peut voir le cache comme une sorte de table de correspondance, qui mémorise des données, chacune étant associée à son adresse mémoire. Le cache contient donc des paires adresse-ligne de cache qui lui permettent de faire le lien entre ligne de cache et adresse. Cela vaut du point de vue du processeur, le fonctionnement interne du cache étant quelque peu différent selon le cache. Il existe des caches dont le fonctionnement interne est bien celui d'une table de correspondance matérielle, d'autres qui sont beaucoup plus optimisés.

Fonctionnement simplifié d'une mémoire cache : les adresses sont dans la colonne de gauche, les données sont dans la colonne de droite. On voit qu'on envoie l'adresse au cache, que celui-ci répond en renvoyant la donnée associée.

La performance des mémoires caches

L'analyse de la performance des mémoires caches est plus riche pour celle des autres mémoires. Sa performance dépend de beaucoup de paramètres, mais on peut cependant citer les principaux. Les deux premiers sont tout bonnement sa latence et son débit, comme pour n'importe quelle autre mémoire. La latence est plus importante que son débit, car le processeur est généralement plus rapide que le cache et qu'il n'aime pas attendre. Mais le critère le plus important pour un cache est sa capacité à empêcher des accès mémoire, son efficacité. Plus les accès mémoire sont servis par le cache au lieu de la RAM, meilleures seront les performances. Pour résumer, la performance d'un cache est surtout caractérisée par deux métriques : le taux de défaut, qui correspond à l’efficacité du cache, et la latence du cache.

Le taux de succès/défaut

Le taux de succès (hit ratio) est un premier indicateur des performances du cache, mais un indicateur assez imparfait. C'est le pourcentage d'accès mémoire qui ne déclenchent pas de défaut de cache. Plus il est élevé, plus le processeur accède au cache à la place de la RAM et plus le cache est efficace. Certains chercheurs préfèrent utiliser le taux de défauts, à savoir le pourcentage d'accès mémoire qui entraînent un défaut de cache. Plus il est bas, meilleures sont les performances. Le taux de défaut est relié au taux de succès par l'équation $T_{\text{succes}}=1-T_{\text{defaut}}$. Par définition, il est égal à :

${\text{Taux de défauts de cache}}={\frac {\text{Nombre de défauts de cache}}{\text{Nombre d’accès mémoires}}}$

Plutôt que de comparer le nombre de défauts/succès de cache au nombre d'accès mémoire, il est aussi possible de diviser le nombre de défauts par le nombre total d'instructions. On obtient alors le taux de défauts/succès par instruction, une autre métrique utile. Par définition, elle est égale à :

${\text{Taux de défauts par instruction}}={\frac {\text{Nombre de défauts de cache}}{\text{Nombre d'instructions}}}={\text{Taux de défauts de cache}}\times {\frac {\text{Nombre d’accès mémoires}}{\text{Nombre d'instructions}}}$

Si certains défauts de cache sont inévitables quel que soit le cache, comme les défauts à froids, mentionnés plus haut, d'autres défauts peuvent être évités en augmentant la capacité du cache. C'est le cas des défauts de capacité qui sont causés par un accès à une donnée qui a été éliminée du cache faute de place. Plus le cache est gros, moins il a de chances d'être rempli, moins il doit rapatrier de données, plus son taux de succès augmente. Mais nous reviendrons sur le lien entre taille du cache et taux de défaut plus bas.

Le taux de succès ne dépend pas que du cache, mais aussi de la conception des programmes exécutés. Une bonne utilisation du cache (ainsi que de la mémoire virtuelle) repose sur le programmeur qui doit prendre en compte les principes de localités dès la conception de ses programmes. Par exemple, un programmeur peut parfaitement tenir compte du cache au niveau de son algorithme : on peut citer l'existence des algorithmes cache oblivious, qui sont conçus pour être optimaux quelle que soit la taille du cache. Ces algorithmes permettent le plus souvent de gros gains en performances dans la plupart des situations sur les architectures modernes. Le programmeur peut aussi choisir ses structures de données de manière à améliorer la localité. Par exemple, un tableau est une structure de donnée respectant le principe de localité spatiale, tandis qu'une liste chaînée ou un arbre n'en sont pas (bien qu'on puisse les implémenter de façon à limiter la casse). D'autres optimisations sont parfois possibles : par exemple, le sens de parcours d'un tableau multidimensionnel peut faire une grosse différence. Cela permet des gains très intéressants pouvant se mesurer avec des nombres à deux ou trois chiffres. Je vous recommande, si vous êtes programmeur, de vous renseigner le plus possible sur les optimisations de code ou algorithmiques qui concernent le cache : il vous suffira de chercher sur Google. Il y a une citation qui résume bien cela, prononcée par un certain Terje Mathisen. Si vous ne le connaissez pas, cet homme est un vieux programmeur (du temps durant lequel on codait encore en assembleur), grand gourou de l’optimisation, qui a notamment travaillé sur le moteur de Quake 3 Arena.

«
	Almost all programming can be viewed as an exercise in caching.
	»
	— Terje Mathisen

La latence moyenne d'un cache

Le temps mis pour lire ou écrire une donnée varie en présence d'un cache. Certaines lectures/écritures vont atterrir directement dans le cache (succès) tandis que d'autres devront aller chercher leur contenu en mémoire RAM (défaut de cache). Dans tous les cas, qu'il y ait défaut ou non, le cache sera consulté et mettra un certain temps à répondre, égal au temps de latence du cache. Tous les accès mémoires auront donc une durée au moins égale au temps de latence du cache, qui sera notée $T_{c}$.

En cas de succès, le cache aura effectué la lecture ou l'écriture, et aucune action supplémentaire n'est requise. Ce qui n'est pas le cas en cas de défaut : le processeur devra aller lire/écrire la donnée en RAM, ce qui prend un temps supplémentaire égal au temps de latence de la mémoire RAM. Un défaut ajoute donc un temps, une pénalité, à l'accès mémoire. Dans ce qui suivra, le temps d'accès à la RAM sera noté $T_{m}$. Fort de ces informations, nous pouvons calculer le temps de latence moyen d'un accès mémoire, qui est la somme du temps d'accès au cache (pour tous les accès mémoire), multiplié par le temps lié aux défauts. On a alors :

$T=T_{c}+{\text{Taux de défaut}}\times T_{m}$

On voit que plus le taux de succès est élevé, plus le temps de latence moyen sera bas, et inversement. Ce qui explique l'influence du taux de succès sur les performances du cache, influence assez importante sur les processeurs actuels. De nos jours, le temps que passe le processeur dans les défauts de cache devient de plus en plus un problème au fil du temps, et gérer correctement le cache est une nécessité, particulièrement sur les processeurs multi-cœurs.

Il faut dire que la différence de vitesse entre processeur et mémoire est tellement importante que les défauts de cache sont très lents : alors qu'un succès de cache va prendre entre 1 et 5 cycles d'horloge, un cache miss fera plus dans les 400-1000 cycles d'horloge. Tout ce temps sera du temps de perdu que le processeur aura du mal à mitiger. Autant dire que réduire les défauts de cache est beaucoup plus efficace que d'optimiser les calculs effectués par le processeur (erreur courante chez de nombreux programmeurs, notamment débutants).

L'impact de la taille du cache sur le taux de défaut et la latence

Il y a un lien entre taille du cache, taux de défaut, débit binaire et latence moyenne. Globalement, plus un cache est gros, plus il est lent. Simple application de la notion de hiérarchie mémoire vue il y a quelques chapitres. Les raisons à cela sont nombreuses, mais nous ne pouvons pas les aborder ici, car il faudrait que nous sachions comment fonctionne un cache et ce qu'il y a à l'intérieur, ce qui sera vu dans la suite du chapitre. Toujours est-il que la latence moyenne d'un cache assez gros est assez importante. De même, le débit binaire d'un cache diminue avec sa taille, mais dans une moindre mesure. Les petits caches ont donc un gros débit binaire et une faible latence, alors que c'est l'inverse pour les gros caches.

Une grande capacité de cache améliore le taux de succès, mais cela se fait au détriment de son temps de latence et de son débit, ce qui fait qu'il y a un compromis assez difficile à trouver entre taille du cache, latence et débit. Il peut arriver qu'augmenter la taille du cache augmente son temps d'accès au point d’entraîner une baisse de performance. Par exemple, les processeurs Nehalem d'Intel ont vus leurs performances dans certains jeux vidéos baisser de 2 à 3 %, malgré de nombreuses améliorations architecturales, parce que la latence du cache L1 avait augmentée de 2 cycles d'horloge.

Pour avoir une petite idée du compromis à faire, regardons la relation entre taille du cache et taux de défaut. Il existe une relation approximative entre ces deux variables, appelée la loi de puissance des défauts de cache. Elle donne le nombre total de défaut de cache en fonction de la taille du cache et de deux autres paramètres. Voici cette loi :

${\text{Taux de défauts de cache}}\approx K\times {\text{Taille du cache}}^{-\alpha }$, avec $K$ et $\alpha$ deux coefficients qui dépendent du programme exécuté.

Le coefficient $\alpha$ est généralement compris entre 0.3 et 0.7, guère plus, et varie suivant le programme exécuté. Précisons que cette loi ne marche que si le cache est assez petit par rapport aux données à utiliser. Pour un cache assez gros et des données très petites, la relation précédente est mise en défaut. Pour s'en rendre compte, il suffit d'étudier le cas extrême où toutes les données nécessaires tiennent dans le cache. Dans ce cas, il n'y a qu'un nombre fixe de défauts de cache : autant qu'il faut charger de données dans le cache. Le nombre de défauts de cache observé dans cette situation n'est autre que le coefficient $K$ de la situation précédente, mais il n'y a aucune dépendance entre taux de défaut et taille du cache.

L'origine de cette relation s'explique quand on regarde combien de fois chaque donnée est réutilisée lors de l’exécution d'un programme. La plupart des données finissent par être ré-accédées à un moment ou un autre et il se passe un certain temps entre deux accès à une même donnée. Sur la plupart des programmes, les observations montrent que beaucoup de réutilisations de données se font après un temps très court et qu'inversement, peu de ré-accès se font après un temps inter-accès long. Si on compte le nombre de réutilisation qui ont un temps inter-accès bien précis, on retrouve une loi de puissance identique à celle vue précédemment :

${\text{Nombre de réaccès avec un temps inter-accès égal à t}}\approx K\times t^{-\beta }$, avec t le temps moyen entre deux réutilisations.

Le coefficient $\beta$ est ici compris entre 1.7 et 1.3. De manière générale, les coefficients $\alpha$ et $\beta$ sont reliés par la relation $\alpha =1-\beta$, ce qui montre qu'il y a un lien entre les deux relations.

Précisons cependant que la loi de puissance précédente ne vaut pas pour tous les programmes informatiques, mais seulement pour la plupart d’entre eux. Il n'est pas rare de trouver quelques programmes pour lesquels les accès aux données sont relativement prédictibles et où une bonne optimisation du code fait que la loi de puissance précédente n'est pas valide.

La loi de puissance des défauts de cache peut se démontrer à partir de la relation précédente, sous certaines hypothèses. Si un suppose que le cache est assez petit par rapport aux données, alors les deux relations sont équivalentes. L'idée qui se cache derrière la démonstration est que si le temps entre deux accès à une donnée est trop long, alors la donnée accédée aura plus de chance d'être rapatriée en RAM, ce qui cause un défaut de cache. La chance de rapatriement dépend de la taille du cache, un cache plus gros peut conserver plus de données et a donc un temps avant rapatriement plus long.

Les lignes de cache et leurs tags

Du point de vue du processeur, les lectures et écritures se font mot mémoire par mot mémoire. Un processeur avec des entiers de 64 bits recoit des données de 64 bits de la part du cache, et y écrit des mots de 64 bits. Mais quand on regarde comment sont stockées les données à l'intérieur du cache, les choses sont différentes.

Les données sont mémorisées dans le cache par blocs de plusieurs bytes, d'environ 64 à 256 octets chacun, qui portent le nom de lignes de cache. Les lignes de cache sont l'unité de stockage que l'on trouve à l'intérieur du cache, mais elles servent aussi d'unité de transaction avec la mémoire RAM. Sur les caches actuels, on transfère les données entre le cache et la RAM ligne de cache par ligne de cache, dans la limite de la taille du bus mémoire. Mais d'autres caches plus anciens permettaient de faire des transferts plus fins. C’est-à-dire qu'on pouvait mettre à jour quelques octets dans une ligne de cache sans avoir à la recopier intégralement depuis ou dans la mémoire RAM.

En théorie, on pourrait imaginer des caches où les données sont stockées différemment, où l'unité serait le mot mémoire, par exemple. Par exemple, sur un processeur 64 bits, on aurait une ligne de cache de 64 bits. Cela aurait l'avantage de la simplicité : les transferts entre le processeur et la mémoire serait de même taille, l'intérieur du cache ressemblerait à son interface montrée au processeur. Mais cela aurait quelques défauts qui sont compensés par l'organisation en lignes de cache de grande taille.

Le premier avantage des lignes de cache est lié à la localité spatiale, la tendance qu'on les programmes à accéder à des données proches les unes des autres. Des accès mémoires consécutifs ont tendance à se faire à des adresses proches, qui ont de bonnes chances d'être dans la même ligne de cache. Et des accès consécutifs à une même ligne de cache sont plus rapides que des accès à deux lignes distinctes. Une autre raison est tout simplement que cela simplifie considérablement la circuiterie du cache. Pour une capacité identique, il vaut mieux avoir peu de lignes de cache assez grosses, que beaucoup de petites lignes de cache. La raison est que les circuits du cache, comme le décodeur, l'encodeur et autres, ont moins de sorties et sont donc plus simples.

L'alignement des lignes de cache

Les lignes de cache sont des blocs de plusieurs dizaines à centaines de bytes, dont la taille est presque toujours une puissance de deux. De plus, les lignes de cache sont alignées en mémoire. Nous avions déjà abordé la notion d'alignement mémoire dans un chapitre précédent, mais le concept d'alignement des lignes de cache est quelque peu différent. Quand nous avions parlé d'alignement auparavant, il s'agissait de l'alignement des données manipulées par le processeur, qui faisait partie du jeu d'instruction du processeur. Ici, nous parlons d'un alignement totalement différent, invisible pour le programmeur, sans lien avec le jeu d’instruction. Voyons de quoi il retourne.

Concrètement, cela veut dire que du point de vue du cache, la RAM est découpée en blocs qui font la même taille qu'une ligne de cache, aux positions prédéterminées, sans recouvrement entre les blocs. Par exemple, pour un cache dont les lignes de cache font 256 octets, le premier bloc est à l'adresse 0, le second est 256 octets plus loin, c'est à dire à l'adresse 256, le troisième à l'adresse 512, la quatrième à l'adresse 768, etc. Une ligne de cache de 256 octets contiendra une donnée provenant d'un bloc de RAM de 256 octets, dont l'adresse est systématiquement un multiple de 256. Il n'est pas possible qu'une ligne de cache contienne un bloc de 256 octets dont l'adresse du premier octet serait l'adresse 64, ou l'adresse 32, par exemple. En clair, les adresses de ces blocs sont des multiples de la taille de la ligne de cache, de la taille des blocs. Cela rappelle les contraintes d'alignement vues dans le chapitre "Le modèle mémoire : alignement et boutisme", mais appliquées aux lignes de cache.

L'alignement des lignes de cache a des conséquences pratiques pour la conception des caches. Notons qu'il est en théorie possible d'avoir des caches dont les lignes de cache ne sont pas alignées, mais cela poserait des problèmes majeurs. Il serait en effet possible qu'une donnée soit présente dans deux lignes de cache à la fois. Par exemple, prenons le cas où une ligne de cache de 256 commence à l'adresse 64 et une autre ligne de cache commence à l'adresse 0. L'adresse 128 serait dans les deux lignes de cache ! Et cela poserait des problèmes lors des lectures, mais encore plus lors des écritures. C'est pour éviter ce genre de problèmes que les lignes de cache sont alignées avec la mémoire RAM dans tous les caches existants.

L'alignement des lignes de cache est une chose que les programmeurs doivent parfois prendre en compte quand ils écrivent du code ultra-optimisé, destiné à des programmes demandant des performances extrêmes. Il arrive que les contraintes d'alignement posent des problèmes. Nous avions vu dans le chapitre sur le boutisme et l'alignement qu'il valait mieux gérer l'alignement des variables des structures de données, pour éviter les accès non-alignés avec le bus mémoire. La même chose est possible, mais pour l'alignement avec des lignes de cache. Typiquement, l'idéal est que, pour une structure de donnée, on puisse en mettre un nombre entier dans une ligne de cache. Ou alors, si la structure est vraiment grande, que celle-ci occupe un nombre entier de lignes de cache. Si ce n'est pas le cas, il y a un risque d'accès non-alignés, c'est à dire qu'une structure se retrouve à cheval sur deux lignes de cache, avec les défauts que cela implique.

Le tag d'une ligne de cache

Plus haut, nous avions dit que le cache mémorise, pour chaque ligne de cache, l'adresse RAM associée. Le cache contient donc des paires adresse-ligne de cache qui lui permettent de faire le lien entre ligne de cache et adresse. Mais du fait de l'organisation du cache en lignes de cache de grande taille, qui sont de plus alignées en mémoire, il faut nuancer cette affirmation. Le cache ne mémorise pas la totalité de l'adresse, ce qui serait inutile. L'alignement des lignes de cache en RAM fait que les bits de poids faible de l'adresse ne sont pas à prendre en compte pour l'association adresse-ligne de cache. Dans ces conditions, on mémorise seulement la partie utile de l'adresse mémoire correspondante, qui forme ce qu'on appelle le tag.

Le reste de l'adresse indique quelle est la position de la donnée dans la ligne de cache. Par exemple, prenons le cas où le processeur gère des nombres entiers de 64 bits (8 octets) et des lignes de cache de 128 octets : chaque ligne de cache contient donc 16 entiers. Si le processeur veut lire ou écrire un entier bien précis, il doit préciser sa place dans la ligne de cache. Et ce sont les bits de l'adresse mémoire non-inclus dans le cache qui permettent de faire ça. En clair, une adresse mémoire à lire/écrire est interprété par le cache comme la concaténation d'un tag et de la position de la donnée dans la ligne de cache correspondante.

Adressage d'un cache totalement associatif

Le cache est donc une grande table de correspondance entre tags et lignes de cache. Lors d'un accès mémoire, le cache extrait le tag de l'adresse à lire ou écrire, et le compare avec les tags de chaque ligne de cache. Si une ligne contient ce tag, alors c'est que cette ligne correspond à l'adresse, et c'est un défaut de cache sinon. Lors d'un succès de cache, la ligne de cache est lue depuis le cache et envoyée à un multiplexeur qui sélectionne la donnée à lire dans la ligne de cache. Le fonctionnement est similaire pour une écriture : la donnée à écrire passe dans un démultiplexeur, qui envoie la donnée au bon endroit dans la ligne de cache sélectionnée.

Lecture d'une donnée dans un cache CPU, organisé en lignes de cache.

Le contenu d'une ligne de cache

Dans ce qui va suivre, nous allons considérer que chaque ligne de cache mémorise son tag, les données de la ligne de cache proprement dit, et quelques bits de contrôle annexes qui varient suivant le cache considéré. L'usage du terme ligne de cache désignera soit un bloc de données copiées depuis la RAM d'une taille de 64/128/256/... octets, soit la concaténation de ces données avec le tag et des bits de contrôle. Les deux définitions ne sont pas équivalentes, mais l'usage a entériné cet abus de langage. Et il faut avouer que cela rend les explications du chapitre plus simples.

Tag d'une ligne de cache.

Sur certains caches assez anciens, on pouvait transférer les lignes de caches morceaux par morceaux. Ces caches avaient des lignes de cache divisées en sous-secteurs, ces sous-secteurs étant des morceaux de ligne de cache qu'on pouvait charger indépendamment les uns des autres (mais qui sont consécutifs en RAM). Chaque secteur avait ses propres bits de contrôle, mais le tag était commun à tous les secteurs.

Cache à secteurs.

L'associativité des caches et leur adressage implicite

Lorsqu'on souhaite accéder au cache, il faut trouver quelle est la ligne de cache dont le tag correspond à l'adresse demandée. On peut classifier les caches selon leur stratégie de recherche de la ligne correspondante en trois types de caches : totalement associatifs, directement adressés (direct mapped) et associatifs par voie.

Les caches totalement associatifs

Avec les caches totalement associatifs, toute donnée chargée depuis la mémoire peut être placée dans n'importe quelle ligne de cache, sans aucune restriction. Ces caches ont un taux de succès très élevé, quand on les compare aux autres caches.

Cache totalement associatif.

Concevoir un cache totalement associatif peut se faire de deux grandes manières différentes. La première consiste tout simplement à combiner une mémoire associative avec une mémoire RAM, en ajoutant éventuellement quelques circuits annexes. La mémoire associative mémorise les tags, alors que la mémoire RAM mémorise les données de la ligne de cache, éventuellement avec quelques bits de contrôle. La ligne de cache est stockée à une adresse A dans la mémoire RAM et son tag est stocké à la même adresse, mais dans la mémoire CAM. Ce faisant, quand on envoie le tag à la mémoire CAM, elle renvoie l'adresse de la ligne de cache dans la mémoire RAM. Cette adresse est alors envoyée directement sur le bus d'adresse de la RAM, et la lecture est effectuée automatiquement. Il faut ajouter quelques circuits annexes pour garantir que les écritures se passent correctement dans les deux mémoires, mais rien de bien terrible.

Cache fabriqué avec une mémoire associative et une RAM

Il est cependant possible d'optimiser un tel cache, en fusionnant la mémoire CAM et la mémoire RAM, afin d'éliminer des circuits redondants. Pour comprendre pourquoi, rappelons que les mémoires CAM sont composées d'un plan mémoire, d'un paquet de comparateurs et d'un encodeur. Quant à la mémoire RAM, elle est composée d'un décodeur connecté au plan mémoire. En mettant une CAM suivie d'une RAM, on a un encodeur dont l'entrée est envoyée à un décodeur.

Cache totalement associatif naif

Or, le décodeur réalise l'opération inverse de l'encodeur, ce qui fait que mettre les deux composants à la suite ne sert à rien. On peut donc retirer l'encodeur et le décodeur, et envoyer directement les résultats des comparateurs sur les entrées de commande du plan mémoire de la RAM.

Cache totalement associatif optimisé

Avec cette méthode, les circuits du cache ressemblent à ce qui illustré ci-dessous. Le tag est envoyé à chaque ligne de cache. Le tag envoyé est alors comparé avec le Tag contenu dans chaque ligne de cache, comme c'est le cas sur les mémoires associatives. Si une ligne de cache matche avec le tag envoyé en entrée, la ligne pour laquelle il y a eu une égalité est alors connectée sur les lignes de bit (bitlines). Cela est réalisé par un circuit commandé par le comparateur de la ligne de cache. Il ne reste plus qu'à sélectionner la portion de la ligne de cache qui nous intéresse, grâce à un paquet de multiplexeurs. Cela permet d'effectuer une lecture ou écriture, mais il faut aussi préciser si il y a eu un défaut de cache ou un succès. Un succès de cache a lieu quand au moins des comparaisons est positive, alors que c'est un défaut de cache sinon. En clair, détecter un succès de cache demande juste de connecter une porte OU à plusieurs entrées à tous les comparateurs.

Organisation générale d'un cache totalement associatif.

Les caches directement adressés

Les caches directement adressés peuvent être vus comme un cache totalement associatif auquel on aurait ajouté des restrictions assez drastiques. Plus haut, on a vu qu'un cache totalement adressé est équivalent à la combinaison d'une CAM avec une RAM. La mémoire CAM prend en entrée un Tag et traduit celui-ci en une adresse qui commande la mémoire RAM interne au cache. Dans ce qui suit, l'adresse interne au cache sera appelé l'indice pour éviter toute confusion.

Fonctionnement interne du cache, expliquée sous forme abstraite, en utilisant la notion d'indice interne au cache.

Les caches directement adressés cherchent à remplacer la mémoire CAM par un circuit combinatoire. Ce circuit traduit le Tag en indice, mais est beaucoup plus simple qu'une mémoire CAM. Mais qui dit circuit plus simple dit circuit plus limité. Un circuit combinatoire n'est pas aussi versatile que ce qui est permis avec une mémoire CAM. En conséquence, une restriction majeure apparait : toute adresse mémoire est associée dans une ligne de cache prédéfinie, toujours la même. L'association entre ligne de cache et adresse mémoire est faite par le circuit combinatoire, et ne peut pas changer.

Les concepteurs de caches s'arrangent pour que des adresses consécutives en mémoire RAM occupent des lignes de cache consécutives, par souci de simplicité. Tout se passe comme suit la mémoire RAM était découpés en blocs de la même taille que le cache. La première adresse du bloc est associée à la première ligne de cache (celle d'indice 0), la seconde adresse est associée à la seconde adresse du_ bloc, et ainsi de suite. Le tout est illustré ci-dessous.

Cache adressé directement.

Avec cette contrainte, le circuit de traduction de l'adresse en adresse mémoire pour la RAM interne au cache est drastiquement simplifié, et disparait même. Une partie de l'adresse mémoire sert à indiquer la position de la donnée dans le cache, le reste de l'adresse sert encode le tag et la position de la donnée dans le ligne de cache.

Adresse d'une ligne de cache sur un cache adressé directement.

Un cache directement adressé est conçu avec une RAM, un comparateur, et un paquet de multiplexeurs. En général, la mémoire RAM stocke les lignes de caches complète. Il arrive que l'on utilise deux mémoires RAM : une pour les tags et une pour les données, mais cette technique augmente le nombre de circuits et de portes logiques nécessaires, ce qui réduit la capacité du cache. L'index à lire/écrire est envoyé sur l'entrée d'adresse de la RAM, la RAM réagit en mettant la ligne de cache sur sa sortie de donnée. Sur cette sortie, un comparateur compare le tag de la ligne de cache lue avec le tag de l'adresse à lire ou écrire. On saura alors si on doit faire face à un défaut de cache. Ensuite, un multiplexeur récupère la donnée à lire/écrire.

Cache directement adressé.

L'accès à un cache directement adressé a l'avantage d'être très rapide vu qu'il suffit de vérifier une seule ligne de cache : celle prédéfinie. Mais ces caches ne sont cependant pas sans défauts. Vu que le cache est plus petit que la mémoire, certaines adresses mémoires se partagent la même ligne de cache. Si le processeur a besoin d’accéder fréquemment à ces adresses, chaque accès à une adresse supprimera l'autre du cache : tout accès à l'ancienne adresse se soldera par un défaut de cache. Ce genre de défauts de cache causés par le fait que deux adresses mémoires ne peuvent utiliser la même ligne de cache s'appelle un défaut par conflit (conflict miss). Les défauts par conflit n'existent pas sur les caches totalement associatifs. En conséquence, le taux de succès des caches directement adressés est assez faible comparé aux autres caches.

Exemple de Conflict Miss.

Les caches associatifs par voie

Les caches associatifs par voie sont un compromis entre les caches directement adressés et les caches totalement associatifs. Pour simplifier, ces caches sont composés de plusieurs caches directement adressés accessibles en parallèle, chaque cache/RAM étant appelé une voie. Avec ces caches, toute adresse mémoire en RAM est associée à une ligne de cache dans chaque voie.

Cache associatif par voie.

Le schéma ci-dessous compare un cache directement adressé et un cache associatif à deux voies. On voit que chaque adresse est associée à une ligne de cache bien précise avec un cache directement dressé, et à deux lignes de cache avec un cache associatif à deux voies. L'adresse sera associée à 4 lignes de cache sur un cache associatif à 4 voies, à 8 lignes pour un cache à 8 voies, etc. L'ensemble des lignes de cache associées à une adresse est appelé un ensemble.

Comparaison entre un cache directement adressé et un cache associatif à deux voies.

Sur ces caches, toute adresse est découpée en trois parties : un tag, un index, et un décalage, comme sur les caches directement adressés. Comme vous pouvez le voir, l'organisation est identique à celle d'un cache totalement associatif, à part que chaque ensemble tag-ligne de cache est remplacé par une mémoire RAM qui en contient plusieurs.

Implémentation d'un cache associatif par voie.

Le risque de conflits d'accès au cache est donc réduit sur un cache associatif à plusieurs voies, et il est d'autant plus réduit que le cache a de voies. Par contre, leur conception interne fait qu'ils ont un temps d'accès légèrement élevé que les caches directement adressés. Les caches associatifs par voie ont donc un taux de succès et un temps d'accès intermédiaire, situé entre les caches directement adressés et totalement associatifs. Ils sont une sorte de compromis entre réduction des défaut par conflits d'accès au cache et temps d'accès, et complexité des circuits.

Les caches pseudo-associatifs

Les caches pseudo-associatifs sont identiques aux caches associatifs par voie, si ce n'est qu'ils vérifient chaque voie une par une. Le temps d'accès dans le meilleur des cas est plus faible pour les caches pseudo-associatifs, mais le pire des cas teste tous les caches avant de tomber sur le bon. Les performances sont donc réduites, mais la consommation énergétique est meilleure, vu qu'on ne vérifie pas forcément toutes les voies.

Les caches skew associative

Vous aurez remarqué que dans une voie, les lignes sont accédées en adressage direct : les défauts par conflit sont possibles sur un cache associatif par voie. Pour éviter cela, certains chercheurs ont créé des caches skew associative (ou associatifs à biais). Pour faire simple, les index des lignes de cache subissent un petit traitement avant d'être utilisés. Le traitement en question est différent suivant la voie de destination, histoire que deux adresses mémoires avec des index identiques donnent des index différents après traitement. Le traitement en question est souvent une permutation des bits de l'index, qui est différente suivant la voie prise, ou un simple XOR avec un nombre qui dépend de la voie.

Implémentation d'un cache skew associative.

La prédiction de voie

Pour réduire le temps d'accès de ces caches, certains chercheurs ont inventé la prédiction de voie, qui consiste à faire des paris sur la prochaine voie accédée. Au lieu d'attendre que les comparaisons de tags donnent leur résultat, le processeur sélectionne automatiquement une voie et configure les multiplexeurs à l'avance. Si le processeur ne se trompe pas, le processeur accède à la donnée un à deux cycles plus tôt que prévu. S'il se trompe, le processeur annule la lecture effectuée en avance et recommence en allant chercher la donnée dans la bonne voie. Cette technique permet de mettre en veille les voies sur lesquels le processeur n'a pas parié, ce qui permet de diminuer la consommation énergétique du processeur. C'est plus efficace que d'aller lire plusieurs données dans des voies différentes et de n'en garder qu'une.

Prédire quelle voie sera la bonne est assez simple. En vertu du principe de localité, les accès futurs ont des chances de tomber dans les voies les plus fréquemment utilisées ou dans celle plus récemment utilisée. Il suffit de retenir la voie la plus récemment accédée dans un registre, qui sera utilisée comme prédiction. Pour vérifier que la prédiction est correcte, il suffit de comparer le registre et le résultat obtenu après vérification des tags.

Cependant, on peut complexifier l'implémentation pour prendre en compte l'adresse à lire/écrire, l'instruction à l'origine de l'accès mémoire ou tout autre paramètre utile. Par exemple, des instructions différentes ont tendance à aller chercher leurs données dans des ensembles différents et la voie à choisir n'est pas la même. Pour cela, il suffit d'utiliser un cache pour stocker la correspondance instruction - voie. Pour plus de simplicité, la mémoire cache des prédictions est parfois remplacée par une RAM, qui est adressée :

• soit par le program counter de l'instruction à l'origine de l'accès (en réalité, seulement quelques bits de poids faible de l'adresse) ;
• soit par l'adresse à accéder (là encore, quelques bits de poids faible) ;
• soit (pour les modes d'adressage qui utilisent un registre de base et un décalage) par un XOR entre les bits de poids faible de l'adresse de base et le décalage ;
• soit par autre chose.

L'adressage physique ou logique des caches

Le cache utilise les adresses à lire/écrire pour déterminer s'il a une copie de la donnée en son sein. Mais l’interaction entre caches et mémoire virtuelle donne lieu à un petit problème : l'adresse utilisée est-elle une adresse virtuelle/logique ou physique ? La réponse varie suivant le processeur : certains caches utilisent l'adresse virtuelle, tandis que d'autres prennent l'adresse physique. On parle de cache virtuellement tagué dans le premier cas et de cache physiquement tagué dans le second.

Cache tagué virtuellement.

Cache tagué physiquement.

L'accès à un cache physiquement/virtuellement tagué

La manière d'accéder à un cache dépend de s'il est virtuellement ou physiquement tagué. Il faut utiliser l'adresse virtuelle pour les premiers, physique pour les seconds.

Avec un cache virtuellement tagué, l'adresse logique peut être envoyée directement au cache. La MMU ne traduit les adresses que s'il faut accéder à la mémoire RAM. Ces caches sont donc plus rapides.

Avec un cache physiquement tagué, le processeur doit traduire l'adresse logique en adresse physique dans la MMU, avant d'accéder au cache. La traduction d'adresse se fait soit en accédant à une table des pages en mémoire RAM, soit en accédant à un cache spécifiquement dédié à accélérer la traduction d'adresse, la TLB (Translation Lookaside Buffer). Dans la quasi-totalité des cas, la traduction d'adresse passe par la TLB, ce qui fait qu'elle est raisonnablement rapide. Toujours est-il que chaque accès au cache demande d'accéder à la TLB et de faire la traduction d'adresse avant d'accéder au cache. L'accès est donc plus lent que sur les caches virtuellement tagués, où les accès sont plus directs.

Cache tagué virtuellement versus physiquement tagué.

Les défauts des caches virtuellement tagués

Les caches physiquement tagués sont moins rapides que les caches virtuellement adressés. Pourtant, les caches virtuellement tagués sont peu fréquents sur les processeurs modernes. Et la raison est assez intéressante : c'est une question d'adresses homonymes et synonymes.

Les droits d'accès doivent être vérifiés lors d'un accès au cache

Un premier problème est que la protection mémoire est compliquée avec de tels caches. Rappelons que certaines portions de mémoire sont accessibles seulement en lecture, ou sont interdites en écriture, sont inexécutables, etc. Ces droits d'accès sont gérés par la MMU, qui vérifie pour chaque accès mémoire que l'accès est autorisé. En bypassant la MMU, l'accès au cache virtuellement tagué ne permet pas de faire ces vérifications. Il est possible de charger une donnée en lecture seule dans le cache, mais d'y faire des accès en écriture pour les accès ultérieurs.

Les solutions à cela sont multiples. La première consiste à consulter la MMU en parallèle de l'accès au cache. L'accès au cache est alors réalisé de manière spéculative, et est ensuite confirmé/annulé une fois que la MMU a rendu son verdict. Les performances du cache restent alors les mêmes : l'accès à la MMU se fait en parallèle de l'accès au cache, pas avant. Une autre solution est d'ajouter les droits d'accès en question dans la ligne de cache, dans les bits de contrôle situés après le Tag. Chaque accès au cache récupère ces bits de contrôle et vérifie si l'accès est autorisé. L'inconvénient est que les lignes de cache deviennent plus longues, les droits d'accès sont dupliqués entre MMU et cache. Mais si le budget en transistor suit, ce n'est rien d'insurmontable.

Les adresses homonymes perturbent la gestion du cache

Pour rappel, une adresse logique homonyme correspond à plusieurs adresses physiques différentes. Elles surviennent quand chaque programme a son propre espace d'adressage. Dans ce cas, une adresse logique correspondra à une adresse physique différente par programme. La correspondance adresse logique - physique dépend alors du programme. Les caches doivent gérer ces adresses homonymes, et faire en sorte que la lecture/écriture d'une adresse homonyme se fasse à la bonne adresse physique, dans la bonne ligne de cache. Et autant un cache physiquement tagué n'a aucun problème avec ça, vu qu'il ne gére que des adresses physiques, les caches virtuellement tagués doivent gérer de telles adresses.

Pour cela, il existe deux grandes méthodes. La première méthode utilise les identifiants de processus, qui sont pour rappel un numéro associé à chaque espace d'adressage. Chaque ligne de cache contient le numéro de l'espace d'adressage associé, dans son tag. Lors de chaque accès mémoire, l'ID du registre est comparé à l'ID de la ligne de cache accédée, pour vérifier que l'accès mémoire accède à la bonne donnée. Cette méthode n'est pas très économe en termes de transistors.

Une autre solution consiste à vider les caches en changeant de programme : leur contenu est considéré comme invalide, les caches sont remis à zéro. Lorsque le système d'exploitation déclenche une commutation de contexte, à savoir qu'il change le programme en cours d'exécution, le processeur invalide tous les caches du processeur. Les interruptions font la même chose, elles invalident tous les caches du processeur. Mais le défaut est que non seulement les caches doivent être invalidés, mais aussi d'autres structures du processeur, que nous n'avons pas encore vu à ce point du cours.

Les adresses synonymes perturbent aussi la gestion du cache

La gestion des adresses synonymes est aussi un gros problème sur les caches virtuellement tagués. Pour rappel, il s'agit du cas où des adresses logiques différentes pointent vers la même adresse physique. Typiquement, quand deux programmes se partagent un morceau de mémoire, ce morceau correspondra à des adresses synonymes dans les deux espaces d'adressage. Mais il arrive que l'on ait des adresses synonymes dans le même espace d'adressage, ce n'est pas si rare !

Autant les adresses synonymes ne posent aucun problème avec les caches physiquement tagués, ce n'est pas le cas avec les caches virtuellement adressés. Sur ces caches, deux adresses logiques synonymes vont tomber dans deux lignes de cache différentes. Corriger ce problème demande d'ajouter des circuits annexes pour détecter les adresses synonymes, qui sont vraiment complexes et ont un cout en termes de performance. Aussi, les caches virtuellement tagués sont très peu utilisés sur les processeurs modernes.

Les caches virtuellement adressés, mais physiquement tagués

Si les caches physiquement et virtuellement tagués ont des défauts, il existe un intermédiaire qui est un bon compromis entre ces deux extrêmes. Il s'agit des caches virtuellement adressés - physiquement tagués, aussi appelés caches pseudo-virtuels. Pour comprendre comment ils fonctionnent, précisons que ces caches sont soit des caches direct-mapped, soit des caches associatifs par voie (composés de plusieurs RAM direct-mapped accédées en parallèle, plusieurs voies).

L'accès à ce genre de cache se fait en deux temps : on accède à un ou plusieurs RAM direct-mapped et on vérifie ensuite les Tags pour sélectionner la bonne voie. Sur les caches direct-mapped, on n'a qu'une seule RAM direct-mapped. Sur les caches associatifs, on a plusieurs RAM direct-mapped, appelées des voies, qui sont accédées en parallèle. L'accès se fait donc en deux étapes : adresser les RAM direct-mapped avec un indice, vérifier les tags avec le reste de l'adresse.

Une autre chose à rappeler est que l'adresse logique est composée de deux parties : un numéro de page logique qui indique dans quel page se situe l'adresse, un décalage/offset qui indique la position de l'adresse dans la page. La traduction d'adresse transforme le numéro de page logique en numéro de page physique, mais laisse le décalage intouché. L'idée est d'utiliser le décalage pour adresser les RAM avec le décalage, tandis que le numéro de page sert de tag. Le décalage est découpé en deux lors de l'accès au cache : les bits de poids fort forment l'indice (l'adresse envoyée à la voie), les bits de poids faible donnent la position de l'adresse dans la ligne de cache.

L'idée est d'utiliser un numéro de page physique pour les tags, mais d'adresser les voies avec le décalage logique. Les deux servent à des instants différents : vérification des tags pour l'adresse physique, accès aux voies pour l'adresse logique. Ainsi, le problème des adresses synonymes ou homonymes est résolu par l'utilisation de l'adresse physique pour les tags. Par contre, l'accès au cache est plus rapide, car on utilise l'adresse logique pour la première étape. Le processeur accède à la TLB et récupère l'adresse physique pendant que l'on adresse les voies, les deux sont faits en parallèle, ce qui fait que tout se passe comme si l'accès à la TLB était gratuit. La TLB étant assez rapide comparé au cache, l'adresse physique est disponible quand on doit faire la comparaison avec les tags.

Adressage pseudo virtuel des caches.

Il s'agit d'un excellent compromis entre performance et correction des problèmes des adresses synonymes/homonymes. Tous les caches des processeurs haute performance utilisent cette méthode, au moins pour leurs caches L1. Les caches L2 tendent à utiliser des caches physiquement adressés, pour lesquels la latence d'accès est suffisante pour qu'on accède à la TLB en amont. La raison est assez simple à expliquer, elle provient d'une contrainte assez précise sur le calcul de l'indice.

La conséquence est qu'un cache direct-mapped ne peut pas dépasser la taille d'une page, soit 4 kibioctets sur les ordinateurs actuels. Sur les caches associatifs, on peut dépasser cette limite en augmentant le nombre de voies, mais la taille maximale d'une voie reste celle d'une page. Cette contrainte n'est pas trop grave sur les caches de petite taille, dont les caches L1. La plupart d'entre eux ont trouvé un compromis idéal avec moins d'une dizaine de voies par cache, chacun de 4 kibioctets, ce qui donne des caches allant de 16 à 64 kibioctets, soit entre 4 et 16 voies. Par contre, un cache de grande taille doit utiliser un grand nombre de voies, ce qui est peu pratique. Aussi, cette technique de caches pseudo-virtuels n'est pas toujours appliquée sur les caches L2, qui sont physiquement adressés. Il faut dire qu'on accède au cache L2 lors d'un défaut dans le cache L1, et l'adresse physique est disponible à ce moment-là, elle a déjà été récupérée lors de l'accès au cache L1. On peut donc l'utiliser pour adresser le cache L2 sans perte de performance.

L'invalidation des caches

Plus haut, nous avons vu que les caches doivent parfois être invalidés, à savoir qu'ils doivent être réinitialisés et leur contenu effacé. Dans cette section, nous allons voir quelles sont les circonstances qui peuvent mener à une invalidation du cache, et voir comment l'invalidation est mise en œuvre.

Les déclencheurs : cohérence des caches, multi-programmation

Invalider le cache est utile dans deux situations : soit lors d'un changement de processus, soit quand survient un défaut de cohérence des caches.

Le cas d'un changement de processus a été vu plus haut. Notez qu'il demande cependant certaines conditions. Déjà, il n'est pas nécessaire sur les caches physiquement tagués. Seuls les caches totalement ou partiellement tagués ont besoin d'être invalidés lors d'un changement de processus. De plus, il faut que le cache n'intègre pas d'optimisations permettant d'éviter les invalidations. Si le cache intègre les identifiants de processus, l'invalidation n'est strictement pas nécessaire.

Les défauts de cohérence des caches sont eux plus fréquents. Il s'agit de situations où un tiers écrit en mémoire RAM, le tiers étant soit un autre processeur, soit un périphérique qui fait un transfert DMA, soit autre chose qui n'est pas le processeur détenteur du cache. Vu que l'écriture n'est pas du fait du processeur, elle ne passe pas par l'intermédiaire du cache. Si la donnée modifiée est copiée dans le cache, le cache aura une donnée périmée, alors que la mémoire aura une donnée mise à jour.

De telles situations surviennent sur les architectures multiprocesseurs ou multicœurs. Par exemple, prenons deux processeurs qui ont chacun une copie d'une donnée dans leur cache. Si un processeur modifie sa copie de la donnée, l'autre ne sera pas mise à jour. L'autre processeur manipule donc une donnée périmée : il n'y a pas cohérence des caches. Résoudre de telles situations requière des mécanismes de cohérence des caches assez complexes, qui seront vus dans le chapitre dédié aux architectures multiprocesseurs et multicœurs.

Cohérence des caches

De telles situations d'incohérence surviennent aussi lors des transferts DMA, comme nous l'avions vu dans le chapitre dédié. Nous avions vu qu'il y avait alors deux solutions pour résoudre ces problèmes. La première est d'interdire la mise en cache de certaines portions de mémoire, dédiées aux transferts DMA. L'autre solution est d'invalider les caches après un transfert DMA.

Cohérence des caches avec DMA.

L'implémentation de l'invalidation des caches

Invalider tous les caches du processeur est une opération assez simple à implémenter. Contrairement à ce qu'on pourrait penser, le cache n'est pas vidé ou effacé lors d'une invalidation, la réalité est tout autre. Pour chaque ligne de cache, on ajoute un bit Valid, qui indique si la ligne de cache a un contenu valide ou non : 1 pour une ligne de cache valide, 0 pour du contenu invalide. Lorsqu'on invalide une ligne de cache, son bit Valid est juste mis à 0.

Le cache peut être invalidé complétement, ce qui signifie que toutes ses lignes de cache sont invalidées. Mais il existe des situations où seules quelques lignes de cache doivent être invalidées, voire une seule. L'invalidation est généralement réalisée par une instruction machine dédiée. L'instruction a plusieurs "modes d'adressages", qui permettent de préciser la ligne de cache à invalider, ou invalider tout le cache. Il est possible de n'invalider que le cache L1, voire le cache L2.

Le remplacement des lignes de cache

Lorsqu'un cache est rempli et qu'on charge une nouvelle donnée dedans, il faut faire de la place pour cette dernière. Dans le cas d'un cache directement adressé, il n'y a rien à faire vu que la ligne de cache à évincer est déterminée lors de la conception du cache. Mais pour les autres caches, la donnée peut aller dans n'importe quelle ligne ou voie. Or, le choix des données à rapatrier en RAM doit être le plus judicieux possible : on doit virer de préférence des données inutiles. Rapatrier une donnée qui sera surement utilisée sous peu est inutile, et il vaudrait mieux supprimer des données qui ne serviront plus ou alors dans longtemps.

Il existe différents algorithmes spécialement dédiés à résoudre ce problème efficacement, directement câblés dans les unités de gestion du cache. Certains sont vraiment très complexes, aussi je vais vous présenter quelques algorithmes particulièrement simples.

Mais avant de voir ces algorithmes, il faut absolument que je vous parle d'une chose très importante. Quel que soit l'algorithme en question, il choisit la ligne de cache à évincer et recopie son contenu dans la RAM. Ce qui demande d'identifier et de sélectionner une ligne de cache parmi toutes les autres. Pour cela, le circuit de remplacement attribue une adresse chaque ligne de cache ! Vous avez bien vu : chaque ligne de cache est numérotée par une adresse, interne au cache.

Le remplacement aléatoire

Premier algorithme : la donnée effacée du cache est choisie au hasard ! C'est contre-intuitif, mais cet algorithme donne des résultats assez honorables, en plus d'utiliser très peu de portes logiques (un générateur de nombres pseudo-aléatoire est un circuit assez simple). Généralement, les défauts de cache sont séparés par un nombre assez important et irrégulier de cycles d'horloge. Dans ces conditions, cette technique donne un bon résultat.

FIFO : first in, first out

Avec l'algorithme FIFO, la donnée effacée du cache est la plus ancienne, celle chargée dans le cache avant les autres. Cet algorithme est très simple à implémenter en circuit, concevoir une mémoire de type FIFO n'étant pas très compliqué, comme on l’a vu dans le chapitre dédié à ce type de mémoires. Et on peut dire que dans le cas d'un cache, l'implémentation est encore plus simple et se contente d'un seul registre/compteur. Typiquement, il suffit d'ajouter un registre qui mémorise où se situe la donnée la plus récente. Toute insertion d'une nouvelle donnée se fait à l'adresse suivante, ce qui demande juste d'incrémenter le registre avant d'utiliser son contenu pour l'accès mémoire.

Algorithme FIFO de remplacement des lignes de cache.

Cet algorithme possède une petite particularité sur les caches associatifs par voie : en augmentant le nombre d'ensembles, les performances peuvent se dégrader : c'est ce qu'on appelle l'anomalie de Bélády.

MRU : most recently used

Avec l'algorithme MRU, la donnée remplacée est celle qui a été utilisée le plus récemment. Cet algorithme s'implémente simplement avec un registre, dans lequel on place le numéro de la dernière ligne de cache utilisée.

Cet algorithme de remplacement est très utile quand un programme traverse des tableaux du premier élément jusqu'au dernier : les données du tableau sont rarement réutilisées, rendant le cache inutile. Il est prouvé que dans ces conditions, l'algorithme MRU est optimal. Mais dans toutes les autres conditions, cet algorithme a des performances assez misérables.

LFU : least frequently used

Avec l'algorithme LFU, la donnée supprimée est celle qui est utilisée le moins fréquemment. Cet algorithme s'implémente en associant un compteur à chaque ligne de cache, qui est incrémenté à chaque accès mémoire. La ligne la moins récemment utilisée est celle dont le compteur associé a la plus petite valeur. Implémenter cet algorithme prend pas mal de transistors, car il faut rajouter autant de compteurs qu'il y a de lignes de cache, en plus d'un circuit pour comparer les compteurs et d'un encodeur.

Algorithme LFU de remplacement des lignes de cache

LRU : least recently used

Avec l'algorithme LRU, la donnée remplacée est celle qui a été utilisée le moins récemment. Cet algorithme se base sur le principe de localité temporelle, qui stipule qu'une donnée accédée récemment a de fortes chances d'être réutilisée dans un futur proche. Et inversement, la donnée la moins récemment utilisée du cache est celle qui a le plus de chance de ne servir à rien dans le futur. Autant la supprimer en priorité pour faire de la place à des données potentiellement utiles.

Implémenter l'algorithme LRU peut se faire de différentes manières, qui ont pour point commun d'enregistrer les accès au cache pour en déduire la ligne la moins récemment accédée. La manière la plus simple demande d'utiliser un compteur pour chaque ligne de mémoire cache, un peu comme le LFU. La différence avec le LFU est que le compteur n'est pas incrémenté lors d'un accès mémoire. À la place, ce compteur est incrémenté régulièrement, chaque incrémentation ayant lieu en même temps pour tous les compteurs. Quand un bloc est chargé dans le cache, ce compteur est mis à zéro. Quand une ligne de cache doit être remplacée, un circuit va vérifier la valeur de tous les compteurs : la ligne LRU (la moins récemment utilisée), est celle dont le compteur a la valeur la plus haute. Le circuit est composé d'un paquet de comparateurs, et d'un encodeur, comme pour l'agorithme LFU.

Les approximations du LRU

Implémenter le LRU demande un nombre de transistors proportionnel au carré du nombre de lignes de cache. Autant dire que le LRU devient impraticable sur de gros caches. Ce qui fait que les processeurs modernes implémentent des variantes du LRU, moins couteuses en transistors, qui donnent un résultat approximativement semblable au LRU. En clair, ils ne sélectionnent pas toujours la ligne de cache la moins récemment utilisée, mais une ligne de cache parmi les moins récemment utilisées. Ce n'est pas un problème si grave que cela car les lignes les moins récemment utilisées ont toutes assez peu de chance d'être utilisées dans le futur. Entre choisir de remplacer une ligne qui a 0,5 % de chances d'être utilisée dans le futur et une autre qui a une chance de seulement 1 %, la différence est négligeable en termes de taux de succès. Mais les gains en termes de circuits ou de temps d'accès au cache de ces algorithmes sont très intéressants.

L'algorithme le plus simple consiste à couper le cache (ou chaque voie s'il est associatif) en plusieurs sections. L'algorithme détermine la section la moins récemment utilisée, avant de choisir aléatoirement une ligne de cache dans cette section. Pour implémenter cet algorithme, il nous suffit d'un registre qui mémorise le morceau le moins récemment utilisé, et d'un circuit qui choisit aléatoirement une ligne de cache. Cette technique s'adapte particulièrement bien avec des caches associatifs à voies : il suffit d'utiliser autant de morceaux que de voies.

Autre algorithme, un peu plus efficace : le pseudo-LRU de type M. Cet algorithme attribue un bit à chaque ligne de cache, bit qui sert à indiquer de façon approximative si la ligne de cache associée est une candidate pour un remplacement ou non. Il vaut 1 si la ligne n'est pas une candidate pour un remplacement et zéro sinon. Le bit est mis à 1 lorsque la ligne de cache associée est lue ou écrite. Évidemment, au fil du temps, toutes les lignes du cache finiront par avoir leur bit à 1. Lorsque cela arrive, l'algorithme remet tous les bits à zéro, sauf pour la dernière ligne de cache accédée. L'idée derrière cet algorithme est d'encercler la ligne de cache la moins récemment utilisée au fur et à mesure des accès. L'encerclement commence lorsque l'on remet tous les bits associés aux lignes de cache à 0, sauf pour la ligne accédée en dernier. Au fur et à mesure des accès, l'étau se resserre autour de la ligne de cache la moins récemment utilisée. Après un nombre suffisant d'accès, l'algorithme donne une estimation particulièrement fiable. Et comme les remplacements de lignes de cache sont rares comparés aux accès aux lignes, cet algorithme finit par donner une bonne estimation avant qu'on ait besoin d'effectuer un remplacement.

Le dernier algorithme d'approximation, le PLURt, se base sur ce qu'on appelle un arbre de décision. Il a besoin de n − 1 bits pour déterminer la ligne LRU. Ces bits doivent être organisés en arbre, comme illustré plus bas. Chacun de ces bits sert à dire : le LRU est à ma droite ou à ma gauche : il est à gauche si je vaux 0, et à droite si je vaux 1. Trouver le LRU se fait en traversant cet arbre, et en interprétant les bits un par un. Au fur et à mesure des lectures, les bits sont mis à jour dans cet arbre, et pointent plus ou moins bien sur le LRU. La mise à jour des bits s'effectue lors des lectures et écritures : quand une ligne est lue ou écrite, elle n'est pas la ligne LRU. Pour l'indiquer, les bits à 1 qui pointent vers la ligne de cache sont mis à 0 lors de la lecture ou écriture.

Organisation des bits avec l'algorithme PLURt.

Ligne de cache pointée par les bits de l'algorithme.

LRU amélioré

L'algorithme LRU, ainsi que ses variantes approximatives, sont très efficaces tant que le programme respecte relativement bien la localité temporelle. Par contre, Le LRU se comporte assez mal dans les circonstances ou la localité temporelle est mauvaise mais où la localité spatiale est respectée, le cas le plus emblématique étant le parcours d'un tableau. Pour résoudre ce problème, des variantes du LRU existent.

Une variante très connue, l'algorithme 2Q, utilise deux caches : un cache FIFO pour les données accédées une seule fois et un second cache LRU. Évidemment, les données lues une seconde fois sont migrées du cache FIFO vers le cache LRU, ce qui n'est pas très pratique. Les processeurs n'utilisent donc pas cette technique, mais celle-ci est utilisée dans les caches de disque dur.

D'autres variantes du LRU combinent plusieurs algorithmes à la fois et vont choisir lequel de ces algorithmes est le plus adapté à la situation. Notre cache pourra ainsi détecter s’il vaut mieux utiliser du MRU, du LRU, ou du LFU suivant la situation.

Les caches Write-back et write-through

Les écritures se font à une adresse mémoire bien précise, qui peut ou non être chargée dans le cache. Si la donnée à écrire est chargée dans le cache, elle est modifiée directement dans le cache, mais elle ne l'est pas forcément en mémoire RAM. Suivant le processeur, les écritures sont ou non propagées en mémoire RAM. Il existe deux stratégies d'écritures, appelées respectivement le write-back et le write-through.

Avec un cache write-back, si la donnée à mettre à jour est présente dans le cache, on écrit dans celui-ci sans écrire dans la mémoire RAM. Dans ces conditions, une donnée n'est enregistrée en mémoire que si celle-ci quitte le cache, ce qui évite de nombreuses écritures mémoires inutiles.

Cache write-through.

Avec les caches Write-Through, toute écriture dans le cache est propagée en RAM. Cette stratégie augmente le nombre d'écritures dans la mémoire RAM, ce qui peut saturer le bus reliant le processeur à la mémoire. Les performances de ces caches sont donc légèrement moins bonnes que pour les caches write back. Par contre, ils sont utiles dans les architectures avec plusieurs processeurs, comme nous le verrons dans les chapitres sur les architectures multiprocesseurs.

Cache write-back.

Les caches Write-through

Sans optimisation particulière, on ne peut écrire dans un cache write-through pendant qu'une écriture en RAM a lieu en même temps : cela forcerait à effectuer deux écritures simultanées, en comptant celle imposée par l'écriture dans le cache.

Pour éviter cela, certains caches write-through intègrent un tampon d’écriture, qui sert de file d'attente pour les écritures en RAM. C'est une mémoire FIFO dans laquelle on place temporairement les données à écrire en RAM, où elles attendent en attendant que la RAM soit libre. Grâce à lui, le processeur peut écrire dans un cache même si d'autres écritures sont en attente dans le tampon d'écriture. Par souci d'efficacité, des écritures à la même adresse en attente dans le tampon d’écriture sont fusionnées en une seule. Cela fait un peu de place dans le tampon d’écriture, et lui permet d'accumuler plus d'écritures avant de devoir bloquer le cache. Il est aussi possible de fusionner des écritures à adresses consécutives de la mémoire en une seule écriture en rafales. Dans les deux cas, on parle de combinaison d'écriture.

Mais la technique du tampon d'écriture a cependant un léger défaut qui se manifeste dans une situation bien précise : quand le processeur veut lire une donnée en attente dans le tampon d’écriture. La première manière de gérer cette situation est de mettre en attente la lecture tant que la donnée n'a pas été écrite en mémoire RAM. On peut aussi lire la donnée directement dans le tampon d'écriture, cette optimisation portant le nom de store-to-load forwading. Dans tous les cas, il faut détecter le cas où une lecture accède à une donnée dans le tampon d'écriture. À chaque lecture, l'adresse à lire est envoyée au tampon d'écriture, qui vérifie si une écriture en attente se fait à cette adresse. Pour cela, le tampon d’écriture doit être un cache, dont chaque entrée mémorise une écriture. Chaque ligne de cache contient la donnée à écrire, et le tag de la ligne de cache contient l'adresse où écrire la donnée. Notons que cache d'écriture a une politique de remplacement de type FIFO, le tampon d'écriture non-optimisé étant une mémoire FIFO.

Les caches Write-back

Les caches write-back ont beau avoir des performances supérieures à celles des caches write-through, il existe des optimisations qui permettent d'améliorer leurs performances. Ces optimisations consistent à ajouter des caches spécialisés à côté du cache proprement dit. Ces caches permettent de mémoriser des données qui sont éliminées du cache par les algorithmes de remplacement de ligne cache, sans pour autant faire une écriture en RAM.

En suivant la procédure habituelle de remplacement des lignes de cache, on doit rapatrier la ligne en RAM avant d'en charger une nouvelle. On peut améliorer la situation en faisant l'inverse : on charge la nouvelle ligne pendant que l'ancienne donnée est rapatriée en RAM. Ainsi, la nouvelle ligne est disponible plus tôt pour le processeur, diminuant son temps d'attente. Pour implémenter cette technique, on doit mémoriser l'ancienne ligne de cache temporairement dans un cache d’éviction (ou write-back buffer).

Cache d’éviction

Les caches directement adressés ou associatifs par voie possèdent aussi un tampon d’écriture amélioré. Pour limiter les défauts par conflit de ces caches, des scientifiques ont eu l'idée d'insérer un cache pour stocker les données virées du cache. En faisant ainsi, si une donnée est virée du cache, on peut alors la retrouver dans ce cache spécialisé. Ce cache s'appelle le cache de victime. Ce cache de victime est géré par un algorithme de suppression des lignes de cache de type FIFO. Petit détail : ce cache utilise un tag légèrement plus long que celui du cache directement adressé au-dessus de lui. L'index de la ligne de cache doit en effet être contenu dans le tag du cache de victime, pour bien distinguer deux adresses différentes, qui iraient dans la même ligne du cache juste au-dessus.

Cache de victime.

L’allocation sur écriture

Que faire quand une écriture modifie une donnée qui n'est pas dans le cache ? Doit-on écrire la donnée dans le cache, ou non ? Si la donnée est écrite dans le cache, on dit que le cache fait une allocation sur l'écriture (ou write-allocate). Certains caches effectuent une telle allocation sur écriture, mais d'autres ne le font pas ou du moins pas systématiquement.

Avec allocation sur écriture

L’allocation sur écriture peut se décliner en deux sous-catégories : le chargement à la demande et l'écriture immédiate. Dans le premier cas, on charge la donnée à modifier dans le cache, et on la remplace avec la donnée écrite. Dans l'écriture immédiate, l'écriture a lieu directement dans le cache et la donnée à modifier n'est pas chargée dans le cache. Évidemment, seule une portion de la ligne de cache contient la donnée écrite (valide), et le reste contient des données invalides. Le cache doit savoir quelles sont les portions du cache qui sont valides : cela demande d'utiliser un sector cache.

Cache Write-back avec allocation sur écriture.

Sans allocation sur écriture

Sans allocation sur écriture, l'écriture est transférée directement aux niveaux de cache inférieurs ou à la mémoire si la donnée à modifier n'est pas dans le cache. Certains caches de ce genre utilisent une petite optimisation : lors de toute écriture, ils supposent que l'écriture donnera un succès de cache. Si c'est le cas, la ligne de cache qui contient la donnée est mise à jour avec la donnée à écrire. Mais si ce n'est pas le cas, la ligne de cache est invalidée, et l'écriture est transférée directement à la mémoire ou aux niveaux de cache inférieurs.

Cache Write-through sans allocation sur écriture.

La cohérence des caches

Il arrive parfois que la mémoire d'un ordinateur soit mise à jour, sans que les modifications soient répercutées dans les mémoires cache. Dans ce cas, le cache contient une donnée périmée. Or, un processeur doit toujours éviter de se retrouver avec une donnée périmée et doit toujours avoir la valeur correcte dans ses caches : cela s'appelle la cohérence des caches. Il est possible de se retrouver avec des valeurs périmées dans le cache sur les ordinateurs avec plusieurs processeurs, ou si un périphérique écrit en RAM, les modifications ne sont pas répercutées automatiquement dans les mémoires cache.

Pour résoudre ce problème, on peut interdire de charger dans le cache des données stockées dans les zones de la mémoire dédiées aux périphériques. Toute lecture ou écriture dans ces zones de mémoire ira donc directement dans la mémoire RAM, sans passer par la ou les mémoires cache. Autre solution : utiliser le fait que les périphériques déclenchent une interruption matérielle pour laisser le contrôleur DMA accéder à la mémoire. Dans ce cas, il suffit de vider les caches à chaque interruption matérielle. Le processeur peut le faire automatiquement, ou fournir des instructions pour.

La hiérarchie mémoire des caches

Hiérarchie de caches

On pourrait croire qu'un seul cache est largement suffisant pour compenser la lenteur de la mémoire. Hélas, les processeurs sont devenus tellement rapides que les caches sont eux-mêmes très lents ! Pour rappel, plus une mémoire peut contenir de données, plus elle est lente. Et les caches ne sont pas épargnés. Si on devait utiliser un seul cache, celui-ci serait très gros et donc trop lent. La situation qu'on cherche à éviter avec la mémoire RAM revient de plus belle.

Même problème, même solution : si on a décidé de diviser la mémoire principale en plusieurs mémoires de taille et de vitesse différentes, on peut bien faire la même chose avec la mémoire cache. Depuis environ une vingtaine d'années, un processeur contient plusieurs caches de capacités très différentes : les caches L1, L2 et parfois un cache L3. Certains de ces caches sont petits, mais très rapides : c'est ceux auxquels on va accéder en priorité. Viennent ensuite d'autres caches, de taille variable, mais plus lents. Les processeurs ont donc une hiérarchie de caches qui se fait de plus en plus complexe avec le temps. Cette hiérarchie est composée de plusieurs niveaux de cache, qui vont des niveaux inférieurs proches de la mémoire RAM à des niveaux supérieurs proches du processeur. Plus on monte vers les niveaux supérieurs, plus les caches sont petits et rapides.

Un accès mémoire dans une hiérarchie de cache fonctionne comme suit : on commence par vérifier si la donnée recherchée est dans le cache le plus rapide, à savoir le cache L1. Si c'est le cas,n on la charge depuis ce cache directement. Si elle n’y est pas, on vérifie si elle est dans le cache de niveau supérieur, le cache L2. Et rebelote ! Si elle n'y est pas, on vérifie le cache du niveau supérieur. Et on répète cette opération, jusqu’à avoir vérifié tous les caches. Si la donnée n'est dans aucun cache, on doit alors aller chercher la donnée en mémoire.

Hiérarchie de caches

Les caches exclusifs et inclusifs

Notons que du point de vue de cette vérification, il faut distinguer les caches inclusifs et exclusifs. Avec les caches inclusifs, si une donnée est présente dans un cache, alors elle est présente dans les caches des niveaux inférieurs, ce qui implique l'existence de données en doublon dans plusieurs niveaux de cache. À l'opposé, les caches exclusifs font que toute donnée est présente dans un seul cache, pas les autres. Il existe aussi des caches qui ne sont ni inclusifs, ni exclusifs. Sur ces caches, chaque niveau de cache gère lui-même ses données, sans se préoccuper du contenu des autres caches. Pas besoin de mettre à jour les niveaux de cache antérieurs en cas de mise à jour de son contenu, ou en cas d'éviction d'une ligne de cache. La conception de tels caches est bien plus simple.

Dans les caches exclusifs, le contenu d'un cache n'est pas recopié dans le cache de niveau inférieur. Il n'y a pas de donnée en double et on utilise 100 % de la capacité du cache, ce qui améliore le taux de succès. Par contre, le temps d'accès est un peu plus long. La raison est que si une donnée n'est pas dans le cache L1, on doit vérifier l'intégralité du cache L2, puis du cache L3. De plus, assurer qu'une donnée n'est présente que dans un seul cache nécessite aux différents niveaux de caches de communiquer entre eux pour garantir que l'on a pas de copies en trop d'une ligne de cache, ce qui peut prendre du temps.

Caches exclusifs

Dans le cas des caches inclusifs, le contenu d'un cache est recopié dans les caches de niveau inférieur. Par exemple, le cache L1 est recopié dans le cache L2 et éventuellement dans le cache L3. Ce genre de cache a un avantage : le temps d'accès à une donnée est plus faible. La raison est qu'il ne faut pas vérifier tout un cache, mais seulement la partie qui ne contient pas de donnée en doublon. Par exemple, si la donnée voulue n'est pas dans le cache L1, on n'est pas obligé de vérifier la partie du cache L2 qui contient la copie du L1. Ainsi, pas besoin de vérifier certaines portions du cache, ce qui est plus rapide et permet de simplifier les circuits de vérification. En contrepartie, l'inclusion fait que qu'une partie du cache contient des copies inutiles, comme si le cache était plus petit. De plus, maintenir l'inclusion est compliqué et demande des circuits en plus et/ou des échanges de données entre caches.

Caches inclusifs

Maintenir l'inclusion demande de respecter des contraintes assez fortes, ce qui ne se fait pas facilement. Premièrement, toute donnée chargée dans un cache doit aussi l'être dans les caches de niveau inférieur. Ensuite, quand une donnée est présente dans un cache, elle doit être maintenue dans les niveaux de cache inférieurs. De plus, toute donnée effacée d'un cache doit être effacée des niveaux de cache supérieurs : si une donnée quitte le cache L2, elle doit être effacée du L1. Ces trois contraintes posent des problèmes si chaque cache décide du remplacement des lignes de cache en utilisant un algorithme comme LRU, LFU, MRU, ou autre, qui utilise l'historique des accès. En effet, dans ce cas, le cache décide de remplacer les lignes de cache selon l'historique des accès, historique qui varie suivant chaque niveau de cache. Par exemple, une donnée rarement utilisée dans le L2 peut parfaitement être très fréquemment utilisée dans le L1 : la donnée sera alors remplacée dans le L2, mais sera maintenue dans le L1. On observe aussi des problèmes quand il existe plusieurs caches à un seul niveau : chaque cache peut remplacer les lignes de cache d'une manière indépendante des autres caches du même niveau, donnant lieu au même type de problème.

Pour maintenir l'inclusion, les caches doivent se transmettre des informations qui permettent de maintenir l'inclusion. Par exemple, les caches de niveaux inférieurs doivent prévenir les niveaux de cache supérieurs quand ils remplacent une ligne de cache. De plus, toute mise à jour dans un cache doit être répercutée dans les niveaux de cache inférieurs et/ou supérieurs. On doit donc transférer des informations de mise à jour entre les différents niveaux de cache. Généralement, le contenu des caches d'instruction n'est pas inclus dans les caches de niveau inférieurs, afin d'éviter que les instructions et les données se marchent sur les pieds.

Enfin, il faut aussi savoir que la taille des lignes de cache n'est pas la même suivant les niveaux de cache : le L2 peut avoir des lignes plus grandes que celles du L1. Dans ce cas, l'inclusion est plus difficile à maintenir, pour des raisons assez techniques.

Les caches eDRAM, sur la carte mère et autres

D'ordinaire, les mémoires caches sont intégrées au processeur et sont fabriqués avec de la SRAM. Les caches sont en SRAM car cette forme de mémoire est facile à implémenter dans un circuit intégré. Les registres sont déjà fabriqués en SRAM, et ne laisser qu'un seul type de cellule mémoire pour les registre et le cache est assez logique. De même, intégrer tous les caches dans le processeur est une solution et efficace. Et cela vaut à tous les niveaux de la hiérarchie des caches : tous sont en SRAM et dans le processeur. Mais certains processeurs ont procédé autrement.

Cache-on-a-stick module

Certains processeurs incorporaient un cache L1 dans le processeur, mais plaçaient un cache L2 sur la carte mère. Le cache était clippé sur un connecteur sur la carte mère, un peu comme le sont les barrettes de mémoire. Les premiers processeurs avec un cache faisaient ainsi, au début des années 90. On parlait alors de Cache on a stick (COAST). L'avantage est que cela permettait de mettre plus de cache, à une époque où les circuits étaient limités en transistors. De plus, cela permettait au consommateur de choisir quelle quantité de cache il voulait, selon ses finances. Il était possible de laisser le processeur fonctionner sans mémoire cache, avec un cache de 256 Kibioctets, de 512 Kibioctets, etc. Il était possible d'upgrader le cache si besoin. On aurait pu s'attendre à ce que de tels caches soient en DRAM, vu qu'ils sont placés sur des barrettes de RAM, mais la ressemblance avec la mémoire RAM principale s'arrête là. Le cache était fabriqué en mémoire SRAM, même s'il est en théorie possible de faire de tels caches avec de la DRAM.

A l'inverse, certains processeurs possédaient un cache fabriqué en mémoire DRAM, mais qui étaient intégrés dans le processeur. Il sont fabriqués avec de la mémoire eDRAM, à savoir une mémoire DRAM intégrée directement dans le processeur, dans la même puce de silicium, le même circuit intégré. Sur les processeurs Intel de microarchitecture Crystalwell, le cache L4 était un simple cache de victime qui récupérait les données évincées du cache L3. Il était alors placé avant le contrôleur mémoire intégré dans le processeur. Sur les processeurs Intel qui ont suivi, ceux de microarchitecture Skylake et Broadwell, le cache L4 en eDRAM était cette fois-ci un cache normal, pas un victime cache. Et il était placé après le contrôleur mémoire intégré au processeur. La carte graphique intégrée au processeur avait accès à ce cache L4, le cache étant partagé entre le processeur et la carte graphique suivant les besoins, à la volée.

Les caches à accès non-uniforme

Sur les caches de grande capacité, il arrive souvent que le temps de propagation des signaux varie fortement suivant la ligne de cache à lire. D'ordinaire, on se cale sur la ligne de cache la plus lente pour caler la fréquence d'horloge du cache, même si on pourrait faire mieux. Cependant, certains caches ont une latence différente pour chaque ligne d'un même cache. Les caches qui fonctionnent sur ce principe sont appelés des caches à accès non uniforme.

La première version de ce genre de caches a une correspondance ligne de cache → bloc de mémoire statique : on ne peut pas déplacer le contenu d'une ligne de cache dans une autre portion de mémoire plus rapide suivant les besoins. Mais des versions plus optimisées en sont capables : la correspondance entre une ligne de cache et un bloc de mémoire cache peut varier à l’exécution. Ainsi, les lignes de cache les plus utilisées peuvent migrer dans un bloc de mémoire plus rapide : cela demande juste de copier les données entre blocs de mémoire et de mettre à jour la correspondance entre ligne de cache et bloc de mémoire.

Les caches non bloquants

Un cache bloquant est un cache auquel le processeur ne peut pas accéder pendant un défaut de cache. Il faut attendre que la lecture ou écriture en RAM soit terminée avant de pouvoir utiliser de nouveau le cache. Un cache non bloquant n'a pas ce problème : on peut l'utiliser pendant un défaut de cache. Tous les caches non bloquants permettent ainsi de démarrer une nouvelle lecture ou écriture alors qu'une autre est en cours, ce qui permet d'exécuter plusieurs lectures ou écritures en même temps. Les caches non bloquants sont de deux types, qui portent les noms barbares de caches de type succès après défaut et défaut après défaut. Sur le premier type, il ne peut pas y avoir plusieurs défauts de cache simultanés. Le second type est plus souple et autorise la survenue de plusieurs défauts de cache simultanés. Du moins, jusqu'à une certaine limite, car le cache ne peut supporter qu'un nombre limité d'accès mémoires simultanés (pipelinés).

Su un cache bloquant, lors d'un défaut de cache, le cache et la mémoire RAM communiquent directement. Pendant un défaut de cache, le contrôleur mémoire charge la donnée depuis la mémoire et la copie plus ou moins directement dans le cache. Le cache étant utilisé, il ne peut pas être utilisé aussi bien en lecture qu'en écriture. Pour rendre un cache non-bloquant, il faut ajouter un intermédiaire entre la RAM et le cache, typiquement une mémoire tampon. Lors d'un défaut de cache, le contrôleur mémoire charge la donnée de la RAM dans la mémoire tampon, avant que le contenu du tampon soit recopié dans le cache. La conséquence est que le cache n'est pas utilisé, ni en lecture, ni en écriture, ce qui permet de l'utiliser. Il faut aussi rajouter quelques circuits pour gérer, par exemple, la survenue de défauts de cache successifs.

Les caches non bloquants de type succès après défaut

Sur les caches non-bloquants, lors d'un défaut de cache, on doit attendre que toute la ligne concernée par le défaut de cache soit chargée avant d'être utilisable. Or, la taille d'une ligne de cache est supérieure à la largeur du bus mémoire, ce qui fait qu'une ligne de cache est chargée en plusieurs fois, morceaux par morceaux. Et cela permet une optimisation qui donne les caches non-bloquants les plus basiques qui soient. L'optimisation revient à utiliser un morceau de ligne de cache tout juste chargé alors que la ligne de cache complète n'est pas totalement lue depuis la mémoire. Avec cette technique, le cache est utilisable lors d'un défaut de cache, ce qui fait qu'il est légèrement non bloquant. Ces processeurs incorporent un tampon de remplissage de ligne (line-fill buffer), une sorte de registre, qui stocke le dernier morceau d'une ligne de cache à avoir été chargé depuis la mémoire. Ce morceau est stocké avec un tag, qui indique l'adresse du bloc stocké dans le tampon de remplissage de ligne. Ainsi, un processeur qui veut lire dans le cache après un défaut peut accéder à la donnée directement depuis le tampon de remplissage de ligne, alors que la ligne de cache n'a pas encore été totalement recopiée en mémoire.

Pour utiliser au mieux ce tampon de remplissage de ligne, les processeurs actuels implémentent des techniques de critical word load. Sans critical word load, la ligne de cache est chargée morceau par morceau, dans l'ordre de placement de ces morceaux en mémoire. Mais si l'adresse lue ou écrite par le processeur n'est pas le premier mot mémoire de la ligne de cache, il devra attendre que celui-ci soit chargé. Durant ce temps d'attente, les blocs qui précédent la donnée demandée par le processeur seront chargés. Avec le critical word load, le contrôleur mémoire va charger les blocs en commençant par le bloc dans lequel se trouve la donnée demandée, avant de poursuivre avec les blocs suivants, avant de revenir au début du bloc pour charger les blocs restants. Ainsi, la donnée demandée par le processeur sera la première disponible.

Les caches non bloquants de type défaut après défaut

Au-dessus, on a vu des caches incapables de gérer plusieurs défauts simultanés.Voyons maintenant les caches capables de gérer un nombre limité de défauts de cache avant de bloquer, permettant ainsi aux lectures et écritures qui suivent un deuxième ou troisième défaut de fonctionner. Ceux-ci sont dits de type défaut après défaut (miss under miss).

Les miss status handling registers

Pendant qu'un accès en RAM est démarré par le contrôleur mémoire, il ne peut pas démarrer de nouvelle lecture ou écriture en RAM immédiatement après (sauf dans certains cas exceptionnels). Il y a toujours un temps d'attente entre l'envoi de deux requêtes d'accès mémoire. Dans ces conditions, les autres défauts doivent être mis en attente tant que la RAM n'est pas libre pour démarrer une nouvelle requête. Cette mise en attente s’effectue des miss status handling registers, que j’appellerais dorénavant MSHR. Ils sont aussi appelés des miss buffer, ce nom trahisant le fait que la mise en attente réalisée par une petite mémoire plutôt que par des registres indépendants. Le nombre de MSHR donne le nombre de défauts simultanés maximal.

Le contenu des MSHR varie beaucoup suivant le processeur, mais ces derniers stockent au minimum trois informations :

• l'adresse à l'origine du défaut de cache ;
• sa destination : le numéro de la ligne de cache où stocker la donnée du défaut de cache ;
• un bit de validité qui indique si le MSHR est vide ou pas et qui est mis à 0 quand le défaut de cache est résolu.

Supposons qu'un défaut de cache ait lieu lors de la lecture ou écriture d'une adresse bien précise. Dans ce cas, le processeur va vérifier si un autre défaut de cache est en attente dans les MSHR, pour cette même adresse. Il réagira différemment suivant si c'est le cas ou non. Mais détecter cela demande de comparer l'adresse du défaut avec celles déjà mises en attente dans les MSHR. Pour ce faire, chaque MSHR est relié à un comparateur et avec quelques circuits, le tout formant une mémoire associative. On fait alors à deux situations, suivant qu'un défaut soit déjà en attente à la même adresse ou non. S’il n'y a aucun défaut de cache en attente à l'adresse à lire/écrire, il suffit de réserver un MSHR vide pour ce défaut. Dans le cas contraire, tout dépend du cache. Certains caches mettent le cache en pause, ce qui veut dire qu'il ne peut plus accepter de nouveau défaut de cache tant que le premier défaut de cache n'est pas résolu (le cache reste non-bloquant vu que le blocage a lieu pour des accès successifs à la même adresse seulement). D'autres caches sont plus malins, et peuvent mettre en attente plusieurs défauts de cache qui tombent sur la même adresse.

Les accès simultanés à une même ligne de cache

Les MSHR sont une première avancée, qui permet à un processeur de gérer plusieurs défauts de cache, associés à des lignes de cache différentes. Toutefois, un second accès mémoire à la même ligne de cache va bloquer le cache. On se retrouve alors dans deux cas. Dans le premier cas, les adresses des deux défauts de cache ont des tags différents et le premier défaut de cache doit finir avant que le second puisse démarrer. Dans l'autre cas, les tags sont identiques, mais pas les index et les décalages. Les données sont alors proches en mémoire RAM et sont localisées dans la même ligne de cache, mais au même endroit. Quand le premier défaut de cache sera résolu, les données du second défaut de cache seront présentes dans le bloc. Dans ces conditions, il est inutile de bloquer le cache : le second défaut de cache peut être fusionné avec le premier.

Pour cela, quand un défaut de cache a lieu et que celui-ci accède à des données chargées par un défaut de cache précédent, les deux défauts sont fusionnés dans le même MSHR. Cette détection de coïncidence de l'adresse s'effectue lors de la vérification des MSHR. Le tag contenu dans le MSHR est comparé avec le tag de l'adresse responsable du nouveau défaut de cache. Reste qu'il faut mémoriser les index et les décalages pour chaque défaut, pour configurer le cache correctement une fois la ligne de cache disponible. Dans ces conditions, il faut les mémoriser quelque part, de préférence dans les MSHR.

La solution la plus simple consiste à utiliser des MSHR adressés implicitement. Ces MSHR contiennent une entrée pour chaque mot mémoire dans la ligne de cache concernée par le défaut. Chaque entrée dit si un défaut de cache compte lire ou écrire dans le mot mémoire en question. Ces entrées contiennent diverses informations :

• la destination de la lecture effectuée par le défaut de cache (généralement un registre) ;
• un format, qui donne des informations sur l'instruction à l’origine du défaut ;
• un bit de validité, qui dit si le mot mémoire associé à l'entrée est lu ou non par le défaut de cache ;
• un bit empty, qui dit si l'entrée est vide ou non.

La fusion de deux défauts de cache est ainsi assez simple. Si deux défauts de cache à la même adresse lisent des mots mémoire différents, il suffit de configurer les entrées convenablement. Le premier défaut configurera ses entrées, et le second aura les siennes. Avec cette organisation, le nombre de MSHR indique combien de lignes de cache peuvent être lues en même temps depuis la mémoire. Quant au nombre d'entrées par MSHR, il détermine combien d'accès mémoires qui ne se recouvrent pas peuvent avoir lieu en même temps.

Pour éviter de bloquer le cache lors d'accès à la même ligne de cache, certains chercheurs ont inventé des MSHR adressés explicitement. Ces MSHR sont aussi constitués d'entrées. La différence, c'est qu'une entrée est réservée à un accès mémoire, et non à un mot mémoire dans le cache. Chaque entrée va ainsi stocker :

• les index et décalages d'un accès mémoire dans la ligne de cache ;
• la destination de la lecture effectuée par le défaut de cache (généralement un registre) ;
• un format, qui donne des informations sur l'instruction à l’origine du défaut ;
• un bit empty, qui dit si l'entrée est vide ou non.

Avec cette organisation, le nombre de MSHR indique combien de lignes de cache peuvent être lues en même temps depuis la mémoire. Quant au nombre d'entrées par MSHR, il détermine combien d'accès mémoires qui atterrissent dans la même ligne de cache peuvent avoir lieu en même temps, sans contraintes de recouvrement.

Généralement, plus on veut supporter de défauts de cache, plus le nombre de MSHR et d'entrées augmente. Mais au-delà d'un certain nombre d'entrées et de MSHR, les MSHR adressés implicitement et explicitement ont tendance à bouffer un peu trop de circuits. Utiliser une organisation un peu moins gourmande en circuits est donc une nécessité. Cette organisation plus économe se base sur des MSHR inversés. Ces MSHR ne contiennent qu'une seule entrée, en quelque sorte : au lieu d’utiliser n MSHR de m entrées chacun, on va utiliser n × m MSHR inversés. La différence, c'est que plusieurs MSHR peuvent contenir un tag identique, contrairement aux MSHR adressés implicitement et explicitement. Lorsqu'un défaut de cache a lieu, chaque MSHR est vérifié. Si jamais aucun MSHR ne contient de tag identique à celui utilisé par le défaut, un MSHR vide est choisi pour stocker ce défaut, et une requête de lecture en mémoire est lancée. Dans le cas contraire, un MSHR est réservé au défaut de cache, mais la requête n'est pas lancée. Quand la donnée est disponible, les MSHR correspondant à la ligne qui vient d'être chargée vont être utilisés un par un pour résoudre les défauts de cache en attente.

Certains chercheurs ont remarqué que pendant qu'une ligne de cache est en train de subir un défaut de cache, celle-ci reste inutilisée, et son contenu est destiné à être perdu une fois le défaut de cache résolu. Ils se sont dit que, plutôt que d'utiliser des MSHR séparés, il vaudrait mieux utiliser la ligne de cache pour stocker les informations sur les défauts de cache en attente dans cette ligne de cache. Pour éviter tout problème, il faut rajouter un bit dans les bits de contrôle de la ligne de cache, qui sert à indiquer que la ligne de cache est occupée : un défaut de cache a eu lieu dans cette ligne, et elle stocke donc des informations pour résoudre les défauts de cache.

Le cache bypassing : contourner le cache

Dans certaines situations, le cache n'est pas utilisé pour certains accès mémoire. Diverses techniques permettent en effet d'effectuer des accès mémoire qui contournent le cache, qui ne passent pas par le cache. De tels accès sont utiles soit pour des raisons de performance, soit pour des raisons autres. Outre la performance, ils sont utilisés quand l'accès en cache fait que des instructions normales ne fonctionne pas. Par exemple, de tels accès directs à la RAM sont notamment utilisés pour l'implémentation d'instructions atomiques, une classe d'instructions spécifiques utilisées sur les processeurs multicoeurs, dont nous parlerons dans plusieurs chapitres. Mais ils sont aussi utilisés pour l'accès aux périphériques

Contourner le cache pour accèder aux périphériques

Pour rappel, de nombreux périphériques sont mappés en mémoire, ce qui veut dire qu'une partie des adresses accessibles par le processeur sont utilisées non pas pour la RAM/ROM, mais pour communiquer avec les périphériques. Dans ce cas, il arrive que le périphérique modifie ses registres d’interfaçage ou sa mémoire interne, ce qui se répercute dans l'espace d’adressage. Une lecture directe renverra l'état du périphérique. Mais ces modifications ne sont pas transmises au cache.

Si les accès aux périphériques passaient par l'intermédiaire du cache, on aurait droit à des problèmes. Il arriverait qu'un périphérique modifie une donnée en RAM, tandis que le cache continuerait de mémoriser une copie périmée de la donnée (si la donnée modifiée par le périphérique était mise en cache). Le même problème survient quand un contrôleur DMA manipule la RAM : les écritures réalisées par le contrôleur DMA ne sont pas transmises au cache. Dans les deux cas, on se retrouve dans une situation où le contenu du cache devrait être mis à jour pour refléter le contenu de la RAM, mais ne l'est pas. C'est un problème dit de cohérence des caches.

Cohérence des caches avec des périphériques

La solution est que les accès aux périphériques ne doivent pas passer par l’intermédiaire du cache, si on veut qu'ils marchent comme ils le doivent. Cela demande d'adapter le cache et le matériel pour que accès aux périphériques mappés en mémoire contournent le cache. Des adresses, voire des zones entières de la mémoire, sont marquées comme étant non-cachables. Toute lecture ou écriture dans ces zones de mémoire ira donc directement dans la mémoire RAM, sans passer par la ou les mémoires caches.

Contourner le cache pour des raisons de performance

Il arrive que des données avec une faible localité soient chargées dans le cache inutilement. Or, il vaut mieux que ces données transitent directement entre le processeur et la mémoire, sans passer par l'intermédiaire du cache. Pour cela, le processeur peut fournir des instructions d'accès mémoire qui ne passent pas par le cache, à côté d'instructions normales. Mais il existe aussi des techniques matérielles, où le cache détecte à l'exécution les lectures qui gagnent à contourner le cache.

La dernière méthode demande d'identifier les instructions à l'origine des défauts de cache, le processeur accédant directement à la RAM quand une telle instruction est détectée. Si une instruction d'accès mémoire fait trop de défauts de cache, c'est signe qu'elle gagne à contourner le cache. L'idée est de mémoriser, pour chaque instruction d'accès mémoire, un historique de ses défauts de cache. Il existe plusieurs méthodes pour cela, mais toutes demande d'ajouter un cache un peu particulier au processeur. Ce cache s'appelle la table d’historique des défauts de lecture (load miss history table). Comme son nom l'indique, cette table mémorise, pour chaque instruction, un petit historique des défauts de cache qu'a généré l'instruction. L'historique en question est, dans sa version la plus simple, un compteur de quelques bits incrémenté à chaque succès de cache et décrémenté à chaque défaut de cache, qui indique si l'instruction a en moyenne fait plus de défauts ou de succès de cache. La table associe le program counter d'une instruction mémoire à cet historique. À la première exécution d'une instruction d'accès mémoire, une entrée de cette table est réservée pour l'instruction. Lors des accès ultérieurs, le processeur récupérer les informations associées et décide s'il faut contourner le cache ou non.

Les caches adressés par somme et hashés

Pour rappel, la gestion de certains modes d'adressage demande que le processeur calcule l'adresse. Les calculs d'adresse en question sont généralement assez simples : ils prennent une adresse de base, à laquelle ils ajoutent une constante. Généralement, l'adresse de base est l'adresse d'un tableau ou d'une structure, et la constante ajoutée indique la position de la donnée dans le tableau/la structure. Le processeur lit généralement l'adresse de base et le décalage (la constante à ajouter) depuis deux registres et c'est l'unité d'accès à la mémoire qui fait l'addition. Mais dans certains cas, l'addition peut être faite directement dans la mémoire cache, voire omise ou remplacée par des opérations plus simples. Les optimisations qui permettent cela donne les caches hashés et les caches adressés par somme. Voyons d'abord les caches hashés, avant de passer aux caches adressés par somme.

Les caches hashés

Sur les caches hashés, l'addition est remplacée par une autre opération, par exemple des opérations bit à bit du style XOR, AND ou OR, etc. Seulement, utiliser des opérations bit à bit pose un problème : il arrive que deux couples Adresse/décalage donnent le même résultat. Par exemple, le couple Adresse/décalage 11101111/0001 donnera la même adresse que le couple 11110000/0000. Dit autrement, deux adresses censées être différentes (après application du décalage) sont en réalité attribuées à la même ligne de cache. Il est toutefois possible de gérer ces situations, mais cela demande des astuces de haute volée pour faire fonctionner la mémoire cache correctement.

Les caches adressés par somme

Sur les caches adressés par somme, le décodeur est modifié pour se passer de l'addition. Pour comprendre comment, il faut rappeler qu'un décodeur normal est composé de comparateurs, qui vérifient si l'entrée est égale à une constante bien précise. Sur un cache ordinaire, l'addition est faite séparément du décodage des adresses par le cache, dans l'unité de calcul ou dans l'unité de génération d'adresse.

Cache normal.

Mais les caches adressés par somme modifient le décodeur, qui est alors composé de comparateurs qui testent si la somme adresse + décalage est égale à une constante.

Cache adressé par somme.

Chaque circuit du décodeur fait le test suivant, avec K une constante qui dépend du circuit :

$A+B=K$

Ce qui est équivalent à faire le test suivant :

$A+B-K=0$

En complément à deux, on a $-K={\overline {K}}+1$. En injectant dans l'équation précédente, on a :

$A+B+{\overline {K}}+1=0$

En réorganisant les termes, on a :

$A+B+{\overline {K}}=-1$

Il suffit d'utiliser un additionneur carry-save pour faire l'addition des trois termes. Rappelons qu'un tel additionneur fournit deux résultats en sortie : une somme calculée sans propager les retenues et les retenues en question. Notons que les retenues sont à décaler d'un cran, vu qu'elles sont censées s'appliquer à la colonne suivante. En notant la somme S et les retenues R, on a:

$S+(R<<1)=-1$, le décalage d'un cran à gauche étant noté $<<1$.

Ensuite, -1 est codé avec un nombre dont tous les bits sont à 1 en complément à un/deux.

$S+(R<<1)=111\cdots 111111$

Sum + retenue add

Un simple raisonnement nous permet de savoir si le résultat est bien -1, sans faire l'addition $S+(R<<1)$. En effet, on ne peut obtenir -1 que si la somme est l'inverse des retenues : un 0 dans le premier nombre correspond à un 1 dans l'autre, et réciproquement. En clair, on doit avoir ${\overline {S}}=R<<1$. Pour vérifier cela, il suffit de faire un simple XOR entre la somme et les retenues décalées d'un cran. On a alors :

$S\oplus (R<<1)=111\cdots 111111$

La comparaison avec -1 se fait avec une porte ET à plusieurs entrées. En effet, la porte donnera un 1 seulement si tous les bits d'entrée sont à 1, ce qui est ce qu'on veut tester.

Au final, l'additionneur pour l'addition adresse + décalage est remplacé par un additionneur carry-save suivi d'une couche de portes XOR et d'un comparateur avec une constante, ce qui économise de circuits et améliore les performances.

Cache adressé par somme.

En prenant en compte que la constante K est justement une constante, certaines entrées de l'additionneur carry-save sont toujours à 0 ou à 1, ce qui permet quelques simplifications à grand coup d’algèbre de Boole. Chaque additionneur complet qui compose l’additionneur carry-save est remplacée par des demi-additionneurs (ou par un circuit similaire). Autant dire que l'on gagne tout de même un petit peu en rapidité, en supprimant une couche de portes logiques. Le circuit de décodage économise aussi des portes logiques, ce qui est appréciable.