LRU (1970)

概念上维护一个 recency stack,栈顶是 MRU 项，栈底是 LRU 项
实现上可以精确维护一个 stack 或者给每个 line 维护一个计数器实现(1998)

Insertion Promotion Aging Victim Selection
MRU position MRU position Move 1 position towards LRU LRU position

在两种场景下性能较差:

  1. 访存范围超出 cache size ，会出现 cache 颠簸 thrashing
  2. 扫描模式下，LRU 项更容易被使用

MRU

类似于 LRU，但 replace 时踢出 MRU 项
目的是为了解决访存范围超出 cache size 时出现的 cache thrashing 问题，因为 MRU 策略会尽可能将访存范围的某一部分保留在 cache 中

Insertion Promotion Aging Victim Selection
MRU position MRU position Move 1 position towards LRU MRU position

缺点是:

  1. 对于 recency-friendly 访存模式，性能较差，因为该策略不容易将较新的工作集保存在 cache 中
  2. 很难适应不同的工作集大小

EELRU, Early Eviction LRU (1999)

主要目的：避免 cache 颠簸

检测访存范围是否超出 cache size ，超出则随机踢出一部分 lines ，以便于剩下的 lines 可以更好地被 LRU 策略管理

根据访问的时间顺序从最近到最早，将 cacheline 划分为 late region, early region, LRU memory region

EELRU

两种 evict 模式：

  1. Ealry Eviction: late region 的 hits 多于early region，认为此时发生了 cache 颠簸，踢出 ealry region 中的 cacheline
  2. LRU Eviction: late region 的 hits 低于 ealry region，认为此时没有发生 cache 颠簸，采用 LRU 策略踢出 cacheline
Insertion Promotion Aging Victim Selection
MRU position MRU position Move 1 position towards LRU Choose between LRU or $e^{th}$ recently used line

Segmented LRU, Seg-LRU (1994)

Ramakrishna Karedla, J Spencer Love, and Bradley G Wherry. Caching strategies to improve disk system performance. Computer, (3):38–46, 1994.

将 LRU stack 区分为两个 logic segments

  1. probationary segment: 所有 cacheline 首先进入该 segment，在该 segment 中 hit 一次后提升到 protected segment
  2. protected segment: 其中的 cacheline 都至少被访问过两次
    发生 evcition 时首先从 probationary segment 中选择 LRU 项踢出

cacheline 从 probationary segment 提升到 protected segment 时，如果 protected segment 满，则会导致 protected segment 中的 LRU 项替换到 probationary segment 中的 MRU 项，而不是立即踢出 cache

Insertion Promotion Aging Victim Selection
MRU position in probationary segment MRU position in protected segment Increment recency counter LRU position from probationary segment

可以很好的处理扫描模式

Seg-LRU 的一个变体获得了 the First Cache Replacement Championship 的冠军:

Hongliang Gao and Chris Wilkerson. A dueling segmented LRU replacement algorithm with adaptive bypassing. In JWAC 2010-1st JILP Workshop on Computer Architecture Competitions: Cache Replacement Championship, 2010.

LIP, LRU Insertion Policy(2007)

Moinuddin K Qureshi, Aamer Jaleel, Yale N Patt, Simon C Steely, and Joel Emer. Adaptive insertion policies for high performance caching. In Proceedings of the International Symposium on Computer Architecture (ISCA), pages 381–391, 2007.

  • 插入新 cacheline 时，优先插入到 LRU 项
  • 踢出 cacheline 时，优先踢出 LRU 项
Insertion Promotion Aging Victim Selection
LRU position MRU position Move 1 position towards LRU LRU position

可以抗抖动，但无法适应工作集的变化

BIP, Bimodel Insertion Policy(2007)

Moinuddin K Qureshi, Aamer Jaleel, Yale N Patt, Simon C Steely, and Joel Emer. Adaptive insertion policies for high performance caching. In Proceedings of the International Symposium on Computer Architecture (ISCA), pages 381–391, 2007.

