« Fonctionnement d'un ordinateur/Les mémoires cache » : différence entre les versions

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
Ligne 115 : Ligne 115 :
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 la 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.
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 la 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.


[[File:Algorithme FIFO de remplacement des lignes de cache.png|centre|Algorithme FIFO de remplacement des lignes de cache.]]
[[File:Algorithme FIFO de remplacement des lignes de cache.png|centre|vignette|upright=2|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'''.
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'''.

Version du 17 novembre 2021 à 18:51

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 est divisé en groupes de plusieurs bytes (de 64 à 256 octets chacun), qui portent le nom de lignes de cache. Sur les caches actuels, on transfère les données entre le cache et la RAM ligne de cache par ligne de cache. 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.

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. Le nombre de succès de cache par nombre d'accès mémoire , appelé le taux de succès (hit ratio), est déterminant pour les performances : plus il est élevé, plus le cache est efficace.

Les défauts de cache peuvent avoir des origines diverses. Lorsqu'on exécute une instruction ou qu'on accède à une donnée pour le première fois, il se produit un défaut à froid (cold miss). La raison est que l'instruction ou la donnée n'a pas encore été chargée dans le cache, ce qui rend le défaut de cache inévitable. Autre situation : le cache est trop petit pour les besoins et le cache fait alors le ménage, en retirant des données du cache. Toute tentative ultérieure aux données qui ont quitté le cache tombera en RAM, donnant un défaut de volume de cache (capacity cache miss). Les seules solutions pour éviter cela consistent à augmenter la taille du cache, faire en sorte que le programme prenne moins de mémoire cache, et améliorer la localité du programme exécuté.

Le tag d'une ligne de cache

Cache hash table

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. Pour faire la correspondance entre une ligne de cache et l'adresse mémoire correspondante, la ligne de cache mémorise tout ou partie de l'adresse mémoire correspondante. Les bits de l'adresse mémoire qui sont mémorisés dans la ligne de cache forment dce qu'on appelle le tag. Lors d'un accès mémoire, le cache extrait le tag de l'adresse à lire ou écrire, et compare celui-ci avec les tag 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.

Tag d'une ligne de cache.

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

Cache à secteurs.

L'adressage physique ou logique des caches

Adressages physique et virtuel.

L’interaction entre caches et mémoire virtuelle donne lieu à un petit problème : l'adresse utilisée pour les tags est-elle une adresse physique ou virtuelle ? 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. Un cache virtuellement tagué n'a pas besoin d'attendre que la MMU ait fini de traduire l'adresse logique en adresse physique pour vérifier la présence de la donnée dans le cache : ces caches sont donc plus rapides. Mais les problèmes arrivent facilement quand on utilise plusieurs programmes : une adresse logique correspond à des adresses physiques différentes suivant le programme. Pour éviter toute confusion, on peut rajouter des bits de contrôle pour identifier le programme qui possède la ligne de cache. On peut aussi vider le cache en changeant de programme. Les caches physiquement tagués ont les avantages et inconvénients inverses : moins rapides, ils permettent un partage du cache entre plusieurs programmes aisément.

Cache tagué virtuellement.
Cache tagué physiquement.

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 :

  • directement adressés, ou direct mapped ;
  • associatifs par voie ;
  • totalement associatifs.

Les caches directement adressés

Avec les caches directement adressés, le contenu d'une adresse mémoire est chargée dans une ligne de cache prédéfinie, toujours la même. L'accès au cache a donc 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). Ainsi, le taux de succès de ce genre de cache est assez faible.

Cache adressé directement.

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é. Chaque ligne de cache possède un indice, une sorte d'adresse interne qui permet de l'identifier et la sélectionner parmi toutes les autres lignes. Il ne s'agit pas vraiment d'une adresse, vu que le cache n'est pas adressable via le bus d'adresse.

Cache hash table - 2

Avec cette implémentation, l'adresse mémoire doit permettre de spécifier l'index de la donnée. Le tag correspond aux bits de poids fort de l'adresse mémoire correspondant à notre ligne de cache. Le reste des bits de l'adresse représente l'index de notre ligne, et la position de la donnée dans la ligne.

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. La mémoire RAM stocke les lignes de caches complète, mais il arrive que l'on utilise deux mémoires RAM : une pour les tags et une pour les données. 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é.

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é, vu qu'il n’y a pas de possibilité de défaut par conflit.

Cache totalement associatif.

Sur ces caches, il n'a pas d'index ou quoique ce soit du genre. L'adresse mémoire est donc juste découpée en un tag, et de quoi identifier la position de la donnée dans la ligne de cache correspondante. Pour déterminer l’occurrence d'un défaut de cache, il suffit de comparer le tag de l'adresse avec tout les tags présents dans le cache. Si il y a une égalité, pas de défaut de cache. Quelques comparateurs (un par ligne de cache), et un arbre de portes ET suffit pour faire cette comparaison. La ligne pour laquelle il y a eu une égalité est alors connectée sur la sortie de donnée du 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, comme pour les autres caches.

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

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, qui sont accessibles en parallèle, chaque cache étant appelé une voie. Les caches associatifs par voie ont donc un taux de succès et un temps d'accès intermédiaire.

Cache associatif par voie.

L'adresse d'une case mémoire 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.

Les caches pseudo-associatifs

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

Les caches skew associative

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

Implémentation d'un cache skew associative.

La prédiction de voie

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

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

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

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

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 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 la 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
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

Comme on l'a vu, implémenter le LRU coute cher en transistors, le nombre de transistors utilisés étant proportionnel au carré du nombre de lignes de cache. Autant dire que le LRU devient impraticable sur de gros caches. Pour résoudre ce problème, nos processeurs implémentent des variantes du LRU, moins couteuses en transistors, mais qui ne sont pas exactement du LRU : ils donnent un résultat assez semblable au LRU, mais un peu plus approximatif. 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. Il faut dire que 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 : cela aura une influence assez faible 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 peuvent donner des résultats impressionnants.

L'algorithme le plus simple consiste à couper le cache (ou chaque ensemble du cache s'il est associatif à voie) en deux. L'algorithme consiste à choisir le morceau de cache le moins récemment utilisé, et de choisir aléatoirement une ligne de cache dans ce morceau. Pour implémenter cet algorithme, il nous suffit d'une simple bascule qui mémorise le morceau le moins récemment utilisé, et d'un circuit qui choisit aléatoirement une ligne de cache dans ce morceau. On peut aussi généraliser cette technique avec plus de deux morceaux de cache : il suffit juste de rajouter quelques circuits. Dans ce cas, cette technique s'adapte particulièrement bien avec des cache associatifs à n voies : il suffit d'utiliser autant de morceaux que de voies, de sous-caches adressés directement. En effet, avec un cache adressé directement, on a juste à savoir quelle est la voie la moins utilisée, sans se préoccuper de la ligne exacte : la ligne dans laquelle écrire dépendra uniquement de l'adresse de la donnée chargée, en raison du caractère directement adressé de la voie.

