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 lignes de cache

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.

Un point important est que les caches modernes ajoutent des bits de détection/correction d'erreur dans les bits de contrôle. Pour rappel, les codes de détection/correction d'erreur permettent de se prémunir contre des erreurs matérielles, qui corrompent les données stockées dans une mémoire, ici une mémoire cache. Ils ajoutent un ou plusieurs bits à la ligne de cache, dans les bits de contrôle. Nous reviendrons dessus dans une section ultérieur de ce chapitre.

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 optimisations des caches associatifs par voie et adressés directement

Les caches associatifs par voie peuvent être optimisés de nombreuses manières, que ce soit pour gagner en performance ou pour économiser de l’énergie. Il en est de même pour les caches direct mapped, adressés directement, mais ces optimisations sont plus rares. Dans cette section, nous allons voir quelles sont ces optimisations.

Les phased caches

Dans cette section, nous allons voir les caches splittés (phased caches), qui sont une variante des caches direct-mapped, dans lequel le cache est accédé en deux étapes consécutives. Il ne s'agit pas des caches pipelinés, que nous verrons dans le chapitre sur les processeurs pipélinés, mais laissons cela à plus tard. Il est possible d'appliquer la même méthode sur un cache associatif par voie, mais il y a des méthodes plus simples, qui permettent là aussi d’accéder au cache en plusieurs étapes consécutives. Abordons donc la technique pour les caches direct-mapped.

Dans les caches direct-mapped, on trouve une mémoire SRAM dont chaque mot mémoire contient une ligne de cache entière, tag inclus. Mais il est possible de scinder cette mémoire SRAM en deux : une pour les tags, une pour les données de la ligne de cache. Les bits de contrôle peuvent être mis dans l'une ou l'autre SRAM, peu importe. En faisant cela, quelques optimisations deviennent possibles, afin de réduire la consommation énergétique en contrepartie d'une perte de performance.

Précisons qu'il s'agit bien de deux mémoires SRAM adressables, on n'est pas dans le cas d'un cache associatif avec une CAM et une RAM combinée. L'adresse à laquelle accéder est envoyée à la SRAM des tags, puis ensuite à la SRAM des données si besoin. On n'est pas dans le cas où on récupère une adresse dans la SRAM des tags, pour l'envoyer à la RAM des données.

L'idée est d’accéder aux tags pour déterminer s'il y a un succès de cache ou un défaut, et ensuite d'accéder aux données. On n’accède pas aux données en parallèle des tags. Faire cela est évidemment plus lent. En cas de défaut de cache, le temps d'accès est similaire : le tag ne correspond pas, on n'accède pas à la SRAM pour les données. Par contre, vu qu'on n'a pas activé la SRAM pour les données, on économise un peu d'énergie, ce qui réduit la consommation d'énergie. En cas de succès de cache, on accède à la SRAM pour les tags, puis à celle pour les données. Pas d'économie d'énergie à l'horizon, sans compter que le temps d'accès augmente : on accède au cache en deux étapes au lieu de faire les deux accès en parallèle.

Phased cache

Précisons cependant que ce design peut avoir deux avantages en termes de performance. Premièrement, le temps d'accès au cache est légèrement amélioré en cas de défaut de cache. En effet, la SRAM des tags est assez petite, idem pour celle des données. Leur temps d'accès est donc plus faible que pour une grosse SRAM contenant données et tags. Le gain en temps d'accès est donc un avantage, qui ne se manifeste surtout en cas de défaut de cache. Un autre avantage est que l'accès au cache se pipeline plus facilement, ce qui fait qu'on peut effectuer plusieurs accès simultanés au cache. Mais nous verrons cela dans quelques chapitres.

Un autre avantage est que cela permet au cache de servir à la fois de mémoire cache, mais aussi de local store, de mémoire RAM de petite taille. C'est notamment utilisé sur certaines cartes graphiques, sur lesquelles le cache L1 et un local store sont en réalité la même structure configurable pour servir soit comme l'un, soit comme l'autre. Le fonctionnement est assez simple à comprendre. Lors d'un accès au cache, on accède aux tags, puis à la RAM interne au cache. Lors d'un accès au local store, on contourne l'accès au tags et on accède à la RAM interne au cache directement.

Hydride cache - local store

La compression de cache

Une autre optimisation permise par les phased caches est l'implémentation de techniques de compression de cache, qui visent à compresser des lignes de cache. L'intérêt est qu'on peut stocker plus de données dans le cache, à capacité égale. L'inconvénient est qu'on doit compresser/décompresser les lignes de cache, ce qui demande un circuit en plus et allonge les temps d'accès. En effet, le temps mis pour compresser/décompresser une ligne de cache s'ajoute au temps d'accès. Aussi, la compression de cache sert surtout pour les caches de bas niveau dans la hiérarchie mémoire, les gros caches aux temps d'accès assez longs.