对 LIP 进行了修改，使新 cacheline 以较低概率(1/32 或 1/64)插入到 MRU 项(用于适应工作集的变化)，大部分情况下还是插入到 LRU 项(抗抖动)

Insertion Promotion Aging Victim Selection
MRU position with probability $\epsilon$ MRU position Move 1 position towards LRU LRU position

Static Re-Reference Interval Prediction (SRRIP, 2010)

Aamer Jaleel, Kevin B. Theobald, Simon C. Steely Jr, and Joel Emer. High performance cache replacement using re-reference interval prediction (RRIP). In Proceedings of the International Symposium on Computer Architecture (ISCA), pages 60–71, 2010b.

思路：RRIP

将 cache replacement 视为一个 Re-Reference Interval Prediction (RRIP) 问题

  1. 位于 RRIP 链顶端的 cacheline 将被预测为会最快被重新引用
  2. 位于 RRIP 链底端的 cacheline 将被预测为会最晚被重新引用
    cacheline evcition 将选择 RRIP 链底端的 cacheline

LRU 链也可以视为一种 RRIP 链，cacheline 在 LRU 链上的位置代表其自上次访问以来的时间间隔

  • LRU 新插入的 cacheline 预测为最近重引用
  • LIP 新插入的 cacheline 预测为最晚重引用

实现

SRRIP 策略对于新插入的 cacheline 预测一个 RRIP 链中间的重引用间隔 (增加了抗扫描能力，可以防止具有较晚重引用间隔的 cacheline 驱逐具有较近重引用间隔的 cacheline)

SRRIP 为每个 cacheline 关联一个 M 位计数器存储其重引用间隔预测值 RRPV (实验发现，2 位的 RRPV 足以提供抗扫描能力)

flowchart LR;
  A((0))--Age-->B((1));
  B--Age-->C((2));
  C--Age-->D((3));
  D--Evict-->Out[" "];
  B--Promote-->A;
  C--Promote-->A;
  D--Promote-->A;
  LRU-->A;
  SRRIP-->C;
  MRU-->D;
Insertion Promotion Aging Victim Selection
RRPV = 2 RRPV = 0 Increment all RRPVs (if no line with RRPV = 3) RRPV = 3

SRRIP 的缺点：当重引用间隔超出 cache 容量时，同样容易发生 cache 颠簸(抗抖动能力差)

Bimodel Re-Reference Interval Prediction (BRRIP, 2010)

Aamer Jaleel, Kevin B. Theobald, Simon C. Steely Jr, and Joel Emer. High performance cache replacement using re-reference interval prediction (RRIP). In Proceedings of the International Symposium on Computer Architecture (ISCA), pages 60–71, 2010b.

结合了 SRRIP 和 BIP 策略，新插入的大多数 cacheline 具有较远的重引用间隔预测（即RRPV = 3），而极少插入具有中等重引用间隔预测的缓存块（即RRPV = 2）

Insertion Promotion Aging Victim Selection
RRPV = 3 for most insertions, RRPV = 2 with probability $\epsilon$ RRPV = 0 Increment all RRPVs (if no line with RRPV = 3) RRPV = 3

缺点：当 workload 在近期友好型和 cache 颠簸型之间切换时，表现不佳

Protecting Distance-Based Policy (PDP, 2012)

Nam Duong, Dali Zhao, Taesu Kim, Rosario Cammarota, Mateo Valero, and Alexander V. Veidenbaum. Improving cache management policies using dynamic reuse distances. In 45th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 389–400, 2012.

思想：保护距离

PDP 策略动态地估计一个保护距离 (PD)

  • 所有 cacheline 在被踢出 cache 前都会受到保护，可抵御 PD 次访问
  • 保护距离是一个单一值，但会根据应用程序的动态行为持续更新

保护距离的计算

  • PDP会计算重用距离分布 (RDD)，即程序在最近一段执行时间内观察到的重用距离的分布
  • 利用 RDD，保护距离被定义为覆盖 cache 中大多数 cacheline 的重用距离，使得大多数 cacheline 在 PD 或更小的距离内被重用