Autre algorithme, un peu plus efficace : le pseudo-LRU de type m. Cet algorithme est assez simple : à chaque ligne de cache, on attribue un bit. Ce bit sert à indiquer de façon approximative si la ligne de cache associée est une candidate pour un remplacement ou non. Si ce bit est à 1, cela veut dire : attention, cette ligne n'est pas une candidate pour un remplacement. Inversement, si ce bit est à zéro, la ligne peut potentiellement être choisie pour laisser la place aux jeunes. Lorsqu'on lit ou écrit dans une ligne de cache, ce bit est mis à 1. Histoire de dire : pas touche ! Évidemment, au fil du temps, toutes les lignes du cache finiront par avoir leur bit à 1. Aussi, l'algorithme permet de remettre les pendules à l'heure. Si tous les bits sont à 1, on les remet tous à 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. Tout commence lorsque l'on remet tous les bits associés aux lignes de cache à 0 (sauf pour la ligne accédée en dernier). Puis, au fur et à mesure que nos lignes de cache voient leurs bits passer à un, l'étau se resserre autour de notre ligne de cache la moins utilisée. Et on finit par l'encercler de plus en plus : au final, après quelques accès, l'algorithme donne une estimation particulièrement fiable. Et comme les remplacement 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 dans la majorité des programmes. Du moment que notre programme respecte relativement bien la localité temporelle, cet algorithme donnera de très bons résultats : le taux de succès du cache sera très élevé. Par contre, cet algorithme se comporte assez mal dans certaines circonstances, et notamment quand on traverse des tableaux. Dans ces conditions, on n'a pas la moindre localité temporelle, mais une bonne localité spatiale. Pour résoudre ce petit inconvénient, des variantes du LRU existent. Une première de ces variante, 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 doivent migrer du cache FIFO vers le cache LRU : cela consomme du matériel, de l'énergie et des cycles d'horloge. 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 optimisations 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 écriture 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 rafale. 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. A 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 soit rapatriée en RAM. Ainsi, la nouvelle ligne est disponible plus tôt pour le processeur, diminuant son temps d'attente. Pour implémenter cette technique, on doit mémoriser l'ancienne ligne de cache temporairement dans un cache d’éviction (ou write-back buffer).