Une première technique, assez simple à implémenter et peu couteuse en circuit, est celle de la compression des lignes de cache nulles. Elle compresse uniquement les lignes de cache qui ne contiennent que des zéros. L'idée est qu'on ajoute, dans la mémoire des tags, un bit de contrôle pour chaque ligne de cache appelé le bit null. Il indique si la ligne de cache ne contient que des zéros. Quand on lit une ligne de cache, la mémoire des tags est accédée et on vérifie le bit null : s'il vaut 1, on n'accède pas à la mémoire cache de données et un multiplexeur envoie un zéro sur le port de lecture. Le bit null est fixé lors de l'écriture d'une ligne de cache : elle passe dans un comparateur avec zéro relié à la mémoire des tags. La comparaison avec zéro peut se faire en parallèle de l'écriture ou avant (dans ce cas, on n'écrit pas la ligne de cache dans le cache).

Les autres techniques de compression de cache permettent de compresser autre chose que des lignes de cache nulles. L'idée est qu'une ligne de cache physique peut par moment mémoriser plusieurs lignes de caches compressées. Par exemple, prenons un cache dont les lignes de cache font 64 octets. Il est possible de compresser deux lignes de cache pour qu'elles fassent chacune 32 octets, et les stocker dans une seule ligne de cache. Les deux lignes de cache auront des tags différents, mais pointeront sur la même ligne de cache physique. Et cela demande d'utiliser un phased cache dont la mémoire pour les tags est plus grande que la mémoire pour les données. Il n'y a donc plus une bijection entre tags et ligne de cache, mais une relation surjective. Chose qui n'est possible qu'avec un phased cache. De plus, des bits de contrôles associés à chaque tag indiquent où se trouvent les lignes de cache compressées dans la ligne de cache : est-ce que c'est les 32 octets de poids fort ou de poids faible ?

Compression de cache

Il ne semble pas que les techniques de compression de cache soient implémentées sur les processeurs modernes. Aucun n'utilise de compression de cache, à ma connaissance. Il faut dire que les techniques connues sont de mauvais compromis : le temps d'accès du cache augmente beaucoup, le cout en circuit pourrait être utilisé pour un cache non-compressé mais plus grand. Et notons que la compression de cache ne marche que si les données peuvent se compresser. Si ce n'est pas le cas, une partie de la mémoire des tags est inutilisée.

Une revue de la littérature académique sur la compression de cache est disponible via ce lien, pour les curieux :

• Understanding Cache Compression, par Carvalho et Seznec.

Les caches pseudo-associatifs

Les caches adressés par voie contiennent une mémoire SRAM par voie. En théorie, les voies sont accédées en parallèles, en même temps, afin de voir si l'on a un succès de cache ou un défaut. Les caches pseudo-associatifs sont identiques aux caches associatifs par voie, si ce n'est qu'ils vérifient chaque voie une par une. Ils ont été utilisés sur des processeurs commerciaux, un exemple étant l'IBM 370.

Là encore, on perd en performance pour gagner en consommation d'énergie. 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 en parallèle. On teste la première voie, éventuellement la seconde, peut-être la troisième, etc. Mais dans le cas général, on ne teste qu'une partie des voies, pas toutes, ce qui donne un gain en termes d'énergie.

L'implémentation de caches de ce genre demande que l'on parcoure les voies une par une, en commençant de la première jusqu'à la dernière. Pour cela, un simple compteur suffit. Suivant la valeur du compteur, la voie associée est activée puis accédée. Toute la complexité revient à ajouter un circuit qui prend la valeur du compteur, et active la voie associée, lance un accès mémoire dessus. Vu que les voies sont chacune des caches direct mapped, il suffit pour cela de geler les entrées d'adresse, soit en les déconnectant, soit en utilisant du clock gating ou de l'évaluation gardée. Les détails d'implémentation, non-cités ici, varient selon le cache.

La prédiction de voie

Pour réduire le temps d'accès des caches pseudo-associatifs, certains chercheurs ont inventé la prédiction de voie, qui consiste à faire des paris sur la prochaine voie accédée. L'idée est d'accéder à la voie qui contient la donnée voulue du premier coup, en lisant celle-ci en priorité.

