Cache Replacement Policies
2022-6-27|2023-2-10
DieInADream
type
status
date
slug
summary
tags
category
icon
password
Property
Feb 10, 2023 09:12 AM
Abstract
- 这本书总结了CPU数据缓存的缓存替换策略。
- 本文的重点是算法问题，因此作者首先定义了一个分类法，将以前的策略分为两大类，分别称为粗粒度策略和细粒度策略。然后每个类别又分为三个子类别，分别描述了解决缓存替换问题的不同方法，并总结了每个类别中的重要工作。更丰富的因素，包括优化指标超出缓存失误率，为多核设置量身定制的解决方案，考虑与预取器的交互，并考虑新的内存技术，然后进行探索。
- 本书最后讨论了未来工作的趋势和挑战。这本书假设读者对计算机架构和缓存有一个基本的理解，将对该领域的学者和实践者有用
Introduction
- 提升缓存命中率的三种方法
- 增加缓存的大小
- 增加缓存的关联性（局部性）
- 选择一个好的缓存替换策略（本书的主题）
Taxonomy
- 缓存替换策略的目标是什么？
- 目标是预测是否应该允许 任何给定的行 留在缓存中
缓存替换策略二分类
粗粒度缓存替换策略
- 当所有的行插入缓存时，它们被相同地对待，并且只根据它们在缓存中的行为来区分行
- 观察驻留在缓存中的行的重用行为来区分对缓存友好的行和对缓存不友好的行
- 分类：
- 基于最近访问时间 Recency-Based Policies
- 固定的生命周期
- eg. LRU/MRU
- 延长的生命周期
- 该结构为具有较长重用距离的行提供第二次接收缓存命中的机会
- 基于访问频率 Frequency-Based Policies
- 一些策略单调地增加计数器
- 另一些策略则随着时间的推移使计数器老化 Aging (降低其值)
- 一些策略驱逐频率最低的行
- 另一些策略驱逐频率满足预定义标准的行
- 随着时间的推移监视缓存行为，以便在给定的时间段内动态地选择最佳粗粒度策略 Hybrid Policies
- 由于不同的粗粒度策略适用于不同的缓存访问模式，因此混合策略可以在几个预先确定的粗粒度策略中动态选择，以适应程序执行中的阶段变化
- 评估期间观察一些候选粗粒度策略的命中率，并使用此反馈来为未来访问选择最佳的粗粒度策略
- 自适应策略是有利的，因为它们有助于克服单个粗粒度策略的问题
细粒度缓存替换策略
- 细粒度策略在 插入到缓存时 区分行 (除了观察它们驻留在缓存中的行为)
- 细粒度策略通常依赖于关于缓存访问行为的历史信息
- 分类：
- 基于分类的策略与每一组可能的预测之一相关联，即缓存友好型和缓存厌恶型 Classification-Based Policies
- 主要思想是优先清除不利于缓存的行，以便为利于缓存的行留下更多的空间。缓存友好的行优先级因此更高
- 在缓存友好的行之间维护二级排序，通常基于最近次数。基于分类的策略被广泛认为是最先进的
- (1) 它们可以利用过去行为的长期历史来为未来做出更明智的决定
- (2) 它们可以容纳所有类型的缓存访问模式。
- 基于重用距离的策略尝试预测每组缓存行的详细重用距离信息 Reuse Distance-Based Policies
- 超过预期重用距离而没有接收到命中的行将从缓存中删除
- 可以被视为基于最近的策略或基于频率的策略的预测变体
- 因为基于最近的和基于频率的策略都通过监视缓存行在缓存驻留时的重用行为隐式地估计重用距离 (分别通过最近和频率)。
- 利用历史信息对重用距离的显式预测有其独特的优点和缺点
基础概念
- Insertion Policy：当新行插入缓存时，替换策略如何初始化它的替换状态?
- Promotion Policy：当缓存行在缓存中命中的时候，替换策略如何更新该行的替换状态?
- Aging Policy：当插入或提升竞争行时，替换策略如何更新该行的替换状态?
- Eviction Policy：给定固定数量的选择，哪一行执行替换策略驱逐？
对应两种策略
- 从缓存行的生命周期来看，我们可以看到 粗粒度策略在插入时对所有缓存行的处理是相同的，所以它们主要依赖于聪明的 Aging 和 promotion 策略来操作替换优先级。
- 相反，细粒度策略使用更智能的插入策略。当然，细粒度策略还需要适当的 Aging 和 promotion 来更新替换状态，因为在插入时并不能预测所有行为
设计考量
- 粒度: 在插入时，行的粒度是多少? 是否所有的高速缓存行都被相同的处理，或者它们是否根据历史信息分配不同的优先级
- 历史: 替换策略在做决策时利用了多少历史信息?
- 访问模式: 替换策略对特定访问模式的专门化程度如何? 它对访问模式的更改或不同访问模式的混合是否健壮?
现有缓存算法的分类
- 当我们移到图的右侧(通常与更新的策略相对应)时，趋势是 趋向于使用较长的历史记录并能够适应各种访问模式的更细粒度的解决方案
- 在细粒度预测缓存行为的重要性可以通过观察最近的cache Replacement Championship(2017)的前四个解决方案都是细粒度的来衡量。细粒度预测为最新的细粒度策略提供了两个优势。
- 允许细粒度策略只将缓存空间专用于最有可能从缓存中受益的行
- 相比之下，粗粒度策略倾向于重复将缓存资源分配给没有产生任何命中的行。
- 允许细粒度策略动态地确定不同组的行的访问模式
- 粗粒度策略假设整个缓存遵循统一的缓存访问模式
- 在细粒度的策略中，趋势是使用更长的历史作为 state-of-the-art 细粒度策略(Jain and Lin, 2016) 从历史是8样本信息缓存的大小(见第4章)。悠久的历史的应用让策略检测缓存友好长期重用行，否则就会被一长串缓存不友好的中间访问所混淆。
粗粒度缓存
- 粗粒度策略设计中的一个运行主题是识别三种常见的缓存访问模式，即 最近友好访问、抖动访问 和 扫描
- 当应用程序的工作集小到足以装进缓存时，就会出现最近友好访问，这样大多数内存引用的重用距离小于缓存的大小。
- 当应用程序的工作集超过缓存的大小时，就会发生抖动访问，这样大多数内存引用的重用距离都大于缓存的大小
- 扫描是一个永不重复的流访问序列
- 几乎所有粗粒度替换策略都专门针对这些访问模式或这三种访问模式的混合进行了优化
RECENCY-BASED POLICIES
- 基于最近的策略根据最近的信息对行进行优先排序。
LRU
- LRU 策略只是从一组给定的候选缓存行中删除最老的行。为了找到最老的行，LRU 策略在概念上维护一个最近栈，其中栈的顶部代表 MRU 行，堆栈的底部代表 LRU 行。通过为每一行关联一个计数器并更新它，可以精确地或近似地维护这个最近堆栈
- 当引用存在时间局域性时，即最近使用的数据可能在不久的将来被重用时，LRU的性能很好。但是对于另外两种类型的访问模式，它的性能很差。
- 当应用程序的工作集大小超过缓存大小时，它可能是悲观的，导致一种称为抖动的现象
- LRU在有扫描的情况下表现很差，因为它缓存了最近使用的扫描，代价是更有可能被重用的旧行。
LRU 变体
MRU
- MRU 策略通过淘汰新行以保留旧行来解决问题 （和 LRU 的唯一区别：Victim Selection，也就是淘汰策略）
- 当工作集大于缓存时，它能够保留工作集的一部分
- MRU 对于抖动访问是理想的，但它在最近友好访问出现时表现很差
- 对应用程序工作集的变化适应性很差，因为它不太可能缓存来自新工作集的任何行
EELRU
- 避免了抖动。主要思想是检测工作集大小超过缓存大小的情况，在这种情况下，有几行会提前被逐出。因此，早期驱逐会丢弃一些随机选择的行，这样剩余的行就可以通过 LRU 策略进行有效管理。
- 当工作集与缓存相近时，EELRU 会收回 LRU 行，
- 但当它观察到在一个比主存大的大概的循环模式中接触了太多行时，它会驱逐 最近使用的行
- 下图显示了EELRU在最近轴的三个区域之间的区别。最近轴的左端点表示MRU线，右端点表示LRU线。LRU内存区域由最近使用的行组成，位置e和M分别表示早期驱逐区域和晚期驱逐区域的开始。在 miss 时，EELRU 策略要么淘汰最近最少使用的位置(晚区域)的行，要么淘汰 位置(早区域)的行。
- 为了决定是使用早期驱逐还是 LRU 驱逐，EELRU 跟踪每个地区收到的命中次数。
- 如果该分布是单调递减的，则 EELRU 假设没有振荡，并将 LRU 行逐出
- 但是，如果分布显示晚期区域比早期区域的命中次数更多，那么 EELRU 将从早期区域删除，这使得晚期区域的行在缓存中保留的时间更长。表3.3总结了 EELRU 的操作
Seg-LRU - Segmented LRU
- 分段 LRU 通过 优先保留至少访问过两次的行来处理扫描访问[Karedla et al.， 1994]。
- Seg-LRU 将 LRU堆栈划分为两个逻辑段(见图3.4)，即适用段段和受保护段。
- 新进来的缓存行被添加到试用段，当他们收到再次命中，被提升到保护段。因此，受保护段中的行至少被访问了两次，而扫描访问永远不会提升到受保护段。
- 在驱逐中，从试用部分中选择最近使用最少的一行。
- 表 3.4 总结了 seg-lru 的操作。
- 在预备段的 MRU 位置插入新的行
- 在缓存命中时，行被提升到保护段的 MRU 位置。因为受保护的部分是有限的，提升到受保护的部分可能会迫使受保护部分的 LRU 行迁移到试用部分的 MRU 末端，使这一行在从试用部分被驱逐之前有另一个机会获得 hit。
- 因此，Seg-LRU 可以适应工作集的变化，因为老的缓存行最终被降级到试用段。
- Seg-LRU 策略的一个变体赢得了第一次缓存替换锦标赛[Gao和Wilkerson, 2010]。
LIP - BEYOND LRU: INSERTION AND PROMOTION POLICIES
- Qureshi 等人[2007]观察到，通过修改插入策略，同时保持驱逐策略不变(将缓存行逐出LRU位置)，可以实现基于最近的策略的变体。例如，可以使用 LRU Insertion policy (LIP) [Qureshi et al.， 2007] 来模拟 MRU (表3.2)，该策略在 LRU 位置插入新行，而不是 MRU 位置(见表3.5)。
- 这种见解促进了使用新的插入和 promotion 策略的替换策略的设计。通过以不同的方式解释最近的信息，这些策略可以处理比 LRU 更广泛的访问模式类。在本节中，我们将讨论这方面的一些值得注意的解决方案。由于应用程序通常由许多不同的访问模式组成，这些策略本身都不够，通常被用作混合解决方案的一部分，我们将在3.3节中讨论。
BIP - Bimodal Insertion Policy
- 由于像 LIP(和MRU) 这样的抗抖动策略不能适应在阶段变化期间工作集的变化，BIP [Qureshi等人，2007] 修改LIP，使缓存行偶尔(以低概率)插入到 MRU 位置。
- BIP 保持 LIP 的抗抖动，因为它在大多数时间插入 LRU 位置，但它也可以通过偶尔保留较新的行来适应阶段变化。表3.6显示，BIP 插入到 MRU 位置的概率为 e，设为 1/32 或 1/64。e 取值为 1 表示在 MRU 位置插入(模拟 LRU 插入策略)，e 取值为 0 表示在 LRU 位置插入(模拟 LIP 插入策略)。因此，从实现的角度来看，BIP 的参数统一了 LRU 和 MRU 插入光谱中不同位置的所有插入策略。
SRRIP - Static Re-Reference Interval Prediction
- Jaleel 等人 [2010b] 认为缓存替换可以被认为是一个重新引用区间预测 (RRIP) 问题，传统的 LRU 链可以被认为是一个 RRIP 链; LRU 链上一行的位置代表了自上次使用以来的时间，而 RRIP 链上一行的位置代表了它被预测重新引用的顺序 [Jaleel et al.， 2010b]。特别是，预测在 RRIP 链首的行将被最快的重新引用(最短的重新引用间隔)，而在 RRIP 链尾的行将被最远的重新引用(最大的重新引用间隔)。当缓存丢失时，位于 RRIP 链尾部的行将被替换。
- 在这个视图中，我们可以看到，LRU 策略预计，新的缓存行将有 near immediate re-reference 间隔（插入在 RRIP 链的头），而 thrash-resistant LIP 策略预测，新行将有一个遥远的 re-reference 间隔（插入在 RRIP 的尾部）。图 3.5 用一个 2bit 重引用预测值(RRPV)表示的RRIP 链说明了这一点：00 对应最近的重参考区间预测，11 对应遥远的重参考区间预测。
- Jaleel等人[2010b]表明，与预测位于 RRIP 链末端的重新引用间隔不同，预测中间的重新引用间隔有很大的好处，它允许替换策略适应不同访问模式的混合。
- 特别是，扫描对未重用数据的引用会破坏最近友好策略(如 LRU)，因为它们会丢弃应用程序的工作集，而不会产生任何缓存命中。
- 为了适应最近友好访问和扫描的混合，Jaleel等人 [2010b] 提出了 SRRIP，给进入的行一个中间的重新引用间隔，然后如果它们被重用，将它们提升到链首。因此，SRRIP 为最近友好的策略增加了抗扫描的能力，因为它防止具有远重引用间隔的行(扫描)驱逐具有近重引用间隔的行。
- 在大多数情况下，SRRIP 为每个缓存块关联一个 m 位值来存储它的 Re-Reference Prediction value (RRPV)，但是 Jaleel 等人[2010b] 发现一个 2 位的RRPV值就足以提供抗扫描能力。表 3.7 总结了2位 RPRV 值对 SRRIP 的操作。
BRRIP - Bimodal re-reference interval prediction policy
- 和 LRU 一样，当所有块的重引用间隔大于可用缓存时，SRRIP 会对缓存进行震荡。
- 为了添加 thrash-resistance scan-resistant 策略)，Jaleel et al. [2010b] 提出 BimodalRRIP (BRRIP), BIP[Qureshi et al., 2007] 的一个变种，大多数缓存块都插入了一个远端重引用间隔预测 (即 RRPV 为 3)，它很少插入一个中间重引用间隔预测(即 RRPV 为 2 )的缓存块。. BRRIP 业务的 RRPV 汇总于表 3.8。
- 由于应用程序可以在最近友好型和抖动型工作集之间交替使用，因此 SRRIP 和 BRRIP 本身都是不够的。在3.3节中，我们将讨论可以解决所有三种常见访问模式(最近友好、抖动和扫描)的 SRRIP 和 BRRIP 的混合版本，为许多应用程序带来性能改进。
PDP - Protecting Distance-Based Policy
- PDP 策略 [Duong et al.， 2012]是 RRIP 的一种推广，因为它 动态估计保护距离 (PD)，所有的缓存行在 PD 访问时都受到保护，然后才能被驱逐。PD 是一个单独的值，用于插入到缓存中的所有行，但它会根据应用程序的动态行为不断更新。
- 为了估计 PD, PDP 计算重用距离分布(RDD)，这是在程序执行的最近间隔内观察到的重用距离分布。使用 RDD, PD 被定义为覆盖缓存中大多数行的重用距离，这样大多数行在 PD 或更小的距离被重用。例如，图 3.6 显示了 436.cactusADM 的 RDD。这里 PD 设置为 64。使用小型专用处理器很少重新计算 PD。
- 更具体地说，在插入或提升时，每条缓存行都被赋一个值来表示其剩余的 PD (RPD)，即它仍然受到保护的访问的次数；这个值被初始化为 PD。每次访问一个集合后，该集合中每一行的 RPD 值都是通过递减的 RPD 值 (在0处饱和) 来老化的。只有当该行的 RPD 大于 0 时，该行才会受到保护。未受保护的行被选为受害者进行逐出。
GIPPR - Genetic Insertion and Promotion for PseudoLRU Replacement
- 受 RRIP 的启发，Jiménez[2013] 观察到在插入和 Promote 的选择上有很多自由度，因此他们使用 Insert/Promote 向量(IPV) 的概念概括了 插入和 Promote 策略的修改。
- 当块被插入到缓存中，或者从最近栈的不同位置提升时，IPV 则指示块在最近栈中的新位置。特别是，k 路 set-associative 缓存，IPV 是一个 k+1 个项组成的向量的，其中每个项的整数从 0 到 k-1，其中第 I 个位置的值表示位置 I 的块在被重新引用时应该提升到的新位置。IPV 中的第 k 个项表示应该插入一个新的传入块的位置。如果最近堆栈中的新位置小于旧位置，则块向下移动以腾出空间；否则，块会向上移动以腾出空间。
- 图3.7显示了两个样本IPVs，第一个代表LRU，第二个代表更复杂的插入和提升策略。
- 正如不存在适用于所有工作负载的单一插入策略或 RRIP 策略一样，每个工作负载的最佳 IPV 也是不同的。因此，Jiménez[2013] 提出了一种混合解决方案，使用 set dueling (见章节3.3) 来考虑多个 IPVs。
EXTENDED LIFETIME RECENCY-BASED POLICIES
- 延长生存期策略是基于最近的策略的一个特殊类，它通过将一些缓存行存储在辅助缓冲区或受害缓存中人为地延长它们的生存期。
- 这里的关键动机是将驱逐决定推迟到更晚的时候，以便做出更明智的决定。此策略允许粗粒度策略稍微增大缓存命中的重用窗口，使其大于缓存的大小。
Shepherd Cache
- Shepherd Cache (SC) 模仿了 Belady 的最优策略 [Rajan and Govindarajan, 2007]。由于 Belady 的策略需要未来访问的知识，Rajan 和 Govindarajan 在一个叫做 Shepherd Cache 的辅助缓存的帮助下模拟了这个未来的前瞻性。
- 特别地，缓存在逻辑上分为两个组件，模拟最佳替换的主缓存(MC)和使用简单的FIFO替换策略的 SC。
- SC 通过提供一个前视窗口来支持 MC 的最佳替换。
- 新行最初在 SC 中进行缓冲，直到新行离开 SC 时，才从 MC 决定替换受害者。当新行在 SC 中时，将收集关于替换候选人在 MC 中重用顺序的信息。
- 例如，由于 Belady 的策略驱逐了在未来被重用最多的行，所以早期被重用的行就不太可能被驱逐。当从 SC 中移除新行(由于 SC 中的其他插入)时，将通过从前瞻性窗口中尚未重用的 MC 中选择一个候选者或最后重用的候选者来选择一个替换候选者; 如果 MC 中的所有行在 SC 行重用之前被重用，那么 SC 行将替换自己。尽管 SC 和 MC 在逻辑上是分离的，Rajan 和 Govindarajan[2007] 通过组织缓存避免了数据从一个组件到另一个组件的任何移动，这样两个逻辑组件可以被组织为一个单一的物理结构。
- 因此，SC 通过在 SC的帮助下延长 MC 缓存中的行的生命周期，模拟了一种更好的替换方案, SC 的权衡是 MC 中的替换以高 lookahead 接近真正的最优，而更高的 lookahead 是以降低 MC 容量为代价的。不幸的是，Jain 和 Lin[2016] 的后续工作表明，为了接近 belady 的最优策略的行为，该策略需要提前 8x 缓存的大小。
- 简单总结：cache 分为 main 和 shepherd 两部分，MC 使用 LRU，SC 使用 FIFO替换策略。新的 cacheline 首先放入SC中，在此期间统计MC中的访问状况。若这个cacheline在离开SC时，MC中存在没有被访问的单元，则进行SC->MC的替换。但该方法的问题是 lookahead 来源于SC，但 SC 过大则会导致MC容量不足。
FREQUENCY-BASED POLICIES
- 基于频率的策略不依赖于最近的访问频率，而是使用访问频率来识别受害者，因此访问频率较高的行优先缓存在访问频率较低的行之上。这种方法不太容易受到扫描的干扰，并且在较长一段时间内考虑重用行为，而不仅仅是最后一次使用。
- 最简单的基于频率的策略是最少频繁使用(LFU)策略[Coffman and Denning, 1973]，它将频率计数器与每条缓存行关联起来。当该行插入缓存时，频率计数器初始化为 0，每次访问该行时，频率计数器都增加。在缓存丢失时，频率最低的候选对象将被逐出。表 3.9 总结了这些操作。
- 不幸的是，基于频率的策略不能很好地适应应用程序阶段中的更改，因为即使不再访问前一阶段中具有高频率计数的行，它们仍然会缓存到新的阶段中。为了解决这个问题，有几个解决方案[Lee等人，2001年，O Neil等人，1993年，Robinson和Devarakonda, 1990年，Shasha和Johnson, 1994] 用最近的信息增加频率信息，让旧的行优雅地老化。这里我们讨论两种这样的解决方案。
FBR - Frequency-Based Replacement
- FBR [Robinson和Devarakonda, 1990] 指出，基于频率的方法容易受到短时局域性突发的高计数器值的误导。
- 因此，FBR 通过选择性地增加频率计数器从频率计数中剔除局部性。特别是，FBR 不增加 LRU 堆栈的顶部部分的频率计数器，这被称为新部分。因此，时间局部性的短突发不会影响频率计数器。图 3.8 说明了这个策略。
- 不幸的是，这种策略有一个缺点，即一旦新部分的行老化，即使是经常使用的行也会很快被淘汰，因为它们没有足够的时间来建立频率计数。因此，FBR 进一步限制替换在一个旧的部分中使用最少的行，其中包括最近没有被访问的行(LRU堆栈的底部)。堆栈的其余部分称为中间部分，它为经常使用的行提供了足够的时间来建立它们的频率值。
- 表 3.10 总结了 FBR 的操作策略。
- 同时维护frequency和recency stack. 将recency stack分为new/middle/old三个区域，new区域的计数不增加，逐出old区域的LFU。
LRFU - Least Recently/FrequentlyUsed
- LRFU 策略 [Lee等人，2001] 建立在这样的观察之上：LRU 和 LFU 策略代表了结合了最近和频率信息的一系列政策的极端点(见图3.9)。LRFU 使用一种名为联合近期和频率(Combined Recency and Frequency, CRF)的新指标，通过允许近期和频率之间的灵活权衡来探索这个频谱。
- 与基于频率的策略一样，LRFU 将每个过去对块的引用计算进去，但与基于频率的策略不同的是，LRFU 通过一个权重函数来衡量每个引用的相对贡献。特别地，LRFU 为每个区块计算 CRF 值
- CRF 值是权重函数 F(x) 对每个过去的参考的总和，其中 x 是过去的引用距离当前时间的距离。
- 因此，对于纯粹基于频率的策略仿真，权重函数可以对所有过去的引用给予同等的优先级，而对于基于最近的策略仿真，权重函数可以对最后的引用给予较高的优先级。
- LRFU 采用式3.1中的权重函数，其中 λ 是经验选择的参数。权重函数为老的缓存行提供指数级的低优先级，这使得 LRFU 保留了 FBR 的好处，同时支持优雅的老化。
- 表 3.11 总结了块 b 在不同决策点上的 LFRU 策略操作。
- LRFU 的性能很大程度上依赖于此，因此随后开发的 ALRFU 策略动态调整 λ 的值 [Lee et al.， 1999]。
Hybrid
- 混合策略 [Jaleel et al.， 2010b, Qureshi et al.， 2006, 2007] 认识到不同的工作负载，甚至相同工作负载中的不同阶段，可以从不同的替代策略中受益。例如，如果程序在小工作集和大工作集之间交替，当工作集较小时，它将受益于最近友好策略，当工作集较大时，它将受益于抗抖动策略。因此，混合策略评估应用程序当前工作集的需求，并从多个竞争策略中动态选择。混合策略面临的两个主要挑战是
- (1) 准确识别最有利的策略
- (2) 以较低的硬件成本管理多个策略
ADAPTIVE REPLACEMENT CACHE (ARC)
- 自适应替换缓存(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。
SET DUELING
- ARC 等混合策略的一个问题是维护附加标记目录的巨大开销。
- Qureshi 等人[2006] 引入了 Set Dueling，这是一种以较低的硬件成本对不同策略的行为进行抽样的精确机制。
- Set Dueling 建立在这样的观察之上: 一些随机选择的集合可以准确地表示整个缓存上不同替换策略的行为。
- Qureshi 等人[2006] 用数学方法表明，对于 1-4MB(1024–4096 sets) 的缓存，64 个集合就足以捕获整个缓存的行为。现在，我们通过讨论两个具有代表性的策略来更详细地讨论 Set Dueling。
DIP - Dynamic Insertion Policy
- Dynamic InsertionPolicy(DIP) 动态插入策略(DIP)通过动态调整传入缓存行的插入位置，结合了最近友好策略和抗抖动策略的优点 [Qureshi等人，2007]。特别地，DIP 在最近友好的 LRU(表3.1) 和抗抖动的双模态插入策略 BIP (表3.6) 之间交替使用。
- LRU 插入到 MRU 位置
- BIP 以一定的概率插入到 MRU 位置，一定概率插入到 LRU 位置
- 为了在两个策略中进行选择，DIP 使用 Set Dueling 动态跟踪每个策略的命中率。图 3.11 显示 DIP 专用于 LRU (图3.11中的集0、5、10和15) 和 BIP(图3.11中的集3、6、9和12)。这些专用集被称为 Set Dueling 监视器(SDM)，而其余集被称为跟随集。
- The policy selection 策略选择(PSEL) 饱和计数器通过识别接收更多缓存命中的 SDM 来决定获胜策略。特别地，当专用于 LRU 的 SDM 接收到命中时，PSEL 增加，当专用于 BIP 的 SDM 接收到命中时，PSEL 减少 ( k 位 PSEL 计数器初始化为 2^{k-1}。
- 获胜的策略由 PSEL 的 MSB 确定。如果 PSEL 的 MSB (最高有效位) 为 0，跟随集使用 LRU 策略；否则跟踪集将使用 BIP。因此，Set Dueling 不需要任何单独的存储结构，除了 PSEL 计数器。
DRRIP - Dynamic Re-Reference Interval Policy
- DRRIP 建立在 DIP 的基础上，增加了抗扫描的能力。特别是，DRRIP 使用 set dueling 创建了 SRRIP 和 BRRIP 的混合，SRRIP 是 LRU 的抗扫描版本(表3.7)，BRRIP 是 BIP 的抗扫描版本(表3.8)。
- 正如我们将在第 4 章中看到的，Set Dueling 背后的洞察力对许多后续细粒度策略产生了很大的影响，这些策略使用 Set 采样的概念来有效地跟踪元数据，以确定细粒度缓存行为。
细粒度缓存
- 细粒度策略在插入时区分高速缓存行，这种区分通常基于类似高速缓存行的前一个生存期的回收信息。
- 例如，如果细粒度策略得知某一行在其之前的生命周期中没有被重用而被逐出，那么它可以以低优先级将该行插入到缓存中。
- 相比之下，粗粒度策略(如LRU)只有在从 MRU 位置迁移到 LRU 位置后才会驱逐一行，所以该方案强制缓存行驻留在缓存很长一段时间，消耗宝贵的缓存空间来确定行应该驱逐。因此，通过学习以前缓存行的行为，细粒度策略可以更有效地使用缓存。
重用距离
二分类
其他
- Utterance