Ê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.
Cours associés (11)
CS-307: Introduction to multiprocessor architecture
Multiprocessors are a core component in all types of computing infrastructure, from phones to datacenters. This course will build on the prerequisites of processor design and concurrency to introduce
CS-471: Advanced multiprocessor architecture
Multiprocessors are now the defacto building blocks for all computer systems. This course will build upon the basic concepts offered in Computer Architecture I to cover the architecture and organizati
CS-550: Formal verification
We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to u
Personnes associées (41)
Concepts associés (7)
Erreur de page
Une erreur de page (page fault) est dans le fonctionnement d'un ordinateur la découverte d'une différence entre le plan d'adressage et la mémoire vive. Cette interruption ou exception est émise par le matériel (l'unité de gestion mémoire du processeur) en direction du logiciel (le système d'exploitation). Cette erreur est fréquente et tout à fait bénigne dans les systèmes d'exploitation modernes car ceux-ci utilisent une grande quantité de mémoire virtuelle sans en avertir les applications.
Optimisation de code
En programmation informatique, l'optimisation de code est la pratique consistant à améliorer l'efficacité du code informatique d'un programme ou d'une bibliothèque logicielle. Ces améliorations permettent généralement au programme résultant de s'exécuter plus rapidement, de prendre moins de place en mémoire, de limiter sa consommation de ressources (par exemple les fichiers), ou de consommer moins d'énergie électrique. La règle numéro un de l'optimisation est qu'elle ne doit intervenir qu'une fois que le programme fonctionne et répond aux spécifications fonctionnelles.
Principe de localité (informatique)
Le principe de localité est un terme générique en informatique, qui correspond à une observation des programmes actuels et regroupe différents types de localités. Les programmes possèdent deux caractéristiques intéressantes : ils tendent à utiliser les instructions et les données qui sont situées dans la zone mémoire proche des données et instructions accédées récemment: il s'agit du principe de localité spatiale. Alors que les programmes suivent fréquemment des boucles et des sauts pour les instructions, la localité spatiale est encore plus marquée pour les données.