Dans son implémentation la plus simple, le cache reste un cache pseudo-associatif. Lors d'un accès au cache, les voies sont toutes parcoures une par une. Par contre, les voies ne sont donc pas parcourues de la première vers la dernière, mais dans un ordre différent. 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. L'implémentation est assez simple : il suffit d'ajouter un circuit de prédiction de voie,relié au compteur de voie.

Une amélioration de la technique fait fonctionner le cache comme un intermédiaire entre cache pseudo-associatif et associatif par voies. L'idée est de chercher la voie prédite en premier, puis de chercher dans toutes les voies en parallèle en cas de défaut de cache. 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 plus tôt que prévu. S'il se trompe, le processeur annule la lecture effectuée en avance et recommence en faisant un accès en parallèle aux autres voies. Le compromis entre performance et consommation d'énergie est alors différent. On économise de l'énergie par rapport à un cache associatif par voie, au prix d'une petite perte de performance (doublement des temps d'accès). Mais par rapport à un cache pseudo-associatif, l'économie d'énergie est bien moindre, au prix d'un gain en performance assez manifeste.

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.

La mise en veille sélective des voies

Les caches associatifs ont tendance à utiliser beaucoup d'énergie, même quand on n'y accède pas. Aussi, certains processeurs détectent quand le cache est peu utilisé et en profitent pour mettre en veille les voies inutilisées. Vous vous demandez certainement ce qui se passe quand une donnée à lire/écrire est dans une voie désactivée. La réponse est que le cache détecte cette situation, car elle déclenche un succès de cache. Les tags ne sont en effet pas désactivés, seules les données sont mises en veille. L'implémentation est plus simple sur les caches qui séparent les tags et les données dans deux RAM différentes.

Cette optimisation marche surtout sur les gros caches, qui ont des chances d'avoir une portion significative d’inutilisée (pas assez de données pour les remplir), donc généralement les caches L3/L4. Par exemple, les processeurs d'Intel de microarchitecture Ivy Bridge disposent d'un cache de 8 mébioctets à 16 voies, qu'ils peuvent faire passer à 512 kibioctets si le besoin s'en fait sentir. Quand ces processeurs détectent une faible activité, ils mettent en veille 14 voies et n'en gardent que 2 d'actives. Évidemment, les 14 voies sont vidées avant d'être mises en veille, afin qu'une aucune donnée ne soit perdu.

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.

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

Dans certaines conditions bien précises, 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. Pour résumer, 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.

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

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

Un autre problème similaire a lieu quand un périphérique modifie une donnée en RAM : le cache continue 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). L'exemple classique est celui d'un contrôleur DMA qui manipule la RAM : les écritures réalisées par le contrôleur DMA ne sont pas transmises au cache. 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.

La configuration du fonctionnement du cache

Sur de nombreux processeurs, il est possible de configurer la mémoire cache pour qu'elle fonctionne soit en mode write-back, soit en mode write-through. Pour cela, les processeurs modernes incorporent des registres de configuration du cache. Le terme registre de configuration du cache est assez transparent et indique bien quel est leur rôle. Ils configurent comment le cache est utilisé et permettent notamment de configurer le cache pour dire s'il doit fonctionner en mode write-back ou write-through. Ils permettent aussi d'activer ou de désactiver la combinaison sur écriture.

Les registres en question sont configurés soit par le BIOS, soit par le système d'exploitation. Ce sont des registres protégés, que les applications ne peuvent pas configurer, elles n'en ont pas le droit. Typiquement, ils ne sont accessibles en écriture qu'en mode noyau.

Organisation Mémoire PC x86.

Sur les processeurs x86, les registres de configuration du cache sont appelés des Memory type range registers (MTRRs). Les MTRRs sont assez nombreux, et il y a notamment une différence entre mode réel et protégé. Si vous vous souvenez des chapitres sur le mode d'adressage et la mémoire virtuelle, vous vous souvenez que les processeurs x86 incorporent plusieurs modes de fonctionnement. En mode réel, le processeur ne peut adresser qu'un mébioctet de RAM, avec un système de segmentation particulier. En mode protégé, le processeur peut adresser toute la mémoire et la segmentation fonctionne différemment, quand elle n'est pas simplement désactivée.

Les MTRRs sont séparés en deux : ceux pour le mode réel, ceux pour le mode protégé. Les MTRRs fixes sont ceux qui configurent le cache en mode réel, ils étaient utilisés pour gérer l'accès au BIOS, à la mémoire VGA de la carte graphique, et quelques autres accès aux entrées-sorties basiques gérées nativement par le BIOS. Pour le mode protégé, les processeurs au-delà du 386 incorporent des MTRRs variables, qui servent pour les autres entrées-sorties en général, notamment les périphériques PCI, la mémoire vidéo de la carte graphique, et j'en passe.

