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

m
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.
 
==CachesLes caches adressés par somme et hashés==
 
Pour rappel, certains modes d'adressage ont besoin de faire des calculs d'adresse, les plus communs consistant à ajouter un décalage à une adresse.
 
===CachesLes caches hashés===
 
Pour éviter d'avoir à effectuer l'addition entre l'adresse et le décalage, certains concepteurs de mémoire cache ont donc cherchés à ruser en remplaçant cette l'addition par autre chose, notamment des opérations bit à bit du style XOR, AND ou OR, etc. De tels caches sont appelés des '''caches hashés'''. Seulement, utiliser des opérations bit à bit a un problème : il arrive que deux couples Adresse/décalage donnent la même adresse mémoire, après l'application de l’opération bit à bit. 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 était toutefois possible de gérer ces situations, mais cela nécessitait quelques techniques de haute volée pour faire fonctionner la mémoire cache correctement.
 
===CachesLes caches adressés par somme===
 
UneSur technique plus puissante a été inventé, donnant naissance auxles '''caches adressés par somme'''. Avec eux, le décodeur est modifié pour se passer de l'addition.
 
Pour comprendre comment font ceux-ci, 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.
 
[[File:InternalsNon ofsum decoderadressed cache.png|centre|Internalsvignette|upright=2|Cache of decodernormal.]]
 
Mais certains processeurs effectuent ce calcul directementl'addition dans le cache en modifiant ses décodeurs de celui-ci. En modifiant quelque peu la comparaison, on peut rendre le décodeur plus puissant, ce qui permet d'éviter de faire l'addition mentionnée plus haut. Le décodeur nouvelle version est composé de comparateurs qui testent si la somme adresse + décalage est égale à une constante. Ainsi, on peut se passer de l'addition en remplaçant les comparateurs par des circuits qui vérifient si la somme Adresse + décalage est égale à une constante. Si on sait créer ces circuits de base, il suffira d'en mettre plusieurs, de les calibrer convenablement, et le tour est joué !
Sur un cache ordinaire, l'addition est faite séparément du décodage des adresses par le cache : cette addition est parfois faite dans l'unité de calcul ou dans l'Adress Generation Unit.
 
[[File:NonCache sumadressé adressedpar cachesomme.png|centre|Nonvignette|upright=2|Cache sumadressé adressedpar cachesomme.]]
 
Notons qu'on peut simplifier les calculs en utilisant les règles du complément à deux. On sait que :
Mais certains processeurs effectuent ce calcul directement dans le cache en modifiant ses décodeurs de celui-ci. En modifiant quelque peu la comparaison, on peut rendre le décodeur plus puissant, ce qui permet d'éviter de faire l'addition mentionnée plus haut. Le décodeur nouvelle version est composé de comparateurs qui testent si la somme adresse + décalage est égale à une constante. Ainsi, on peut se passer de l'addition en remplaçant les comparateurs par des circuits qui vérifient si la somme Adresse + décalage est égale à une constante. Si on sait créer ces circuits de base, il suffira d'en mettre plusieurs, de les calibrer convenablement, et le tour est joué !
 
: <math> A + B += \overline{K} <=> A + B - 1K = 0</math>
[[File:Cache adressé par somme.png|centre|Cache adressé par somme.]]
 
En complément à deux, on a <math>- K = \overline{K} + 1</math>. En injectant dans l'équation précédente, on a :
Cette solution semble avoir un problème : on replace une seule addition par une addition suivie d'une comparaison. Mais on peut ruser fortement, de manière à simplifier les calculs. En effet, on sait que :
 
: <math> A + B =+ \overline{K <=> A} + B - K1 = 0 </math>.
 
En réorganisant les termes, on a :
On peut alors remplacer la soustraction en se souvenant que <math> - K = \overline{K} + 1</math>, ce qui donne :
 
: <math> A + B + \overline{K} += - 1 = 0 </math>
 
Il suffit d'utiliser un additionneur ''carry-save'' pour faire l'addition des trois termes, faire l'addition de la somme et des retenues et ajouter un comparateur avec -1. Or, on sait que -1, quelque soit la représentation (en complément) est codé avec un nombre dont tous les bits sont à 1 en complément à un/deux. Vérifier que l'addition donne bien -1 demande donc de vérifier que tous les bits du résultat sont à 1 : cela peut se faire avec une simple porte ET à plusieurs sorties.
<math> A + B + \overline{K} = - 1 </math>
 
[[File:Sum + retenue add.png|centre|vignette|upright=2|Sum + retenue add]]
Il suffit d'utiliser un additionneur carry-save pour faire l'addition des trois termes, et ajouter un comparateur avec -1. Or, on sait que -1, quelque soit la représentation (en complément) est codé avec un nombre dont tous les bits sont à 1. Vérifier que l'addition donne bien -1 demande donc de vérifier que tous les bits du résultat sont à 1 : cela peut se faire avec une simple porte ET à plusieurs sorties.
 
Le circuit est alors nettement plus simple que prévu : lL'additionneur pour l'addition adresse + décalage est remplacé par un additionneur carry-save, d'où des performances améliorées. Le temps total pour effectuer un accès au cache, calcul d'adresse compris, est donc réduit. Cette amélioration en performance est appréciable dans de nombreuses situations.
[[File:Sum + retenue add.png|centre|Sum + retenue add]]
 
[[File:CacheFinal adressécircuit parof sommesum addressed cache.png|centre|vignette|upright=2|Cache adressé par somme.]]
Le circuit est alors nettement plus simple que prévu : l'additionneur pour l'addition adresse + décalage est remplacé par un additionneur carry-save, d'où des performances améliorées. Le temps total pour effectuer un accès au cache, calcul d'adresse compris, est donc réduit. Cette amélioration en performance est appréciable dans de nombreuses situations.
 
[[File:Final circuit of sum addressed cache.png|centre|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 ouche de portes logiques. Le circuit de décodage économise aussi des portes logiques, ce qui est appréciable.
39 538

modifications