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

Aller à la navigation Aller à la recherche
m
L'algorithme le plus simple consiste à couper le cache (ou chaque voie s'il est associatif) en plusieurs sections. L'algorithme détecte quelle est la section la moins récemment utilisée, avant de choisir aléatoirement une ligne de cache dans cette section. Pour implémenter cet algorithme, il nous suffit d'un registre qui mémorise le morceau le moins récemment utilisé, et d'un circuit qui choisit aléatoirement une ligne de cache. Cette technique s'adapte particulièrement bien avec des cache associatifs à voies : il suffit d'utiliser autant de morceaux que de voies.
 
Autre algorithme, un peu plus efficace : le '''pseudo-LRU de type M'''. Cet algorithme estattribue assezun simple :bit à chaque ligne de cache, on attribue un bit. Ce bitqui sert à indiquer de façon approximative si la ligne de cache associée est une candidate pour un remplacement ou non. SiIl ce bit est àvaut 1, celasi veut dire : attention, cettela ligne n'est pas une candidate pour un remplacement. Inversement,et sizéro cesinon. Le bit est mis à zéro,1 la ligne peut potentiellement être choisie pour laisserlorsque la place aux jeunes. Lorsqu'on lit ou écrit dans une ligne de cache, ce bitassociée est mislue àou 1écrite. Histoire de dire : pas touche ! Évidemment, au fil du temps, toutes les lignes du cache finiront par avoir leur bit à 1. AussiLorsque cela arrive, l'algorithme permet de remettre les pendules à l'heure. Siremet tous les bits sont à 1, on les remet tous à zéro, sauf pour la dernière ligne de cache accédée. L'idée derrière cet algorithme est d'encercler la ligne de cache la moins récemment utilisée au fur et à mesure des accès. ToutL'encerclement commence lorsque l'on remet tous les bits associés aux lignes de cache à 0, (sauf pour la ligne accédée en dernier). Puis, auAu fur et à mesure quedes nos lignes de cache voient leurs bits passer à unaccès, l'étau se resserre autour de notrela ligne de cache la moins récemment utilisée. EtAprès onun finitnombre parsuffisant ld'encercler de plus en plus : au final, après quelques accès, l'algorithme donne une estimation particulièrement fiable. Et comme les remplacement de lignes de cache sont rares comparés aux accès aux lignes, cet algorithme finit par donner une bonne estimation avant qu'on ait besoin d'effectuer un remplacement.
 
Le dernier algorithme d'approximation, le '''PLURt''', se base sur ce qu'on appelle un arbre de décision. Il a besoin de n − 1 bits pour déterminer la ligne LRU. Ces bits doivent être organisés en arbre, comme illustré plus bas. Chacun de ces bits sert à dire : le LRU est à ma droite ou à ma gauche : il est à gauche si je vaux 0, et à droite si je vaux 1. Trouver le LRU se fait en traversant cet arbre, et en interprétant les bits un par un. Au fur et à mesure des lectures, les bits sont mis à jour dans cet arbre, et pointent plus ou moins bien sur le LRU. La mise à jour des bits s'effectue lors des lectures et écritures : quand une ligne est lue ou écrite, elle n'est pas la ligne LRU. Pour l'indiquer, les bits à 1 qui pointent vers la ligne de cache sont mis à 0 lors de la lecture ou écriture.
40 544

modifications

Menu de navigation