Cache Replacement Policies - introduction
Cache Replacement Policies - introduction
缓存替代算法读书笔记，记录Cache Replacement Policies的内容
introduction
数据访问的延时远远超过指令执行延时，因而需要缓存。
对于缓存，使用命中率来衡量有效性：定义$s/r$ 其中s是缓存处理的内存请求，r是向缓存发出的总内存请求。
提高缓存命中率有几种方法。一种方法是增加缓存的大小，通常会以增加延迟为代价。第二种方法是增加缓存的关联性，这会增加缓存线可以映射到的可能位置的数量。
在一个极端情况下，直接映射缓存（关联性为1）将每个缓存线映射到缓存中的一个单一位置。在另一个极端情况下，全关联缓存允许缓存线放置在缓存的任何位置。
选择一个好的缓存替换策略是为了避免因关联性过大而导致资源和设计复杂度增加
分类
• Insertion Policy: 当新的行被插入到缓存时，替换策略如何初始化该行的替换状态？
• Promotion Policy: 当某一行在缓存中命中时，替换策略如何更新该行的替换状态？
• Aging Policy: 当有竞争行被插入或Promote时，替换策略如何更新某行的替换状态？
• Eviction Policy:在固定数量的选择中，替换策略会驱逐哪一行？
粗粒度策略在插入时对所有缓存行一视同仁，因此它们主要依赖巧妙的Aging和Promote策略来操纵替换优先级。
细粒度策略采用更智能的插入策略。当然，细粒度策略也需要适当的Aging和Promote来更新替换状态，因为在插入时无法预测所有行为。
粗粒度策略（Coarse-Grained Policies）
粗粒度策略在缓存行（cache line）首次插入缓存时对所有缓存行一视同仁，它们通过观察缓存行在缓存中的重用行为（reuse behavior）来区分“缓存友好型”（cache-friendly）与“缓存不友好型”（cache-averse）数据。我们进一步根据用于区分缓存驻留行的度量标准，将粗粒度策略划分为三类：
- 第一类（也是粗粒度策略中的主流）是基于访问新近性的策略（Recency-Based Policies），它们按照缓存行最近被访问的时间顺序进行排序。
- 第二类是基于访问频率的策略（Frequency-Based Policies），它们依据缓存行被访问的次数进行排序。
- 第三类是自适应策略（Hybrid Policies），它们动态监控缓存行为，随着时间推移选择当前阶段最合适的粗粒度策略。
基于新近性的策略（Recency-Based Policies）
这类策略根据缓存行在其生命周期中的最新一次访问时间对其排序。为实现这种排序，策略通常维护一个逻辑新近性栈（recency stack），用于表示缓存行被访问的相对顺序。不同策略以不同方式利用该新近性信息。
例如，常用的最近最少使用（LRU）策略及其变种倾向于淘汰最久未被使用的缓存行，而最近最多使用（MRU）策略则倾向于淘汰最近被访问过的缓存行。还有一些策略则采用中间折衷的淘汰方式。
我们进一步将新近性策略根据其观察生命周期的定义进行划分：
- 第一类定义缓存行的生命周期在其被**驱逐（evicted）出缓存时终止，称为固定生命周期（fixed lifetime）**策略；
- 第二类策略则通过引入一个临时结构（如Victim Cache或Re-Reference Prediction Table），将缓存行的生命周期延长至驱逐之后，使得那些具有较长重用距离的缓存行有“第二次机会”获得命中，我们称这类策略具有扩展生命周期（extended lifetime）。
基于频率的策略（Frequency-Based Policies）
频率策略通过维护访问计数器（frequency counters）来对缓存行进行排序，计数器记录每个缓存行被访问的频率。不同替换策略采用不同方式更新和解释这些计数器：
- 有的策略将计数器单调递增；
- 有的策略则采用“衰老机制”（aging），即随着时间推移逐渐降低计数值；
- 某些策略会直接淘汰计数值最低的缓存行；
- 其他策略则根据预设标准来决定淘汰哪些缓存行。
混合策略（Hybrid Policies）
由于不同的粗粒度策略适用于不同的缓存访问模式，混合策略会在程序执行过程中根据“阶段性行为（phase behavior）”动态地选择最合适的策略。这些策略在“评估周期（evaluation period）”中监测多个候选粗粒度策略的命中率（hit rate），然后根据反馈选择未来访问中最优的策略。
自适应策略的优势在于可以避免单一策略可能出现的性能瓶颈或“路径依赖问题（pathologies）”。
在第3章中我们将看到，先进的混合策略在不同时间段内采用不同的插入优先级（insertion priority）来切换粗粒度策略。尽管插入优先级会随时间变化，这些策略在每个时间段内仍然是粗粒度的，因为在同一时间段内，所有缓存行的处理方式是一致的。
细粒度策略（Fine-Grained Policies）
细粒度策略在缓存行被插入缓存时就对它们进行区分。这种区分依赖于缓存行以往生命周期中的行为信息。例如，如果某条缓存行在过去从未命中过，那么它可以被以低优先级插入缓存。
由于不可能记录所有缓存行的完整历史行为，细粒度策略通常选择对缓存行的分组（grouping）**进行行为记录。例如，许多策略会将**由同一个加载指令（load instruction）访问过的缓存行归为一组。
当然，所有细粒度策略的核心问题是：在插入时如何区分这些分组。我们根据所使用的度量方式，将细粒度策略分为两个大类：
- 基于分类的策略（Classification-Based Policies）：为每个缓存行分组预测两种可能的状态之一 —— “缓存友好型（cache-friendly）”或“缓存不友好型（cache-averse）”；
- 基于重用距离的策略（Reuse Distance-Based Policies）：试图为每个缓存行分组预测更详细的**重用距离（reuse distance）**信息。
这两类策略分别代表了细粒度策略谱系的两个极端：
- 分类策略只有两个预测值（友好 / 不友好）；
- 而重用距离策略则可能预测多个可能值（比如四种、八种等更精细的距离划分）；
- 实际上，大多数策略介于两者之间，在多个有限值之间做出选择。
最后，Beckmann 和 Sanchez（2017） 提出了新的预测度量方式，我们将在第三类中对这些**新型指标（novel metrics）**进行讨论。
基于分类的策略（Classification-Based Policies）
这类策略将即将插入的缓存行划分为两类：
- 缓存友好型（Cache-friendly）
- 缓存不友好型（Cache-averse）
其核心思想是：优先淘汰缓存不友好型的缓存行，以便为缓存友好型行腾出空间。因而，缓存友好型行以更高优先级被插入；在缓存友好型行之间，一般还会根据**新近性（recency）**维护一个二级排序。
分类策略被广泛认为是当前的先进状态（state-of-the-art）策略，原因如下：
- 它们能够利用缓存行为的长期历史信息做出更智能的决策；
- 它们适用于各种不同的缓存访问模式。
我们将在第 4.2 节详细介绍这类策略。
基于重用距离的策略（Reuse Distance-Based Policies）
这类策略试图为即将插入的缓存行预测其重用距离（reuse distance）：
- 如果某条缓存行在超过预测的重用距离之前都未再次被命中，则会被提前淘汰。
这类策略可以看作是**“预测版本”的新近性策略或频率策略**，因为传统的新近性（如 LRU）或频率策略（如 LFU）其实也是在间接估算重用距离，只不过它们是基于在缓存驻留期内的行为。
而重用距离策略是通过历史信息进行显式预测，因此具备独特的优劣势，我们将在第 4.1 节详细探讨这些内容。
细粒度策略（Fine-Grained Policies）
细粒度策略在缓存行被插入缓存时就对它们进行区分。这种区分依赖于缓存行以往生命周期中的行为信息。例如，如果某条缓存行在过去从未命中过，那么它可以被以低优先级插入缓存。
由于不可能记录所有缓存行的完整历史行为，细粒度策略通常选择对缓存行的分组（grouping）**进行行为记录。例如，许多策略会将由同一个加载指令（load instruction）访问过的缓存行归为一组。
当然，所有细粒度策略的核心问题是：在插入时如何区分这些分组。我们根据所使用的度量方式，将细粒度策略分为两个大类：
- 基于分类的策略（Classification-Based Policies）：为每个缓存行分组预测两种可能的状态之一 —— “缓存友好型（cache-friendly）”或“缓存不友好型（cache-averse）”；
- 基于重用距离的策略（Reuse Distance-Based Policies）：试图为每个缓存行分组预测更详细的**重用距离（reuse distance）**信息。
这两类策略分别代表了细粒度策略谱系的两个极端：
- 分类策略只有两个预测值（友好 / 不友好）；
- 而重用距离策略则可能预测多个可能值（比如四种、八种等更精细的距离划分）；
- 实际上，大多数策略介于两者之间，在多个有限值之间做出选择。
最后，Beckmann 和 Sanchez（2017） 提出了新的预测度量方式，我们将在第三类中对这些**新型指标（novel metrics）**进行讨论。
基于分类的策略（Classification-Based Policies）
这类策略将即将插入的缓存行划分为两类：
- 缓存友好型（Cache-friendly）
- 缓存不友好型（Cache-averse）
其核心思想是：优先淘汰缓存不友好型的缓存行，以便为缓存友好型行腾出空间。因而，缓存友好型行以更高优先级被插入；在缓存友好型行之间，一般还会根据**新近性（recency）**维护一个二级排序。
分类策略被广泛认为是当前的先进状态（state-of-the-art）策略，原因如下：
- 它们能够利用缓存行为的长期历史信息做出更智能的决策；
- 它们适用于各种不同的缓存访问模式。
我们将在第 4.2 节详细介绍这类策略。
基于重用距离的策略（Reuse Distance-Based Policies）
这类策略试图为即将插入的缓存行预测其重用距离（reuse distance）：
- 如果某条缓存行在超过预测的重用距离之前都未再次被命中，则会被提前淘汰。
这类策略可以看作是**“预测版本”的新近性策略或频率策略**，因为传统的新近性（如 LRU）或频率策略（如 LFU）其实也是在间接估算重用距离，只不过它们是基于在缓存驻留期内的行为。
而重用距离策略是通过历史信息进行显式预测，因此具备独特的优劣势，我们将在第 4.1 节详细探讨这些内容。
设计考虑因素
●粒度：在插入时以何种粒度区分线路？所有缓存线路是否被同等对待，还是根据历史信息赋予不同的优先级？
●历史：替换策略在做出决策时利用了多少历史信息？
● 访问模式：替换策略对特定访问模式的专门化程度如何？它对访问模式的变化或不同访问模式的混合是否具有鲁棒性？
系列文章：
[缓存替换算法1-粗颗粒策略](缓存替换算法 | Chilh)
[缓存替换算法2-细颗粒策略](缓存替换算法 | Chilh)
