algorithme LRU, le nombre de bits nécessaires pour mettre en œuvre cet algorithme?
J'ai une petite question à propos de l'algorithme LRU.
Si vous avez un cache avec quatre blocs , le nombre de bits avez-vous besoin pour mettre en œuvre cet algorithme ?
- Quelle est la taille du bloc?
Vous devez vous connecter pour publier un commentaire.
Il y a un bon jeu de diapositives à http://www.powershow.com/view/95163-NzkyO/4_4_Page_replacement_algorithms_powerpoint_ppt_presentation qui parle de divers régimes de remplacement de page. Il explique également la LRU, la mise en œuvre à l'aide de mxm matrice de vraiment bien.
En supposant que vous dire un 4-way set-associative cache:
Un "parfait" LRU serait essentiellement attribuant à chaque ligne exacte de l'indice dans l'ordre d'utilisation. Vous pouvez aussi considérer que comme un "âge". De sorte que chacun des 4 éléments nécessiterait un index de 2 bits (car on a besoin de compter les 4 âges distincts), en indiquant son emplacement dans la LRU ordre - ce qui signifie que 2 bits * 4 voies, pour chaque ensemble de la cache.
Dans le cas général de n façons, vous auriez besoin de log2(n) bits par ligne, ou n*log2(n) bits par set.
Par ailleurs, il existe des moyens moins coûteux pour atteindre une quasi-LRU comportement, voir par exemple Pseudo-LRU qui n'aurait besoin que de 3 bits pour l'ensemble dans votre cas (ou en général:
#ways - 1)Le nombre minimum de par-ensemble de bits est plafond(log2(N!)) où N est le nombre de façons.
Cela peut être vu facilement par quatre chemin l'associativité en notant que le MRU bloc (A) peut être l'un des quatre blocs, la presque MRU bloc peut être l'un des trois blocs restants (B ∈ {0,1,2,3} et B ≠ A), près de la LRU bloc ne peut être l'un des deux blocs restants (C ∈ {0,1,2,3} et C ≠ A et C ≠ B), et pour la LRU qu'un seul bloc à bloc est disponible. Par conséquent, le nombre d'états possibles dans total est le produit du nombre de ces états indépendants, c'est à dire, 4! (ou pour le cas général de N!).
B bits peut coder 2B états, de sorte que B doit être supérieure ou égale à log2(the_number_of_states). Pour les 24 états de quatre à l'associativité, cinq bits sont nécessaires.
(En augmentant le nombre de bits peut simplifier l'état de la machine utilisée pour gérer cette information, de sorte que le nombre minimum de bits requis peut ne pas correspondre au nombre de bits utilisés dans le monde réel de la mise en œuvre.)
Comme Leeor réponse noté, arbre pseudo-LRU (qui maintient un arbre d'un seul bit/deux voies LRU choix) exige seulement N-1 bits. Cette pLRU est relativement simple à mettre en œuvre, de sorte que même à 4 voies associativité (où seuls les deux bouts de stockage sont enregistrés — 3 bits vs 5 bits) cette forme de pLRU peut être attrayant.
(À 8 voies de l'associativité, la vraie LRU nécessite 16 bits d'état, comparativement à seulement 7 bits pour l'arbre pLRU. Clairement plus associativities, vrai LRU devient de plus en plus cher, mais il peut être utile dans la simplification des cas les pires temps d'exécution de l'analyse et il a été choisi comme une politique de remplacement pour certains totalement associatif Tlb.)
Dans un N-chemin ensemble associatif de la mémoire cache de l'architecture, d'un bloc de mémoire peut être placé dans l'une quelconque de N ensembles dans une ligne de cache. Donc, pour une ligne de cache si il y a des N ensembles dans lequel un bloc peut être placé, il y aura N! les permutations possibles de rangements.
Plus précisément, il N nombre de compteurs(pour chaque ensemble de N ensembles dans une ligne de cache). Chaque fois qu'un hit/miss est produite, les valeurs de ces compteurs changement et est fixé selon la convention que, à l'encontre de la valeur '0' représentera le moins utilisé des blocs et de la valeur du compteur 'N-1' représente le plus récemment utilisé des blocs.
Depuis chaque compteur dans une ligne de cache peut avoir la taille selon le nombre de jeux en ligne(N), le compteur de valeurs vont de 0 à N-1. Et donc chaque compteur sera de LogN bits. Et il y a des N ensembles dans une ligne pour chaque ligne de cache auront NLogN bits en conséquence.