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

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
m →‎Le cache de boucle : Suppression de la partie sur le Cache de boucles qui est maintenant placé dans un autre chapitre, en plus détaillé
Ligne 248 : Ligne 248 :


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

===Le cache de boucle===

Il est possible d'optimiser le fonctionnement des boucles sur les processeurs pipelinés. D'ordinaire, lorsqu'une instruction doit être exécutée plusieurs fois dans un temps très court, elle doit être chargée depuis la mémoire et décodée, puis exécutée plusieurs fois. Sur les processeurs qui disposent de pipelines, ce chargement répété peut être omis en utilisant un cache de boucle, un cache chargé de stocker les dernières instructions chargées et/ou décodées. Si une instruction doit être réexécutée (signe d'une boucle), il suffit d'aller chercher l'instruction directement dans le cache de boucle, au lieu de la recharger. Néanmoins, ce cache ne peut stocker qu'un nombre limité d'instructions, ce qui limite la taille des boucles pouvant profiter de ce cache.


===Les caches à accès non-uniforme===
===Les caches à accès non-uniforme===

Version du 17 novembre 2021 à 00:45

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.

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. Un cache est une mémoire associative : tout accès mémoire sera intercepté par le cache, qui vérifiera si la donnée demandée est présente ou non dans le cache. Si c'est le cas, 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) : on est obligé d’accéder à la RAM ou de recopier notre donnée de la RAM dans le cache. 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. En effet, plus celui-ci est élevé, plus on accède au cache à la place de la RAM et 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, celle-ci (l’instruction ou la donnée) n'a pas encore été chargée dans le cache. Le défaut de cache est inévitable : ce genre de défaut de cache s'appelle un défaut à froid (cold miss). Si on accède à beaucoup de données, le cache finit par être trop petit pour conserver les anciennes données : elles vont quitter le cache, et toute tentative ultérieure d'accès 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é.

Tag d'une ligne de cache

Cache hash table
Cache hash table

Les données présentes dans le cache sont (pré)chargées depuis la mémoire : toute donnée présente 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, on ajoute des bits supplémentaires à chaque ligne de cache, qui contiennent une partie (voir la totalité) des bits de l'adresse mémoire correspondante. Ces bits supplémentaires forment ce qu'on appelle le tag. Quand notre cache reçoit une demande de lecture ou écriture, il va comparer le tag de chaque ligne avec les bits de poids fort de l'adresse à lire ou écrire. Si une ligne contient ce tag, alors c'est que cette ligne correspond à l'adresse, et c'est un défaut de cache sinon. Cela demande de comparer le tag avec un nombre de lignes de cache qui peut être conséquent, et qui varie suivant l'organisation du cache.

Tag d'une ligne de cache.
Tag d'une ligne de cache.

Sur certains caches assez anciens, on pouvait transférer nos 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.
Cache à secteurs.

Adresses physiques ou logiques ?

L’interaction entre caches et mémoire virtuelle donne lieu à un petit problème : l'adresse utilisée lors de l'accès au cache est-elle une adresse physique ou virtuelle ? Et bien cela varie suivant le processeur : certains caches utilisent une correspondance entre une adresse virtuelle et une ligne de cache, tandis que d'autres l'effectuent avec l'adresse physique. Notre cache peut donc être placé aussi bien avant qu'après la MMU. 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.
Adressages physique et virtuel.

Vérification des tags

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 quatre types de caches :

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

Les caches directement adressés

Avec ce genre de caches, le contenu d'une adresse mémoire sera chargée dans une ligne de cache prédéfinie, toujours la même, quelles que soient les circonstances. 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 devront se partager la même ligne de cache. Si on a besoin de manipuler fréquemment des données qui se partagent la même ligne de cache, chaque accès à une donnée supprimera l'autre du cache : tout accès à l'ancienne donnée 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 quelque peu… comique, ce qui réduit les gains de performances gagnés de part leur faible temps d'accès.

Cache adressé directement.
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, afin de simplifier les circuits de gestion du cache. 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
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.
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 et les tags. Un mot mémoire de cette RAM contient une ligne de cache, avec son tag (parfois, on utilise une mémoire séparée pour les tags). Chaque ligne étant sélectionnée par son index, on devine aisément que l'index de notre ligne de cache sera envoyée sur le bus d'adresse de notre mémoire RAM pour sélectionner celle-ci. Ensuite, il suffira de comparer le tag récupéré avec le tag de l'adresse à lire ou écrire. On saura alors si on doit faire face à un défaut de cache. Ensuite, on devra sélectionner la bonne donnée dans notre ligne de cache avec un ensemble de multiplexeurs.

Cache directement adressé.
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.
Cache totalement associatif.

