基于 reuse distance 的策略会预测 cacheline 的 reuse distance，其中 reuse distance 可以定义为对同一 cacheline 连续两次访问之间的访问次数或周期数

完美预测 reuse distance 足以模拟 Belady 的最优替换策略，但由于 reuse distance 变化很大，很难精确预测

现实的解决方案是: 估计 reuse distance 分布或其他聚合的 reuse distance 统计信息

Expiration-Based Dead Block Predictors

使用过去的 eviction 来估计平均 reuse distance 统计信息，并踢出那些未在其预期 reuse distance 内被重用的 cacheline

Hu: Live Time

Hu 等人提出的策略 学习了 cacheline 的 live time

  • live time 被定义为一个 cacheline 在 cache 中保持 live 的周期数
  • 当一个 cacheline 被插入时，其 lifetime 被预测为与其上一次 lifetime 相似
  • 如果一个 cacheline 在 cache 中停留的时间达到其预测 lifetime 的两倍仍未收到 cache hit ，则该块被标记为 dead 并从 cache 中踢出

Abella

Abella 等人使用类似的 dead block 预测策略来关闭 L2 Cacheline

  • 将 reuse distance 定义为连续引用之间的 cache 访问次数

Kharbutli

Kharbutli 等人使用计数器来追踪每个 cacheline 的访问间隔

  • 其中访问间隔被定义为对该 cacheline 进行后续访问之间所访问的其他 cacheline 的数量
  • 此外，他们预测，如果一个 cacheline 的访问间隔超过某个阈值，则该 cacheline 标记为 dead block
  • 该阈值由访问间隔预测器（AIP）预测，该预测器追踪所有过去 eviction 的访问间隔，并在一个 PC-based table 中记录所有此类间隔的最大值

Leeway

Faldu 等人提出了 Leeway 策略，该策略利用 live distance 来识别 dead block

  • 其中 live distance 定义为一个 cacheline 在其生命周期内观察到的最大栈距离
  • 当一个 cacheline 超过其 live distance 时，它就被预测为 dead block
  • 过去生命周期中的 live distance 通过一个 per-PC Live Distance Predictor Table（LDPT）来记录
  • LDPT为即将进入的 cacheline 预测 live distance，任何在 LRU Stack 中移动距离超过其预测 live distance 的 cacheline 都被预测为 dead block
  • 为了避免不同 lifetime 之间以及由同一 PC 访问的 cacheline 之间 live distance 的高度可变性，Leeway 部署了两种更新策略, 根据工作负载特性控制 LDPT 中 live distance 的调整速率
    1. 第一种策略是激进的，倾向于旁路
    2. 第二种策略是保守的，倾向于缓存

Leeway 使用 set dueling 的方法来在这两种策略之间进行选择

Reuse Distance Ordering

ETA Policy

Keramidas 等人利用 reuse distance 预测来踢出预期在未来最远时间被重用的 cacheline

该策略:

  1. 为每条 load 指令（PC）学习一个 reuse distance，并为每个新进入的 cacheline 计算一个 Estimated Time of Access (ETA) 预计访问时间，该时间是当前时间与预期重用间隔之和
  2. 然后根据 ETA 对 cacheline 进行排序，并踢出 ETA 最大的 cacheline
    为防止出现 ETA 预测不可用的情况，此方案还会跟踪 cacheline 的衰减值，这是对某个 cacheline 保持未被访问状态的时间长度的估计，如果其衰减间隔大于其 ETA ，则将其踢出