1 简介

范围：为了取得广度和简洁之间的平衡，本文专注于最近的创新或有洞见的缓存预取研究成果，而不包括其他技术或处理器部件。只讨论中央处理器（CPU）的预取，而不讨论图形处理器（GPU）。文中仅展示研究成果的关键思想，而不包括定量结果，因为评估平台和方法各异。我们根据关键特征对这些成果进行分类，希望揭示其中的相似和差异之处。希望本文能够对研究人员、系统设计师、应用程序开发者等提供鸟瞰预取技术的状态。

2 背景与回顾

下文简要讨论预取技术（2.1节）并将引用既有分类工作和详细背景 [Srinivasan 等 2004; Vanderwiel 和 Lilja 2000; Sherwood 等 2000; Falsafi 和 Wenisch 2014]。 第2.2至2.6节介绍预取算法和研究工作中部分关键参数。第2.7节讨论了充分发挥预取潜力时所需的权衡。

2.1 指标和术语

一些参数和指标可用于表征预取器 [Emma 等 2005]。图2(a)描述了预取度（prefetch degree，预取数据超前当前数据的行数）和预取距离（prefetch distance，连续预取数据的行数）。覆盖范围（converage）表示预取消除的原本未命中的缓存行部分。准确（accurate）或有效（useful）预取是指消除了原本未命中的预取操作，而有害（harmful）预取是指替换掉有用数据而导致未命中的预取操作。及时（timely）预取是指在数据被访问前就完成预取请求并放入缓存中的预取操作，反正称为延迟（late）预取。超前（lookahead）表示预取提前的程度，即预取的数据按时到达缓存并且不会被其他数据替换。 如果预取的数据块已经存在于缓存中，则预取是多余（redundant）的。

2.2 硬件与软件预取

硬件预取会占用额外存储（如：表）来检测特定的内存访问模式（如定步长间隔访问），并据此来预取期望稍后会被引用的数据。软件预取则是基于编译器或预执行分析，在源代码中添加预取指令，例如链式数据结构中，编译器可以插入预取被访问过节点的子节点的预取指令。图3展示了软件预取的一个示例。

2.3 数据和指令预取

与访问指令相比，数据的访问模式对输入数据集更敏感且规律性更小，这使得数据预取更具有挑战性。运行商业载荷的大型程序块可能导致 L1 和 L2 缓存缺失，所以仍需要关注指令预取。然而，对于指令缓存未命中忽略不计的应用（例如科学运算）则不要求指令预取。

2.4 核心端和内存端预取

在核心端（core-side or processor-side）预取中，预取请求由缓存层次结构中的引擎发起，而在内存端（memory-side）预取中，引擎则位于主存子系统中，在内存总线之后。内存端预取可以通过在片外存储元数据来节省宝贵的芯片空间，还可以在主存端进行优化 [Yedlapalli 等 2013]。与此相对比，核心端预取可以更准确地了解内存引用模式，并可执行缓存级别的优化，例如避免缓存污染 [Srinath 等 2007]。

2.5 基于模式和复杂程度的分类

预取器可以根据它们所针对的未命中或访问模式的规律性或复杂性进行分类。 下 K 行预取器（next-K line prefetcher）在当前未命中时预取其后的 K 行。步长预取器（stride prefetcher）预取与当前未命中相关的定步长间隔模式对应的缓存行 [Chen 和 Baer 1995]，参见图 2(b)。例如，如果此前被加载的访问地址序列是 A、A+Q、A+2Q 和 A+3Q，那么地址 A+3Q+Q 处的数据将被预取，因为该序列的步长为Q。Q=1 时称为流预取（stream prefetching）。

然而在许多应用中，访问模式并不是完美的定步长间隔，这被称为不规律（irregular）模式，参见图2(c)。相关预取（correlation prefetching）跟踪历史引用序列或未命中地址，以检测某些相关性并用来预测需要被预取的未来的未命中地址。 空间预取器（spatial prefetcher）假定存在空间局部性，因此预取当前未命中的附近行。[Somogyi et al. 2006] 时间预取器（temporal prefetcher）假设最近看到的地址流将会重复出现，因此基于最近未命中历史的时间流进行预取。[Wenisch et al. 2005]

