Algorithmes de remplacement des lignes de cache - Définition
La liste des auteurs de cet article est disponible ici.
Algorithmes usuels
LRU (Least Recently Used)
Cet algorithme remplace la ligne utilisée le moins récemment. L'idée sous-jacente est de garder les données récemment utilisées, conformément au principe de localité. Tous les accès aux différentes lignes de la mémoire cache sont enregistrés ; ce qui explique que cet algorithme coûte cher en termes d'opérations de traitement de liste. De plus, ce coût, qui est un élément vital des systèmes embarqués notamment, augmente exponentiellement avec le nombre de voies de la mémoire cache.
Plusieurs implémentations de cet algorithme sont possibles. L'une d'entre elles est assez simple et se fonde sur l'utilisation d'une matrice triangulaire NxN (où N est le nombre de voies de la mémoire cache). Quand une ligne i est référencée, la ligne i de la matrice est fixée à 1 et la colonne i à 0. La ligne accédée le moins récemment est ainsi la ligne dont la ligne est entièrement égale à 0 et dont la colonne est entièrement égale à 1. Cette définition peut paraître étrange mais par ligne et colonne de la matrice triangulaire, il est entendu tous les éléments non nuls par définition de la matrice (i.e. pour lesquels le numéro de ligne est inférieur au numéro de colonne). Cet algorithme s'exécute rapidement et est assez facile à implémenter en hardware mais sa complexité croît rapidement avec la taille de la mémoire cache. Ainsi, avoir un nombre de voies limité semble préférable mais un faible nombre de voies est source de nombreux conflits… La solution n'est donc pas évidente.
FIFO (First In First Out)
Comme il vient d'être présenté, l'implémentation de l'algorithme LRU est compliquée pour un nombre de voies important. Une approximation de cet algorithme a donc été développée, il s'agit d'un algorithme FIFO : les lignes de la mémoire cache sont effacées dans l'ordre où elles sont arrivées dans la mémoire cache, utilisant ainsi le principe de localité de la manière la plus simple possible. Cette simplicité de conception, qui lui a valu un franc succès dans l'industrie, est malheureusement obtenue au détriment de l'efficacité. Ainsi, selon Smith, le nombre de défauts de cache obtenus par cet algorithme est entre 12 et 20 % plus important que pour le LRU.
L'implémentation hardware est assez simple car elle ne requiert que log2(Nvoies) bits par ensemble de lignes de mémoire cache. Ces bits permettent de désigner la ligne à évincer. Ce compteur est incrémenté à chaque défaut de cache. Si le compteur est initialisé à 0 lors d'un nettoyage de cache, les lignes sont ainsi évincées dans l'ordre où elles ont été enregistrées dans le cache. Cette relation d'ordre n'est valable que pour deux lignes d'un même ensemble.
Malgré sa simplicité, cet algorithme présente l'inconvénient majeur de ne pas relier directement performance et taille de la mémoire cache. Ainsi augmenter la taille du cache peut avoir un effet négatif sur la performance pour certaines séquences d'accès. Ce phénomène est connu sous le nom d'anomalie de Belady.
Algorithme aléatoire
L'algorithme aléatoire est le plus simple : la ligne évincée est choisie au hasard. Cette méthode ne requiert que peu de ressources mais son efficacité est limitée car elle n'est pas fondée sur l'usage des données. Cela peut être implémenté de manière assez simple à l'aide de registres à décalage avec rétroaction linéaire. Selon Al-Zoubi et al., cet algorithme est en moyenne 22% moins efficace que LRU.
Cet algorithme possède un avantage indéniable sur l'algorithme FIFO car ses variations dépendent faiblement de la taille de l'ensemble des données, du nombre de lignes de cache…
LFU (Least Frequently Used)
Alors que LRU enregistre l'ordre d'accès des différentes lignes de mémoire cache, LFU quant à lui garde trace de la fréquence d'accès de ces lignes et remplace la moins fréquemment utilisée. Le point faible de cet algorithme est une pollution du cache. En effet, des lignes qui ont été accédées très fréquemment mais qui ne sont plus utilisées dans le futur tendent à rester dans la mémoire cache. Une solution habituelle est l'ajout d'une politique d'ancienneté : au-delà d'un certain temps, la ligne est désignée comme ligne à remplacer. Néanmoins, en raison de sa complexité d'implémentation, cet algorithme est peu utilisé dans l'industrie.
