一、引言
LRU（Least Recently Used）是 cache 的经典替换策略之一，但当 Cache 的路数比较大时（多路组相连结构），实现 LRU 的硬件开销就会变得很大。现代处理器一般会考虑使用 PLRU（pseudo-LRU）作为 Cache 的替换策略而不是 LRU。
PLRU 是 LRU 的一种优化，本文要介绍的是PLRU中的 tree-PLRU（tree-based pseudo-LRU）。
二、PLRU算法原理
若当前 Cache 为 n 路组相连结构，即一个 Cache Set 中有n个 Cacheline，则 tree-PLRU 会使用（n-1）位来表示近似访问历史顺序的二叉树。根据二叉树的特性，tree-PLRU 将这 n 个Cacheline划分成不同的区块，并用0/1表示区块的访问时间的远近。
假设有一个4路组相连的 Cache，Cache 替换时会在一个 Cache Set 中的4条 Cache line 中选择一条进行替换，假设这四条 Cache line 编号分别为line_0~3，则 tree-PLRU 会使用 4-1=3bit 来构建二叉树来反映 Cache line 的历史访问顺序。
如上图所示，每1bit代表了二叉树的一个分支，假设1表示左侧比右侧最近被访问，0表示右侧比左侧最近被访问，判断最近访问行时，箭头指向是“左1右0”。
假设 branch_bits = 3'b011，表示最近访问的是 line_0 或 line_1，并且访问的是 Line_0。line_2和 line_3 中最近访问的是 line_3。这样我们就能近似得到一个最近访问顺序了，也即最近访问了 line_0 和 line_3，但 line_1 和 line_2 的之间的访问顺序不确定。
三、PLRU替换过程举例
假设state = 3'b000，tree-PLRU的初始状态图如下。
用 state 绘制的二叉树和我们判断最近访问的 branch_bits 正好相反，因为 branch_bits 是判断最近访问的叶子节点，而二叉树反映的是需要剔除的叶子节点（很久未访问），因此正好相反。选择替换行时箭头指的方向是“左0右1”。此时 state=3’b000 表示需要替换的 Cache line 为 line_0，因此我们往 line_0 中填入 data_0。
填入 data_0 之后，原本指向 line_0 的箭头，因为 line_0 被访问替换了，因此指向 line_1。同理，根节点原本指向左侧（近期访问 line_0 或 line_1）的，反过来指向右侧，表示接下来要去替换（line_2 或 line_3），此时 state = 3’b110。倘若此时来了一个 data_1，将替换 line_2，如下图所示。
填入 data_1 之后，原本指向 line_2 的箭头，因为 line_2被访问替换了，因此指向 line_3。同理，根节点原本指向右侧（近期访问 line_2 或 line_3）的，反过来指向左侧，表示接下来要去替换（line_0 或 line_1），此时 state = 3’b011。倘若此时来了一个 data_2，将替换 line_1，如下图所示。
填入 data_2 之后，原本指向 line_1 的箭头，因为 line_1 被访问替换了，因此指向 line_0。同理，根节点原本指向左侧（近期访问line_0 或 line_1）的，反过来指向左侧，表示接下来要去替换（line_2 或 line_3），此时 state = 3’b101。倘若此时来了一个 data_3，将替换 line_3，如下图所示。
替换掉 line_3 之后，二叉树替换情况的最新 state=3’b000，回到了一开始的时候。由此我们可以发现，每发生一次 cache miss，从根节点到叶子节点路径上的箭头指向都要换向（从↙到↘或从↘到↙）。
以上是一个4路组相连结构的 Cache 连续发生4次 Cache miss 的 Cache line 替换情况。倘若中途发生了 Cache hit 该如何处理呢？
我们以上图情况的二叉树为例，倘若此时来了一个 load 访问请求命中了 line_0，那么从第二层到第三层叶子结点的箭头不用发生改变，但是从根节点到第二层节点的箭头需要发生转换。
根节点的转换表示：由于 line_0 或 line_1 最近被访问了，接下来要去替换的是 line_2 或 line_3。这是 Cache hit 有别于 Cache miss 的点。
四、参考资料
1.people.computing.clemson.edu/~mark/464/p_lru.txt