在插入或提升时，每个 cacheline 会被分配一个值来代表其剩余保护距离（RPD），即它保持受保护状态的剩余访问次数

  • 该值初始化为保护距离（PD）
  • 在每次对 set 进行访问后，set 中每个 cacheline 的 RPD 会通过递减其 RPD 值（下限为 0）来老化
  • 仅当缓存行的 RPD 大于 0 时，它才受到保护
  • 未受保护的 cacheline 将被选为 victim cacheline

Genetic Insertion and Promotion for Pseudo LRU Replacement (GIPPR, 2013)

Daniel A. Jiménez. Insertion and promotion for tree-based PseudoLRU last-level caches. In 46th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 284–296, 2013.

使用插入/提升向量 (IPV) 的概念来概括对插入与提升策略的修改

IPV 规定了一个 cacheline 在插入时，以及从LRU 栈的不同位置被提升时，其在 LRU 栈中的新位置

对于一个 k 路组相联 cache，一个 IPV 是一个包含 k+1 个条目的整数向量

  • 取值范围从0 到 k−1
  • 其中第 ith 个位置的值表示位于位置 i 的 cacheline 在被重新引用时应被提升到的新位置
  • 第 kth 个条目表示新进入的 cacheline 应被插入的位置
  • 如果 LRU 栈中的新位置小于旧位置，则 cacheline 会向下移动以腾出空间；否则，cacheline 会向上移动以腾出空间

问题:

  • 可能的 IPV 数量呈指数级增长（对于一个 k 路缓存有 $k^{k+1}$ 种可能的 IPV）
  • 最佳的 IPV 因工作负载而异

通过离线遗传搜索针对 SPEC2006 演化出了一种 IPV 配置：
GIPPR

Shepherd Cache (2007)

Kaushik Rajan and Ramaswamy Govindarajan. Emulating optimal replacement with a shepherd cache. In the 40th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 445–454, 2007.

思路：扩展寿命策略
是 Recence-Based Policy 的一个特殊类别

  • 通过将某些 cacheline 存储在辅助缓冲区或 victim cache 中，人为地延长其生命周期
  • 关键动机: 将 eviction 决策推迟以便做出更明智的决定
  • 这种策略允许粗粒度策略将 cache hit 的重用窗口略微扩展到比 cache 本身的大小更大

Shepherd Cache 模仿了Belady的最优策略

  • 借助一个称为 Shepherd Cache 的辅助缓存来模拟 Belady 的未来前瞻
  • cache 在逻辑上被划分为两个部分
    1. 模拟最优替换的主 cache（MC）
    2. 使用简单 FIFO 替换策略的 Shepherd Cache (SC）
  • SC 通过提供一个前瞻窗口来支持 MC 的最优替换
  • 新 cacheline 最初被存到 SC 中
  • 从 MC 中替换 cacheline 的决策会推迟到新 cacheline 离开 SC 时
  • 当新 cacheline 位于 SC 中时，会收集关于MC 中替换 cacheline 重用顺序的信息
    • 较早被重用的 cacheline 被驱逐的可能性较低
  • 当新 cacheline 因 SC 中的其他插入而被踢出 SC 时，会选择一个替换 cacheline:
    • 要么选择在 SC cacheline 被重用前 MC 中未被重用的 cacheline
    • 要么选择最后被重用的 cacheline
    • 如果 MC 中的所有 cacheline 在 SC cacheline 被重用前都已重用，则 SC cacheline 替换自身
  • MC 和 SC 被组织成一个单一的物理结构，避免了数据在组件间的移动

Trade-Off:

  • MC 中的替换在高前瞻性下接近真正的最优性
  • 更高的前瞻性是以牺牲 MC 容量为代价的
    (实验证明，为接近 Belady MIN 策略，该策略需要的前瞻性大小需达到 8× cache 的大小)

证明实验出自：
Akanksha Jain and Calvin Lin. Back to the future: Leveraging belady’s algorithm for improved cache replacement. In Proceedings of the International Symposium on Computer Architecture (ISCA), June 2016.