De nos jours, les registres de configuration du cache sont désuets et cette fonctionnalité est gérée directement par la mémoire virtuelle. La table des pages contient, pour chaque page mémoire, des bits de contrôle qui disent si la page mémoire est cacheable ou non. Le contournement de cache est alors géré par le système de mémoire virtuelle, le cache de TLB et tout ce qui va avec.

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

Il y a des différences assez notables entre chaque niveau de cache. Par exemple, les différents niveaux de cache n'ont pas forcément les mêmes politiques de remplacement des lignes de cache. Le cache L1 a généralement une politique de remplacement simple, très rapide, mais peu efficace.

De même, il faut aussi savoir que la taille des lignes de cache n'est pas la même suivant les niveaux de cache. Par exemple, le L2 peut avoir des lignes plus grandes que celles du L1.

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. Par exemple, 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.

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. Ils sont utilisés quand l'accès en cache fait que des instructions normales ne fonctionnent 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 multicœurs, dont nous parlerons dans plusieurs chapitres. Mais ils sont aussi utilisés pour l'accès aux périphériques, ce que nous allons voir maintenant.

Accéder aux périphériques demande de contourner le cache

Pour rappel, un périphérique (au sens d'entrée-sortie) contient des registres d’interfaçage qui ont une adresse au même titre que les cases mémoire. Un périphérique peut à tout instant modifier ses registres d’interfaçage, ce qui se répercute automatiquement dans l'espace d'adressage, mais rien de tout cela n'est transmis au cache. Si les accès aux périphériques passaient par l'intermédiaire du cache, on aurait droit à des problèmes. On aurait encore une fois droit à des problèmes de cohérence des caches. Le problème est géré différemment suivant que l'on utilise un espace d'adressage séparé ou des entrées-sorties mappées en mémoire.

La solution est que les accès aux périphériques ne doivent pas passer par l’intermédiaire du cache. Cela demande d'adapter le cache et le processeur. L'implémentation exacte dépend de comment sont adressés les périphériques. Pour rappel, il y a deux solutions pour adresser les périphériques : soit les périphériques disposent d'un espace d'adressage séparé de celui de la mémoire, soit il y un espace d'adressage unique partagé entre processeur et mémoire. Les deux cas donnent des solutions différentes.

Avec un espace d'adressage séparé, l'espace d'adressage des périphériques n'est pas caché : aucun accès dans cet espace d'adressage ne passe par le cache. La mémoire cache n'est utilisée que pour l'espace d'adressage des mémoires, rien d'autre. C'est de loin le cas le plus simple : il suffit de concevoir le processeur pour. Il dispose d'instructions séparées pour les accès aux registres d’interfaçage et à la RAM/ROM, les premières ne passent pas par le cache, les autres si.

Avec des entrées-sorties mappées en mémoire, la même solution est utilisée, mais dans une version un peu différente. Là encore, 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. Là encore, le processeur doit être prévu pour : on doit pouvoir le configurer de manière à marquer certaines zones de la RAM comme non-cacheable.

Reste qu'il faut marquer des régions de la RAM comme non-cacheable. Pour cela, on améliore les registres de configuration du cache, vus plus haut, afin qu'ils permettent de configurer certaines portions de la RAM pour préciser qu'elles ne doivent pas être mises en cache, qu'il faut activer le contournement de cache pour celles-ci.

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 demandent d'ajouter de quoi mémoriser l'historique des défauts de cache des instructions. L'historique est mémorisé dans une mémoire appelée la table d’historique des défauts de lecture (load miss history table), qui est souvent un cache.

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.

La tolérance aux erreurs des caches

Une mémoire cache reste avant tout une mémoire RAM, bien que ce soit de la SRAM. Elle n'est pas parfaite et est donc sujette à des erreurs, qui peuvent inverser un bit ou l'effacer. De telles erreurs sont liées à des rayons cosmiques très énergétiques, à des particules alpha produites par le packaging ou le métal deu circuit intégré, peu importe : l'essentiel est qu'ils inversent parfois un bit. Les mémoires modernes savent se protéger contre de telles erreurs, en utilisant trois moyens.

Les mémoires caches ECC et à bit de parité

Le premier moyen est l'usage de codes correcteurs d'erreurs, qui ajoutent un ou plusieurs bits à la ligne de cache, dans les bits de contrôle. Les bits ajoutés dépendent de la donnée mémorisée dans le byte, et servent à détecter une erreur, éventuellement à la corriger. Le cas le plus simple ajoute un simple bit de parité pour chaque byte et se contente de détecter les erreurs dans les corriger. Les autres codes ECC permettent eux de corriger des erreurs, mais ils demandent d'ajouter au moins deux bits par byte, ce qui a un cout en circuit plus élevé.

Un simple bit de parité permet de détecter qu'un bit a été inversé, mais ne permet pas de corriger l'erreur. En soi, ce n'est pas un problème. Si une erreur est détectée, on considère que la ligne de cache est invalide. Le cache gère la situation comme un défaut de cache et va chercher la donnée valide en mémoire RAM. Le cout en circuits est donc faible, mais les défauts de cache sont plus nombreux. Les codes ECC sont eux capables de corriger les erreurs, si elles ne modifient pas trop de bits d'un coup. Par contre, ils utilisent deux à trois bits par octet, ce qui a un cout en circuits loin d'être négligeable. Il y a donc un compromis entre défauts de cache et cout en circuits.

La gestion de l'ECC est différente suivant le niveau de cache. Généralement, le cache L1 n'utilise pas l'ECC mais se contente d'un simple bit de parité pour éviter la corruption de ses données. Le cache étant petit, les corruptions de données sont assez rares, et les défauts de cache induits faibles. Il est plus important d'utiliser un code de détection d'erreur simple, rapide, qui ne ralentit pas le cache et n'augmente pas sa latence. Si une ligne de cache est corrompue, il a juste à aller lire la ligne depuis le cache L2, ou un niveau de cache inférieur. Du moins, c'est possible sur le cache en question est un cache inclusif et/ou write-through.

Par contre, le niveau de cache L2 et ceux en-dessous utilisent presque systématiquement une mémoire SRAM ECC. La raison principale étant que ce sont des caches assez gros, pour lesquels la probabilité d'une erreur est assez élevée. Plus une mémoire a de bits et prend de la place, plus il y a une chance élevée qu'un bit s'inverse. Et vu que les caches L2/L3/L4 sont par nature plus lents et plus gros, ils peuvent se permettre le cout en performance lié à l'ECC, idem pour le cout en circuit. Sans compter qu'en cas d'erreur, ils doivent aller lire la ligne de cache originelle en mémoire RAM, ce qui est très lent  ! Mieux vaut corriger l'erreur sur place en utilisant l'ECC.

L'usage du memory scrubbing sur les caches

La plupart des erreurs ne changent qu'un seul bit dans un byte, mais le problème est que ces erreurs s'accumulent. Entre deux accès à une ligne de cache, il se peut que plusieurs erreurs se soient accumulées, ce qui dépasse les capacités de correction de l'ECC. Dans ce cas, il existe une solution appelée le memory scrubbing, qui permet de résoudre le problème au prix d'un certain cout en performance.

Pour rappel, l'idée est de vérifier les lignes de caches régulièrement, pour éviter que les erreurs s'accumulent. Par exemple, on peut vérifier chaque ligne de cache toutes les N millisecondes, et corriger une éventuelle erreur lors de cette vérification. En faisant des vérifications régulières, on garantir que les erreurs n'ont pas le temps de s'accumuler, sauf en cas de malchance avec des erreurs très proches dans le temps. Il ne s'agit pas d'un rafraichissement mémoire, car les SRAM ne s'effacent pas), mais ça a un effet similaire.

Et évidemment, le memory scrubbing a un cout en performance. On peut faire une comparaison avec le rafraichissement mémoire : les rafraichissement réguliers réduisent les performances, car cela fait des accès en plus. Des accès qui sont de plus timés à des instants bien précis qui ne sont pas forcément les plus adéquats. Il est possible qu'un rafraichissement ait lieu en même temps qu'un accès mémoire et le rafraichissement a la priorité, ce qui réduit les performances. La même chose arrive avec les vérifications du memory scrubbing. Malgré tout, la technique a été utilisée sur les caches de certains processeurs commerciaux, dont des processeurs AMD Athlon et Athlon 64. Elle est surtout utilisable sur les caches L2/L3, pour lesquels le cout du pseudo-rafraichissement est acceptable.

Un exemple de cache : le cache d'instruction

Sur certains processeurs, il y a deux caches L1 séparés : un cache d'instructions, dédié aux instructions, et un autre pour les données. Les deux caches sont reliés au reste du processeur, ainsi qu'au cache L2. Pour les liaisons avec le processeur proprement dit, il y a un bus séparé pour le cache d'instruction et un autre pour le cache de données. Une telle organisation permet de charger une instruction tout en lisant une donnée en même temps. C'est théoriquement possible avec un cache L2 multiport, mais l'usage de caches séparés est plus simple. Pour les connexions avec le cache L2, tout dépend du processeur. Certains utilisent un cache L2 multiport, qui permet aux deux caches L1 de lire ou écrire dans le cache L2 simultanément.

Cache d'instructions.

Si le cache L2 ne gère pas les accès simultanés, il n'y a qu'un seul bus relié aux caches L1 et au cache L2. On doit effectuer un arbitrage pour décider quel cache a la priorité, chose qui est réalisé par un circuit d'arbitrage spécialisé.

Circuit d'arbitrage du cache.

Généralement, les caches d'instructions peuvent se permettre d'être plus petits que les caches de données, car les programmes sont souvent plus petits que les données manipulées. Songez que des programmes de quelques mébioctets peuvent parfois remplir la RAM avec plusieurs gibioctets de données. Lancez votre navigateur internet et ouvrez une page web un peu chargée, pour vous en convaincre !

Pourquoi séparer instructions et données dans des caches séparés ?

En soi, le fait de dédier un cache séparé pour les instructions est assez logique, vu que données et instructions sont deux choses radicalement différentes. Les conséquences sont multiples : les algorithmes de remplacement des lignes de cache optimaux pour les données ne le sont pas pour les instructions, de même que la taille optimale du cache, la taille des lignes de cache optimale, ou même les algorithmes de préchargement. Par exemple, pour le remplacement des lignes de cache, un simple algorithme LRU est presque optimal pour les instructions, autant il peut donner de mauvaises performances quand on manipule beaucoup de tableaux. Cela justifie d'utiliser des caches spécialisés pour chacune. On peut adapter le cache d'instruction à son contenu, ce qui le rend plus rapide ou plus petit à performance égale.

La différence principale est que, comparé aux données, les instructions ont tendance à avoir une bonne localité spatiale et temporelle. Localité spatiale tout d'abord parce que des instructions consécutives se suivent en mémoire. On pourrait rétorquer que les branchements sont à l'origine de sauts dans le programme, mais les branchements qui sautent à un point éloigné dans le programme sont rares. La plupart des branchements font sauter à un endroit proche, ce qui conserve une bonne localité. De plus, les branchements sont beaucoup utilisés pour faire des boucles qui répètent la même séquence d'instruction. Les boucles sont tellement fréquentes et utilisées que la localité temporelle des instructions est généralement très bonne. Par contre, les données ont une localité moins bonne. Il faut dire que rien ne garantit que des données utilisées ensemble soient regroupées en mémoire comme le sont les instructions consécutives.

C'est aussi la raison pour laquelle, sur les architectures conventionnelles, le cache d'instruction a plus d'impact sur les performances que le cache de données. Et il existe des processeurs assez extrêmes qui se contentent d'un cache d'instruction unique, sans cache de données. C'est le cas sur les processeurs vectoriels ou les GPU que nous verrons dans les chapitres de fin de ce wikilivres. La raison est que ces processeurs sont spécialisés dans la manipulation de tableaux de données, traitement qui a une faible localité temporelle. En conséquence, utiliser un cache de données n'est pas vraiment utile, voire peu être contreproductif. Par contre, un cache d’instruction fonctionne parfaitement, les programmes exécutés ayant une bonne localité, aussi bien temporelle que spatiale.

Les avantages et inconvénients des caches d'instructions

Les arguments précédents justifient que l'on puisse dédier un cache aux instructions. Cependant, ces arguments sont valables à tous les niveaux de la hiérarchie mémoire, y compris au niveau du cache L2 et L3, qui sont eux unifiés. On n'a pas de cache L2 dédié aux instructions ou aux données, mais un cache L2 unique pour les deux. Comment expliquer alors que la spécialisation se fasse spécifiquement au niveau du cache L1 ? La raison est que les contraintes au niveau du cache L1 et L2 ne sont pas les mêmes. Les caches L1 et L2/L3 ont des usages différents : cache petit mais rapide pour le L1, gros et lent pour le L2/L3. Et ces contraintes sont déterminantes pour décider si tel ou tel niveau de cache est séparé en deux caches spécialisés ou non.

L'usage d'un cache d’instruction séparé du cache de données est à contraster avec l'usage d'un cache unique, capable de mémoriser à la fois instructions et données. Les deux solutions sont possibles ont été utilisées. Les premiers processeurs disposant d'un cache avaient un cache unique et multiport, mais ce n'est plus le cas sur les processeurs modernes, car les contraintes ne sont pas les mêmes. N'oublions pas que les concepteurs de processeurs sont limités en transistors et doivent faire des choix. Les transistors utilisés pour le cache d'instruction auraient pu être utilisés pour autre chose, comme augmenter la capacité des caches existants, et notamment le cache L1. Ajouter un cache d'instruction demande de faire des choix, de bien peser le pour et le contre, de bien juger des avantages et inconvénients d'un cache d'instruction.

Le premier compromis à faire est celui entre capacité des caches et performances, plus précisément entre le temps d'accès et la capacité totale du cache L1. Pour faire simple, on a le choix entre deux petits caches rapides et un gros cache plus lent. Pour rappel, plus un cache est petit, plus il est rapide et chauffe moins. Donc au lieu d'utiliser, par exemple, un gros cache lent de 64 Kibioctets, on utilise deux caches de 32 kibioctets, plus rapides. La capacité totale est la même, mais le temps d'accès plus faible. Cependant, cela vient avec un défaut qui réduit la capacité effective. Par exemple, pour un cache d'une capacité de 64 kibioctets, on peut décider de réserver 10 kb aux instructions et le reste aux données, ou encore 40 Kb aux instructions, etc. La répartition se fait naturellement, en fonction de la politique de remplacement du cache et est proche de l'optimal. Avec deux caches séparés, la répartition de la capacité du cache L1 est fixée une bonne fois pour toutes. Par exemple, avec un cache d'instruction de 32 Kb et un cache de données de 32 Kb, impossible d'allouer 40 Kb aux données et 20 aux instructions : le cache de données est trop petit. C'est là un désavantage des caches d'instructions/données séparés : une capacité effective moindre. Et cela explique en grande partie pour seul le cache L1 est séparé en deux : c'est le temps d'accès qui prime pour le cache L1, alors que la capacité effective prime pour les niveaux L2 et au-delà.

La communication du cache d'instruction avec le séquenceur

Une autre différence entre instructions et données est la suivante : les instructions sont utilisées par le séquenceur et les données par le chemin de données. Et cela se marie bien avec deux caches séparés, placés à des endroits très différents du processeur. Le cache d’instruction se situe en théorie entre l'unité de chargement et l'unité de décodage. En effet, ce cache prend en entrée une adresse et fournit une instruction. L'adresse est fournie par le program counter, l'instruction est envoyée dans l'unité de décodage. Le cache se situe donc entre les deux. Il est parfois intégré à l'unité de chargement, par simplicité de conception du processeur. Quant au cache de données L1 est connecté au chemin de données, et notamment aux unités de communication avec la mémoire, pas au séquenceur.

Caches L1 et positions dans le processeur

Les deux caches sont reliés au processeur par des bus séparés. Pour simplifier, l'ensemble ressemble à une architecture Harvard, mais où les caches remplacent les mémoires RAM/ROM. Le cache d'instruction prend la place de la mémoire ROM et le cache de données prend la place de la mémoire RAM. Évidemment, il y a des niveaux de caches en dessous des caches de données/instruction, et ceux-ci contiennent à la fois données et instructions, les deux ne sont pas séparées dans des mémoires/caches séparés. Raison pour laquelle l'ensemble est appelé une architecture Harvard modifiée. Architecture Harvard, car l'accès aux données et instructions se font par des voies séparées pour le processeur, modifiée car la séparation n'est effective que pour le cache L1 et pas les autres niveaux de cache, et encore moins la RAM.

Une telle organisation facilite l'implémentation de certaines optimisations, voire rend celles-ci possibles. Citons comme exemple, la technique dite du prédécodage. Pour accélérer le décodage des instructions, certains concepteurs de processeurs ont décidés d'utiliser la (ou les) mémoire cache dédiée aux instructions pour accélérer ce décodage. Lorsque ces instructions sont chargées depuis la RAM ou les niveaux de cache inférieurs, celles-ci sont partiellement décodées. On peut par exemple rajouter des informations qui permettent de délimiter les instructions ou déterminer leur taille, ce qui est utile pour décoder les instructions de taille variable. Bref, le cache d'instructions peut se charger d'une partie du décodage des instructions, grâce à un circuit séparé de l'unité de décodage d'instruction.

Prédécodage des instructions dans le cache L1

Le cache d'instruction est souvent en lecture seule

Un point important est que les instructions sont rarement modifiées ou accédées en écritures, contrairement aux données. Et cela permet d'utiliser un cache simplifié pour les instructions. Autant un cache généraliste doit permettre les lectures et écritures depuis le processeur (avec les échanges avec la RAM), autant un cache d'instruction peut se contenter des lectures provenant du CPU et des échanges avec la RAM. Le cache d'instructions est donc très souvent en « lecture seule » : le processeur ne peut pas écrire dedans, mais juste le lire ou charger des instructions dedans.

Un cache d'instruction est donc plus simple qu'un cache pour les données : on peut retirer les circuits en charge de l'écriture (mais on doit laisser un port d'écriture pour charger les instructions dedans). Le gain en circuits permet d'utiliser un cache d'instruction plus gros ou au contraire de laisser de la place pour le cache de données. Le gain en termes de capacité compense alors un peu les inconvénients des caches séparés.

