« Fonctionnement d'un ordinateur/Les mémoires cache » : différence entre les versions

Contenu supprimé Contenu ajouté
Ligne 101 :
==Remplacement des lignes de cache==
 
Lorsqu'un cache est rempli et qu'on charge une nouvelle donnée dedans, il faut faire de la place pour cette dernière. Dans le cas d'un cache directement adressé, il n'y rien à faire vu que la ligne de cache à évincer est déterminée lors de la conception du cache. Mais pour les autres caches, la donnée peut aller dans n'importe quelle ligne ou voie. Or, le choix des données à rapatrier en RAM doit être le plus judicieux possible : on doit virer de préférence des données inutiles. Rapatrier une donnée qui sera surement utilisée sous peu est inutile, et il vaudrait mieux supprimer des données qui ne serviront plus ou alors dans longtemps. Il existe différents algorithmes spécialement dédiés à résoudre ce problème efficacement, directement câblés dans les unités de gestion du cache. Certains sont vraiment très complexes, aussi je vais vous présenter quelques algorithmes particulièrement simples. Mais avant de voir ces algorithmes, il faut absolument que je vous parle d'une chose très importante. Quel que soit l'algorithme en question, il va obligatoirement choisir une ligne de cache à remplacer et recopier son contenu dans la RAM. Difficile de faire la sélection en utilisant nos tags. Pour résoudre ce problème, le circuit de remplacement des lignes de cache va adresser chaque ligne de cache ! Eh oui, vous avez bien vu : chaque ligne de cache sera numérotée par une adresse, interne au cache.
 
Il existe différents algorithmes spécialement dédiés à résoudre ce problème efficacement, directement câblés dans les unités de gestion du cache. Certains sont vraiment très complexes, aussi je vais vous présenter quelques algorithmes particulièrement simples.
===Aléatoire===
 
Mais avant de voir ces algorithmes, il faut absolument que je vous parle d'une chose très importante. Quel que soit l'algorithme en question, il choisit la ligne de cache à évincer et recopie son contenu dans la RAM. Ce qui demande d'identifier et de sélectionner une ligne de cache parmi toutes les autres. Pour cela, le circuit de remplacement attribue une adresse chaque ligne de cache ! Vous avez bien vu : chaque ligne de cache est numérotée par une adresse, interne au cache.
 
===Le remplacement aléatoire===
 
Premier algorithme : la donnée effacée du cache est choisie au hasard ! C'est contre-intuitif, mais cet algorithme donne des résultats assez honorables, en plus d'utiliser très peu de portes logiques (un générateur de nombres pseudo-aléatoire est un circuit assez simple). Généralement, les défauts de cache sont séparés par un nombre assez important et irrégulier de cycles d'horloge. Dans ces conditions, cette technique donne un bon résultat.
Ligne 109 ⟶ 113 :
===FIFO : first in, first out===
 
Avec l'algorithme FIFO, la donnée effacée du cache est la plus ancienne, celle chargée dans le cache avant les autres. Cet algorithme possèdeest unetrès petitesimple particularitéà sur les caches associatifs par voie :implémenter en augmentant le nombre d'ensemblescircuit, lesconcevoir performancesune peuventmémoire sede dégradertype :FIFO cn'estétant cepas qu'ontrès appellecompliqué, l''''anomaliecomme deon Bélády'''.la Cetvu algorithmedans estle unchapitre des plus simpledédié à implémenterce entype circuitde :mémoires. unEt vulgaire compteur suffit. Onon peut insérer lesdire donnéesque dans le cachecas les unes à la suite des autres. Exemple : si jd'ai inséré une donnée dans la ligne deun cache, numérol'implémentation X,est alorsencore laplus prochainesimple donnéeet irase danscontente lad'un ligneseul numéro X+1registre/compteur. Si jamais on débordeTypiquement, onil revientsuffit automatiquementd'ajouter àun zéro.registre Enqui faisantmémorise ainsi, nosse lignes de cache seront triées desitue la plus ancienne àdonnée la plus récente automatiquement. LaToute ligneinsertion ded'une cachenouvelle ladonnée plusse ancienne sera localiséefait à un certainl'adresse endroitsuivante, etce laqui plusdemande récentejuste serad'incrémenter localiséele justeregistre avant. Ild'utiliser suffitson decontenu sepour souvenir de la localisation de la donnée la plus ancienne avec un compteur par voie, et le tour estl'accès jouémémoire.
 
[[File:Algorithme FIFO de remplacement des lignes de cache.png|centre|Algorithme FIFO de remplacement des lignes de cache.]]
 
Cet algorithme possède une petite particularité sur les caches associatifs par voie : en augmentant le nombre d'ensembles, les performances peuvent se dégrader : c'est ce qu'on appelle l''''anomalie de Bélády'''.
 
===MRU : most recently used===