Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithmes de remplacement des lignes de cache
Résumé
Article principal : mémoire cache
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'une mémoire cache logicielle, il est possible qu'elle soit totalement associative et gérée globalement.
Dans les deux cas, se pose le problème de devoir dégager 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.
Un algorithme de remplacement de ligne de cache (ou politique de remplacement) choisit alors la ligne qui sera dégagée et remplacée. On a proposé une variété de tels algorithmes, avec chacun leurs avantages et inconvénients.
Le principe de fonctionnement de la majorité de ces algorithmes repose sur le principe de localité. 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.
Cet algorithme, formalisé par L.A. Belady, 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.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.