Cache d’éviction

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

Cache de victime.

L’allocation sur écriture

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

Avec allocation sur écriture

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

Cache Write-back avec allocation sur écriture.

Sans allocation sur écriture

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

Cache Write-through sans allocation sur écriture.

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.

Cohérence des caches.

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 inférieur, le cache L2. Et rebelote ! Si elle n'y est pas, on vérifie le cache du niveau inférieur. Et on répète cette opération, jusqu’à avoir vérifié tous les caches. Si la donnée n'est dans aucun cache, on doit alors aller chercher la donnée en mémoire.

Hiérarchie de caches

Les caches exclusifs et inclusifs

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

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

Caches exclusifs

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

Caches inclusifs

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

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

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

Les caches d'instructions

Sur certains processeurs, il y a deux caches L1 séparés : un cache dédié aux instructions, et un autre pour les données. Ils sont reliés au reste du processeur par des bus séparés, ce qui permet de charger une instruction et manipuler une donnée en même temps, ce qui est un gros avantage en termes de performances.

Rien n’empêche aux deux mémoires cache L1 de vouloir lire ou écrire dans le cache L2 simultanément. Si le cache L2 gère ces écritures/lectures simultanées, pas de problème.

Cache d'instructions.

Mais s'il ne peut pas, on doit effectuer un arbitrage pour décider quel cache a la priorité.

Circuit d'arbitrage du cache.

Le cache L1 dédié aux instructions est souvent en « lecture seule » : on ne peut pas modifier son contenu, mais juste le lire ou charger des instructions dedans. Cela complique la gestion du code automodifiant, c'est-à-dire des programme 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 va devoir écrire en mémoire cache L2 ou en RAM, et va ensuite devoir recharger les instructions modifiées dans le cache L1, ce qui prend du temps ! Et pire : cela peut parfois donner lieu à des erreurs si le cache L1 n'est pas mis à jour.

Sur certains processeurs, l'étape de décodage est assez complexe et lente. Pour accélérer cette étape, 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.

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, mais cela gâche les faible latences des lignes de cache qui sont tout près du contrôleur de cache. 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.

Caches non bloquants

Un cache bloquant est un cache auquel le processeur ne peut pas accéder pendant un défaut de cache. Il faut alors attendre que la donnée voulue soit lue ou écrite dans la RAM avant de pouvoir utiliser de nouveau le cache. Un cache non bloquant n'a pas ce problème : on peut l'utiliser immédiatement après un défaut de cache. Cela permet d'accéder à la mémoire cache en attendant des données en provenance de la RAM. Tous les caches non bloquants peuvent ainsi permettre de démarrer une nouvelle lecture ou écriture alors qu'une autre est en cours. On peut ainsi exécuter plusieurs lectures ou écritures en même temps : c'est ce qu'on appelle du parallélisme au niveau de la mémoire (memory level parallelism). Mais au bout d'un certain nombre d'accès simultané, le cache va saturer et va dire « stop ». Il ne peut supporter qu'un nombre limité d'accès mémoires simultanés (pipelinés).

Succès après défaut