Une adresse mémoire ne peut pas servir à identifier une ligne en particulier : elle est donc 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 seule égalité, pas de défaut de cache. Quelques comparateurs (un par ligne de cache), et un arbre de portes ET suffit.Toutes nos lignes de caches sont reliées à un bus interne qui permettra de relier chaque ligne de cache à l’extérieur. Si les deux tags sont identiques, la ligne de cache associée est la bonne, et elle doit être connectée sur le bus : on relie donc la sortie du comparateur à des transistors chargés de connecter ou de connecter les lignes de cache sur notre bus. Ensuite, 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.
Organisation générale d'un cache totalement associatif.

Les caches associatifs par voie

Les caches précédents ont chacun leur défaut : un taux de succès médiocre pour les premiers, et un temps d'accès trop long pour les autres. Certains caches implémentent une sorte de compromis destiné à trouver un juste milieu : ce sont les caches associatifs par voie. Pour simplifier, ces caches sont composés de plusieurs caches directement adressés accessibles en parallèle, chaque cache étant appelé une voie.

Cache associatif par voie.
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.
Implémentation d'un cache associatif par voie.

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.
Implémentation d'un cache skew associative.

Les caches associatifs par voie sont donc une sorte de compromis entre caches directement adressés et caches totalement associatifs, avec un taux de succès et un temps d'accès intermédiaire. Pour réduire ce temps d'accès, 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 va accéder à la donnée de façon précoce, et commencer à l'utiliser un à deux cycles plus tôt que prévu. S'il se trompe, le processeur devra annuler la lecture effectuée en avance, et recommencer en allant chercher la donnée dans le bon ensemble. Cette technique peut être adaptée de façon à diminuer la consommation énergétique du processeur. Pour cela, il suffit de mettre en veille tous les caches directement adressés sur lesquels le processeur n'a pas parié. C'est plus efficace que d'aller lire plusieurs données dans des mémoires différentes, et n'en garder qu'une.

En vertu du principe de localité, on peut décemment penser que si on a accédé à une voie, les accès futurs auront lieu dans celle-ci. 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 au résultat obtenu après vérification des tags. Cependant, on peut complexifier l'implémentation pour prendre en compte un paramètre assez important : on peut discriminer la voie à choisir en tenant compte de paramètres comme l'adresse à lire/écrire, ou l'instruction à l'origine de l'accès mémoire. En effet, 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 les voies à mémoriser : une par instruction. On peut aussi utiliser le même mécanisme pour faire la différence non pas suivant l'instruction à l'origine de l'accès au cache, mais en fonction de l'adresse à lire, ou des numéros de registre, voire des données utilisées pour calculer l'adresse.

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.

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.

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 va obligatoirement choisir une ligne de cache à remplacer et recopier son contenu dans la RAM. Difficile de faire la sélection en utilisant nos tags. Pour résoudre ce problème, le circuit de remplacement des lignes de cache va adresser chaque ligne de cache ! Eh oui, vous avez bien vu : chaque ligne de cache sera numérotée par une adresse, interne au cache.

Aléatoire

Premier algorithme : la donnée effacée du cache est choisie au hasard ! Si l'on dispose d'un cache avec n lignes, cet algorithme s'implémente avec un circuit qui fournit un nombre pseudo-aléatoire compris entre 0 et n. Contrintuitivement, cet algorithme donne des résultats assez honorables, en plus d'utiliser très peu de portes logiques. Reste à implémenter cet algorithme. Pour cela, on peut utiliser un compteur qui s'incrémente à chaque cycle d'horloge. 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. Mais il est aussi possible d'utiliser des circuits un peu plus élaborés, à savoir des registres à décalage à rétroaction linéaire.

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 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 est un des plus simple à implémenter en circuit : un vulgaire compteur suffit. On peut insérer les données dans le cache les unes à la suite des autres. Exemple : si j'ai inséré une donnée dans la ligne de cache numéro X, alors la prochaine donnée ira dans la ligne numéro X+1. Si jamais on déborde, on revient automatiquement à zéro. En faisant ainsi, nos lignes de cache seront triées de la plus ancienne à la plus récente automatiquement. La ligne de cache la plus ancienne sera localisée à un certain endroit, et la plus récente sera localisée juste avant. Il suffit de se souvenir de la localisation de la donnée la plus ancienne avec un compteur par voie, et le tour est joué.

Algorithme FIFO de remplacement des lignes de cache.
Algorithme FIFO de remplacement des lignes de cache.

MRU : most recently used

Avec l'algorithme MRU, la donnée qui est effacé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. À chaque fois qu'on lit ou écrit dans cette ligne de cache, le compteur associé est incrémenté. 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 : il faut rajouter autant de compteurs qu'il y a de lignes de cache, en plus d'un circuit pour déduire quel compteur contient la plus petite valeur et en déduire la ligne de cache en question. Le circuit qui détermine quel compteur a la plus petite valeur est composé d'un grand nombre de comparateurs et quelques portes logiques ET. L'autre circuit est 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 que si une donnée a été accédée récemment, alors elle a de fortes chances d'être réutilisée dans un futur proche. Et inversement, toute donnée peu utilisée récemment a peu de chances d'être réutilisée dans le futur. D'après le principe de localité temporelle, la donnée la moins récemment utilisée du cache est donc 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 cet algorithme LRU peut se faire de différentes manières. Dans tous les cas, ces techniques sont basées sur un même principe : les circuits reliés au cache doivent enregistrer les accès au cache pour en déduire la ligne la moins récemment accédée. La première technique 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.

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.

