Cache Replacement Policies - Fine-Grained Classification

• Cache Replacement Policies - Fine-Grained Classification

CLASSIFICATION-BASED POLICIES

• 基于分类的策略学习了传入行的二分类：缓存访问是否可能导致未来的命中？ 对缓存友好的行，预期会导致缓存命中的行以更高的优先级插入缓存，以便它们有足够的机会接收缓存命中，而不喜欢缓存的行(不期望缓存命中的行)则以较低的优先级插入，这样它们就可以在不浪费缓存资源的情况下被快速清除。
• 与其他类替换策略相比，基于分类的策略有几个优点。与混合替换策略对给定时间段内的所有行进行统一决策相比，基于分类的替换策略可以插入一些高优先级的行和一些低优先级的行。与基于重用距离的策略(目标是数值的重用距离预测)相比，基于分类的策略解决了一个更简单的二分预测问题。
• 正如我们将看到的，基于分类的政策起源于两种不同的文献。基于采样的死块预测器(SDBP) [Khan等人，2010] (章节4.2.1) 建立在死块预测文献的基础上，而基于签名的命中预测 (SHiP) [Wu等人，2011a] (章节4.2.2)则来源于缓存替换策略文献。有趣的是，这两种解决方案都得到了概念上相似的想法，而且事后看来，这两篇论文共同统一了这两个领域。
• 现在我们将讨论这些和其他最近的基于分类的策略。虽然这些政策之间存在显著差异，但它们都有两个特点。
  • 首先，它们都包含一个二分预测器，该预测器可以学习过去的缓存行为，以指导各个行的插入优先级。
  • 其次，他们都从最先进的粗粒度政策中借鉴了 Promotion、老化 和 驱逐模式，这有助于解释不准确的预测。
• 在描述这些策略时，我们将考虑以下设计问题。
  • 哪种缓存解决方案是策略学习？
  • 预测机制是什么，预测的粒度是什么？
  • 是什么老化机制确保不准确的预测最终被淘汰？

SAMPLING BASED DEAD BLOCK PREDICTION (SDBP)

• 许多研究发现，由于LLC中的大部分块都是死块(它们在被驱逐之前不会再次重用)，死块预测可以用来指导缓存替换和死块的早期旁路（旁路即为不缓存） [Khan等人，2010,Lai和Falsafi, 2000]。Lai 和 Falsafi[2000] 引入了使用死块预测器将数据预取到 L1 中的死块的思想。他们的 reftrace 预测器预测，如果指令地址的 trace 导致最后一次访问一个块，那么同样的 trace 也会导致最后一次访问其他块。为了降低为所有缓存块维护指令跟踪的成本，Khan 等人[2010] 引入了基于采样的死块预测器(SDBP)，它对程序计数器(PC)的缓存行为进行采样，以确定传入的块是否可能 dead。来自已知插入死块的 PC 的未来缓存访问被 Bypass，这样他们就不会污染缓存。来自没有插入死块的 PC 的访问将使用一些基本策略(即随机或 LRU 替换策略)插入缓存。
• 值得注意的是，SDBP 从使用一小部分缓存访问填充的解耦采样器学习(参见图4.2)。如果一个块被从采样器中移除而不被重用，则对相应的 PC 进行负向训练；否则，预测器被积极训练。解耦采样器有几个优点：
  • 首先，只使用所有缓存访问的一小部分样本来训练预测器，这导致了功率和空间效率高的预测器设计和采样器中易管理的元数据(为每个采样器条目维护 PC)。
  • 其次，采样器的替换策略不必与缓存的替换策略相匹配。Khan 等人[2010] 对采样器使用 LRU 策略，他们对主缓存使用随机替换。
  • 最后，采样器的结合性独立于缓存的结合性，这允许开销更小的采样器设计。Khan 等人使用 12 路采样器作为 16 路缓存。表 4.1 总结了SDBP的关键操作。
    
    
• 因此，为了回答我们在本节开始时概述的问题:
  • (1) SDBP 学习基于 LRU 的采样器的缓存决策;
  • (2) 它预测死块(缓存厌恶与缓存友好) 使用一个倾斜的预测器设计，以 PC 的粒度进行这些预测;
  • (3) SDBP 绕过所有预测为缓存厌恶的传入块，使用基线替换策略管理剩余的行，因此假阳性(预测为缓存友好的缓存厌恶块)使用基线替换策略老化，而假阴性(缓存友好的块被预测为缓存厌恶)没有任何机会重用。

SIGNATURE BASED HIT PREDICTION (SHIP)

