Wikilivres

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

Navigation interactive dans l’historique
← Modification précédenteModification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
Ligne 99 :
* soit par autre chose.
 
==RemplacementLe 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.
Ligne 121 :
===MRU : most recently used===
 
Avec l'algorithme MRU, la donnée qui est effacéeremplacée est celle qui a été utilisée le plus récemment. Cet algorithme s'implémente simplement avec un registre, dans lequel on place le numéro de la dernière ligne de cache utilisée.

Cet algorithme de remplacement est très utile quand un programme traverse des tableaux du premier élément jusqu'au dernier : les données du tableau sont rarement réutilisées, rendant le cache inutile. Il est prouvé que dans ces conditions, l'algorithme MRU est optimal. Mais dans toutes les autres conditions, cet algorithme a des performances assez misérables.
 
===LFU : least frequently used===
 
Avec l'algorithme LFU, la donnée supprimée est celle qui est utilisée le moins fréquemment. Cet algorithme s'implémente en associant un compteur à chaque ligne de cache., Àqui chaqueest foisincrémenté qu'onà litchaque ouaccès écrit dans cette ligne de cache, le compteur associé est incrémentémémoire. La ligne la moins récemment utilisée est celle dont le compteur associé a la plus petite valeur. Implémenter cet algorithme prend pas mal de transistors, :car il faut rajouter autant de compteurs qu'il y a de lignes de cache, en plus d'un circuit pour déduirecomparer quelles compteur contient la plus petite valeurcompteurs 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.
 
[[File:Algorithme LFU de remplacement des lignes de cache.png|centre|Algorithme LFU de remplacement des lignes de cache]]
Ligne 131 ⟶ 133 :
===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 qu'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 l'algorithme LRU peut se faire de différentes manières. Dans tous les cas, cesqui techniquesont sontpour baséespoint sur un même principe : les circuits reliés au cache doiventcommun d'enregistrer les accès au cache pour en déduire la ligne la moins récemment accédée. La premièremanière la plus techniquesimple 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.
 
===ApproximationsLes 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.
Récupérée de « https://fr.wikibooks.org/wiki/Fonctionnement_d%27un_ordinateur/Les_mémoires_cache »