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

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

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

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

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 touttous les tags présents dans le cache. Si ilS’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.

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

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 lal’a vu dans le chapitre dédié à ce type de mémoires. Et on peut dire que dans le cas d'un cache, l'implémentation est encore plus simple et se contente d'un seul registre/compteur. Typiquement, il suffit d'ajouter un registre qui mémorise où se situe la donnée la plus récente. Toute insertion d'une nouvelle donnée se fait à l'adresse suivante, ce qui demande juste d'incrémenter le registre avant d'utiliser son contenu pour l'accès mémoire.

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

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

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

Sans optimisationsoptimisation 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écritures en RAM. C'est une mémoire FIFO dans laquelle on place temporairement les données à écrire en RAM, où elles attendent en attendant que la RAM soit libre. Grâce à lui, le processeur peut écrire dans un cache même si d'autres écritures sont en attente dans le tampon d'écriture. Par souci d'efficacité, des écritures à la même adresse en attente dans le tampon d’écriture sont fusionnées en une seule. Cela fait un peu de place dans le tampon d’écriture, et lui permet d'accumuler plus d'écritures avant de devoir bloquer le cache. Il est aussi possible de fusionner des écritures à adresses consécutives de la mémoire en une seule écriture en rafalerafales. 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.

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.

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 programmeprogrammes 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 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 faiblefaibles 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'''.

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

Les caches non bloquants sont de deux types, qui portent les noms barbarebarbares de caches de type succès après défaut et défaut après défaut. Sur le premier type, il ne peut pas y avoir plusieurs défauts de cache simultanés. Le second type est plus souple et autorise la survenue de plusieurs défauts de cache simultanés, jusqu'à une certaine limite. Dans ce qui va suivre, nous allons voir comment ces deux types de cache fonctionnent et comment ils sont fabriqués.

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

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

La fusion de deux défauts de cache est ainsi assez simple. Si deux défauts de cache à la même adresse lisent des mots mémoire différents, il suffit de configurer les entrées convenablement. Le premier défaut configurera ses entrées, et le second aura les siennes. Avec cette organisation, le nombre de MSHR indique combien de lignes de cache peuvent être lues en même temps depuis la mémoire. Quant auxau 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ésinventé 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 :

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 auxau 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éeentrées chacun, on va utiliser n × m MSHR inversés. La différence, c'est que plusieurs MSHR peuvent contenir un tag identique, contrairement aux MSHR adressés implicitement et explicitement. Lorsqu'un défaut de cache a lieu, chaque MSHR est vérifié. Si jamais aucun MSHR ne contient de tag identique à celui utilisé par le défaut, un MSHR vide est choisi pour stocker ce défaut, et une requête de lecture en mémoire est lancée. Dans le cas contraire, un MSHR est réservé au défaut de cache, mais la requête n'est pas lancée. Quand la donnée est disponible, les MSHR correspondant à la ligne qui vient d'être chargée vont être utilisés un par un pour résoudre les défauts de cache en attente.

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

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

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éesdonnée dans le tableau/la structure. Le processeur lit généralement l'adresse de base et le décalage (la constante à ajouter) depuis deux registres et c'est l'unité d'accès à la mémoire qui fait l'addition. Mais dans certains cas, l'addition peut être faite directement dans la mémoire cache, voire omise ou remplacée par des opérations plus simples. Les optimisations qui permettent cela donnentdonne 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.

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