zztaki

fitness and bulking~

0%

cache replacement policies

Posted on Edited on In
Symbols count in article: 6.4k Reading time ≈ 11 mins.
《cache replacement policies》笔记

Abstract：

  1. 本书总结了 CPU 数据缓存的缓存替换策略概况；
  2. 重点讨论算法，因此作者及那个以前的策略分为两大类——粗粒度和细粒度，每类又分为三个子类，以描述解决缓存替换问题的不同方法和每个类别中重要工作的总结；
  3. 探索更多的评价指标，包括不单单局限于缓存缺失率指标、针对多喝设置定制的解决方案、考虑和预取之间的影响、考虑新型内存；
  4. 最后，本书讨论未来工作的趋势和挑战。

Introduction

  1. why cache is important？ 如今传输数据的延迟比执行一条指令的延迟还长，而缓存的存在，可以减少内存延迟和减少内存流量。
  2. 启发式——考虑访问频率、新近度；最近的预测技术。
  3. 如何将缓存替换策略和死块预测结合起来。

A Taxonomy of Cache Replacement Policies

  1. 本书为什么这样分类？
    • 建立在缓存替换策略解决预测问题的观察之上，其目标是预测是否应允许任何给定对象保留在缓存中；
    • 预测的决策发生在缓存块中的很多地方，从缓存块插入缓存开始，到它从缓存中淘汰；
  2. 本书对缓存替换算法如何分类？
    • 首先根据插入决策的粒度分为两类：第一类是粗粒度策略，对所有插入对象进行相同的处理，并且仅依据它们在缓存中驻留的表现进行区别对待，例如，对象在缓存中被重用次数增加时优先级会提高；第二类是细粒度策略，除了在缓存中驻留的表现会影响优先级外，不同对象在插入时就不一样，这依靠缓存访问模式的历史信息，比如，细粒度策略了解到某个特定指令加载的对象在过去没有被重用就淘汰了，它就会给它在插入时更低的优先级。
  3. 缓存替换策略包括：
    • 插入策略：How does the replacement policy initialize the replacement state of a new line when it is inserted into the cache?
    • 提升策略：How does the replacement policy update the replacement state of a line when it hits in the cache?
    • 衰减策略：How does the replacement policy update the replacement state of a line when a competing line is inserted or promoted?
    • 驱逐策略：which line does the replacement policy evict to hold new line?

Coarse-Grained Policies

粗粒度策略可以认为无“插入策略”，它就区分驻留对象优先级的方式又分为三类：新近度、频率、根据工作负载的变化动态选择不同粗粒度策略的混合策略。

Fine-Grained Policies

细粒度策略就对象插入时的区分方式分为两类：基于分类（对对象分为缓存友好和缓存不友好两种）、基于重用距离（尝试去预测对象的重用距离）

  1. 分类：通常被认为是最先进的，因为（1）可以利用过去的访问历史为未来做出更正确的决策，（2）可以适应各种缓存访问模式。
  2. 重用距离预测：使用历史信息进行重用距离预测有好有坏，在 4.1 节中进行讨论。

Design Considerations

缓存替换策略的只要目标是提升缓存命中率，以下这些设计因素有助于实现更高的命中率：

  1. 粒度：
  2. 历史信息：替换策略在做决策时使用了多少历史信息；
  3. 访问模式：替换策略是否适应工作负载。

在大体趋势上，从左到右是更近时候提出的，使用了更长历史记录并且可以适应更多工作负载的算法，可以看到，细粒度预测非常有优势，它提供了：

  1. 允许细粒度策略仅将缓存空间专用于缓存友好对象；
  2. 允许细粒度策略的每个缓存组动态适应工作负载的变化。

Coarse-Grained Replacement Policies

每个对象仅和少量替换状态相关，所有新插入对象被统一初始化，然后在缓存命中时进行简单的提升操作。

