Inclusion Aware Cache Replacement

Inclusive cache 要求多级 cache 中所有 upper level cache 的内容必须是 LLC 的子集

Inclusion 极大地简化了 cache 一致性协议,但会将 cache hierarchy的有效容量限制为 LLC 的大小（而 exclusive cache hierarchy 中有效容量是所有 cache 容量之和）

Aamer Jaleel, Eric Borch, Malini Bhandaru, Simon C Steely Jr, and Joel Emer. Achieving non-inclusive cache performance with inclusive caches: Temporal locality aware (tla) cache management policies. In Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture, pages 151–162. IEEE Computer Society, 2010a.

Jaleel 等人表明，在 inclusive cache hierarchy 中，LLC 的替换策略对 upper cache 有显著影响

  • 当一个 cacheline 从 LLC 中被踢出时，它会在较小的 cache 中被置为 invalid 以强制执行 inclusion
  • 这些 inclusion victim cacheline 会降低 upper level cache 的 hit rate，因为它们可能会踢出具有高时间局部性的 cacheline
  • Jaleel 等人表明，non-inclusion 的首要好处是消除了 inclusion victims，而非额外的 cache 容量

为避免在 inclusive cache hierarchy 中出现这种病态现象，Jaleel 等人提出了三种 cache 替换策略，以在 upper level cache 中保留 hot cacheline，并延长此类 cacheline 在 LLC 中的生命周期:

  1. Temporal Locality Hints, TLH
  2. Early Core Invalidation, ECI
  3. Query Based Selection, QBS

通过对 LLC 替换策略进行这些简单的修改，inclusive cache hierarchy 的性能可以与 non-inclusive cache hierarchy 相当

Temporal Locality Hints (TLH):

  • TLH 通过向 LLC 发送 Hints 来传递 upper level cache 中 hit cacheline 的时间局部性
  • 这些 Hints 用于更新 LLC 中的替换状态，从而使 LLC 不太可能选择一个会强制引发 inclusive victim 的 cacheline

Early Core Invalidation (ECI):

  • ECI 在某 cacheline 于 LLC 中仍具有高优先级时，推导该 cacheline 在 upper level cache 中的时间局部性
  • 主要思想是提前选择一个 cacheline，使其在 upper level cache 中 invalid，同时保留在 LLC 中；随后对该 cacheline 向 LLC 发出的请求即表明了其时间局部性

Query Based Selection (QBS):

  • QBS 直接查询 upper cache：当 LLC 选择一个替换 victim cacheline 时，它会向 upper cache 查询以获取批准，并利用该信息来做出其替换决策

Compression-Aware Cache Replacement

增加 cache 容量可以通过提高 hit rate 来改善系统性能，但这会以面积和能耗为代价

压缩 cache 提供了一种替代解决方案，即压缩 cache 中的数据以获得更高的有效容量

并非所有 cacheline 都能被压缩，因此压缩会产生可变大小的 cacheline，较大的（未压缩）cacheline 比较小的（压缩）cacheline占用更多的缓存空间

因此，压缩 cache 使用不同的 cache 架构来支持不同可压缩级别的可变大小块, 并且它们需要新的 cache 替换策略，除了考虑时间局部性外，还要考虑可压缩性

  • 压缩 cache 替换策略必须考虑踢出较大 cacheline 与踢出较小 cacheline 所带来的不平衡收益
  • 踢出未压缩的 cacheline 是有益的，因为它们将释放出更多的 cache 容量，这些容量可用于缓存多个压缩 cacheline
  • 踢出未压缩 cacheline 的收益需要与踢出那些近期不会被再次引用的 cacheline 的需求相权衡

Compression-Aware Management Policy (CAMP, 2015)

Gennady Pekhimenko, Tyler Huberty, Rui Cai, Onur Mutlu, Phillip B Gibbons, Michael A Kozuch, and Todd C Mowry. Exploiting compressed block size as an indicator of future reuse. In 2015 IEEE 21st International Symposium on High Performance Computer Architecture (HPCA), pages 51–63. IEEE, 2015.

CAMP 是一种同时考虑压缩 cacheline 大小和时间局部性的替换策略

CAMP 的 Minimal-Value Eviction (MVE) 机制：

  • 基于 insight:
    • 只要一组 cacheline 具有足够的局部性，能共同提供更多的 hit ，那么踢出一个具有良好局部性的未压缩 cacheline ，为总大小相同的一组更小的压缩 cacheline 腾出空间是更可取的
    • 当两个 cacheline 具有相似的局部性特征时，踢出较大的 cacheline 更可取
  • MVE 通过结合 cacheline 大小和预期未来重用信息来计算价值，并踢出价值最低的cacheline
  • 每个 cacheline 的价值定义为：$V_i=p_i/s_i$，其中 $s_i$ 是 cacheline i 的压缩后的大小
  • $p_i$ 是局部性预测器的预测值，值越大，表明 cacheline i 将被更早地重新引用(使用 RRIP 策略进行估计)
  • 价值随着时间局部性的增强而增加，随着 cacheline 大小的增大而减小
  • 总体价值较低的 cacheline 更适合被踢出

CAMP的第二个机制 Size-Based Insertion Policy (SIP)

  • 基于 insight: cacheline 的压缩大小有时可用作其重用特性的指标，即 $s_i$可用于预测$p_i$，属于同一数据结构的元素可能具有相似的压缩性和相似的重用特性
  • SIP 通过以高优先级插入特定大小的 cacheline，以找到能从高优先级插入中受益的 cacheline 大小 (使用动态集合采样)

Base Victim Compression (2016)

Jayesh Gaur, Alaa R Alameldeen, and Sreenivas Subramoney. Base-victim compression: An opportunistic cache compression architecture. In Computer Architecture (ISCA), 2016 ACM/IEEE 43rd Annual International Symposium on, pages 317328. IEEE, 2016.

cache 压缩和替换策略可能互相抑制: 偏向压缩 cache 而非未压缩 cacheline 的决策可能导致次优的替换决策，因为它们迫使智能替换策略改变其替换顺序，导致压缩 cache 失去了来自最先进替换策略的性能增益

为避免与替换策略产生负面交互，Gaur 等人引入了一种 cache 设计，保证所有原本的未压缩 cacheline ，在压缩 cache 中也同样存在

  • 保持 data array 不变，但修改 tag array 以适应压缩
  • tag array 被增强，为每个 way 关联两个 tag
  • 从逻辑上讲，cache 被划分为一个 baseline cache （其管理方式与未压缩 cache 完全相同）和一个 victim cache（如果来自 baseline cache 的 victim lines 可以被压缩，则机会性地缓存它们）
  • 保证了 hit rate 至少与未压缩 cache 一样高，因此能够享受高级替换策略带来的好处