概述

plru和lru的对比

plru最早是intel提出的，再此之前使用的有lru算法，lru算法中使用age_matrix记录了所有cache_way之间的年龄关系，但是问题就是：age_matrix过于占面积了，4way的cache需要的年龄信息是：4*4=16bit，虽然可以压缩成3+2+1=6bit，但是plru在4way的cache只需要1+2=3bit,这个面积优势十分明显。

plru的问题

是plru算法也有问题：访问过一次的元素可以永远留在cache中。(没仔细研究过，参考链接说的)

前提知识

plru保存信息的方式和数据结构有关系，在数据结构中有提及如何使用一维数组保存完全二叉树

你需要知道这些信息：

当父节点在一维度的数据中的索引是i的时候，其子节点的索引

• 左子树索引：2*i+1

• 右子树索引：2*i+2

如何计算替换的way_id

符号定义

• cache line 保存的plru的信号：plru_message

• 表示最old的way_id的信号: most_old_way_id

plru_message中的每一个bit表示什么含义呢？

它应该表示这样的逻辑表达式：最old的节点在右子树上？，是则为1，不是则为0

查找

现在讲解如何使用plru_message获取到most_old_way_id,为了方便理解，我们先将plru_message展成完全二叉树的形式，然后画出最old的节点在完全二叉树上的路径（由根节点到最old节点的所有节点构成）即为most_old_way_id

本处使用一个在四路组相联的cache中plru的信息位作为演示，plru_message是3’b010

‘

从上图所得most_old_way_id是2'b01

如何进行更新plru的信息位

新增加符号定义

• 输出更新plru_message的信号：plru_update_message

• cache访问的way_id信号：access_way_id

• 要访问的节点（最新节点）的路径：accsess_node_route

前面我们介绍了plru_message中bit位表示什么含义了，那access_way的bit表示上面含义？表示：要访问的节点在是否在右子树。换一句说就是（最新的节点是否在右子树上，正好和plru_message表示的含义相反）。

更新策略：

我们要使用access_way这个信息找到最新的节点在完全二叉树上的路径access_node_route,然后设置access_node_route[i]=~access_way_id[i]

假设输入的access_way_id=2'b10即要访问way2

所以最新节点所在的路径是

查找到要访问的节点（最新节点）和其在完全二叉树上的路径。然后我们进行更新即access_node_route[i]=~access_way_id[i]，得到下面结果

可以发现虽然最old节点所在路径没有改变，但是修改了根节点右子树上的最old节点所在路径

最后得到的plru_updage_message=3'b110

参考链接

这个链接中收罗的信息还是比较全的

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