Recency-Based Policies

  1. LRU：无法适应搅拌和扫描工作负载；
  2. LRU变种：
    • MRU：仅能适应搅拌工作负载；难以适应工作负载模式的变化，因为新来的工作集很难被持续缓存；
    • EELRU：主要思想是检测工作集大小是否超过缓存大小，当工作集小于缓存容量时，会驱逐 LRU 端对象，当工作集大于缓存容量时，则驱逐距离 MRU 位置长度为 e 的对象；
    • Seg-LRU
    • LIP：和 MRU 其实一个道理，但它通过改变插入策略而使得 LIP 的驱逐策略和 LRU 一致，这启发我们在设计 LRU 变体算法时，只需要修改插入和提升操作，驱逐操作保持不变即可；
    • BIP：以较大概率插入 LRU 端，较低概率插入 MRU 端；
    • SRRIP、BRRIP、PDP、GIPPR

可以看到 LRU 家族很多都在考虑适应搅拌工作负载，因为 CPU 缓存容量小于工作集是较易发生的，但这在内存缓存或者 CDN 缓存中似乎很难出现。

Frequency-Based Policies

基于频率的策略可以一定程度上抵抗扫描工作负载。

  1. LFU：容易造成缓存污染；
  2. Frequency-Based Replacement（FBR）：靠近 MRU 端的对象访问频数不会增加，以避免短时间的高频访问拔高对象优先级；
  3. Least Recently/Frequently Used（LRFU）

Hybrid Policies

混合策略能够适应工作负载的变化。它面临两个挑战：（1）如何准确确定哪个策略是最有利的；（2）以较低的硬件成本管理多个策略。

  1. ARC
  2. DIP
  3. DRRIP

Fine-Grained Replacement Policies

细粒度策略在插入时就会根据不同对象的历史信息进行区分，以决定它们的插入位置。例如，如果对象上一次加入缓存后没有被重用就被驱逐了，当再次请求该对象时，就可以把它插入到较低的位置。

细粒度策略基于预测插入优先级的指标分为三类：预测重用距离、预测是否被重用、引入的新预测指标。

Reuse Distance Prediction Policies

重用距离的具体值很难被准确预测，因此，更现实的解决方案是估计重用距离分布或其它聚合重用距离统计。

Expiration-Based Dead Block Predictors

许多死块预测器使用过去的实际后向重用距离来估计未来的前向重用距离，并驱逐没有在预期重用距离内被重用的对象；

还有一些使用过去的实际生命周期预测未来的生命周期，当在预测的两倍生命周期时间内没有被重用，该块就从缓存中淘汰。

Reuse Distance Ordering

Classification-Based Policies

基于分类的策略相比重用距离预测简单一下，接下来会考虑一下设计问题：

  1. Which caching solution is the policy learning?
  2. What is the prediction mechanism, and at what granularity are the predictions being made?
  3. What is the aging mechanism for ensuring that inaccurate predictions are eventually evicted?

Sampling Based Dead Block Prediction（SDBP）

为降低对所有告诉缓存块维护指令跟踪的成本，引入了基于采样的死块预测器。预测结果为死块的不会被插入缓存（缓存准入）。对于上面的三个问题的回答：

  1. SDBP 从 LRU 采样器中学习缓存决策；
  2. 在 PC 的粒度上使用 skewed 预测器预测死块；
  3. 预测为缓存友好的一次性访问按照基本的替换策略衰减，预测为缓存不友好的可以重用的对象永远无法得到重用（不太好）。

Signature Based Hit Prediction（SHIP）

idea 是重用行为与将对象插入缓存的 PC 值相关，在 memory cache 和 CDN cache 中似乎没有类似相关的参照。

Hawkeye

