缓存替换：tree-based PLRU

LRU（Least Recently Used）是经典的缓存替换策略之一，但当缓存相联度较大时（通常路数大于4路），LRU的实现开销变得很高。PLRU（pseudo-LRU）是 LRU 的开销优化版本，本文要介绍的是PLRU中的tree-PLRU（tree-based pseudo-LRU）¹。因为网络上的一些 PLRU 博客讲述得有些复杂，本文按照官方文档和网上资料的理解，梳理了一套比较简单的理解方式。

（1）1-bit 实现 2-way 组相联替换

访问时，使用1-bit记录访问路；替换时，取反即为要替换的路。

（2）3-bit 实现 4-way 组相联替换

下图是 tree-plru 官方文档的直观解释。

3-bit 的数据，构成一个二元决策图，每 bit 可视为一个 branch-point，branch 指向要替换的路，其中 0 指向左边，1 指向右边。

访问时：因为 3-bit 数据是替换指向，所以当访问路时，需要将该 branch point 的替换指向更新为反向（即是说，相等则取反，其他情况不变，对应上图的 [ref to, next state] 表格）。比如（下列数值均为二进制）决策值 000，访问路 00，则有：访问路第一比特为0，和第一层节点0相等，则后者取反更新为1；访问路第二比特为0，访问第二层左边节点，两者相等则后者取反更新为1；最后决策值为 110。

替换时：根据决策值指向的叶子节点，替换对应的路，对应上图的 [state, replace] 表格；此外，替换路径上的 branch point 值均取反。比如（下列数值均为二进制），决策值000，将要替换路00，其中路径上的节点值取反，得到最后的决策值为110。

（3）更多路的组相联替换

逻辑和（2）类似。一般地，缓存路会设置为2的幂数 $2^n$，对应的 tree-PLRU 的硬件开销为 $2^n-1$ 比特，相比于 LRU 来说，开销可控，故现代处理器如Intel 486和PowerPC系统的一些处理器，常采用 PLRU 而不是 LRU。

（4）tree-PLRU 存在的问题

在 LRU 理论下应该被替换的节点的邻居节点被访问，该节点将不会被换出，根据（2）中的访问更新策略即可推出。

比如决策值000，各路的缓存行为ACBD，接下来的访问序列是 C、B、D、A。当下一个访问为E时，决策值指向的B将被替换，而不是LRU理论下的C被替换。

综上，tree-PLRU 不是严格的 LRU，得到的是一个近似解，但开销比 LRU 低很多。

参考资料：

1. Cache替换策略之tree-PLRU - 知乎