为什么 Bit-PLRU 与 LRU 不同
Why Bit-PLRU is different from LRU
以下是关于bit-plru的说明
Bit-PLRU stores one status bit for each cache line. We call these bits MRU-
bits. Every access to a line sets its MRU-bit to 1, indicating that the line was recently used. Whenever the last remaining 0 bit of a set's status bits is set to 1, all other bits are reset to 0. At cache misses, the line with lowest index whose MRU-bit is 0 is replaced.
我觉得lru和bit-plru的replace policy是一样的，miss rate也是一样的。
我的理由：At cache misses, the line with lowest index whose MRU-bit is 0 is replaced.
索引最低的行表示最近最少使用，因此它的 mru 位肯定为零（不可能为 1，因为最近没有使用）。那么，mru-bit 是多余的吗？
如果我的理由是错误的，谁能给我一些理由或例子告诉我 bit-plru 和 lru 之间的不同之处？为什么 bit-plru 给出了更好的性能（未命中率）？
谢谢！
最近最少使用是指访问时间最早的线路。但是跟踪访问以始终知道哪个是最旧的可能在缓存上下文中很复杂。存储每个块的访问顺序至少需要 ceil(log2(n!)) 位，或者最有可能的是 n×log2n 位接近 n 小且更易于管理。每当访问内存引用时，都必须将其从顺序列表中删除，放在顶部并更新列表的其余部分。这在 一个 周期内完成可能很复杂。
这就是开发pseudo-LRU方法的原因。他们保证会弹出 "ancient" 行，但不会弹出最古老的行。
考虑您问题的 bit-LRU 的示例。我们假设初始设置状态如下。
line status real order
(index) (MRU)
0 0 3 LRU
1 1 0 MRU
2 1 1
3 0 2
真正的顺序没有存储，但我们会用它来理解算法的行为（最小的是最小的）。
现在，假设我们访问现有的第 0 行。状态变为
line status real order
(index) (MRU)
0 1 0 MRU
1 1 1
2 1 2
3 0 3 LRU
假设这之后是未命中，所以我们应用该方法并替换第 3 行：
Whenever the last remaining 0 bit of a set's status bits is set to 1, all other bits are reset to 0.
line status real order
(index) (MRU)
0 0 1
1 0 2
2 0 3 LRU
3 1 0 MRU
因此该算法已正确弹出 LRU（第 3 行）。
假设还有一个小姐。算法状态：
At cache misses, the line with lowest index whose MRU-bit is 0 is replaced.
因此第 0 行将被替换。但是第2行是not LRU，甚至是古行中的"youngest"。但它的指数最低。
要弹出另一条更好的线路，需要有关访问时间的更多信息。
也许可以简单地添加弹射中的一些随机性。但是找到真正的 LRU 比较复杂。
请注意，有更好的方法来获得伪 LRU。 Tree-LRU 比方说好多了，但是仍然不能保证会使用真正的 LRU。
对于实际应用，pLRU 给出了类似于真实 LRU 的错误率，同时更简单。
但即使是真正的 LRU 也不一定总是最好的策略，如果一条线被频繁访问，它很可能会继续被访问，即使它是 LRU 也不应该被替换。
因此，最有效的方法通过跟踪访问次数并通过考虑只访问过一次的行和访问过两次或多次的行的不同方式来扩展 pLRU。这样，每当必须弹出一行时，首选只访问过一次的行。
以下是关于bit-plru的说明
Bit-PLRU stores one status bit for each cache line. We call these bits MRU- bits. Every access to a line sets its MRU-bit to 1, indicating that the line was recently used. Whenever the last remaining 0 bit of a set's status bits is set to 1, all other bits are reset to 0. At cache misses, the line with lowest index whose MRU-bit is 0 is replaced.
我觉得lru和bit-plru的replace policy是一样的，miss rate也是一样的。
我的理由：At cache misses, the line with lowest index whose MRU-bit is 0 is replaced.
索引最低的行表示最近最少使用，因此它的 mru 位肯定为零（不可能为 1，因为最近没有使用）。那么，mru-bit 是多余的吗？
如果我的理由是错误的，谁能给我一些理由或例子告诉我 bit-plru 和 lru 之间的不同之处？为什么 bit-plru 给出了更好的性能（未命中率）？
谢谢！
最近最少使用是指访问时间最早的线路。但是跟踪访问以始终知道哪个是最旧的可能在缓存上下文中很复杂。存储每个块的访问顺序至少需要 ceil(log2(n!)) 位，或者最有可能的是 n×log2n 位接近 n 小且更易于管理。每当访问内存引用时，都必须将其从顺序列表中删除，放在顶部并更新列表的其余部分。这在 一个 周期内完成可能很复杂。
这就是开发pseudo-LRU方法的原因。他们保证会弹出 "ancient" 行，但不会弹出最古老的行。
考虑您问题的 bit-LRU 的示例。我们假设初始设置状态如下。
line status real order
(index) (MRU)
0 0 3 LRU
1 1 0 MRU
2 1 1
3 0 2
真正的顺序没有存储，但我们会用它来理解算法的行为（最小的是最小的）。
现在，假设我们访问现有的第 0 行。状态变为
line status real order
(index) (MRU)
0 1 0 MRU
1 1 1
2 1 2
3 0 3 LRU
假设这之后是未命中，所以我们应用该方法并替换第 3 行：
Whenever the last remaining 0 bit of a set's status bits is set to 1, all other bits are reset to 0.
line status real order
(index) (MRU)
0 0 1
1 0 2
2 0 3 LRU
3 1 0 MRU
因此该算法已正确弹出 LRU（第 3 行）。
假设还有一个小姐。算法状态：
At cache misses, the line with lowest index whose MRU-bit is 0 is replaced.
因此第 0 行将被替换。但是第2行是not LRU，甚至是古行中的"youngest"。但它的指数最低。
要弹出另一条更好的线路，需要有关访问时间的更多信息。
也许可以简单地添加弹射中的一些随机性。但是找到真正的 LRU 比较复杂。
请注意，有更好的方法来获得伪 LRU。 Tree-LRU 比方说好多了，但是仍然不能保证会使用真正的 LRU。
对于实际应用，pLRU 给出了类似于真实 LRU 的错误率，同时更简单。
但即使是真正的 LRU 也不一定总是最好的策略，如果一条线被频繁访问，它很可能会继续被访问，即使它是 LRU 也不应该被替换。
因此，最有效的方法通过跟踪访问次数并通过考虑只访问过一次的行和访问过两次或多次的行的不同方式来扩展 pLRU。这样，每当必须弹出一行时，首选只访问过一次的行。