个人感觉参考价值比较高，也带有一点 learning 的想法。

  1. 主要目标：避免基于启发式的解决方案（例如LRU）的病态；

  2. idea：建立在 Belady 方法之上，因为 Belady 方法作为理论最优方法，它是适应所有工作负载的，但它又必须依靠未来的信息，无法使用在实际生产环境中；

  3. 关键见解：虽然无法知道未来的信息，但可以应用 Belady 于过去的内存引用。如果过去的行为和未来的行为相关性很高，那么效果应该也是很好的；

  4. 该使用多少历史信息？ 为了精准地找到后向重用距离，应该使用所有的历史信息，但这无疑开销很大而且是越来越大的那种，在这里作者使用实验来指导时间窗口的大小，最终使用 8 倍缓存容量的时间窗口。

  5. 8 倍缓存空间的历史信息似乎仍然太大了，于是 Hawkeye 只计算几个抽样集的最优解。

通过使用过去的访问记录来模拟 OPT 算法的行为产生输入来训练 Hawkeye Predictor，再基于 Predictor 做决策。

Perceptron-Based Prediction

这样从发展脉络来看，AI4Cache 是可以走的。

SDBP、SHIP 和 Hawkeye 全都使用基于 PC 的预测器实现了接近 70%-80% 的准确率。后面有研究者使用更好的特征和更好的预测器模型提高了预测准确率。

比如使用感知机（简单的人工神经元）为 PC 增加更多的特征（PC 的历史、来自内存地址的位、数据的压缩表示、块被访问的次数），每个特征都被用来索引一个不同的饱和计数器表，然后将其相加并与阈值进行比较以生成二进制预测结果。小部分访问被采样以便按照感知机规则去更新模型：如果预测不正确，或者如果总和未能超过某个数量级，则计数器在访问时递减并在驱逐时递增。

Other Prediction Metrics

Economic Value Added（EVA）

一方面，对象在缓存中得到重用而创造出价值，另一方面，一个对象在缓存中待得越久它就牺牲了部分缓存空间。

$EVA = 预期命中数 - (缓存命中率/缓存大小) * 预期在缓存驻留时间$

Richer Considerations

（前面都是谈 CPU 缓存替换的具体算法，这一节是讨论缓存替换策略中的具体主义事项，值得借鉴的地方会更多。）

前面都是狭隘地关注缓存替换问题，无论是从指标方面——缓存命中率，还是在和计算机其它组件的配合方面。

Cost-Aware Cache Replacement

如果所有的缓存未命中代价相同，那么设计最小化全局缺失率的缓存替换算法就可以了，但实际上，不同的缓存未命中对性能产生不同的影响，比如孤立的未命中（低内存级并行性）往往比集群未命中（高内存并行性）代价更高，因为并行性越高，多个缓存缺失同时发生可能只会造成一次停顿，再比如在程序关键路径上的未命中对程序性能的影响比不在程序关键路径上的更大。考虑到这些成本的智能替换策略可以优先缓存高成本的未命中（以较低的命中率为代价）以获得更好的程序性能。

  1. 最优成本感知替换策略（The optimal cost-aware replacement policy, CSOPT）目的就是将所有未命中的总成本降至最低，而不是将未命中的数量降至最低。其基本思想是遵循 MIN 策略，同样也是离线算法。
  2. MLP（memory-level parallelism）考虑并行性缺失和独立性缺失的影响（第一个例子）；

Criticality-Driven Cache Optimizations

关键性是比 MLP 更通用的成本函数，将关键负载定义为需要提前完成以防止处理器停顿的任何负载，而非关键负载是可以容忍长时间延迟的负载。而关键驱动的缓存优化优先考虑关键负载而不是非关键负载。

将关键负载从低级别缓存预取到高级别缓存。

Mutil-Core-Aware Cache Management

多核竞争访问共享缓存容量可能会发生流式应用程序驱逐其它缓存友好应用程序的有用数据。

为处理这种共享缓存干扰，可以（1）在内核之间进行对缓存进行分区以避免竞争；（2）修改替换策略以避免病态的访问行为。

缓存分区保证了强隔离和公平性保证。在实现时它有两个主要考虑因素：（1）如何在缓存中强制执行分区？（2）分区大小如何确定？