还有一些针对不规则访问模式的复杂预取器，诸如[Jain and Lin 2013; Somogyi et al. 2009]。本文也讨论一些其他的预取器或上述预取器的变体。

2.6 基于目标核缓存级别的分类

...

2.7 预取面临的挑战

要充分发挥预取的潜力，需要解决以下几个挑战。

2.7.1 实现开销

...

2.7.2 性能权衡

...

2.7.3 缓存污染和资源争用

如图4所示，预取可看作是旁路（bypass）的互补方法。随着缓存获取的数据量增加，由于更高的存储利用率，命中率随之增加；然而，一旦工作集超过缓存容量，抖动就会开始。预取块会开始替换按需获取的有效数据或由其他核的预取器带入共享缓存的块。由此产生的缓存污染会造成更严重的未命中，这可能会触发更多的预取。随着核心数量的增加，核心间的干扰升级，并且由于每核带宽减少，预取请求导致的争用也会增加。

一些技术将预取块放在额外的缓冲区中（参见6.1节）。然而，顺序或与并行访问会产生额外的能量或延迟开销。此外，预取需要重新组织芯片架构，并杜绝按需获取和预取数据共享缓存空间。显然要达到最佳平衡（图4中的峰值点）需要仔细调节预取参数和激进程度。

2.7.4 可靠性挑战

预取技术会增加数据在缓存中的驻留时间，导致软错误率增加。[Mittal 和 Vetter 2015] 此外，预取引入的额外写入可能会导致写入耐久性有限的非易失性存储器中的硬错误和设备寿命缩短。
后续章节讨论的技术将寻找上述问题的解决之道。

3 硬件预取、数据预取与核心侧预取

在本节中，我们将讨论构成最突出的预取方法的硬件预取、数据预取和核心端预取技术。在本节和下一节中，预取技术将粗略地分成几类来讨论，尽管某些技术属于多个分组。

3.1 流预取和步长预取

Jouppi [1990acm.org] 提出了一种使用流缓冲区的预取方案。当缓存未命中时，序列缓存块将被预取到一个单独的流缓冲区，直至缓冲区填满。这样预取块将不会置于L1缓存中，从而避免缓存污染。这个缓冲区是一个队列（FIFO）结构。下一次，L1缓存未命中需要预取时，流缓冲区中的第一项将被取出，当命中时即可直接放入L1缓存。当预取数据被使用时，将发起更多预取操作，这使得缓冲区在指令执行期间保持饱和，进而隐藏整体延时。Jouppi 还探索了并行使用多个流缓冲区，可预取多个交织的引用流。 这在多种情况下是有用的，例如，当应用程序访问循环内的多个数组时。

基于未命中地址流可以通过 Markov 转移图来近似的假设，Joseph 和 Grunwald [1997acm.org] 提出了一种的预取方法。图中从节点 P 到节点 Q 的每个转移都被赋予了一个权重，它表示下一次访问节点为 Q 时访问节点 P 的比例。假设执行模式是重复的，这个 Markov 图可用于预测当前未命中地址之后的未命中地址。由于程序的时变行为，并且节点数可能非常多，因此构建和存储完整的 Markov 图是不可行的。为了解决这个问题，他们限制了图的节点数及其出度，使之可以存储在表中。当未命中地址与表中的地址匹配时，可以预取通过图预测的下一个地址。从当前地址有更大概率转移到的“下一个地址”具有更高的优先级。如果预取请求队列已满，则丢弃低优先级的请求。

