algorithm - 算法 LRU，实现这个算法需要多少位？

Question

我对算法 LRU 有一个小问题。如果你有一个有四个块的缓存，你需要多少位来实现这个算法？

Answer 1

假设您的意思是 4 路组关联缓存：
“完美”的 LRU 本质上是按照使用顺序为每一行分配一个精确的索引。您也可以将其视为“年龄”。因此，4 个元素中的每一个都需要 2 位的索引（因为我们需要计算 4 个不同的年龄），以 LRU 顺序说明其位置 - 这意味着每组缓存有 2 位 * 4 路。
在 n 方式的一般情况下，您需要每行 log2(n) 位，或每组 n*log2(n) 位。

顺便说一句，有更便宜的方法可以达到几乎 LRU 的行为，例如Pseudo LRU，在您的情况下，整个集合只需要 3 位（或一般情况下#ways - 1：）

Answer 2

每组的最小位数是上限（log2（N！）），其中 N 是路数。

通过注意 MRU 块 (A) 可以是四个块中的任何一个，几乎 MRU 块可以是其余三个块中的任何一个 (B ∈ {0,1,2,3}且 B ≠ A），几乎 LRU 块只能是剩余两个块之一（C ∈ {0,1,2,3} 和 C ≠ A 和 C ≠ B），对于 LRU 块只有一个块是可用的。因此，总共可能的状态数是这些独立状态数的乘积，即 4！（或对于一般情况 N！）。

B 位可以编码 2 ^B个状态，因此 B 必须大于或等于 log2(the_number_of_states)。对于 24 种四路关联性状态，需要 5 位。

（增加位数可能会简化用于管理此信息的状态机，因此所需的最小位数可能与实际实现中使用的实际位数不匹配。）

正如Leeor 的回答所指出的，树伪 LRU（维护单位/双向 LRU 选择的树）只需要 N-1 位。这种 pLRU 实现起来相对简单，因此即使在 4 路关联性下（仅节省了 2 位存储空间——3 位与 5 位），这种形式的 pLRU 也很有吸引力。

（在 8 路关联性下，真正的 LRU 需要 16 位状态，而树 pLRU 仅需要 7 位。显然，在更高的关联性下，真正的 LRU 变得更加昂贵，但在简化最坏情况执行时间分析和它已被选为某些完全关联 TLB 的替代策略。）

Answer 3

在 N 路组关联高速缓存存储器架构中，特定的内存块可以放置在高速缓存行的 N 组中的任何一组中。所以对于一个特定的缓存行，如果有N个集合可以放置一个块，就会有N个！可能排序的排列。

更准确地说，有 N 个计数器（一个高速缓存行中的 N 个集合中的每个集合一个）。每当发生命中/未命中时，这些计数器中的值都会更改并根据约定进行设置，计数器值“0”表示使用最少的块，计数器值“N-1”表示最近使用的块。

由于高速缓存行中的每个计数器可以根据行中的集合数（N）具有大小，因此计数器值的范围从 0 到 N-1。因此每个计数器都是 LogN 位。并且一行中有 N 个集合，因此每个缓存行将具有相应的 NLogN 位。

Answer 4

在http://www.powershow.com/view/95163-NzkyO/4_4_Page_replacement_algorithms_powerpoint_ppt_presentation有一个很好的幻灯片，讨论了各种页面替换方案。它还很好地解释了使用 mxm 矩阵的 LRU 实现。