大多数替换策略旨在最小化整体 cache miss rate ，其前提是所有 cache miss 的代价是相等的。然而不同的 cache miss 对整体性能的影响可能天差地别

  • 孤立的 miss（低内存级并行性）往往比聚集的 miss（高内存级并行性）代价更高，因为更高的并行性意味着有更强的能力来隐藏单个 cache miss 的延迟
  • 位于程序关键路径上的 miss 比不在关键路径上的 miss 对程序性能的影响更为重要

一个考虑这些成本的智能替换策略可以优先缓存高成本的 miss（以较低的 hit rate 为代价），从而实现更好的程序性能

Optimal Cost-Aware Replacement Policy (CSOPT, 2006)

Jaeheon Jeong and Michel Dubois. Cache replacement algorithms with nonuniform miss costs. IEEE Transactions on Computers, 55(4):353–365, 2006.

CSOPT 旨在最小化所有 misses 的总成本，而非最小化 miss 的次数
基本思想:

  • 基本遵循 Belady 的最优页面替换算法
  • 当该算法会踢出一个其 miss 成本高于其他 cacheline 的 line 时，CSOPT 会探索多种替换策略序列，直到它能确定出使总成本最小化的替换策略序列

CSOPT 的一种简单实现：以搜索树的形式展开所有可能的替换策略序列

  • 搜索树的深度等于 cache 访问的次数，因为每次新的 cache 访问都会增加一个新层级，而其宽度等于 cache 大小 s，因为搜索过程在每次 eviction 时最多会考虑 s 种替换选择
  • 贪婪地在树中任意节点缓存一个高成本 cacheline, 从长远来看可能无法转化为最佳替换序列
    • 可能会阻碍缓存另一个成本更高的 cacheline
    • 可能会替换掉多个低成本 cacheline ，而这些 cacheline 的总成本高于单个高成本 cacheline

因此，最佳替换决策取决于未来多条竞争路径的行为，从而产生一个庞大的解决方案搜索空间

CSOPT 的分支定界方法在 cache 访问次数上是指数级的，而 MIN 在缓存访问次数上是线性的

可以采用启发式方法来修剪搜索树并减少搜索空间:

  • 对于一些科学工作负载，这些启发式方法被证明可以使 CSOPT 的计算变得可行——即离线分析能够完成
  • 但通常并不能降低最坏情况下的复杂度

实验证明，CSOPT 相对于 MIN 的成本节省随着成本比率的增加而增加，并且在高成本访问占总访问次数20‑30%时最为显著，因为当成本差异较大且低成本未命中的百分比较高时，CSOPT 相对于 MIN 的优势会增长，在这些情况下，MIN更有可能做出错误的选择。

与 MIN 一样，CSOPT 也是硬件不可实现的，因为需要预知未来的访问

实用的成本感知缓存替换解决方案依赖于直观的启发式方法：

  1. 识别高成本的 cache 访问
  2. 优先缓存高成本负载而非低成本负载

MLP-Aware Linear Replacement Policy (LIN, 2006)

Moinuddin K Qureshi and Yale N Patt. Utility-based cache partitioning: A lowoverhead, high-performance, runtime mechanism to partition shared caches. In 2006 39th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO’06), pages 423–432. IEEE, 2006.

核心思想：孤立 miss（低MLP）对性能的影响比并行 miss（高MLP）更大，因为一个孤立 miss 会阻碍其后的所有依赖指令，并导致处理器长时间停顿。相比之下，并行缺失的成本则不那么高，因为处理器可以通过并行发出多个 load 请求来隐藏其延迟。

MLP 感知缓存替换策略可以通过减少孤立 miss 次数来提升性能(理论上可以优于 Belady MIN)

MLP感知线性（LIN）策略包含两个组成部分：

  1. 一个预测未来 miss MLP 成本的算法
  2. 一个综合考虑最近使用和基于 MLP 成本的替换策略

cache miss 对应的 MLP-based cost 被定义为: 该 miss 等待被服务所花费的周期数

  • 可以轻松地使用 MSHR 进行追踪
  • 对于并行 misses ，周期数在所有并发 misses 之间平均分配
  • 更高的基于 MLP 的成本意味着该 cacheline 很可能导致孤立 miss，因此更希望将其保留在 cache 中

LIN 替换策略线性结合 recency 和 MLP-based cost，并踢出聚合成本最低的 cacheline: $R(i) + \lambda ∗ cost_q(i)$

  • $R(i)$ 是一个 cacheline 的 recency （最大值表示 MRU，最小值表示 LRU）
  • $costq(i)$ 是其量化的 MLP-based cost，那么 LIN 策略将踢出 MLP-based cost 最小的 cacheline
    • λ 是 costq 在选择 victim lines 时的权重
    • λ 值高表示 LIN 很可能保留具有高 MLP-based cost 的 MRU cacheline
    • λ 值低则表示 LIN 可能更侧重于 MRU
    • 论文设置 λ 为 4

由于 LIN 并非总是优于 LRU，论文最终使用set dueling 在 LIN 和 LRU 策略之间动态选择

ReMAP(2014)

Akhil Arunkumar and Carole-Jean Wu. Remap: Reuse and memory access cost aware eviction policy for last level cache management. In 2014 IEEE 32nd International Conference on Computer Design (ICCD), pages 110–117. IEEE, 2014.

核心观点: 将踢出后的重用信息纳入成本度量本身

该策略将一个 cacheline 的总成本定义为: 最近使用, DRAM 延迟和踢出后重用距离的线性组合，其中驱逐后重用距离是使用一个针对被驱逐行的 bloom filter 来计算的

Locality-Aware Cost-Sensitive Cache Replacement Policy (LACS, 2014)

Mazen Kharbutli and Rami Sheikh. Lacs: A locality-aware cost-sensitive cache replacement algorithm. IEEE Transactions on Computers, 63(8):1975–1987, 2014.

该策略通过统计一个 cacheline 发生 LLC miss 期间所发出的指令数量来估算其成本

  • 这种成本定义反映了处理器隐藏 miss 惩罚的能力(与 MLP 类似)
  • cacheline 根据发出的指令数量是高于还是低于一个阈值，被分类为低成本或高成本
  • 对于每个 cacheline ，LACS 维护一个 2 bits 的成本值(二元的成本分类)

LACS 结合了基于局部性和基于成本的替换策略的优势:

  • 在发生 cache miss 时，LACS 选择一个低成本 cacheline 踢出，以便高成本 cacheline 保留在 cache 中
  • 高成本 cacheline 会通过递减其 2 位成本值来老化，这样如果它们在 cache 中停留时间过长，就会放弃保留状态
  • 低成本 cacheline 会通过递增其 2 位成本值来提升，这样如果它们表现出较高的时间局部性，就会被保留在 cache 中