Sherwood 等人 [2000acm.org] 提出了一个方案，流缓冲区遵循地址预测器（address predictor）的预测，而非固定步长预测器（fixed-stride predictor）。（译者注：文中称为该方案为 predictor-directed stream buffer，PSB，预测器指导的流缓冲区）这使得预取可以使用比固定步长预测器更有效的其他预测器。他们演示了使用步长过滤 Markov 预测器（stride-filtered Markov predictor），该预测器在 Markov 预测器的表之前增加了一个双 Delta 步长表（即当连续观察到两次新步长时，才能取代此前预测的步长）。在回写阶段，载入未命中的 PC 将作为用为步长表的索引。如果步长（当前未命中地址-上次地址）与双 Delta 步长或上次的步长不同，那么则无法根据步长预测这个地址，因此，它将被储存在 Markov 预测器中。在 Markov 表中查询上次未命中的地址可寻找下一个预取地址。当命中时，Markov 得到的地址被用于预取，而未命中时则采用一个步长后的地址。该预测器可准确地用于基于指针和基于阵列访问的复杂应用预取。

Sair 等人 [2002psu.edu] 分析了负载未命中流（load miss stream），以增进对预取器有效性的理解。负载缺失流根据访问未命中的模式可分为四类，即下一行（next-line）、步长（stride）、同对象（same-object）和基于指针（pointer-based）的未命中流。同对象未命中发生于访问相同堆内对象上的不同部分时。这类未命中可以通过预取整个对象来避免，或者预取将要访问的对象内一部分的缓存块即可。基于指针的未命中发生于一个指针解引用来访问对应的对象时。由于使用预取方式消除这两类未命中十分具挑战性，文中引入了两个分析指标，并设计了一个缓解策略。指针可变性（pointer variability）显示了频繁变化或稳定的指针发生转换的次数（加载一次指针称为指针转换），它量化了一个地址的指针转换和此前从该地址加载的指针不一样的次数。对象扇出（object fan-out）表示在缓存中有多少指针被转换并经常未命中。因此，具有高可变性和高扇出的程序相对而言更难预取。本文还表明通常硬件就可以精准分类未命中类型，并且基于该分类有效地执行预取。

Iacobovici 等人 [2004acm.org] 注意到，单位步长和单个的非单位步长预取技术不适用于科学计算应用的常见模式。他们提出了一种多步长预取器（multi-stride prefetcher），可以检测和预取至多两个稳态和两个过渡步长的组成的流，即总共四个不同的步长。（译者注：文中称为 recurrent prefetch table，RPT，循环预取表）一个多步长未命中流的例子是：A, A+1, A+2, A+4, A+5, A+6, A+8, ...，其由两次单步长和一次双步长循环组成。在训练阶段，预取器检测步长模式。如果流中相邻的未命中步长相同，则预取器将其视为属于一个状态，保持状态1。如果未命中（步长不同），则预取器过渡到状态2，并设定此时步长为过渡步长 stride12。后续，当第二种步长下未命中时，切换到状态1，并设定步长为过渡步长 stride21。训练结束后，当未命中负载对应步长与记录值相同时，即可触发预取。

Zhu 等人 [2010acm.org] 意识到同一个流中的数据访问的时间间隔是可预测的，例如，在定步长预取器中，流内的相邻访问预期是以几乎相等的时间间隔发生的。文中据此提出新的预取技术，相较传统预取，该方案不仅存储所引用的地址，且记录时间信息用来预测何时未命中。时间信息根据未命中的次数衡量。（译者注：文中称为 time-aware stride prefetcher，TAS，时间感知步长预取器）根据访问是否来自相同的存储区域或指令，可将未命中地址区分为不同的流。该技术通过避免不及时预取来减轻缓存污染和内存带宽浪费。

Kim 等人 [2014acm.org] 提出了一种旨在识别所有潜在的步长流的技术，包括由基于 PC 和基于 Delta 相关性的预取。该技术判断最后一次未命中和之前的未命中是否形成了一个定步长的流，且该流切分了两个以上的未命中地址。由于最后一次未命中可能属于步长不同的其它流，选择出最佳的流需要同时跟踪多个流。在这种情况下，由于长的流可能覆盖更多的未命中且准确性更高，该技术选择最长流作为最佳。这解决了重叠流的问题。检测时，流中的未来的访问可被识别。受存储空间限制，可以跟踪的流数量有限，尽管如此，由于跟踪了多个流，该技术可以跳过其中一些流来延续预取。

3.2 相关预取

