Algorithmes de remplacement des lignes de cache - Définition

LRU améliorés

Les algorithmes LRU et pseudo-LRU fonctionnent bien mais sont faiblement efficaces lors d'accès en burst : les données qui ne sont accédées qu'une fois occupent la mémoire cache et polluent donc cette dernière. Les algorithmes LRU améliorés tentent de résoudre ce problème. Ces algorithmes sont donc très utiles pour les caches de disque ou les copies de fichiers. Tous les algorithmes présentés dans cette section utilisent la même idée : partitionner le cache en deux parties :

• l'une contient les données utilisées une et une seule fois,
• l'autre les données utilisées au moins deux fois.

Les tailles relatives de ces deux groupes sont fixes ou dynamiques, suivant les algorithmes.

2Q

L'idée de cet algorithme est de créer deux queues de taille fixe afin d'éviter la pollution de la mémoire cache. La première liste, qui contient les données accédées une seule fois, est gérée comme une liste FIFO et la seconde comme une liste LRU. La première queue est également partitionnée en deux sous-queues A1in et A1out car les résultats expérimentaux démontrent que la taille optimale de cette queue dépend fortement de la trace.

Selon John et al., cet algorithme donne de meilleurs résultats que LRU, de l'ordre de 5-10%. Le problème est que deux queues doivent êtres gérées ainsi que les migrations de l'une à l'autre ; ce qui requiert beaucoup de hardware et consomme de nombreux cycles d'horloge et d'énergie. Ces raisons expliquent que cet algorithme n'apparaît pas dans les systèmes embarqués mais est une solution utilisée dans les mémoires caches de disque.

LRU-K

Cet algorithme, proposé par O'Neil et al., découpe la mémoire cache en différents groupes qui correspondent aux lignes qui ont été accédées récemment entre 1 et K fois. L'idée de base est la même que celle présentée pour l'algorithme 2Q. Un historique des K derniers accès de chaque ligne de la mémoire principale doit donc être maintenue, ce qui nécessite beaucoup de logique et augmente notablement la consommation. Lors d'un défaut de cache, la ligne à remplacer est choisie en explorant ces listes et en cherchant la donnée qui n'a pas été accédée récemment et dont le K-ème accès est la LRU de la liste K. Cependant, cet algorithme n'est réellement justifié que pour les caches de taille importante.