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

Aller à la navigation Aller à la recherche
m
orthotypo
m (orthotypo)
==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 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 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é.
 
===Le tag d'une ligne de cache===
[[File:Cache hash table.png|vignette|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 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.
 
[[File:Tag d'une ligne de cache.png|centre|vignette|upright=2|Tag d'une ligne de cache.]]
[[File:Cache totalement associatif.png|centre|vignette|upright=2|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 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.
 
[[File:Organisation générale d'un cache totalement associatif.png|centre|vignette|upright=2|Organisation générale d'un cache totalement associatif.]]
==Le remplacement des lignes de cache==
 
Lorsqu'un cache est rempli et qu'on charge une nouvelle donnée dedans, il faut faire de la place pour cette dernière. Dans le cas d'un cache directement adressé, il n'y a rien à faire vu que la ligne de cache à évincer est déterminée lors de la conception du cache. Mais pour les autres caches, la donnée peut aller dans n'importe quelle ligne ou voie. Or, le choix des données à rapatrier en RAM doit être le plus judicieux possible : on doit virer de préférence des données inutiles. Rapatrier une donnée qui sera surement utilisée sous peu est inutile, et il vaudrait mieux supprimer des données qui ne serviront plus ou alors dans longtemps.
 
Il existe différents algorithmes spécialement dédiés à résoudre ce problème efficacement, directement câblés dans les unités de gestion du cache. Certains sont vraiment très complexes, aussi je vais vous présenter quelques algorithmes particulièrement simples.
===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 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.
 
[[File:Algorithme FIFO de remplacement des lignes de cache.png|centre|vignette|upright=2|Algorithme FIFO de remplacement des lignes de cache.]]
Implémenter le LRU demande un nombre de transistors proportionnel au carré du nombre de lignes de cache. Autant dire que le LRU devient impraticable sur de gros caches. Ce qui fait que les processeurs modernes implémentent des variantes du LRU, moins couteuses en transistors, qui donnent un résultat approximativement semblable au LRU. En clair, ils ne sélectionnent pas toujours la ligne de cache la moins récemment utilisée, mais une ligne de cache parmi les moins récemment utilisées. Ce n'est pas un problème si grave que cela car les lignes les moins récemment utilisées ont toutes assez peu de chance d'être utilisées dans le futur. Entre choisir de remplacer une ligne qui a 0,5 % de chances d'être utilisée dans le futur et une autre qui a une chance de seulement 1 %, la différence est négligeable en termes de taux de succès. Mais les gains en termes de circuits ou de temps d'accès au cache de ces algorithmes sont très intéressants.
 
L'algorithme le plus simple consiste à couper le cache (ou chaque voie s'il est associatif) en plusieurs sections. L'algorithme dé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.
 
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.
====LRU amélioré====
 
L'algorithme LRU, ainsi que ses variantes approximatives, sont très efficaces tant que le programme respecte relativement bien la localité temporelle. Par contre, Le LRU se comporte assez mal dans les circonstances ou la localité temporelle est mauvaise mais où la localité spatiale est respectée, le cas le plus emblématique étant lale parcours d'un tableau. Pour résoudre ce problème, des variantes du LRU existent.
 
Une variante très connue, l''''algorithme 2Q''', utilise deux caches : un cache FIFO pour les données accédées une seule fois et un second cache LRU. Évidemment, les données lues une seconde fois sont migrées du cache FIFO vers le cache LRU, ce qui n'est pas très pratique. Les processeurs n'utilisent donc pas cette technique, mais celle-ci est utilisée dans les caches de disque dur.
===Les caches ''Write-through''===
 
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.
 
===Les caches ''Write-back''===
[[File:Cache Hierarchy.png|vignette|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.
[[File:Circuit d'arbitrage du cache.png|centre|vignette|upright=2|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 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 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 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'''.
 
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.
Un '''cache bloquant''' est un cache auquel le processeur ne peut pas accéder pendant un défaut de cache. Il faut attendre que la lecture ou écriture en RAM soit terminée avant de pouvoir utiliser de nouveau le cache. Un '''cache non bloquant''' n'a pas ce problème : on peut l'utiliser pendant un défaut de cache. Tous les caches non bloquants permettent ainsi de démarrer une nouvelle lecture ou écriture alors qu'une autre est en cours. C, ce qui permet d'exécuter plusieurs lectures ou écritures en même temps. Mais le cache ne peut supporter qu'un nombre limité d'accès mémoires simultanés (pipelinés).
 
Su un cache bloquant, lors d'un défaut de cache, le cache et la mémoire RAM communiquent directement. Pendant un défaut de cache, le contrôleur mémoire charge la donnée depuis la mémoire et la copie plus ou moins directement dans le cache. Le cache étant utilisé, il ne peut pas être utilisé aussi bien 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.
 
===Les caches non bloquants de type succès après défaut===
===Les caches non bloquants de type défaut après défaut===
 
Au-dessus, on a vu des caches incapables de gérer plusieurs défauts simultanés.Voyons maintenant les caches 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'').
 
====Les ''miss status handling registers''====
* un bit de validité qui indique si le MSHR est vide ou pas et qui est mis à 0 quand le défaut de cache est résolu.
 
Supposons qu'un défaut de cache 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.
 
====Les accès simultanés à une même ligne de cache====
* un bit empty, qui dit si l'entrée est vide ou non.
 
La fusion de deux défauts de cache est ainsi assez simple. Si deux défauts de cache à la même adresse lisent des mots mémoire différents, il suffit de configurer les entrées convenablement. Le premier défaut configurera ses entrées, et le second aura les siennes. Avec cette organisation, le nombre de MSHR indique combien de lignes de cache peuvent être lues en même temps depuis la mémoire. Quant 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 :
* 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 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 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.
 
==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'à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.
 
==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é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.
 
===Les caches hashés===
: <math>A + B + \overline{K} = - 1</math>
 
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:
 
: <math>S + (R << 1) = - 1 </math>, le décalage d'un cran à gauche étant noté <math><< 1</math>.
40 609

modifications

Menu de navigation