执行缓存分区最常用的机制是为每个应用程序分配专用通道，这样每个应用程序只能从自己的分区中插入和驱逐数据。更高级的做法是避免硬分区，取而代之的是通过修改替换策略来实现隐式分区。

分区大小可以由用户、操作系统或硬件决定。

显示分区如 UCP、ASM-Cache，隐式分区如 TADIP、PIPP 等。

Prefetch-Aware Cache Replacement

有效的预取隐藏 DRAM 访问的长延时，因此，将预取器和缓存替换策略结合起来是一个很好的想法。

设计预取感知的缓存替换策略有两个主要目标：（1）替换策略应该避免不准确的预取导致的缓存污染；（2）替换策略应该优先丢弃可以预取的对象而不是难以预取的对象。

Cache Pollution

大多数预取感知缓存替换策略侧重于通过识别和驱逐不准确的预取来减少缓存污染。这样的解决方案可以分为两大类。

  1. 从预取器那里获取反馈来识别可能不准确的预取请求；
  2. 独立于预取器工作并监视缓存行为以适应替换决策，但可能缺少精确的预取器特定信息。

Deprioritizing Prefetchable Lines

当存在预取行为时，MIN 算法是不完整的，因为它不区分可预取和难以预取的对象。

Cache Architecture-Aware Cache Replacement

到目前为止，我们假设由缓存替换策略推断的优先级排序与缓存架构无关。但是，缓存架构的变化可能会对缓存替换产生影响。我们现在讨论缓存架构的两个变化。

Inclusion-Aware Cache Replacement

inclusive 缓存要求多级缓存层次结构中所有较小的缓存内容是 LLC 的子集，这种方式简化了缓存一致性协议，但是限制了缓存层次的有效容量为 LLC 的大小，同时当对象从 LLC 中逐出时，小容量缓存中的该对象被强制无效。

Inclusion-Aware Cache Replacement 通常在较小缓存中持续驻留热数据，同时延长 LLC 中此类缓存的生命周期。

Compression-Aware Cache Replacement

增加缓存容量可以提高命中率，提高系统性能，但它是以缓存成本和耗电为代价的。压缩缓存提供了另一种解决方案，其中缓存中的数据被压缩以获得更高的有效容量。例如，如果每个缓存块都可以压缩 4 倍，则有效缓存容量可以增加 4 倍。

当然，并非所有缓存条目都可以压缩，因此压缩会生成可变大小的缓存块，较大的（未压缩的）块比较小的（压缩的）块消耗更多的缓存空间。

进行驱逐操作时，往往更倾向于驱逐较大的、时间局部性较差的缓存块。

New Technology Considerations

几十年来，缓存一直使用 SRAM 技术构建，但更新的内存技术将改变这一现状，因为传统 SRAM 缓存已经被证明有许多限制。

NVM Cache

基于 NVM 的 LLC 缓存容量大且能耗低，但是由于其高写入延迟而导致性能下降。

为了缓解这个问题，有人提出了两种缓存替换策略。首先，引入 Write Congestion Aware Bypass (WCAB) 策略，消除了对 NVM 缓存的大部分写入，同时避免了缓存命中率的大幅降低。其次，建立一个虚拟混合缓存，吸收并消除了冗余写入，否则会导致 NVM 写入缓慢。

DRAM Cache

使用 DRAM Cache 作为 L3 缓存和主存之间的桥梁。

Conclusions

  1. 现在的趋势是细粒度策略；
  2. 现有细粒度策略大多直接使用粗粒度策略的老化机制，未来可以为细粒度策略定制老化机制；
  3. 细粒度策略从过去的行为中学习，但影响其性能主要因素时预测准确性和处理不准确预测的能力；（将缓存替换看作监督学习问题 4.2.3节）
  4. 将缓存替换策略与系统其它组件结合起来，例如预取器，似乎还可以考虑准入器；