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

Implémenter l'algorithme LRU peut se faire de différentes manières, qui ont pour point commun d'enregistrer les accès au cache pour en déduire la ligne la moins récemment accédée. La manière la plus simple 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.

 

 

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.