• 像 SDBP 一样，SHiP [Wu et al.， 2011a] 学习了底层替换策略的淘汰行为，但 SHiP 背后的主要观点是，重用行为与将该行插入缓存的 PC 更紧密相关，而不是与最后访问该行的 PC。因此，在缓存淘汰时，SHiP 的预测器被 PC 训练，PC 首先在缓存丢失时插入该行，预测器只在缓存 MISS 时被咨询(在命中时，行被提升到最高优先级而不咨询预测器)。
• 更具体地说，SHiP 训练一个预测器，它可以学习给定的签名是否具有近或远的重引用间隔。在缓存中采样一些集合以维护签名和训练预测器。在一个采样集中的缓存命中，与这条缓存行相关联的签名被训练为正，以指示一个近重引用，而在驱逐一条从未被重用的行时，该签名被训练为负，以指示一个远重引用。当插入新行时，将使用传入行的签名来咨询预测器，并确定传入行的重新引用间隔(对所有访问执行预测，而不仅仅是对采样集)。一旦插入到缓存中，行就使用一个简单的 RRIP 策略进行管理(参见表4.2)。
  
• 签名的选择对 SHiP 的有效性至关重要。Jaleel 等人 [2010b] 评估了一个程序计数器签名(PC)、一个内存区域签名和一个指令序列历史签名，他们发现 PC 签名性能最好。
• SHiP 基于 DRRIP [Jaleel et al.，2010b] 创建细粒度策略。DRRIP 对 epoch 中的所有缓存行进行统一的重新引用预测，而 SHiP 进行更细粒度的预测：它通过将每个引用与一个唯一的签名关联起来，将传入行的分类到不同的组中。 假设具有相同签名的缓存行具有相似的重引用行为，但允许具有不同签名的缓存行在同一 epoch 内具有不同的重引用行为。
• 现在我们回答本节开始时提到的问题。
  • (1) 最初，SHiP 从 SRRIP 中学习，但一旦 SHiP 的预测器被训练，进一步的训练更新来自 SHiP 自身的重用和驱逐行为。
  • (2) SHiP 使用基于 PC 的预测器，其中与一行相关联的 PC 就是插入一行缓存 miss 的 PC，其中每个 PC 与一个饱和计数器相关联。
  • (3) SHiP 依靠 RRIP 政策来老化所有行。

HAWKEYE

• 为了避免基于启发式的解决方案(如LRU)的病态，Hawkeye [Jain和Lin, 2016] 构建了 Belady 的 MIN 解[Belady, 1966]，这是有趣的两个原因。
  • 首先，Belady 的 MIN 对于任何引用序列都是最优的，因此基于 MIN 的解决方案可能适用于任何访问模式。
  • 其次，Belady 的 MIN 算法是一种不切实际的算法，因为它替换了将来重复使用最多的行；因此，它依赖于未来的知识。
• Hawkeye 的核心见解是，虽然无法预测未来，但可以将 Belady 的 MIN 算法应用到过去的内存引用中。此外，如果一个程序过去的行为是它未来行为的一个很好的预测器，那么通过学习过去的最优解，Hawkeye 可以训练一个预测器，它应该在未来访问中表现良好。
• 为了理解模拟过去事件的 MIN 需要多少历史信息，Jain 和 Lin[2016] 通过限制其未来的窗口来研究 MIN 的性能。图 4.3 显示，虽然 MIN 需要一个很长的窗口到未来(SPECint 2006的 8x 缓存大小)，但它不需要一个无边界窗口。因此，要将 MIN 应用到过去的事件，我们需要一个缓存大小为 8x 的历史记录。
  
• 由于维持缓存大小 8x 的历史信息开销巨大，Hawkeye 只计算几个抽样集的最优解，并引入 OPTgen 算法，为这些抽样集计算与 Belady 的 MIN 策略相同的答案。OPTgen 确定如果使用 MIN 策略将被缓存的行。OPTgen 背后的关键观点是，当一行再次被重用时，可以准确地确定该行的最佳缓存决策。因此，在每次重用时，OPTgen 都会回答以下问题: 这一行是否会在 MIN 情况下是缓存命中还是缓存丢失？这种洞察力使得 OPTgen 能够使用少量的硬件预算和简单的硬件操作，以 O(n) 复杂性再现 Belady 的解决方案。
• 图4.4 显示了 Hawkeye 替换策略的总体设计。OPTgen 训练 Hawkeye 预测器，这是一种基于 PC 的预测器，它可以了解 PC 插入的行是倾向于缓存友好型还是缓存反对型。当 OPTgen 确定一条行将被 MIN 命中时，该行对应的 PC 被正训练，否则被负训练。每次使用传入行的 PC 进行缓存插入和提升时，都会参考预测器。被预测为缓存友好的行将以高优先级插入，而被预测为缓存厌恶的行将以低优先级插入(参见表4.3)。
  
  
• 回答本节开头的问题:
  • (1) Hawkeye 从最优缓存解决方案中学习，而不是从 LRU 或 SRRIP 中学习；
  • (2) Hawkeye 使用基于 PC 的预测器学习最优解;
  • (3) Hawkeye 还依赖于 RRIP 的老化机制，以高优先级插入 age line。为了纠正不准确的预测，Hawkeye 还对预测器进行负训练，当预测到不喜欢缓存的行被取消而没有被重用时。
