Un algorithme de mise en cache (ou politique de remplacement du cache) est un algorithme de gestion de mémoires caches optimal. Le principe de fonctionnement de la majorité de ces algorithmes repose sur le principe de localité. Un algorithme de remplacement de ligne de cache choisit en général la ligne qui sera expulsée et remplacée. Il existe une variété de tels algorithmes, avec chacun leurs avantages et inconvénients. Ces algorithmes sont en général divisés en deux grandes catégories :

• les algorithmes dépendants de l'utilisation des données : LRU, LFU, etc.
• les algorithmes indépendants de l'utilisation des données : aléatoire, FIFO.

Les mémoires caches dans les matériels informatiques sont le plus souvent partiellement associatives : une ligne de la mémoire principale ne peut être rangée que dans une partie bien définie de la mémoire cache. Dans le cas d'un cache logiciel, il est possible qu'elle soit totalement associative et gérée globalement. Dans les deux cas, se pose le problème de devoir évicter une place dans la mémoire cache, ou dans la partie de celle-ci concernée, lorsque celle-ci est pleine et qu'on veut y charger des données de la mémoire principale.

Cet algorithme, formalisé par L.A. Belady^[1], utilise la mémoire cache de manière optimale : il remplace la ligne de mémoire cache qui ne sera pas utilisée pour la plus grande période de temps. Par conséquent, cet algorithme doit connaître les accès futurs afin de désigner la ligne à évincer. Cela est donc impossible à réaliser dans un système réel, mais constitue néanmoins un excellent moyen afin de mesurer l'efficacité d'un algorithme de remplacement en fournissant une référence.

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.^{[réf. nécessaire]}

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.

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^[2], 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 ${\displaystyle \log _{2}(N_{\text{voies}})}$ 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.

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.^[3], 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…

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.

En raison de la complexité d'implémentation de l'algorithme LRU, qui influe de manière négative sur le temps moyen d'accès à la mémoire cache, des approximations de l'algorithme LRU, souvent appelées « pseudo-LRU », ont été développées afin de pallier ces problèmes. Les différents algorithmes présentés dans cette section utilisent tous le fait que dans le bas de la liste d'accès, la probabilité que le processeur requière une de ces lignes est quasiment identique. Par conséquent, désigner une de ces lignes pour l'éviction donne des résultats très proches. Un ordre partiel à l'intérieur de ces ensembles est donc suffisant.

Les algorithmes « pseudo-LRU » ont une performance pratique voisine de celle du LRU^[4].

Toutes les figures dessinées ici respectent la convention suivante : le vert correspond à des lignes protégées de l'éviction et le jaune aux lignes considérées comme LRU.

La première approximation est fondée sur un arbre de décision binaire. Elle ne requiert que N-1 bits par ensemble dans un cache associatif de N voies. Ces différents bits pointent la ligne considérée comme pseudo-LRU. Les bits de l'arbre de décision binaire pointant sur la voie hitée sont inversés pour protéger cette ligne de l'éviction. Prenons l'exemple d'un cache de 4 voies représenté sur la figure ci-dessous. Chaque dessin correspond au résultat de l'accès mémoire présenté.

La nature binaire de cet algorithme est également la faiblesse de l'algorithme : le nœud en haut de l'arbre binaire ne contient qu'une information et ne peut donc pas refléter suffisamment bien l'histoire des différentes voies.

À chaque ligne de mémoire cache est assigné un bit. Lorsqu'une ligne est écrite, son bit est mis à 1. Si tous les bits d'un ensemble sont égaux à 1, tous les bits sauf le dernier sont réinitialisés à zéro. Cet algorithme est populaire dans de nombreux caches. Selon Al-Zoubi et al.^[3], ces deux pseudo-algorithmes sont de très bonnes approximations et PLRUm donne même de meilleurs résultats que LRU sur certains algorithmes.

C'est probablement la plus simple des approximations de l'algorithme LRU et ne requiert qu'un bit par ensemble. Ce bit partage l'ensemble en deux groupes :

• l'un qui contient le MRU (Most Recently Used)
• l'autre non.

Lors d'un hit ou d'un défaut de cache, ce bit est réévalué pour pointer sur la moitié qui ne contient pas le MRU. La ligne à remplacer est ensuite choisie au hasard parmi ce groupe.

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.

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^[5]., cet algorithme donne de meilleurs résultats que LRU, de l'ordre de 5-10 %. Le problème est que deux queues doivent être 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.

Cet algorithme, proposé par O'Neil et al.^[6], 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 maintenu, 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.

On peut vouloir, par analyse statique, établir quels accès sont forcément des succès ou des échecs de cache, par exemple pour borner rigoureusement le temps d'exécution du programme^[7]. La sortie de l'analyse statique est ainsi, pour chaque accès du programme, l'indication de s'il es|autyhort forcément en cache, forcément hors cache, ou de statut indéterminé. Des raffinements sont possibles : on peut par exemple indiquer que tel accès est en cache si la procédure qui le contient est utilisée dans certains contextes d'appel, que tel accès est hors cache lors de la première itération d'une boucle mais en cache pour les suivantes, etc Ceci est notamment utile pour borner le temps d'exécution dans le pire cas de programmes de contrôle de systèmes embarqués critiques (avionique, etc.).

Une approche classique de l'analyse de propriétés de cache LRU est d'associer à chaque bloc possiblement présent dans le cache un âge (0 pour le bloc le plus récemment inséré, etc. jusqu'à l'associativité du cache) et calculer des intervalles d'âges possibles^[8]. Cette analyse peut être raffinée pour distinguer automatiquement des cas où le même point de programme est accessible par des chemins qui provoquent pour certains des accès en cache, pour d'autres des accès hors cache^[9]. On peut même obtenir une analyse exacte (par rapport à un modèle d'exécution ne considérant que le flot de contrôle syntaxique du programme, sans sémantique des conditions) et en même temps efficace en abstrayant les ensembles d'états de cache par des antichaînes elles-mêmes représentées par des diagrammes binaires de décision compacts^[10].

Cette bonne propriété de la politique LRU du point de vue de l'analyse ne se généralise pas aux politiques pseudo-LRU. On démontre notamment que, du point de vue de la théorie de la complexité algorithmique, les problèmes d'analyse statique posés par les algorithmes pseudo-LRU et l'algorithme FIFO appartiennent à des classes de complexité supérieures à celles des algorithmes LRU^[11],[12].

• Mémoire cache

• Portail de l'informatique théorique
• Portail de l’informatique