Par contre, cela complique la gestion du code automodifiant, c'est-à-dire des programmes dont certaines instructions vont aller en modifier d'autres, ce qui sert pour faire de l'optimisation ou est utilisé pour compresser ou cacher un programme (les virus informatiques utilisent beaucoup de genre de procédés). Quand le processeur exécute ce genre de code, il ne peut pas écrire dans ce cache L1 d'instructions, mais doit écrire dans le cache L2 ou en RAM, avant de recharger les instructions modifiées dans le cache L1. Cela qui prend du temps et peut parfois donner lieu à des erreurs si le cache L1 n'est pas mis à jour.

Le cache d'instruction est souvent bloquant

Un point important est que les caches d'instructions sont généralement des caches bloquants. Il ne servirait à rien de rendre un cache d'instruction non-bloquant, le cout en circuits ne se traduirait pas par une augmentation significative des performances.

L'usage d'un cache L1 unique demande d'utiliser un cache multiport

En théorie, on pourrait utiliser un cache L1 unique et le relier à la fois au séquenceur et au chemin de données. Mais utiliser un seul cache unifié demanderait un effort de câblage assez important, le cache devant être à la fois proche du séquenceur et du chemin de données. Les connexions entre le cache L1 unifié et le reste du processeur sont donc assez longues, tortueuses, et difficiles à câbler. De plus, ces longues connexions font que le transfert des bits prend plus de temps pour traverser le fil en longueur, ce qui pose des problèmes à haute fréquence. Avec deux caches séparés, on n'a pas ce problème, ce qui permet de garder des caches L1 très rapides. La lenteur et les problèmes de connexion sont reportés aux connexions entre les caches L1 et le cache L2, mais celui-ci accepte des temps d'accès plus longs.

