Cache Replacement Policies - Coarse-Grained Hybrid

Cache Replacement Policies - Coarse-Grained Hybrid

Hybrid Policies

混合策略 [Jaleel et al.， 2010b, Qureshi et al.， 2006, 2007] 认识到不同的工作负载，甚至相同工作负载中的不同阶段，可以从不同的替代策略中受益。例如，如果程序在小工作集和大工作集之间交替，当工作集较小时，它将受益于最近友好策略，当工作集较大时，它将受益于抗抖动策略。因此，混合策略评估应用程序当前工作集的需求，并从多个竞争策略中动态选择。混合策略面临的两个主要挑战是 (1) 准确识别最有利的策略，以及 (2 以较低的硬件成本管理多个策略。我们现在讨论解决这些挑战的两种解决方案。

自适应替换缓存(ARC) [Megiddo 和 Modha, 2003] 通过动态平衡基于最近次数和基于频率的驱逐，结合了最近次数和频率的优势。特别是，ARC 保持跟踪两个额外的标签目录，L1 和 L2，它们一起记住的元素是基线缓存所能容纳的两倍。L1 目录维护最近使用过的、只访问一次的页面，L2 目录维护最近访问过的、至少访问过两次的页面。ARC 的目标是动态地为 L1 和 L2 选择适当的缓存量(见图3.10)。
更具体地说，ARC 将基线缓存目录分为两个列表 T1 和 T2，分别用于最近和经常引用的条目。T1 和 T2 使用幽灵列表(分别为 B1 和 B2)进行扩展，幽灵列表分别跟踪 T1 和 T2 中最近被逐出的缓存项。幽灵链表只包含标签元数据，而不是实际数据，当相应的数据从缓存中被移除时，条目就会被添加到幽灵链表中。T1 和 B1 共同构成基于最近的 L1 目录，T2 和 B2 共同构成基于频率的L2 目录。
ARC 动态调制 T1 和 T2 专用的缓存空间。一般来说，B1 中的命中会增加 T1 的大小(专用于最近访问的元素的缓存的比例)，B2 中的命中会增加 T2 的大小(专用于至少访问过两次的元素的缓存的比例)。来自 T1 和 T2 的驱逐项分别被添加到 B1 和 B2。

ARC 等混合策略的一个问题是维护附加标记目录的巨大开销。Qureshi 等人[2006] 引入了 Set Dueling，这是一种以较低的硬件成本对不同策略的行为进行抽样的精确机制。Set Dueling 建立在这样的观察之上:一些随机选择的集合可以准确地表示整个缓存上不同替换策略的行为。Qureshi 等人[2006] 用数学方法表明，对于 1-4MB(1024–4096 sets) 的缓存，64 个集合就足以捕获整个缓存的行为。现在，我们通过讨论两个具有代表性的策略来更详细地讨论 Set Dueling。

Dynamic InsertionPolicy(DIP) 动态插入策略(DIP)通过动态调制传入缓存行的插入位置，结合了最近友好策略和抗抖动策略的优点 [Qureshi等人，2007]。特别地，DIP 在最近友好的 LRU(表3.1) 和抗抖动的双模态插入策略(表3.6)之间交替使用。
为了在两个策略中进行选择，DIP 使用 Set Dueling 动态跟踪每个策略的命中率。图 3.11 显示 DIP 专用于 LRU (图3.11中的集0、5、10和15) 和 BIP(图3.11中的集3、6、9和12)。这些专用集被称为 Set Dueling 监视器(SDM)，而其余集被称为跟随集。策略选择(PSEL)饱和计数器通过识别接收更多缓存命中的 SDM 来决定获胜策略。特别地，当专用于 LRU 的 SDM 接收到命中时，PSEL 增加，当专用于 BIP 的 SDM 接收到命中时，PSEL 减少( k 位 PSEL 计数器初始化为 $2^{k-1}$ )。获胜的策略由 PSEL 的 MSB 确定。如果 PSEL 的 MSB 为 0，跟随集使用 LRU 策略；否则跟踪集将使用 BIP。因此，Set Dueling 不需要任何单独的存储结构，除了 PSEL 计数器。

DRRIP 建立在 DIP 的基础上，增加了抗扫描的能力。特别是，DRRIP 使用set dueling 创建了 SRRIP 和 BRRIP 的混合，SRRIP 是 LRU 的抗扫描版本(表3.7)，BRRIP 是 BIP 的抗扫描版本(表3.8)。
正如我们将在第 4 章中看到的，Set Dueling 背后的洞察力对许多后续细粒度策略产生了很大的影响，这些策略使用 Set 采样的概念来有效地跟踪元数据，以确定细粒度缓存行为。