Ces caches non bloquants sont de deux types. Il y a ceux qui autorisent les lectures et écritures dans le cache pendant qu'un défaut de cache a lieu. Pendant un défaut de cache, le contrôleur mémoire va charger la donnée du défaut de cache depuis la mémoire : le cache n'est pas utilisé, ni en lecture, ni en écriture. Dans ces conditions, on peut modifier le contrôleur mémoire pour qu'il gère les succès de cache qui suivent le défaut : on peut donc lire ou écrire dans le cache. Mais le prochain défaut bloquera toute la mémoire cache, empêchant toute lecture ou écriture dedans. Les éventuels succès de cache qui pourront suivre ce deuxième défaut seront alors mis en attente.

Sur certaines mémoires cache, lors d'un défaut de cache, on doit attendre que toute la ligne concernée par le défaut de cache soit chargée avant d'être utilisable. Un cache stocke des lignes de cache dont la taille est supérieure à la largeur du bus mémoire. En conséquence, une ligne de cache est chargée en plusieurs fois, morceaux par morceaux. Certains se sont demandés si on ne pouvait pas gagner quelques cycles en jouant dessus. Eh bien c'est le cas ! Certains processeurs sont capables d'utiliser un morceau de ligne de cache tout juste chargé alors que la ligne de cache complète n'est pas totalement lue depuis la mémoire. Avec cette technique, le cache est utilisable lors d'un défaut de cache, ce qui fait qu'il est légèrement non bloquant. Ces processeurs incorporent un tampon de remplissage de ligne (line-fill buffer), une sorte de registre, qui stocke le dernier morceau d'une ligne de cache à avoir été chargé depuis la mémoire. Ce morceau est stocké avec un tag, qui indique l'adresse du bloc stocké dans le tampon de remplissage de ligne. Ainsi, un processeur qui veut lire dans le cache après un défaut peut accéder à la donnée directement depuis le tampon de remplissage de ligne, alors que la ligne de cache n'a pas encore été totalement recopiée en mémoire.

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

Défaut après défaut

Au-dessus, on a vu des caches capables de lire ou d'écrire lors d'un défaut. Ceux-ci sont incapables de mettre en attente d'autres défauts en attendant que le défaut en cours soit terminé. Mais sur d'autres caches, on peut gérer un nombre arbitraire de défaut de cache avant de bloquer, permettant ainsi aux lectures et écritures qui suivent un deuxième ou troisième défaut de fonctionner. Ceux-ci sont dits de type défaut après défaut (miss under miss).

Ceci dit, ces caches doivent être adaptés. Pendant qu'une lecture ou une écriture est démarrée par le contrôleur mémoire, il ne peut pas démarrer de nouvelle lecture ou écriture immédiatement après (sauf dans certains cas exceptionnels) : il y a toujours un temps d'attente entre l'envoi de deux requêtes d'accès mémoire. Dans ces conditions, les autres défauts doivent être mis en attente : la lecture/écriture doit être mémorisée, et est démarrée par le contrôleur mémoire une fois que celui-ci est libre, qu'il peut démarrer une nouvelle requête. Cette mise en attente s’effectue avec des miss status handling registers. Les miss status handling registers, que j’appellerais dorénavant MSHR, sont des registres qui vont mettre en attente les défauts de cache. Le nombre de MSHR indique combien de blocs de mémoire, de lignes de cache, peuvent être lues en même temps depuis la mémoire. Chacun de ces registres stocke au minimum trois informations :

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