Sur les processeurs modernes, il arrive très souvent que le processeur doive charger une instruction et lire/écrire une donnée en même temps. Et à vrai dire, c'est la règle plus que l'exception. L'usage d'une architecture Harvard modifiée permet cela très facilement : on peut accéder au cache d'instruction via un bus, et au cache de donnée avec l'autre. Mais cet avantage peut s'obtenir avec un cache L1 unique, en utilisant un cache multiport, avec un port relié au séquenceur et un autre au chemin de données. Et le choix entre les deux n'est pas évident. Les caches multiports sont clairement une solution viable : les caches L2 et L3 sont tous des caches multiports. Là encore, tout est histoire de compromis : les mémoires multiport sont plus lentes, plus grosses, plus compliquées à fabriquer. L'impact en termes de temps d'accès est en faveur de la mémoire simple port, tout comme la simplicité de conception. Mais pour ce qui est de l'économie de circuits, c'est moins évident. Entre deux mémoires simple port et une mémoire multiport, la différence en termes de transistors est ambigüe et dépend de la capacité des caches. Pour les caches L1 de petite capacité, le temps d'accès est très important, ce qui favorise les caches séparés. De plus, utiliser deux caches séparés n'a pas trop d'impact sur le budget en transistors, car les caches L1 sont petits. Par contre, pour les caches L2/L3/L4, le temps d'accès n'est pas déterminant, alors que l'économie en circuits est significative.

Et cette histoire de cache simple ou multiport est de plus en plus contraignante. Les processeurs modernes sont capables d’exécuter plusieurs instructions en parallèle, comme on le verra dans quelques chapitres. Et la conséquence est que les caches L1 doivent être capables de lire/écrire plusieurs données en même temps, tout en chargeant plusieurs instructions simultanément. Les deux caches L doivent donc être multiports tous les deux. Le choix est donc entre deux caches avec chacun un nombre limité de ports, ou un cache unique avec beaucoup de ports. S'il fallait utiliser un cache unique, celui-ci aurait au moins une dizaine de ports, voire plus, ce qui serait impraticable. Les concepteurs de processeurs se facilitent la vie en utilisant deux caches séparés avec peu de ports. Mais le fond du compromis est le même : soit un cache rapide avec peu de ports, soit un cache plus lent avec beaucoup de ports.