• Hawkeye 在概念上做出了一个有趣的贡献: 它将缓存替换描述为一个有监督的学习问题，这令人惊讶，因为不像分支预测，程序执行最终提供每个分支的正确结果，硬件缓存不提供这样的标记数据。通过对过去事件应用最优解决方案，Hawkeye 提供了标记数据，这表明缓存替换领域可能会从监督学习的大量研究中受益。

PERCEPTRON-BASED PREDICTION

• 预测性策略在很大程度上取决于预测者的准确性。SDBP、SHiP 和 Hawkeye 都使用基于 PC 的预测器，准确率约为 70 - 80%。Jiménez 和 Teran 旨在通过使用更好的特征和更好的预测模型来提高预测精度 [Jiménez和Teran, 2017, Teran等人，2016]。例如,感知器预测 [Teran et al., 2016] 使用简单的人工神经网络 [Rosenblatt, 1962]，以增加使用带有更丰富的特性的 PC ，如 (1) PCs 历史信息，(2) 来自内存地址的位，(3) 数据的压缩表示，和(4) 一个块被访问的次数。每个特征被用来索引一个不同的饱和计数器表，然后求和并与一个阈值进行比较，生成一个二分预测。一小部分的访问被采样以使用感知器更新策略更新感知器预测器：如果预测是错误的，或者如果总和没有超过某个大小，那么计数器在访问时减少，在驱逐时增加。图 4.5 对比了感知器预测器(右)和先前基于 PC 的预测器(左)。
  
• Multiperspective Reuse Predictor [Jiménez和Teran, 2017] 探索了一组广泛的特性，这些特性捕获了程序的各种属性，生成了一个从多个角度获得信息的预测器。特征被参数化，包含了关于每个训练输入的 LRU 堆栈位置、每个特征被哈希的 PC 位和 PC 历史的长度的更丰富的信息。这些参数一起创建了一个大的特征空间，从而导致更高的预测精度。

EVICTED ADDRESS FILTER(EAF)

• EAF 策略 [Seshadri等人，2012] 单独预测每个缺失块的重用行为，允许比 PC 更细粒度的差异。关键的观察是，如果一个高重用的块被过早地从缓存中逐出，那么它将在逐出后不久被访问，而低重用的块在逐出后很长一段时间内都不会被访问。因此，EAF 策略使用 bloom 过滤器 [bloom, 1970] (一种概率性的、空间效率高的结构，用于确定集合中某个元素的存在或缺失) 来跟踪一小组最近被驱逐的地址。在缓存丢失时，如果新行出现在 bloom 过滤器(也称为逐出地址过滤器)中，那么预测该行是重用友好的，并以高优先级插入; 否则，根据双峰插入策略 the Bimodal Insertion policy 插入新行(参见3.1.2节)。当 bloom 过滤器满时，它被重置。EAF 在概念上类似于一个小型的候选缓存，它跟踪最近从主缓存中删除的行。表 4.4 总结了 EAF 策略的操作。
  
  • 回顾一下 BIP，双峰插入策略，本质是使缓存行以较低的一个概率插入到 MRU 的位置。BIP 保持 LIP 的抗抖动，因为它在大多数时间插入 LRU 位置，但它也可以通过偶尔保留较新的行来适应阶段变化。
• 从概念上讲，EAF 策略延长了缓存行的生存期，超过了淘汰时间，因此一行的生存期从它的插入开始，但当该行从 bloom 过滤器中删除时结束。随着生命周期的延长，对于具有较长重用间隔的行，EAF 观察重用变得可行，从而获得更好的抗扫描能力和抗抖动能力，从而获得更好的性能。
• 重用检测器 (ReD) [crc, 2017, Albericio等人，2013] 提出了类似的想法，因为它绕过 LLC 或地址重用表中没有击中的任何缓存行，跟踪最近的缓存丢失。因此，ReD 只在第二次重用时将行插入缓存中。为了避免在第一次看到所有行时绕过它们，ReD 还使用基于 PC 的预测器来预测在第一次访问后可能被重用的行。