|
====Les approximations du LRU====
Comme on l'a vu, implémenterImplémenter le LRU coutedemande cher en transistors, leun 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. PourCe résoudrequi cefait problème,que nosles processeurs modernes implémentent des variantes du LRU, moins couteuses en transistors, mais qui ne sont pas exactement du LRU : ils donnent un résultat assezapproximativement 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. IlCe fautn'est direpas 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 : 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 dessont résultatstrès impressionnantsintéressants.
L'algorithme le plus simple consiste à couper le cache (ou chaque ensemble du cachevoie s'il est associatif à voie) en deuxplusieurs sections. L'algorithme consistedétecte àquelle choisirest lela morceausection de cache lela moins récemment utiliséutilisée, etavant de choisir aléatoirement une ligne de cache dans cecette morceausection. Pour implémenter cet algorithme, il nous suffit d'une simpleun basculeregistre 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, cetteCette 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 mM'''. 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.
|