表II中列举了许多相关预取技术，这里只讨论其中的一部分。

Lai 等人[2001acm.org] 提出了一种基于死块预测的预取技术。该技术记录了内存引用跟踪，以估计 L1 数据缓存块何时看到最后一次访问。从这个时候开始，直到缓存未命中替换之，该块称为死块。[Mittal 2014] 他们指出死块时间通常很长，且超过从下一级缓存获取数据所需的时间。该技术还使用地址相关性来预测即将被引用的块，并预取它以消除未命中从而提高性能。该块可以存储在L1缓存中的死块位置。文章表明该技术提供了及时有效的数据预取。然而，该技术需要与应用程序工作集大小相当的存储空间。相关性数据需要一直存储，横跨长时间重复的应用程序阶段，并且由于有关上次引用的信息需在每次 L1 访问时计算，因此需要将其存储在芯片内以达到高带宽。因此，为了提供合理的覆盖率，该技术可能需要不切实际的大存储空间。[Ferdman 和 Falsafi 2007]

Nesbit 和 Smith [2004wisconsin.edu] 意识到传统的预取方式使用表存储未命中地址流，虽然表支持快速查找，但需要预留固定大小的空间，而表中的条目将快速变旧，这可能会触发无用预取。他们提出了另一种存储预取历史的结构，该结构取消了预取键（prefetch key）与预取所需的历史信息的存储匹配。首先，预取键用于访问指向全局历史缓冲区（global history buffer，GHB）的指针索引表。而每个 GHB 记录存储了一个全局的未命中地址和一个链接指针（link pointer）。GHB 各记录通过连接指针链形成地址链表，同一链表上的记录具有相同的预取键。而这些不同的键可以分别实现不同的基于历史的预取技术，例如，步长预取可以使用加载指令的 PC，而 Markov 预取 [Joseph 和 Grunwald 1997] 可以使用独立 PC 的全局未命中地址。GHB 可以根据跟踪所需历史的长度设置大小，相较于传统的表有更高的存储效率。GHB 使用 FIFO 缓冲区实现，陈旧记录可自动删除。因此，准确地重构访问方式使得利用复杂访问模式的复杂预取技术得以实现。
...

3.3 改进预取训练的方法

用于预取器训练的流决定了预取器观察到的重复模式，因此训练流对预取器的效果影响重大。 下文将讨论一些改进预取训练的技术（例如，Ferdman 等 [2011]，Manikantan 等 [2011]，Jain 和 Lin [2013]，以及 Guttman 等 [2015]）。

Manikantan 等 [2011acm.org] 研究如何拓展相关预取器存储的训练流以提高其性能。文中定义一级未命中（primary miss）指发起下一级缓存或内存请求的未命中，次级未命中（secondary miss）则指一级未命中请求的数据尚未到达缓存时的未命中请求。他们注意到仅使用一级未命中流来训练预取器，会导致其无法从训练中学习次级未命中和缓存命中信息。他们提出训练流中的次级未命中和缓存命中的运用可以提高预取器观察到的规律性。测量出熵减证实了规律性的提升。虽然其他技术仅在一级未命中时触发预取，但他们认为次级未命中时也触发预取可提高预取器的性能。尽管只有微小的硬件改动，但该技术确实可以提高缓存命中。

Jain 和 Lin [2013acm.org] 提出不规则流缓冲区预取器（irregular stream buffer，ISB），用于确定时间相关的不规则内存访问流。通过引入额外的中间层（indirection level），可以将相关的物理地址分组转换为新地址空间中的连续地址。该技术使得预取元数据可同时具有空间和时间的顺序性。将不规则流预取问题降阶为在新的地址空间中的顺序预取。这种重新映射也提高了精度和覆盖率，因为可以通过加载指令的PC将预取器输入分离为若干流 [Nesbit 和 Smith 2004]。 此外，将大多数元数据存储在芯片上，使得训练可以使用 LLC 访问流而非 LLC 未命中流，这会导致参考流的可预测性有显著提高。

3.4 基于标签的相关预取

...

3.5 预执行或辅助线程预取

...