Write-back et write-through

L'écriture dans un cache fait face à diverses situations, qu'il faut gérer au mieux. Pour gérer certaines situations embarrassantes, deux stratégies d'écritures sont couramment implémentées dans les circuits de gestion du cache :

  • le write-back ;
  • et le write-through.

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. On parle alors de caches Write-Back.

Cache write-through
Cache write-through

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
Cache d’éviction

Les caches directement adressés ou associatifs par voie possèdent aussi un tampon d’écriture amélioré, qui devient un cache en supplément du cache principal. 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.
Cache de victime.

Write-through

Avec les caches Write-Through, toute écriture dans le cache est propagée en RAM.

Cache write-back
Cache write-back

Ces caches ont tendance à commettre beaucoup d'écritures dans la mémoire RAM, ce qui peut saturer le bus reliant le processeur à la mémoire. De plus, on ne peut écrire dans ces caches lorsqu'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 ces temps d'attentes, certains processeurs avec un cache write-through intègrent un tampon d’écriture, une mémoire FIFO dans laquelle on place temporairement les données à transférer du cache vers la RAM en attendant que la RAM soit libre. On n'a pas à se soucier du fait que la mémoire soit occupée, et on peut continuer à écrire dedans tant que celui-ci n'est pas plein, évitant les temps d'attente dus à la RAM. 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. Ainsi, si la taille d'une ligne de cache est petite, comparée à ce qu'une mémoire accepte en écriture en rafale, on peut gagner un peu de performances. Dans les deux cas, on parle de combinaison d'écriture.

Reste à gérer le cas où 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. 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. Pour cela, chaque entrée du tampon d’écriture contient un comparateur : à chaque lecture, l'adresse à lire est envoyée à ce comparateur, qui vérifie que l'adresse de la lecture et l'adresse de la donnée à écrire sont différentes. Si jamais ces deux adresses sont identiques, alors la lecture souhaite lire la donnée présente dans l'entrée, et la lecture est mise en attente. Sinon, la lecture a lieu sans attente.

Comportement d’allocation sur écriture

Les écritures posent un autre problème : l'écriture ne va modifier qu'une portion d'une ligne de cache. Que faire quand l'écriture modifie une donnée qui n'est pas dans le cache ? Doit-on charger la ligne de cache correspondante, ou non ?

Allocation sur écriture

La première solution est simple : on alloue une ligne de cache pour l'écriture. On parle de stratégie d’allocation sur écriture (ou write-allocate). Cette solution permet d'implémenter les écritures relativement facilement. Elle peut se décliner en deux sous-catégories : le chargement à la demande et l'écriture immédiate. Dans le premier cas, on charge le bloc à modifier dans le cache, et on effectue l'écriture sur la donnée chargée dans le cache. Dans l'écriture immédiate, le bloc de mémoire n'est pas chargé dans le cache. Une ligne de cache est allouée, et l'écriture a lieu dedans. É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.
Cache Write-back avec allocation sur écriture.

Pas d'allocation sur écriture

Sur certains caches, on ne réserve pas de ligne de cache pour effectuer l'écriture. Dans ce cas, l'écriture est transférée directement aux niveaux de cache inférieurs, ou à la mémoire. Le cache ne prend pas en charge l'écriture. 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.
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.

Caches inclusifs

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 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. Certains chercheurs ont alors décidé de ruser : ils acceptent d'avoir 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.

Contourner le cache : le cache bypassing

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 les données utiles à l'exécution. Cette méthode repose sur l'identification des instructions à l'origine des défauts de cache, le processeur accédant directement à la RAM quand une telle instruction est détectée.

Pour identifier ces instructions, le processeur dispose d'une mémoire, qui mémorise les program counters des instructions d'accès mémoire déjà rencontrées lors de l'exécution du programme. On appelle cette mémoire la table d’historique des défauts de lecture (load miss history table). À chaque nouvelle exécution d'une instruction d'accès mémoire, une entrée de cette mémoire est réservée pour l'instruction. Chaque adresse est couplée à un compteur de quelques bits, qui est incrémenté à chaque succès de cache et décrémenté à chaque défaut de cache. À chaque fois que l'on exécute une instruction, son program counter est envoyé en entrée de la table d’historique des défauts de lecture. Si jamais l'instruction était déjà présente dans celle-ci, la valeur du compteur est récupérée et le processeur vérifie celle-ci. Si elle tombe en dessous d'un certain seuil, c'est que l'instruction a commis trop de défauts de cache et qu'il faut éviter de lui allouer du cache.

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.