Quand la donnée lue depuis la mémoire est devenue disponible, le MSHR correspondant (celui qui stockait l'adresse à lire) est invalidé : son bit de validité est mis à 0. D'autres informations peuvent être stockées dans un MSHR, mais cela dépend fortement du processeur. Sur les caches directement adressés ou associatifs à n voies, on peut par exemple stocker le numéro de la ligne de cache qui doit mémoriser la donnée chargée depuis la mémoire.

Je vais maintenant décrire le fonctionnement d'un cache non bloquant qui utilise des MSHR. Pour commencer, nous allons prendre le cas où l'adresse à lire ou écrire n'a pas subi de défaut de cache récent : il n'y a aucun défaut de cache en attente à cette adresse. Dans ce cas, il suffit de réserver un MSHR vide pour ce défaut. Maintenant, prenons un autre cas : un ou plusieurs défaut de cache sont déjà en attente pour cette même adresse. Détecter cette situation est simple : il suffit de comparer l'adresse du défaut avec celles déjà mises en attente dans les MSHR. Pour ce faire, chaque MSHR est relié à un comparateur, et avec quelques circuits. Dans ces conditions, certains caches mettent le cache en pause : celui-ci ne peut alors plus accepter de nouveau défaut de cache tant que le premier défaut de cache n'est pas résolu. Si deux défauts de cache différents veulent lire un même bloc de mémoire, le cache se met en pause au deuxième défaut de cache : il reste en pause tant que le premier défaut de cache n'est pas résolu. D'autres caches sont plus malins, et peuvent mettre en attente plusieurs défauts de cache qui tombent sur la même adresse.

Les MSHR sont une première avancée, qui permet à un processeur de gérer plusieurs défauts de cache dans des zones du cache différentes. Toutefois, un second accès mémoire à la même ligne de cache va bloquer le cache. On se retrouve alors dans deux cas. Dans le premier cas, les adresses des deux défauts de cache ont des tags différents : les zones de mémoire adressées lors des deux défauts de cache sont séparées dans la mémoire, et ne font pas partie du même bloc. Dans ce cas, le blocage du cache est inévitable. Le premier défaut de cache doit être géré avant que le second puisse démarrer. Dans l'autre cas, les tags sont identiques, mais pas les index et les décalages. Les données sont proches les unes des autres en mémoire, font partie du même bloc, mais ne se recouvrent pas : il s'agit de données placées les unes à côté des autres, qui seront localisées dans la même ligne de cache. Quand le premier défaut de cache sera résolu, les données du second défaut de cache seront présentes dans le bloc. Dans ces conditions, il est inutile de bloquer le cache : le second défaut de cache peut être fusionné avec le premier.

Pour éviter de bloquer le cache dans la seconde situation, certains caches traitent les requêtes avec une granularité plus fine. Leur principe est simple : quand un défaut de cache a lieu et que celui-ci va lire les données chargées par un défaut de cache précédent, les deux défauts sont fusionnés dans le même MSHR. Cette détection de coïncidence de l'adresse s'effectue lors de la vérification des MSHR : le tag contenu dans le MSHR est comparé avec le tag de l'adresse responsable du nouveau défaut de cache. Reste que les différents défauts de cache vont lire des données différentes dans le cache : les index et les décalages des adresses sont différents. Lorsque le défaut sera résolu, et que la donnée sera disponible, il faudra bien configurer le cache avec les index et décalages corrects. Dans ces conditions, il faut bien les mémoriser quelque part. Et les MSHR sont tout indiqués pour cela.

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

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

La fusion de deux défauts de cache est ainsi assez simple. Si deux défauts de cache vont lire des mots mémoire différents, il suffira de configurer les entrées de mot mémoire de chaque défaut convenablement. Le premier défaut configurera ses entrées, et le second aura les siennes. Le même MSHR sera réutilisé pour les deux défauts. Et on peut ainsi gérer bien plus de deux défauts : tant que des défauts de cache vont lire des mots mémoire différents, on peut les fusionner, sans vraiment de limite. Par contre, si deux défauts de cache veulent réserver la même entrée, alors là, c'est le drame : le cache se bloque automatiquement ! Avec cette organisation, le nombre de MSHR indique combien de lignes de cache peuvent être lues en même temps depuis la mémoire. Quant aux nombre d'entrées par MSHR, il détermine combien d'accès mémoires qui ne se recouvrent pas peuvent avoir lieu en même temps.

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

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

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

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

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

Le cache bypassing : contourner le cache

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

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

Ce qui est équivalent à faire le test suivant :

En complément à deux, on a . En injectant dans l'équation précédente, on a :

En réorganisant les termes, on a :

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ée s'appliquer à la colonne suivante. En notant la somme S et les retenues R, on a:

, le décalage d'un cran à gauche étant noté .

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

Sum + retenue add

Un simple raisonnement nous permet de savoir si le résultat est bien -1, sans faire l'addition . 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 . 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 :

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.