cpu cache中LRU算法所亟需的位数

参考：algorithm LRU, how many bits needed for implement this algorithm?

问题：在cpu缓存中使用的LRU替换算法需要多少位呢？

解决方法：
对于n路相连的缓存来说，LRU每个缓存块需要的位数为log2(n)，那么每个set需要的位数就为n*log2(n)。

（原文：Assuming you mean a 4-way set-associative cache:
A “perfect” LRU would essentially be assigning each line an exact index in the order of usage. You can also think of that as an “age”. So each of the 4 elements would require an index of 2 bits (since we need to count 4 distinct ages) stating its location in the LRU order - this means 2 bits * 4 ways, per each set of the cache.
In the general case of n ways, you’d need log2(n) bits per line, or n*log2(n) bits per set.

By the way, there are cheaper ways to reach an almost-LRU behavior, see for e.g. Pseudo LRU which would only require 3 bits for the entire set in your case (or in general: #ways - 1)）