高级预取技术

Google的数据中心团队在对其最重要的几个服务——Search、Ads、Bigtable——进行性能剖析时发现了一个令人震惊的事实：30%$\sim$40%的CPU周期消耗在LLC Miss的等待上。处理器的执行单元大部分时间都在无所事事地等待数据从DRAM返回。如果有一种硬件机制能够“预知”未来的内存访问模式，并提前将数据搬入Cache——在程序真正需要数据之前就将其准备好——那么这些被浪费的周期就可以被回收为有用的计算。这正是预取器（Prefetcher）要做的事情。

预取是对数据访问模式的一种“投机”——预取正确时，访存延迟被完美隐藏，处理器不必等待DRAM；预取错误时，无用的数据污染了Cache、浪费了宝贵的内存带宽。这种投机与第 6.0 章中讨论的分支预测在哲学上形成了完美的对偶：分支预测是对控制流的投机，预取则是对数据流的投机。两者共同体现了处理器设计的核心理念——在有限的晶体管预算和功耗约束下，通过投机和并行的层层叠加来逼近指令吞吐率的理论上限。

读完本章，你将理解从简单步幅预取到基于神经网络的预取器的完整技术谱系，掌握空间模式预取、时间预取、指针追踪预取和ML预取的核心算法与硬件实现，并学会如何在覆盖率、精度和硬件开销之间进行权衡。

第第 6.0 章章在讨论提高Cache性能的方法时，已经介绍了硬件预取的基本思想：顺序预取和步幅预取可以有效地覆盖具有规则访问模式的应用。然而，现代应用程序的访存行为远比简单的顺序或等步长模式复杂。数据库的索引遍历、图算法的邻接表访问、链表的指针追踪——这些不规则的访问模式构成了现代工作负载中Cache缺失的主要来源，也是性能瓶颈的核心所在。

Data Prefetching Competition（DPC）系列竞赛的研究表明，一个精心设计的预取器可以将SPEC CPU基准测试的IPC提升15%$\sim$40%，而在图遍历等不规则应用上，预取器带来的性能提升甚至可以超过2$\times$。然而，预取是一把双刃剑：不准确的预取会浪费宝贵的存储带宽、污染Cache中的有用数据、增加功耗。因此，现代高性能处理器中的预取子系统需要在覆盖率（Coverage）、精度（Accuracy）和及时性（Timeliness）三个维度上取得精妙的平衡。

本章将系统地讨论超越简单步幅预取的高级预取技术，涵盖空间模式预取、时间预取、指针追踪预取、预取管理机制，以及基于机器学习的新兴预取方法。

在进入具体的预取器设计之前，有必要先明确为什么步幅预取不够。步幅预取器假设访问模式可以用一个固定的地址增量来描述——这个假设在以下场景下失效：

（1）变步幅模式。嵌套循环中，内层循环产生一个步幅（如+1），外层循环跳转到下一行产生另一个步幅（如+100）。步幅预取器只能跟踪一个步幅，无法处理这种交替模式。

（2）间接数组访问。A[B[i]]的访问地址完全取决于B[i]的值，没有任何可预测的步幅。

（3）指针追踪。链表、树、图等数据结构的遍历，下一个访问地址隐藏在当前访问的数据中。

（4）阶段性变化。程序在不同执行阶段可能展现完全不同的访问模式，步幅预取器需要重新训练。

高级预取技术正是为了覆盖这些步幅预取器无法处理的模式而设计的。每种技术针对特定类型的模式进行优化，没有一种单一的预取器能够覆盖所有模式——这就是为什么现代处理器通常部署多个互补的预取器。

表表 7.1给出了本章讨论的预取技术的分类概览。

类别	代表方案	核心思想
空间模式预取	SMS, VLDP, BOP	学习并重播空间/delta模式
时间预取	Markov, STMS, ISB	记录并重播历史地址序列
指针追踪预取	CDP, Runahead	从数据中提取指针或预执行
预取管理	FDP, 多级协调	动态调节预取行为
ML预取	LSTM, Voyager	序列预测模型

高级预取技术分类

空间模式预取

空间模式预取（Spatial Pattern Prefetching）的核心思想是：程序在访问某个内存区域时，往往呈现出特定的空间访问模式（哪些偏移会被访问、哪些不会），而这种模式在程序的不同位置可能会重复出现。空间模式预取器通过学习和记录这些模式，在检测到类似的触发条件时重播（replay）记录的模式，从而实现精确的预取。从本质上看，预取是对Cache层次结构的“前瞻性填充”——与第 5.0 章中讨论的按需填充（demand fill）形成互补：按需填充在Cache缺失发生后被动地取回数据，而预取则在缺失发生前主动地将数据搬入Cache。

与简单的顺序预取或步幅预取相比，空间模式预取的关键优势在于它能够捕捉不规则但可重复的空间访问模式。例如，一个结构体数组的遍历可能只访问结构体中的特定字段，从而在每个Cache行中只产生若干不连续的访问；空间模式预取器可以学习这种稀疏的访问模式并精确地只预取被访问的Cache行，避免预取不必要的数据。

为了更具体地说明空间模式预取的价值，考虑以下代码：

struct Record {
    int id;           // offset 0, 4B
    double value;     // offset 8, 8B
    char name[48];    // offset 16, 48B
    double result;    // offset 64, 8B
    char padding[56]; // offset 72, 56B
};  // total: 128B = 2 cache lines

struct Record data[N];
for (int i = 0; i < N; i++)
    sum += data[i].value + data[i].result;

每个Record占128字节（2个Cache行）。程序只访问value（在第1个行的偏移8处）和result（在第2个行的偏移0处）。理想的预取应该只预取这两行中的实际被访问的行，而非盲目地预取所有连续行。

顺序预取器会预取所有连续行——对于上述模式，它会预取4行但只有2行被使用，精度50%。 步幅预取器检测到步幅为2行，可以准确预取每个结构体的第1行——但它无法同时预取第2行（因为步幅是固定的）。 空间模式预取器（如SMS）在训练阶段记录“每2行的区域中，第0行和第1行都被访问”的位向量模式，然后在后续触发时精确预取这两行——精度100%，覆盖率100%。

SMS

Spatial Memory Streaming（SMS）由Somogyi等人于2006年提出，是空间模式预取的开创性工作。SMS的核心观察是：程序对一个内存区域（称为空间区域，spatial region）的访问模式往往与触发该区域首次访问的指令PC（程序计数器）相关联。如果同一条load指令在不同时刻触发了对不同空间区域的首次访问，那么它在这些区域中产生的后续访问模式很可能是相似的。

基本概念

SMS将物理地址空间划分为固定大小的空间区域（Spatial Region），每个区域的典型大小为2 KB$\sim$4 KB（即32$\sim$64个Cache行）。SMS使用一个位向量（bit vector）来记录每个空间区域中哪些Cache行被访问过。

SMS的操作分为两个阶段：训练阶段（recording）和预测阶段（prediction）。训练阶段观察并记录程序对空间区域的访问模式；预测阶段利用已记录的模式来预取。

硬件结构

SMS由三个主要的硬件表组成：

• 活跃生成表（Active Generation Table, AGT）：跟踪当前正在被访问的空间区域。每个表项包含空间区域的标签、触发PC、以及一个位向量，记录该区域中已被访问的Cache行偏移。

• 模式历史表（Pattern History Table, PHT）：存储已完成的空间访问模式。以触发PC为索引，每个表项包含一个位向量，记录该PC触发的空间区域的典型访问模式。

• 过滤表（Filter Table, FT）：用于检测空间区域的首次访问（即触发访问），并记录触发PC。

图图 7.1展示了SMS的整体架构。

SMS预取器的整体架构

工作流程

SMS的工作流程如下：

1. 检测触发访问：当一个L1 D-Cache缺失发生时，检查该地址所属的空间区域是否已经在AGT中。如果不在，说明这是对该空间区域的首次访问（触发访问），将该区域加入FT/AGT，并记录触发PC和触发偏移。

2. 记录访问模式：后续对同一空间区域的Cache缺失会更新AGT中对应条目的位向量，将新访问的Cache行偏移位设为1。

3. 存储模式：当一个空间区域从AGT中被驱逐时（因为AGT满或区域长时间未被访问），将其位向量与触发PC一起存入PHT。

4. 预取预测：当检测到一个新的触发访问时，以触发PC为索引查找PHT。如果命中，取出对应的位向量，根据位向量中为1的位生成预取请求。

位向量的对齐

一个关键的设计细节是位向量的对齐方式。触发访问可能发生在空间区域的任何偏移处，而位向量记录的是相对于触发偏移的访问模式。SMS将位向量旋转（rotate）使触发偏移对齐到位向量的固定位置（例如位0），从而使不同区域的模式可以正确地进行比较和重播。在预测时，根据新的触发偏移将位向量反向旋转，恢复到正确的物理偏移。

考虑一个具体的例子。假设空间区域大小为2 KB（32个Cache行），位向量有32位。如果触发访问发生在区域内的第10个Cache行（偏移=10），随后的访问模式为第12、15、20个Cache行被访问。原始的位向量（未对齐）为： $$\text{raw} = 00000000\,10000100\,10100000\,00000000_2$$ 其中第10、12、15、20位为1。经过旋转对齐后（将第10位移到第0位）： $$\text{aligned} = 00000000\,00001000\,01010000\,00000101_2$$ 第0、2、5、10位为1——表示“触发后+0, +2, +5, +10行”被访问。

这种旋转对齐的好处是：当同一条PC在另一个空间区域的不同偏移处触发时（例如偏移=25），对齐后的位向量仍然是相同的——因为程序的空间访问模式是相对于触发点的，而非绝对位置。在预测时，将对齐的位向量反向旋转25位，即可得到正确的物理偏移位图。

旋转操作在硬件上通过Barrel Shifter（桶形移位器）实现。一个32位的Barrel Shifter需要$5 \times 32 = 160$个2:1 MUX，面积和延迟都很小（约2个门级延迟）。

存储开销

假设空间区域大小为2 KB（32个Cache行），AGT有32个表项，PHT有1024个表项：

• AGT：每个表项需要区域标签（约20位）+ 触发PC（约20位）+ 位向量（32位）+ 有效位 $\approx$ 9字节，共32 $\times$ 9 = 288字节。

• PHT：每个表项需要PC标签（约15位）+ 位向量（32位）$\approx$ 6字节，共1024 $\times$ 6 $\approx$ 6 KB。

• 总计约6.3 KB。

SMS的变体与改进

SMS自提出以来催生了多种变体和改进工作：

（1）PC+偏移索引：原始SMS仅以PC索引PHT，改进版本使用PC与触发偏移的组合作为索引，以区分同一load指令在不同偏移触发时可能呈现的不同空间模式。例如，一条遍历结构体数组的Load指令可能在结构体的不同字段位置触发，产生不同的后续访问模式——PC+偏移索引可以分别学习这些不同的模式。

（2）多粒度空间区域：不同应用的最佳空间区域大小可能不同。有些应用在2 KB粒度上有好的模式（如结构体大小小于2 KB的数组遍历），另一些在4 KB或8 KB上更佳（如大型对象的遍历）。改进的SMS支持多个区域大小，并动态选择最佳粒度。

一种实现方式是维护两套AGT/PHT：一套使用2 KB区域，另一套使用4 KB区域。在预测时，选择置信度更高的那套来生成预取。这种方式将硬件开销增加到原来的2倍，但可以覆盖更多类型的空间模式。

（3）与步幅预取的融合：SPP（Signature Path Prefetcher）等后续工作将SMS的空间模式思想与delta/步幅预测相结合，使用签名（signature）来编码最近的delta序列，并以此预测后续的空间访问模式。SPP在DPC-3竞赛中获得了亚军。

SPP的核心思想是使用最近$k$个delta值的哈希签名作为预测表的索引——这本质上是VLDP思想和SMS思想的融合。SPP在一个统一的框架中同时捕获步幅模式和空间模式：

• 常数步幅$(\delta, \delta, \delta, \ldots)$的签名始终相同，对应PHT中稳定的预测。

• 空间模式的不同触发偏移产生不同的签名前缀，对应PHT中不同的预测路径。

（4）压缩位向量：原始SMS使用完整的32位位向量（对应2 KB区域中的32个Cache行），但在很多应用中，位向量是稀疏的（大部分位为0）。使用run-length编码或差分编码可以将位向量压缩到原来的30%$\sim$50%，允许PHT存储更多的模式。

（5）跨页面的空间区域：原始SMS的空间区域严格对齐在固定的地址边界上，不能跨越页面边界（因为虚拟地址到物理地址的映射在页面边界处不连续）。改进版本使用虚拟地址而非物理地址来定义空间区域，从而可以跨越页面边界。但这引入了别名问题——不同虚拟地址映射到同一物理地址的情况。

SMS的AGT管理

AGT（Active Generation Table）的管理策略对SMS的效果有重要影响。AGT需要决定何时将一个空间区域的记录“关闭”并将其位向量转移到PHT。

常见的关闭条件包括：

（1）AGT容量驱逐。当AGT满且需要为新的空间区域分配表项时，选择最老的（或最近最少被更新的）表项进行驱逐。被驱逐的表项的位向量被写入PHT。

（2）超时关闭。如果一个空间区域在一定时间窗口内（如1024个周期）没有新的缺失到达，认为该区域的访问已经结束，将其位向量写入PHT并释放AGT表项。这种策略确保了AGT中只保留“活跃”的区域记录。

（3）区域覆盖完成。如果位向量中大部分位都已经被设为1（如超过75%），说明该区域已经被密集访问，继续记录的边际价值有限。此时可以提前关闭该区域并释放AGT表项。

AGT的容量通常为32$\sim$64项。较小的AGT可能导致频繁的提前驱逐，使得一些空间区域的模式记录不完整；较大的AGT增加了面积和搜索延迟。

PHT的更新策略

PHT（Pattern History Table）的更新策略决定了如何融合新旧模式。当一个空间区域从AGT转移到PHT时，如果PHT中已经存在该PC的记录，需要决定如何合并：

（1）直接覆盖：新的位向量直接替换旧的。简单但可能丢失有价值的历史信息。

（2）OR合并：新位向量与旧位向量进行按位OR操作。这保留了所有历史上被访问过的偏移，但可能导致位向量逐渐变“满”（大部分位为1），降低预取精度。

（3）加权合并：为每个位维护一个小的计数器（如2位），记录该偏移在历史上被访问的频率。只有当计数器超过阈值时，该位才被纳入预取位向量。这种方法需要更多的存储空间（每位需要2$\sim$3位计数器而非1位），但可以过滤掉偶发的访问，提高预取精度。

实际的SMS实现通常使用加权合并或OR合并的变体。

性能分析 1 — SMS在SPEC CPU上的性能

在SPEC CPU2006基准上的评估表明，SMS平均可以将IPC提升约12%$\sim$18%。SMS在具有规则结构体遍历模式的基准（如mcf、soplex）上表现尤为突出，IPC提升可达30%以上。SMS的预取精度通常在70%$\sim$90%之间，这得益于空间模式的可重复性。然而，对于访问模式高度不规则的应用（如lbm、milc），SMS的覆盖率有限，因为这些应用的空间模式缺乏可重复性。

具体的分基准数据如下（IPC提升百分比）：mcf: +35%, soplex: +28%, GemsFDTD: +22%, cactusADM: +15%, bwaves: +12%, milc: +3%, sphinx3: +5%。可以看到，SMS对于具有稀疏但重复空间模式的应用效果最好，对于流式访问（如milc）则效果有限——因为流式访问可以被更简单的流预取器高效覆盖。

VLDP

Variable Length Delta Prefetcher（VLDP）由Shevgoor等人于2015年提出，是DPC-2（Data Prefetching Championship 2）的冠军方案。VLDP的核心创新在于使用可变长度的delta历史来预测未来的访问地址，从而统一地处理步幅模式、复杂步幅模式和部分不规则的访问模式。

Delta预测

VLDP以Cache行粒度的地址差值（delta）作为基本预测单元。给定一个访问地址序列$A_0, A_1, A_2, \ldots$，对应的delta序列为： $$\label{eq:vldp-delta} \delta_i = A_i - A_{i-1}$$ VLDP的目标是根据最近的$k$个delta值$(\delta_{i-k+1}, \ldots, \delta_{i-1}, \delta_i)$来预测下一个delta值$\delta_{i+1}$。

多级Delta预测表

VLDP使用多级（通常为3$\sim$4级）Delta预测表（Delta Prediction Table, DPT），每一级使用不同长度的delta历史作为索引：

• DPT-1：以最近1个delta $(\delta_i)$ 为索引，预测$\delta_{i+1}$。

• DPT-2：以最近2个delta $(\delta_{i-1}, \delta_i)$ 为索引，预测$\delta_{i+1}$。

• DPT-3：以最近3个delta $(\delta_{i-2}, \delta_{i-1}, \delta_i)$ 为索引，预测$\delta_{i+1}$。

这种设计的直觉是：更长的历史可以提供更精确的预测，但覆盖率更低（匹配的概率更小）；更短的历史覆盖率更高，但精确度可能不足。VLDP通过多级结构兼顾了两者。

预测优先级

VLDP优先使用更长历史的预测。具体来说，查找从最高级的DPT开始：如果DPT-3命中且其置信度足够高，则使用DPT-3的预测；否则回退到DPT-2；以此类推。这种回退机制确保了预测器在有足够历史信息时提供高精度预测，在信息不足时仍然能给出合理的预测。

Delta页面历史表

VLDP还维护一个Delta页面历史表（Delta History Buffer, DHB），以物理页号为索引，存储每个活跃页面中最近的delta序列。当一个新的Cache缺失发生时，VLDP从DHB中取出对应页面的delta历史，将其用作各级DPT的查找索引。

图图 7.2展示了VLDP的核心结构。

VLDP预取器的多级delta预测架构

置信度管理

每个DPT表项都有一个置信度计数器（通常2$\sim$3位）。当预测正确时（预测的delta与实际观察到的delta一致），置信度递增；预测错误时递减。只有当置信度超过阈值时，VLDP才发出预取请求。这种机制有效地过滤了低置信度的预测，提高了预取精度。

与步幅预取的关系

VLDP可以视为步幅预取器的广义化。一个常数步幅$s$对应的delta序列为$(s, s, s, \ldots)$，DPT-1即可完美预测。而VLDP能够处理的模式远超常数步幅，例如交替步幅$(s_1, s_2, s_1, s_2, \ldots)$可被DPT-2捕获，三元组循环模式可被DPT-3捕获。

为了更直观地理解VLDP的能力，考虑以下代码模式及其delta序列：

• 常数步幅：for(i) A[i*3]。Delta序列：$(3, 3, 3, \ldots)$。DPT-1在一次观察后即可预测。

• 交替步幅：for(i) {A[i*2]; B[i*5]}。Delta序列：$(2, 5, 2, 5, \ldots)$。DPT-2使用上下文$(2, 5)$预测下一个为2，使用$(5, 2)$预测5。

• 嵌套循环：for(i) for(j in 0..3) C[i*100+j]。Delta序列：$(1, 1, 1, 97, 1, 1, 1, 97, \ldots)$。DPT-3使用$(1, 1, 97)$预测1，$(1, 97, 1)$预测1，$(97, 1, 1)$预测1，$(1, 1, 1)$在短序列中可能预测97或1——这里的歧义说明了DPT-3对于4步循环可能不够精确，需要DPT-4。

这些例子展示了多级DPT结构的必要性：更长的上下文可以区分更复杂的delta模式，但需要更多的表项来存储不同上下文下的预测。

VLDP的多步预取

VLDP不仅可以预测下一个delta值，还可以通过链式预测来发出多步预取。具体来说，在预测出$\hat{\delta}_{i+1}$后，VLDP可以将$(\delta_i, \hat{\delta}_{i+1})$作为DPT-2的输入来预测$\hat{\delta}_{i+2}$，进一步将$(\hat{\delta}_{i+1}, \hat{\delta}_{i+2})$作为输入来预测$\hat{\delta}_{i+3}$，以此类推。这种链式预测允许VLDP在一次触发中发出多个预取请求，提高预取的及时性。

链式预测的风险是错误累积：如果第一步预测错误，后续所有预测都可能是错误的。为此，VLDP只在高置信度时才进行多步预测，且步数通常限制在2$\sim$4步以内。

VLDP的预测流程

算法算法 7.1给出了VLDP在每次Cache缺失时的完整预测流程。

$\mathcal{P} \leftarrow \emptyset$ $\mathcal{P}$

存储开销分析

VLDP的总存储预算可以如下估算。DHB以物理页号为索引，假设128个表项，每个表项存储4个历史delta值（每个delta 7位）及页内偏移（6位），共128 $\times$ (页标签20位 + 4 $\times$ 7位 + 6位) $\approx$ 512字节。三级DPT各有512个表项，每个表项存储预测delta（7位）和置信度（3位），索引隐含在哈希中，每级约640字节。总计约2.4 KB——远低于前述的32 KB上限（后者是包含了更大配置的版本）。

VLDP的哈希函数设计

各级DPT的索引使用哈希函数将可变长度的delta历史压缩为固定宽度的索引。哈希函数的设计需要满足两个目标：（1）均匀性——不同的delta历史应该均匀地映射到不同的表项；（2）区分性——不同的delta历史尽可能映射到不同的表项，减少冲突。

VLDP使用的哈希函数通常是简单的XOR-fold方法。对于DPT-$l$，索引的计算方式为： $$\label{eq:vldp-hash} \text{index}l = \text{fold}\left(\bigoplus^{l-1} \left(\delta_{-j} \ll (j \bmod B)\right)\right)$$ 其中$\oplus$为异或，$\ll$为左移，$B$为索引的位宽。fold操作将XOR的结果截断或折叠为$B$位。

这种哈希函数的硬件实现非常简单：$l$个移位器和$l-1$个异或门的级联，总延迟约为$l + \log_2 B$个门级延迟。对于$l = 3$、$B = 9$（512项），延迟约为6个门级——这可以在一个周期内轻松完成。

VLDP与BOP的比较

VLDP和BOP代表了两种截然不同的预取设计哲学：

• VLDP：维护精细的per-page delta历史，使用多级预测表进行上下文相关的预测。优势在于能够处理复杂的非线性delta模式；劣势在于存储开销较大、预测逻辑较复杂。

• BOP：不维护任何per-page或per-PC的历史，只全局性地评估哪个固定偏移值最有效。优势在于存储开销极低（$<$0.5 KB）、实现简单；劣势在于同一时刻只能使用一个偏移值，无法处理多模式混合的工作负载。

在DPC竞赛中，VLDP赢得了DPC-2（2015年），BOP赢得了DPC-3（2016年）。两者的绝对性能非常接近，但BOP以10倍以上更低的硬件开销达到了几乎相同的性能——这使BOP在实际的处理器设计中更具吸引力。

设计权衡 1 — 预取器的复杂度与收益

VLDP和BOP的对比揭示了预取器设计中的一个重要规律：简单预取器的每比特存储效率远高于复杂预取器。BOP用不到0.5 KB的存储达到了VLDP用32 KB存储才能达到的性能——换言之，BOP的“每KB IPC提升”是VLDP的60倍以上。

这一规律的根本原因在于：大部分可预取的缺失来自相对简单的模式（常数步幅、短期固定偏移），只有少量缺失需要复杂的上下文预测。简单预取器（如BOP、stride）可以用最少的资源覆盖大部分“容易”的缺失，而复杂预取器（如VLDP、时间预取器）的额外资源主要用于覆盖少量“困难”的缺失。

在处理器设计中，合理的策略是先部署一个简单高效的基础预取器（如BOP或stride），然后在有富余面积预算时考虑增加更复杂的预取器来覆盖残余缺失。

性能分析 2 — VLDP在DPC-2中的表现

VLDP在DPC-2竞赛中以1.489的加权IPC加速比赢得冠军，在20个测试trace中的16个上取得了最佳或接近最佳的成绩。其总硬件预算约为32 KB（DHB + 各级DPT），在面积和功耗方面是可接受的。VLDP特别擅长处理具有可重复delta模式的应用，如稀疏矩阵运算和图遍历中的规则部分。

BOP

Best Offset Prefetcher（BOP）由Michaud于2016年提出，是DPC-3的冠军方案。BOP采用了一种令人赞叹的简洁设计哲学：它不尝试学习复杂的访问模式，而是动态地找到一个最佳的预取偏移量（best offset），然后简单地对每次访问都预取当前地址加上这个偏移量的Cache行。

核心直觉

BOP的核心直觉是：对于许多工作负载，存在一个固定的偏移值$d$，使得当程序访问地址$A$时，地址$A + d \times L$（$L$为Cache行大小）在不久后也会被访问。这个偏移$d$可能对应于数组的步幅、结构体的大小、或者链表节点之间的典型间距。BOP的任务就是在运行时找到这个最优的$d$值。

偏移评分机制

BOP通过一种精巧的在线评估机制来选择最佳偏移。它维护一个候选偏移集合$D = \{d_1, d_2, \ldots, d_K\}$（通常$K = 46$，包含一组精心选择的正负偏移值），以及一个最近请求表（Recent Request Table, RR）。

评分过程如下：

1. 每当一个Cache行$X$被填充到L2 Cache（无论是demand还是prefetch），将$X$记录到RR表中。

2. 当一个新的demand请求（L2 demand access）到达地址$X$时，对每个候选偏移$d_i$，检查$X - d_i$是否在RR表中。如果在，说明如果之前在访问$X - d_i$时以偏移$d_i$发出预取，那个预取现在正好会被使用。因此给$d_i$的评分加1。

3. 经过一个评分轮次（round，通常256次评分机会）后，选择得分最高的偏移作为当前的最佳偏移。

这种评分机制的优美之处在于它几乎不需要额外的逻辑来跟踪预取的效果——它只需要一个简单的RR表和一组计数器。

BOP预取器的偏移评分机制

偏移候选集的选择

BOP的候选偏移集并非简单地使用$\{1, 2, 3, \ldots, K\}$。Michaud精心选择了一个包含正负偏移的集合，该集合涵盖了常见的步幅值，包括2的幂次、3的倍数以及其他在实际工作负载中经常出现的值。典型的候选集为： $$D = \{1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, \ldots\}$$ 以及对应的负值。候选集中包含负偏移使BOP能够处理逆向遍历（backward traversal）模式。

评分轮次与切换

BOP周期性地进行评分轮次的切换。在每个轮次开始时，所有偏移的评分归零。一个轮次内收集足够的统计数据后（通常256个demand access），选择得分最高的偏移作为新的最佳偏移。这种动态适应机制使BOP能够跟踪工作负载的阶段性变化。

如果在一个轮次中没有任何偏移获得足够高的评分（低于阈值），BOP会关闭预取以避免发出不准确的预取请求。

BOP的在线学习机制详解

BOP的在线学习机制可以被更精确地理解为一个在线强化学习过程：BOP在每个评分轮次中"试验"所有候选偏移，通过RR表间接评估每个偏移的预取价值，然后选择最优偏移作为"策略"应用到实际预取中。

评分过程的正式描述如下。设当前的评分轮次中，demand access地址序列为$X_1, X_2, \ldots, X_T$（$T = 256$为轮次长度）。在每次demand access $X_t$时：

1. 对每个候选偏移$d_i \in D$，检查$X_t - d_i$是否在RR表中。

2. 如果$X_t - d_i \in \text{RR}$，说明在之前某个时刻，地址$X_t - d_i$的数据被填充到Cache中，如果当时以偏移$d_i$发出预取，就会预取地址$X_t$的数据——而$X_t$确实被demand访问了。因此$d_i$的评分递增：$\text{score}[i] \mathrel{+}= 1$。

3. 同时，将$X_t$插入RR表中（供后续demand access的评分使用）。

轮次结束后，选择$d^* = \arg\max_i \text{score}[i]$作为新的最佳偏移。如果$\text{score}[d^*] < \theta$（阈值通常为$T/4 = 64$），则认为没有偏移足够好，关闭预取。

这种评分机制的一个精妙之处在于它不需要实际发出预取请求来评估偏移的效果——它只使用RR表中的历史记录来“回溯性地”评估每个偏移的假想预取效果。这意味着所有候选偏移都在每次demand access时被同时评估，而不需要为每个偏移分别发出预取请求并跟踪其效果。这种“假想评估”大大降低了在线学习的带宽开销。

RR表的实现细节

RR表是BOP评分机制的核心数据结构。它记录了最近被填充到L2 Cache中的Cache行地址。RR表的典型实现是一个直接映射的标签表，使用地址的低位哈希作为索引，高位作为标签。

RR表的大小通常为256项。当一个新的地址被填充到L2时，它被插入到RR表的对应位置（可能替换旧的记录）。查找操作（检查某个地址是否在RR表中）只需一次标签比较——这与Cache的Tag比较完全类似。

需要注意的是，RR表的256项容量决定了BOP可以"回看"多远的历史。如果L2的填充率很高（如每2个周期一次填充），256项RR表只覆盖约512个周期的历史。如果最佳偏移对应的延迟超过512个周期（如偏移很大且访问速度较慢），RR表可能无法捕获到这种关联，导致该偏移的评分被低估。

一种改进是使用采样RR表：不记录每一次L2填充，而是每$k$次填充记录一次。这等效于将RR表的有效历史窗口扩大了$k$倍。Michaud在BOP的原始论文中使用了$k = 1$（即记录每一次填充），但后续的改进工作（如MLOP）探索了不同的采样率。

BOP的局限性与扩展

BOP的最大局限性是它在任何时刻只使用单一偏移。如果程序同时包含两种不同步幅的访问模式（如一个步幅为1的顺序流和一个步幅为8的结构体遍历），BOP只能选择其中一个偏移来预取，另一个模式将被完全忽略。

为了解决这一限制，后续的研究工作提出了多种扩展：

（1）MLOP（Multi-Lookahead Offset Prefetcher）：维护多个评分最高的偏移，同时使用这些偏移发出预取。MLOP为每个偏移维护独立的置信度计数器，只为高置信度的偏移发出预取。

（2）SPP（Signature Path Prefetcher）：使用最近的delta序列的"签名"（signature）来索引一个签名表，每个签名关联一组可能的后续delta值及其置信度。SPP可以视为BOP的路径感知泛化——它不仅考虑单一的最佳偏移，还考虑了到达当前地址的历史路径。

（3）BOP + SMS混合：BOP擅长处理步幅模式，SMS擅长处理空间模式。将两者组合可以获得比单独使用任一预取器更好的覆盖率。组合时需要仲裁两者的预取请求以避免冗余。

存储开销与硬件复杂度

BOP的存储开销极低：

• RR表：256个表项，每个表项存储一个Cache行地址标签（约12位）$\approx$ 384字节。

• 评分计数器：46个候选偏移，每个5位 $\approx$ 29字节。

• 总计不到0.5 KB。

这使得BOP成为存储效率最高的高性能预取器之一。

案例研究 1 — BOP在DPC-3竞赛中的胜出

在DPC-3竞赛中，BOP以其极低的硬件开销（不到1 KB存储）和出色的性能赢得了冠军。在竞赛的20个trace中，BOP的加权IPC加速比为1.302，超过了包括SMS变体和复杂时间预取器在内的所有竞争方案。BOP的成功表明，精巧的设计有时比复杂的机制更有效。值得注意的是，BOP的一个限制是它在任何时刻只使用单一偏移，这使得它无法同时捕捉多种不同步幅的访问模式。后续的多偏移扩展（如MLOP，Multi-Lookahead Offset Prefetcher）试图解决这一限制，通过同时维护多个评分最高的偏移来发出预取。

时间预取

空间模式预取利用的是访问的空间规律性，而时间预取（Temporal Prefetching）则利用访问的时间规律性：如果一个特定的地址访问序列在过去出现过，那么当序列的开头再次出现时，序列的剩余部分很可能会再次跟随出现。时间预取器通过记录历史上的地址访问流（miss address stream），在检测到历史模式重现时重播后续的地址序列。

时间预取的关键优势在于它不依赖于地址之间的任何算术关系（如步幅或delta），因此能够捕捉任意不规则的重复访问模式。其代价是需要大量的存储空间来记录历史地址流。

基于相关性的预取

基于相关性的预取（Correlation-based Prefetching）是最早的时间预取形式之一。其基本思想是建立地址之间的因果关联：如果在历史上，对地址$A$的访问之后总是跟随对地址$B$的访问，那么未来在访问$A$时就应该预取$B$。

Markov预取器

Markov预取器（Joseph和Grunwald，1997）将Cache缺失流建模为一个马尔可夫链：当前的缺失地址是当前状态，下一个缺失地址是转移目标。Markov预取器使用一个地址关联表（Address Correlation Table, ACT）来存储状态转移概率。

ACT以缺失地址为索引，每个表项存储$k$个最可能的后继地址及其出现次数。当一个新的缺失发生时：

1. 用当前缺失地址查找ACT，取出前$k$个后继地址作为预取候选。

2. 更新前一个缺失地址的ACT表项，将当前缺失地址记录为其后继。

Markov预取器的状态转移模型：节点为缺失地址，边权为转移概率

Markov预取器的主要问题是存储开销巨大。如果要跟踪$N$个不同的地址，每个地址存储$k$个后继，则需要$N \times k$个地址条目。对于一个有1M个不同Cache行地址的工作集，即使每个地址只存储2个后继，也需要数MB的存储空间，这远超L1/L2预取器的合理硬件预算。

Markov预取器的精度与覆盖率分析

Markov预取器的精度取决于状态转移的确定性。如果从状态$A$到状态$B$的转移概率为$p_{AB} = 0.9$，则以$B$为预取候选的精度为90%。如果转移概率均匀分布（如$A$有4个等概率的后继），精度仅为25%。

在实际工作负载中，缺失地址流的转移概率分布高度不均匀——大部分缺失地址有1$\sim$2个强关联的后继（概率$>$50%），少数地址有多个弱关联的后继。这意味着Markov预取器在选取top-1后继时的平均精度通常在50%$\sim$70%之间，选取top-2后继时覆盖率可以达到60%$\sim$80%。

Markov预取器的另一个局限是预取深度。1阶Markov预取器只能预测下一个缺失地址，无法提前多步预取。$k$阶Markov预取器可以通过链式预测来实现多步预取（预测$B$后用$B$预测$C$），但链式预测的精度会随步数指数衰减——如果每步精度为$p$，$n$步链式预测的精度仅为$p^n$。

GHB：全局历史缓冲区

为了解决Markov预取器的存储效率问题，Nesbit和Smith于2004年提出了全局历史缓冲区（Global History Buffer, GHB）结构。GHB的核心思想是将所有缺失地址按时间顺序存储在一个环形缓冲区中，然后使用一个索引表（Index Table）将地址映射到它们在缓冲区中最近出现的位置。

GHB中的每个条目存储：(1) 缺失地址；(2) 一个链接指针，指向同一地址上一次出现的位置。通过这种链式结构，可以高效地追溯一个地址的所有历史后继，而无需为每个地址单独分配存储空间。

GHB的硬件结构

GHB的硬件实现由两个主要组件组成：

（1）环形历史缓冲区（Circular History Buffer）：一个FIFO结构，容量为$N$个条目（如$N = 256$或$N = 1024$）。每个条目包含一个缺失地址（34位）和一个链接指针（$\log_2 N$位，指向缓冲区中的另一个位置）。写指针按顺序递增，当到达末尾时回绕到开头。

（2）索引表（Index Table）：以缺失地址的哈希值为索引，每个表项存储一个指向环形缓冲区的指针——指向该地址在缓冲区中最近一次出现的位置。索引表的大小通常为256$\sim$1024项。

GHB的查找过程如下：

1. 新的缺失地址$A$到达。在索引表中查找$A$的哈希槽位，得到$A$上一次出现的缓冲区位置$p$。

2. 从位置$p$开始，沿着链接指针向后遍历，找到$A$的所有历史出现位置。

3. 每次从位置$p$前进到位置$p+1$（下一个时间步的缺失地址），$p+1$处的地址即为$A$的一个历史后继——它是紧跟在$A$之后的缺失地址。

4. 将这些历史后继作为预取候选。

GHB的存储效率远高于Markov预取器。设缓冲区大小为$N$、每个条目约40位，索引表大小为$M$、每个条目约$\log_2 N + 10$位，总存储 = $N \times 40 + M \times (\log_2 N + 10)$。以$N = 256$、$M = 256$为例，总存储 $= 256 \times 40 + 256 \times 18 \approx 1.8$ KB——远小于等效的Markov预取器。

GHB的一个重要优势是它的通用性：通过改变索引表的索引方式（以缺失地址、PC、或PC+delta为索引），可以实现不同类型的时间预取和相关预取。Nesbit和Smith在原始论文中展示了GHB框架可以统一实现Markov预取、stride预取和delta correlation预取——只需改变索引策略而不改变底层的缓冲区结构。

STMS

Sampled Temporal Memory Streaming（STMS）是时间预取领域的重要进展，由Wenisch等人提出。STMS的关键贡献在于解决了全规模时间预取器的存储瓶颈问题。

全规模时间预取的挑战

理想的时间预取器需要记录完整的Cache缺失地址流，并在检测到历史模式重现时重播后续序列。设缺失地址为$m$位（Cache行粒度的物理地址，通常$m \approx 34$位），记录$N$个历史缺失需要$N \times m$位的存储。对于需要记录数百万个历史缺失的大型工作负载，存储需求可达数十MB——这远超芯片上的存储预算。

采样压缩

STMS的核心创新是采样：不记录所有的缺失地址，而只对缺失流进行部分采样。STMS使用地址的低位哈希来决定哪些缺失应该被记录，从而将存储需求降低到原始的$1/S$（$S$为采样率的倒数，通常$S = 32$或$64$）。

采样的直觉是：如果一个时间模式足够强（即重复出现的次数足够多），那么即使只观察一个子集（采样集），也足以检测到该模式。当然，采样会降低对短暂或稀有模式的检测能力，但这些模式的预取价值本身也有限。

硬件结构

STMS由以下组件构成：

• 采样历史缓冲区（Sampled History Buffer）：一个环形缓冲区，只记录采样集中的缺失地址。

• 索引表（Index Table）：以缺失地址为索引，指向历史缓冲区中最近出现的位置。

• 重播指针（Replay Pointer）：当检测到模式重现时，使用重播指针沿着历史缓冲区向前遍历，依次发出预取请求。

模式匹配与重播

当一个新的（被采样的）缺失发生时，STMS在索引表中查找该地址的上一次出现位置。如果找到，STMS假设历史将重复，从上一次出现的下一个位置开始，沿历史缓冲区向前遍历，将遇到的地址作为预取候选发出。重播会持续到预取队列满或到达缓冲区的末尾。

重播过程的具体步骤如下：

1. 当前采样缺失地址$A$被检测到。查找索引表得到$A$在历史缓冲区中的上一次出现位置$p$。

2. 从位置$p+1$开始沿历史缓冲区向前遍历。缓冲区中的每个地址$B_{p+1}, B_{p+2}, \ldots$都是预取候选。

3. 对每个候选地址$B_k$，检查它是否已经在Cache中（避免冗余预取）和MSHR中（避免重复请求）。如果不在，将其加入预取队列。

4. 重播在以下任一条件满足时停止：预取队列满（通常8$\sim$16项）、到达缓冲区末尾、或遇到另一个采样地址（下一个匹配点将由该采样地址触发新的重播）。

STMS的一个重要优化是重播指针持久化。当一次重播被预取队列满而中断时，STMS保存当前的重播指针位置。当预取队列有空闲时，从保存的位置继续重播，而非重新开始。这确保了长序列的重播不会因为队列容量限制而丢失后半部分。

STMS的存储层次适配

STMS的一个实际部署考虑是其数据应该存储在片上还是片外。以$N = 10^5$个采样缺失（采样率$S = 64$，对应$6.4 \times 10^6$个原始缺失）为例，每个地址34位，总存储约$10^5 \times 34 / 8 \approx 425$ KB——这对于片上SRAM来说偏大，但对于eDRAM或3D堆叠SRAM来说是可行的。

一种折中方案是使用二级STMS：片上维护一个小型的“热”历史缓冲区（如8 KB，存储约2000个采样缺失），记录最近的缺失流；片外（如eDRAM或独立的SRAM芯片）维护一个完整的“冷”历史缓冲区（如256 KB）。模式匹配优先在热缓冲区中进行（延迟低），如果热缓冲区没有匹配，再查询冷缓冲区（延迟高但覆盖率更高）。

采样的数学分析

设原始缺失流中一个重复模式的长度为$L$，该模式在整个执行过程中重复$R$次。在采样率为$1/S$的情况下，该模式中每个地址被采样到的概率为$1/S$。为了使STMS至少检测到该模式一次，需要至少两个连续的被采样地址匹配。模式被检测到的概率约为： $$\label{eq:stms-detect} P_{\text{detect}} \approx 1 - \left(1 - \frac{1}{S^2}\right)^{L \cdot R}$$

对于$L = 100$、$R = 50$、$S = 32$，$P_{\text{detect}} \approx 1 - (1 - 1/1024)^{5000} \approx 99.3\%$。这表明即使采样率较低，对于足够长和频繁的模式，检测概率仍然很高。

$$\text{存储节省比} = \frac{\text{全规模存储}}{S} = \frac{N \times m}{S}$$

例如，若全规模需要记录$N = 10^6$个地址（每个34位），总存储约4.25 MB。以$S = 64$采样后，仅需约66 KB——这已接近可在芯片上实现的范围。

ISB

Irregular Stream Buffer（ISB）由Jain和Lin于2013年提出，提供了一种处理不规则访问流的优雅方案。ISB的核心思想是在不规则的物理地址序列和规则的"结构化地址"序列之间建立映射，从而将不规则预取问题转化为常规的流预取问题。

结构化地址空间

ISB引入了一个抽象的结构化地址空间（Structural Address Space）。在这个空间中，时间上相邻的缺失被赋予连续的结构化地址。具体来说，如果缺失流为$A_0, A_1, A_2, \ldots$，则它们被映射为结构化地址$S_0, S_0+1, S_0+2, \ldots$。

ISB维护两个映射表：

• 物理到结构化（Physical-to-Structural, PS）映射：给定物理地址，返回结构化地址。

• 结构化到物理（Structural-to-Physical, SP）映射：给定结构化地址，返回物理地址。

工作流程

当一个Cache缺失发生在物理地址$A_{\text{cur}}$时：

1. 查找PS表，获得$A_{\text{cur}}$的结构化地址$S_{\text{cur}}$。

2. 在结构化地址空间中，预取$S_{\text{cur}} + 1, S_{\text{cur}} + 2, \ldots, S_{\text{cur}} + D$（$D$为预取深度）。

3. 对每个预取目标结构化地址，查找SP表获得对应的物理地址，发出预取请求。

4. 同时，更新PS和SP表：将$A_{\text{cur}}$与前一个缺失$A_{\text{prev}}$关联，确保它们在结构化地址空间中相邻。

ISB通过结构化地址空间将不规则序列转化为规则流

优势与开销

ISB的关键优势是它将时间预取的复杂性封装在两个映射表中，而预取引擎本身只需做简单的流预取（在结构化地址空间中递增）。这使得ISB在概念上非常清晰，且易于与现有的流预取硬件集成。

ISB的存储开销主要来自PS和SP映射表。每个表项需要存储一个物理地址标签和一个结构化地址（或反向），典型的实现使用约32$\sim$64 KB的总存储。ISB还支持通过采样（类似STMS）来进一步降低存储需求。

训练窗口与映射更新

ISB在运行过程中持续更新PS/SP映射。一个重要的设计参数是训练窗口（training window）的大小：在多长的时间范围内，两个缺失被视为"时间相邻"并被赋予连续的结构化地址。如果训练窗口太小，ISB可能错过较远距离的相关缺失；如果太大，不相关的缺失可能被错误地关联在一起。

ISB使用PC信息来辅助映射的建立：只有由相同PC或具有数据依赖关系的PC对产生的缺失才会被关联。这种PC定向（PC-directed）的训练策略大大提高了映射的准确性。

训练窗口的典型大小为64$\sim$256个缺失。过小的窗口会导致长距离的时间关联被忽略——例如，在一个具有1000次迭代的循环中，如果每次迭代产生2次缺失且训练窗口为64，则ISB可以关联最近32次迭代内的缺失。如果程序的时间模式跨越了32次以上的迭代（如每100次迭代重复的访问模式），ISB可能无法捕获。

ISB的结构化地址空间管理

ISB需要维护一个结构化地址分配器来为新的缺失流分配连续的结构化地址。分配器的工作方式类似于一个单调递增的计数器：每当一个新的缺失被关联到一个时间流中，分配器为该缺失分配下一个可用的结构化地址。

当程序的执行阶段发生变化（如从一个函数调用切换到另一个），ISB的训练窗口中可能出现与之前不同的缺失流。此时ISB需要“重置”结构化地址空间——为新的缺失流分配一段新的结构化地址范围，避免与旧流的地址混淆。

实现上，ISB通常维护多个独立的结构化地址空间（以PC为区分），每个PC关联的缺失在自己的地址空间中递增。这样，不同PC触发的缺失流不会互相干扰。

ISB的映射表实现

PS（Physical-to-Structural）和SP（Structural-to-Physical）映射表是ISB的核心数据结构。这两个表本质上是一对反向映射：PS表以物理地址为键、结构化地址为值；SP表以结构化地址为键、物理地址为值。

在硬件实现上，PS表和SP表通常使用直接映射的标签表。以物理地址的低位（如低14位）为PS表的索引，高位为标签。如果发生冲突（两个物理地址映射到同一PS表项），旧的映射被覆盖。

ISB的一个重要实现挑战是映射的一致性维护。当PS表中一个物理地址$A$的结构化地址被更新（因为$A$在新的上下文中出现），需要同时更新SP表中对应的反向映射。这种双向更新需要额外的SP表读写操作，可能增加1$\sim$2个周期的延迟。

与STMS的比较

ISB和STMS都属于时间预取器，但它们的设计哲学有本质区别。STMS直接记录和重播地址序列，本质上是一个"录制-播放"系统；ISB则通过地址空间变换，将不规则模式转化为规则模式，然后利用简单的流预取机制来处理。ISB的优势在于它更好地利用了流预取器已有的硬件基础设施，且映射表的存储效率通常高于STMS的历史缓冲区。

更详细的比较如下：

特性	ISB	STMS
核心数据结构	PS/SP双向映射表	采样历史缓冲区
存储开销	32$\sim$64 KB	32$\sim$128 KB
预测方法	结构化空间中的流预取	历史序列的直接重播
模式检测延迟	即时（映射即可用）	需要序列匹配
适应新模式	映射持续更新	需要完整序列重现
跨页面预取	自然支持	自然支持
SPEC覆盖率	mcf: 65%, omnetpp: 55%	mcf: 55%, omnetpp: 60%

ISB与STMS的详细比较

在SPEC CPU2006的评估中，ISB在mcf上的覆盖率比STMS高约10%，但在omnetpp上STMS略优——这反映了两种方法在不同类型的不规则模式上各有优势。

设计提示

ISB的设计思想揭示了预取领域的一个重要洞察：不规则问题可以通过地址空间变换转化为规则问题。这一思想在后续的许多预取器设计中都有体现，例如将复杂的指针追踪模式映射到线性地址空间。设计预取器时，与其尝试直接预测不规则的地址序列，不如考虑是否存在一个更适合预测的变换空间。

指针追踪预取

指针追踪（Pointer Chasing）是许多重要数据结构——链表、树、图的邻接表、哈希表的冲突链——的核心访问模式。在这种模式中，下一次内存访问的地址存储在当前访问的数据中，形成了严格的数据依赖链。这使得传统的基于地址模式的预取器（步幅、delta、空间模式）几乎无法有效工作，因为下一个地址在当前数据被加载之前是完全未知的。

指针追踪访问模式的特征

指针追踪访问模式具有以下显著特征，使其成为预取领域最具挑战性的问题之一。

串行化的数据依赖

指针追踪形成了一条Load-Use-Load依赖链：每个load的地址来源于前一个load的结果。考虑以下链表遍历代码：

struct Node {
    int data;
    struct Node *next;
};

// 链表遍历
struct Node *p = head;
while (p != NULL) {
    process(p->data);
    p = p->next;  // 下一次load的地址依赖于当前load的结果
}

假设L1 D-Cache的命中延迟为4个周期，L2的命中延迟为12个周期，DRAM的延迟为200个周期。如果每个链表节点都是Cache缺失（在大型链表中这很常见，因为节点通过malloc分配，物理地址分散），那么遍历$N$个节点的总延迟至少为$N \times 200$个周期——乱序执行窗口无法帮助隐藏这种延迟，因为每次load都严格依赖于前一次load的结果。

缺乏地址规律性

指针追踪访问的地址序列通常没有可预测的数值规律。链表节点的地址取决于动态内存分配的行为，可能在物理地址空间中随机分布。这使得基于步幅或delta的预取器无法发现可利用的模式。

有限的内存级并行

指针追踪天然地限制了内存级并行度（Memory-Level Parallelism, MLP）。在一条指针链中，所有load都是串行的，MLP为1。即使处理器有多个未完成缺失的能力（MSHR），在指针追踪中也只能同时有一个缺失在进行。这与数组遍历形成鲜明对比——在数组遍历中，乱序处理器可以同时发起多个独立的load，实现高MLP。

指针追踪的低MLP问题可以从Little定律的角度来理解。Little定律指出：$N = \lambda \times L$，其中$N$为系统中同时处理的请求数（MLP），$\lambda$为请求到达率，$L$为平均服务延迟。对于指针追踪，$L = T_{\text{miss}}$（缺失延迟），$\lambda = 1/T_{\text{miss}}$（每次缺失完成后才能发出下一次缺失），因此$N = 1$——完美地解释了为什么指针追踪的MLP被锁定在1。

要打破这个限制，需要找到一种方式来提前计算未来缺失的地址，而不等待当前缺失完成。这正是指针预取器和Runahead Execution试图解决的核心问题。

多链并行

尽管单条指针链的MLP为1，实际程序中可能同时存在多条独立的指针链。例如，一个多路平衡树的遍历可以同时探索多个子树，每个子树形成一条独立的指针链。如果程序显式地管理多条链（如通过数组存储多个待遍历的根节点），乱序处理器可以同时推进多条链，实现$k$条链的MLP $\approx k$。

数据库系统中的“AMAC”（Asynchronous Memory Access Chaining）技术就是利用这一观察来提高哈希表探测的MLP：将多个独立的键值查找交错执行，使得一个查找等待Cache缺失时，另一个查找可以继续推进。

指针追踪对缓存层次的压力

指针追踪对缓存层次的压力不仅体现在缺失延迟上，还体现在缓存利用率上。在一个典型的链表遍历中，每个节点占64$\sim$128字节，但程序可能只需要节点中的一两个字段（如next指针和一个data字段），其余字节是“浪费”的带宽——它们被加载到Cache中但从未被访问。

这种“Cache行利用率”问题在指针追踪中特别严重。设每个链表节点实际使用的字节数为$u$，Cache行大小为$L = 64$字节，则Cache行利用率为$u/L$。对于一个只读取16字节有效数据的128字节节点（跨两行），利用率仅为$16/128 = 12.5\%$——87.5%的带宽被浪费了。

这一观察促使了一些优化方向：

• 数据结构压缩：将节点的热字段（频繁访问的字段）集中到节点的前部，使它们落在同一个Cache行中，提高行利用率。

• 结构体分裂（Structure Splitting）：将一个大型结构体分裂为多个小型结构体（如Node分为NodePtr和NodeData），只遍历NodePtr数组，减少缓存占用。

• 硬件辅助的部分行加载：只加载Cache行中特定偏移的数据，而非整行。这需要ISA和缓存控制器的特殊支持。

真实工作负载中的指针追踪

指针追踪在以下场景中尤为普遍：

• 数据库系统：B+树索引的遍历、哈希连接中的冲突链遍历。

• 图计算：邻接表表示的图中，边列表的遍历。

• 垃圾回收：标记阶段需要遍历整个对象图。

• 语言运行时：虚函数表查找（vtable lookup）涉及多级指针解引用。

• 网络数据包处理：链式数据结构如sk_buff链表。

硬件指针预取器

硬件指针预取器的基本思路是：在Cache行的数据中识别出可能是指针的值，然后将这些值作为预取地址发出。这种方法不需要等待load指令执行，而是主动地扫描Cache中的数据内容。

Content-Directed Prefetching

Cooksey等人于2002年提出的内容导向预取（Content-Directed Prefetching, CDP）是这一方向的代表性工作。CDP的基本原理是：当一个Cache行被填充到Cache中时，扫描该行中的每一个字（word），将每个字的值解释为一个潜在的内存地址，如果该地址落在合法的内存范围内，就将其作为预取候选。

Content-Directed Prefetching：扫描Cache行中的潜在指针值

CDP的地址过滤流水线

CDP的实现需要一个专用的地址过滤流水线来处理Cache行中的潜在指针。当一个新的Cache行被填充到Cache时，该行的64字节数据被送入过滤流水线，逐个8字节字地进行以下检查：

1. 对齐检查：8字节值的低3位是否为0（即是否8字节对齐）。不对齐的值几乎不可能是指针。

2. 范围检查：值是否落在合法的虚拟地址范围内。在64位系统中，用户空间地址通常在0x0000_0000_0000$\sim$0x7FFF_FFFF_FFFF范围内，内核地址在0xFFFF_8000_0000_0000以上。不在这些范围内的值可以被过滤掉。

3. 自引用过滤：如果值指向的地址与当前Cache行所在的页面相同，可能是有用的指针（如链表节点指向同一页面的下一个节点）；如果指向非常远的地址，可能只是巧合。

4. 重复过滤：如果该地址已经在Cache中或已有预取请求在处理，跳过。

这个过滤流水线每周期处理一个8字节字，处理完一个64字节的Cache行需要8个周期。由于Cache行填充不是每周期都发生的，过滤流水线的带宽通常足够。通过过滤的候选地址被放入一个预取请求队列中，以低优先级发出预取。

挑战与改进

CDP面临几个主要挑战：

（1）误判问题。一个64字节的Cache行包含8个8字节的字，其中许多整数值可能恰好落在合法的地址范围内，但实际上并不是指针。这导致大量无用的预取请求，浪费带宽并可能污染Cache。

（2）指针类型歧义。在64位系统中，一个Cache行中的8个字中可能只有1$\sim$2个是真正的指针。如何高效地区分指针和非指针数据是CDP的核心难题。

后续的改进工作引入了多种启发式来提高指针识别的精度：

• 地址范围过滤：只预取落在堆区或特定内存段范围内的地址。

• 对齐检查：指针通常是对齐的（8字节对齐），因此可以过滤掉不对齐的值。

• 类型标注：利用编译器的类型信息标注数据结构中指针字段的偏移。

• 结合步幅信息：如果连续几个Cache行中相同偏移位置的值都像指针，则增加该偏移是指针的置信度。

Dependence-based Prefetching

Roth等人提出的依赖关系预取将指针预取与处理器的数据流分析相结合。预取器跟踪load指令之间的依赖关系——如果load $L_B$的地址来自load $L_A$的结果（经过可能的地址计算），则建立$L_A \to L_B$的依赖关系。当$L_A$的结果可用时，预取器立即计算$L_B$的地址并发出预取，而无需等待$L_B$真正执行。

这种方法的优势是精确度高（只预取真正被需要的地址），但需要在硬件中实现依赖关系检测和地址计算，增加了设计复杂度。

软硬件协同的指针预取

在纯硬件指针预取器精度不足的情况下，软硬件协同方案提供了另一条路径。核心思想是利用编译器的类型信息来辅助硬件预取器：

（1）编译器标注指针字段。编译器在编译时分析数据结构的定义，确定哪些字段是指针类型。然后在这些字段对应的Load指令上添加特殊的标注（如RISC-V的自定义hint位），告诉硬件该Load指令的结果是一个指针，应该被用作后续预取的地址。

（2）硬件指针追踪预取器。硬件在检测到标注的Load指令时，将其结果地址直接发送到预取引擎。由于编译器标注保证了该值确实是指针，硬件不需要进行地址范围检查或对齐检查，精度大大提高。

（3）预取链追踪。更进一步，编译器可以标注整条指针追踪链——例如“Load A->field1, 结果是指针，指向结构体类型T，接下来应该预取T->field2”。硬件可以利用这些链式标注来实现多步指针预取。

这种软硬件协同方案在RISC-V架构中特别有希望实现，因为RISC-V的指令编码留有大量的hint空间可以用于传递编译器的类型信息。

指针预取的覆盖率上界

值得注意的是，所有指针预取技术都面临一个根本性的延迟限制。设指针链中每个节点的访问延迟为$T_{\text{miss}}$，预取的提前量为$T_{\text{ahead}}$（从发出预取到数据返回），则预取能够覆盖的指针链深度最多为$T_{\text{ahead}} / T_{\text{miss}}$。例如，如果$T_{\text{miss}} = 200$周期而预取器只能提前1步预取（$T_{\text{ahead}} = 200$周期），那么在稳态下最多能将指针链的有效延迟减半。要实现更深的覆盖，需要多级预取（在第一步预取返回后立即发出第二步预取）或者投机跳跃预取（利用指针的历史值猜测未来的指针目标）。

Runahead Execution

Runahead Execution是一种利用处理器自身来发现未来缺失的预取技术。其基本思想是：当处理器因为一个长延迟的Cache缺失而停滞（stall）时，不让处理器闲置等待，而是让它进入一种预执行模式（runahead mode），继续投机性地执行后续指令。虽然预执行的计算结果不会被提交（因为依赖于缺失数据的指令产生的是无效结果），但预执行中触发的Cache缺失会被转化为预取请求，从而提前将未来需要的数据取入Cache。

基本工作流程

Runahead Execution的工作流程如下：

1. 触发条件：当ROB（重排序缓冲区）头部的指令是一个长延迟的Cache缺失（通常是LLC缺失）且ROB即将满时，处理器进入runahead模式。

2. 检查点保存：保存当前的架构状态（寄存器文件、PC等）作为检查点。

3. 预执行：处理器继续取指、译码、执行后续指令。依赖于缺失数据的寄存器被标记为INV（无效），后续使用这些无效寄存器的指令也产生无效结果，但它们的地址计算仍然可能触发有用的Cache缺失。

4. 缺失转化为预取：预执行中产生的所有Cache缺失都被发送到存储系统作为预取请求。

5. 恢复：当原始的阻塞缺失完成时，处理器从检查点恢复正常执行。预执行中所有的架构状态修改被丢弃。

Runahead Execution的执行时间线

无效值传播

Runahead模式中的关键挑战是无效值传播（INV propagation）。当一条指令的源操作数之一被标记为INV时，该指令的结果也被标记为INV。这种INV标记沿着依赖链传播，最终可能使大量寄存器变为INV。如果太多的地址计算依赖于INV寄存器，runahead模式将无法产生有效的预取地址。

对于指针追踪模式，这恰好是最关键的问题：整个指针链都依赖于初始缺失的数据，因此链上所有后续的load地址都是INV。这意味着runahead在单一指针链上的效果有限。然而，runahead的价值在于它能发现与当前缺失不相关的其他缺失——例如，在遍历链表的同时，程序可能还在访问其他独立的数据结构，runahead可以提前触发这些独立缺失的预取。

Runahead的效果量化

Runahead的预取效果高度依赖于工作负载的MLP特征和依赖结构。对于以下类型的工作负载，Runahead的收益分析如下：

• 独立缺失密集型（如稀疏矩阵运算）：ROB满后，runahead可以发现大量独立的缺失并发出预取。IPC提升20%$\sim$40%。

• 指针追踪密集型（如图遍历）：runahead遇到严重的INV传播问题——指针链中所有load的地址都依赖于前一个缺失的数据。有效的预取地址很少。IPC提升仅5%$\sim$10%。

• 混合型（如数据库查询）：runahead可以为独立的部分发出预取，但指针追踪部分仍然受限。IPC提升10%$\sim$20%。

• L1密集型（如矩阵乘法）：ROB很少因为LLC缺失而满，runahead很少被触发。IPC提升$<$3%。

Runahead的功耗开销也需要考虑。在runahead模式下，处理器继续取指、译码和执行指令，功耗接近正常执行模式。设runahead模式的时间占比为$f_{\text{RA}}$，则Runahead引起的平均功耗增加约为$f_{\text{RA}} \times P_{\text{active}}$（其中$P_{\text{active}}$为活跃功耗）。在存储密集型工作负载中，$f_{\text{RA}}$可能高达30%$\sim$50%——处理器有一半的时间在“做无用功”来产生预取。这在功耗受限的移动设备上是不可接受的。

Filtered Runahead

Hashemi等人于2015年提出了Filtered Runahead，通过在正常执行阶段记录哪些指令产生了Cache缺失，在runahead阶段只执行这些缺失相关的指令（及其依赖链），从而减少了runahead模式的功耗开销和资源占用。

Precise Runahead

为了改善runahead在指针追踪场景中的效果，Naithani等人于2020年提出了Precise Runahead。其核心思想是为runahead模式提供一个精确的执行引擎（而非复用乱序处理器的全部资源），该引擎只跟踪与缺失load相关的指令链，并精确地模拟这些指令的执行。当一个load缺失的数据在runahead期间返回时，引擎使用该数据继续推进依赖链，从而有效地"解开"指针追踪的串行依赖。

Precise Runahead的精确引擎包含以下组件：

（1）依赖链提取器（Dependency Chain Extractor, DCE）：在正常执行阶段，DCE分析指令之间的依赖关系，识别出产生缺失Load地址的最小指令子集（“缺失链”）。DCE将这些指令的微操作存储在一个小型的缺失链缓冲区（Miss Chain Buffer, MCB）中。

（2）轻量级执行引擎：一个简化的执行单元，只支持整数加法、移位和Load操作（这些是地址计算最常用的操作）。该引擎从MCB中取出缺失链的指令并执行，产生的Load请求被发送到存储系统作为预取。

（3）结果缓冲区：存储轻量级引擎的执行结果，包括load返回的数据值。当runahead模式结束后，这些结果被丢弃——它们的唯一目的是产生有效的预取地址。

Precise Runahead的关键优势是它能够“解开”指针追踪链：当一个指针Load的数据返回后，轻量级引擎立即使用该数据计算下一个指针Load的地址并发出新的预取。这打破了普通runahead中INV传播的瓶颈。

在SPEC CPU 2017的评估中，Precise Runahead对指针追踪密集型工作负载的IPC提升约为15%$\sim$25%，而普通Runahead只能提升5%$\sim$10%。代价是约$0.03\text{mm}^2$的额外面积（5nm工艺）用于轻量级引擎和MCB。

Runahead的触发与退出条件

Runahead模式的触发条件需要精心设计。最基本的触发条件是“ROB头部指令因LLC缺失阻塞且ROB即将满”，但更精细的触发条件可以提升runahead的效率：

• 延迟阈值触发：只有当阻塞的缺失预期延迟超过某个阈值（如100个周期）时才进入runahead。如果缺失只需要12个周期（L2命中），进入runahead的检查点保存和恢复开销可能超过等待缺失完成的开销。

• ROB利用率触发：只有当ROB占用率超过80%时才进入runahead。如果ROB还有大量空余空间，乱序执行本身就可以继续发现独立指令，无需进入runahead。

• MLP估计触发：如果当前已经有多个MSHR被占用（说明已经有多个并行缺失在处理），runahead的增量价值可能有限。只有当MSHR利用率较低时才进入runahead。

Runahead的退出条件同样重要。最基本的退出条件是“原始阻塞缺失完成”。但也可以提前退出以减少无效的预执行功耗——例如，当runahead模式中产生的有效预取地址（非INV）的数量降低到某个阈值以下时，说明当前的runahead已经无法产生更多有用的预取，可以提前退出以节省功耗。

Runahead与乱序执行的关系

从本质上看，runahead execution可以视为乱序窗口的逻辑扩展。一个拥有256个ROB表项的乱序处理器，其"预见"能力受限于ROB的深度。当ROB满时，处理器无法继续发现新的独立指令。Runahead通过释放ROB（保存检查点后丢弃当前ROB内容）来"重置"乱序窗口，使处理器能够看到远超物理ROB深度的未来指令。

设ROB深度为$R$，平均每条指令的宽度为$W$字节（包括操作数），缺失延迟为$L$个周期，处理器宽度为$N$-wide，则runahead模式最多可以额外扫描约$L \times N$条指令。对于$L = 200$周期、$N = 6$-wide的处理器，这意味着runahead可以探索约1200条指令——相当于将有效的指令窗口从256扩大到了1400+。

Pre-Execution线程

与runahead概念相关的另一种技术是辅助预执行线程（Helper Thread / Pre-Execution Thread），它在SMT处理器的空闲硬件线程上运行一个精简版的程序（只包含地址计算和load指令的依赖链），提前触发Cache缺失。与runahead不同，辅助线程不需要检查点和恢复机制，因为它运行在独立的线程上下文中。然而，它需要消耗一个SMT线程槽位，并与主线程竞争处理器资源。

辅助线程的生成通常需要编译器的支持。编译器对程序进行依赖链提取（Dependency Chain Extraction）：分析主程序的缺失Load指令，从中提取出产生这些Load地址所需的最小指令子集（通常只包括地址计算指令和控制流指令），将这个子集编译为辅助线程的代码。辅助线程的代码量通常只有主线程的10%$\sim$30%——它不做任何“有用的”计算，只是提前执行地址生成和Load指令来触发Cache缺失。

Runahead Buffer

一种更轻量级的runahead变体是Runahead Buffer（也称为Continual Flow Pipeline），它不完全释放ROB，而是将阻塞的指令从ROB的头部“滑出”到一个专用的Runahead Buffer中。这释放了ROB的空间供后续指令使用，同时Runahead Buffer中的指令在缺失数据返回后可以重新注入ROB完成执行。

这种方式的优势是不需要检查点/恢复机制——Runahead Buffer中的指令仍然保持了正确的程序状态，不需要被丢弃。缺点是Runahead Buffer本身需要额外的面积来存储滑出的指令和寄存器状态。

ARM的Cortex-X系列核心被认为实现了某种形式的Runahead Buffer，但ARM没有公开确认具体的实现细节。

设计权衡 2 — Runahead的成本与收益

Runahead Execution的主要开销包括：(1) 检查点保存和恢复的延迟（通常1$\sim$2个周期）；(2) 预执行期间的功耗（处理器在做"无用功"，但产生的预取是有用的）；(3) 预执行可能生成不准确的预取地址（由于INV传播）。

典型的评估数据表明，Runahead在内存密集型工作负载上可以提升10%$\sim$25%的IPC。然而，对于已经被常规预取器很好覆盖的工作负载，runahead的增量收益有限。Runahead的最大价值在于它能够覆盖其他预取器无法覆盖的不规则缺失模式，特别是涉及复杂地址计算的场景。现代设计（如Intel的某些微架构）已经在特定场景下采用了runahead的变体。

预取的管理与控制

预取器的性能不仅取决于其预测算法的精度和覆盖率，还在很大程度上取决于预取请求的管理与控制。不当的预取管理可能导致带宽浪费、Cache污染、甚至性能下降。本节讨论预取系统中的关键管理问题。

预取精度与覆盖率

评估一个预取器的效果需要量化两个核心指标：精度（Accuracy）和覆盖率（Coverage）。

精度

预取精度定义为发出的预取请求中实际被后续demand访问使用的比例： $$\label{eq:pf-accuracy} \text{Accuracy} = \frac{\text{有用预取数}}{\text{总预取数}} = \frac{N_{\text{useful}}}{N_{\text{total}}}$$ 其中"有用预取"是指预取的Cache行在被驱逐之前至少被一次demand访问命中的预取。精度低意味着预取器发出了大量无用请求，浪费了存储带宽和Cache空间。

覆盖率

预取覆盖率定义为被预取器消除的Cache缺失占原始Cache缺失的比例： $$\label{eq:pf-coverage} \text{Coverage} = \frac{\text{被预取消除的缺失数}}{\text{无预取时的总缺失数}} = \frac{N_{\text{eliminated}}}{N_{\text{miss_no_pf}}}$$ 覆盖率高意味着预取器成功地预取了大部分会导致缺失的数据。

及时性

除了精度和覆盖率，及时性（Timeliness）也是一个重要指标：预取的数据是否在被需要之前就已到达Cache。一个预取可能是"有用的"（精度统计为正），但如果它到达得太晚（在demand访问之后才到达），则其对性能的帮助有限。及时性通常不单独量化，而是通过其对AMAT或IPC的影响来间接评估。

精度与覆盖率的权衡

精度和覆盖率之间存在内在的权衡关系。一个激进的预取器（发出大量预取请求）通常有较高的覆盖率但较低的精度；一个保守的预取器（只在高置信度时发出预取）通常有较高的精度但较低的覆盖率。图图 7.8展示了这种权衡关系。

预取精度与覆盖率的权衡关系

IPC影响的分析模型

预取对IPC的影响可以通过以下分析框架来理解。设无预取时的AMAT为$T_0$，预取器的覆盖率为$C$、精度为$A$，每个无用预取造成的额外延迟惩罚为$P$（由于带宽竞争和Cache污染），则有预取时的有效AMAT可近似为：

$$T_{\text{pf}} \approx T_0 \times (1 - C) + P \times \frac{N_{\text{total}} \times (1 - A)}{N_{\text{demand}}}$$

第一项是未被预取覆盖的缺失仍然产生的延迟，第二项是无用预取引入的额外惩罚。只有当$T_{\text{pf}} < T_0$时，预取才是有益的。这个公式清楚地表明，当精度过低时，即使覆盖率很高，预取也可能损害性能。

数值实例

考虑一个具体的场景来说明精度与覆盖率的权衡。假设无预取时的AMAT为$T_0 = 10$周期，demand缺失率为$r = 0.05$（即5%的访问导致缺失），每个无用预取的惩罚为$P = 2$周期（由于带宽竞争和额外的Cache驱逐）。

• 高精度/低覆盖预取器（精度$A=95\%$，覆盖率$C=40\%$）：消除40%的缺失，无用预取比例仅5%。有效AMAT $\approx 10 \times 0.60 + 2 \times 0.05 \times \frac{0.40}{0.95} \approx 6.04$周期。IPC提升约39%。

• 低精度/高覆盖预取器（精度$A=40\%$，覆盖率$C=80\%$）：消除80%的缺失，但60%的预取是无用的。有效AMAT $\approx 10 \times 0.20 + 2 \times 0.05 \times \frac{0.80}{0.40} \approx 2.20$周期。看似更好，但实际上大量无用预取会消耗带宽，在多核场景下可能导致其他核心的访存延迟增加。

这个例子说明，在单核场景下高覆盖率通常更重要；但在多核共享带宽的场景下，高精度变得更加关键，因为每个无用预取不仅浪费发出预取的核心的带宽，还会"偷走"其他核心的可用带宽。归根结底，预取最终的效果受限于第 48.0 章中讨论的DRAM带宽——无论预取器的算法多么精巧，如果DRAM总线已经饱和，额外的预取请求只会增加排队延迟而无法隐藏访存延迟。

及时性的量化分析

预取的及时性（Timeliness）是一个常被忽视但对实际性能有重要影响的指标。一个预取请求可以被分类为以下几种时效状态：

• 及时预取（Timely）：预取的数据在demand访问到达之前已经到达Cache。这是最理想的情况，demand访问直接命中预取的行，缺失延迟被完全隐藏。

• 延迟预取（Late）：demand访问到达时预取请求已经发出但数据尚未返回。demand访问仍然经历缺失，但等待时间缩短——因为预取请求已经在路上了。设预取提前量为$T_{\text{ahead}}$（预取请求比demand访问提前发出的时间），缺失延迟为$T_{\text{miss}}$，则实际的等待时间约为$\max(0, T_{\text{miss}} - T_{\text{ahead}})$。

• 过早预取（Too Early）：预取的数据到达Cache后，在demand访问到达之前就已经被替换策略驱逐。这种情况下预取白做了——消耗了带宽和一次Cache替换，却没有带来任何命中。

• 无用预取（Useless）：预取的数据从未被任何demand访问命中就被驱逐。这可能因为预取地址错误（精度问题）或因为程序的控制流改变（时效问题）。

及时性可以通过以下指标量化：

$$\text{Timeliness} = \frac{N_{\text{timely}}}{N_{\text{timely}} + N_{\text{late}}} = \frac{N_{\text{timely}}}{N_{\text{useful}}}$$

其中$N_{\text{timely}}$为及时到达的有用预取数，$N_{\text{late}}$为延迟到达的有用预取数。注意这里的分母是有用预取数（精度$\times$总预取数），不包括无用预取。

及时性与预取深度的关系

预取深度（Prefetch Distance / Lookahead）$d$是控制及时性的主要参数。设程序的访问间隔为$T_{\text{access}}$周期（两次连续demand访问同一模式的时间间隔），下级Cache的延迟为$T_{\text{miss}}$周期，则理想的预取深度为： $$\label{eq:ch07-ideal-distance} d_{\text{ideal}} = \left\lceil \frac{T_{\text{miss}}}{T_{\text{access}}} \right\rceil$$

对于顺序访问模式，$T_{\text{access}}$约等于处理器每处理一个Cache行数据所需的时间。如果每个Cache行包含8个double元素，每个元素需要1个加法操作（1周期），则$T_{\text{access}} = 8$周期。如果$T_{\text{miss}} = 40$周期（L3延迟），则$d_{\text{ideal}} = 5$行。

但$d_{\text{ideal}}$只是一个下界。实际的预取深度通常需要更大，原因包括：

（1）延迟变化。$T_{\text{miss}}$不是常数——它取决于DRAM行命中/缺失、内存控制器队列深度等因素，可能在30$\sim$300周期之间变化。预取深度需要覆盖最坏情况的延迟。

（2）预取带宽限制。预取请求不能每周期都发出（需要与demand请求竞争MSHR和总线带宽），因此实际的预取间隔可能大于$T_{\text{access}}$，需要更大的深度来补偿。

（3）训练延迟。预取器需要若干次观察（通常2$\sim$3次）来检测模式并建立信心，在训练期间不会发出预取。预取深度需要足够大以覆盖训练期间“漏掉”的行。

实践中，流预取器的深度通常在4$\sim$32行之间动态调整。步幅预取器的深度通常固定为1$\sim$4（因为步幅模式的检测速度较快，不需要太大的提前量）。

预取对IPC的端到端影响模型

将精度、覆盖率和及时性综合起来，可以建立一个预取对IPC的端到端影响模型。设无预取时的CPI（Cycles Per Instruction）为$\text{CPI}_0$，其中存储延迟贡献的CPI分量为$\text{CPI}_{\text{mem}}$，则有预取时的CPI为：

$$\text{CPI}_{\text{pf}} = \text{CPI}_0 - \text{CPI}_{\text{mem}} \times C \times T_{\text{eff}} + \text{CPI}_{\text{pollution}} + \text{CPI}_{\text{bw}}$$

其中：

• $C$：覆盖率，预取消除的缺失比例。

• $T_{\text{eff}}$：有效及时性因子。$T_{\text{eff}} = 1$表示所有有用预取都是及时的；$T_{\text{eff}} < 1$表示部分有用预取是延迟的（仍有部分收益）。

• $\text{CPI}_{\text{pollution}}$：预取引起的Cache污染导致的额外CPI。

• $\text{CPI}_{\text{bw}}$：预取消耗带宽导致demand请求延迟增加的CPI。

只有当$\text{CPI}_{\text{pf}} < \text{CPI}_0$时，预取才是有益的。这要求： $$C \times T_{\text{eff}} > \frac{\text{CPI}_{\text{pollution}} + \text{CPI}_{\text{bw}}}{\text{CPI}_{\text{mem}}}$$

这个不等式清楚地表明了预取器设计的核心挑战：左边的$C \times T_{\text{eff}}$要尽可能大（高覆盖、及时），右边的$\text{CPI}_{\text{pollution}} + \text{CPI}_{\text{bw}}$要尽可能小（低污染、低带宽浪费）。精度$A$间接影响右边两项——低精度导致更多无用预取，增加污染和带宽浪费。

性能分析 3 — 典型预取器在SPEC CPU 2017上的端到端性能

表表 7.3展示了几种典型预取器在SPEC CPU 2017上的平均性能数据。

预取器	精度	覆盖率	及时性	IPC提升
无预取	—	—	—	基准
Next-Line	60%$\sim$80%	30%$\sim$50%	90%+	5%$\sim$8%
IP-Stride	80%$\sim$95%	40%$\sim$60%	85%+	8%$\sim$15%
SMS	70%$\sim$90%	50%$\sim$70%	75%$\sim$90%	12%$\sim$18%
BOP	75%$\sim$90%	50%$\sim$80%	80%$\sim$95%	15%$\sim$25%
多级组合	70%$\sim$85%	65%$\sim$85%	80%$\sim$90%	20%$\sim$35%

“多级组合”指L1 stride + L2 streamer + L2 spatial的组合配置，类似于Intel现代处理器的实际配置。可以看到，多级组合通过覆盖更多类型的访问模式，实现了最高的IPC提升，但精度略低于单一高精度预取器（如IP-Stride），因为多级系统的部分冗余预取降低了整体精度。

自适应预取节流

由于不同工作负载的访问模式差异很大，一个在所有场景下都使用固定激进度的预取器很难在所有情况下都表现良好。自适应预取节流（Adaptive Prefetch Throttling）通过在运行时动态调节预取器的激进度来优化性能。

反馈指标

自适应节流机制通常基于以下一个或多个运行时反馈指标来调节预取行为：

• 预取精度：通过统计有用预取和无用预取的比例来计算。如果精度低于阈值（如50%），降低预取激进度；如果精度高（如90%以上），增加激进度。

• Cache污染率：统计由于预取数据占用了有用demand数据的Cache位置而导致的额外缺失数。高污染率暗示预取过于激进。

• MSHR占用率：如果预取请求频繁占满MSHR，可能会延迟demand请求的处理。

• 带宽利用率：如果存储系统接近带宽饱和，应降低预取频率以优先服务demand请求。

节流机制的实现

常见的节流机制包括：

（1）预取度调节（Degree Control）：动态调整预取深度（每次触发时预取的Cache行数）。例如，步幅预取器的预取度可以从1调节到8或更高：

$$\text{Degree}_{t+1} = \begin{cases} \min(\text{Degree}_t + 1, D_{\max}) & \text{if accuracy} > \theta_{\text{high}} \\ \max(\text{Degree}_t - 1, 1) & \text{if accuracy} < \theta_{\text{low}} \\ \text{Degree}_t & \text{otherwise} \end{cases}$$

（2）预取距离调节（Distance Control）：调整预取的提前量（prefetch ahead distance），即预取地址领先于当前访问地址的距离。更远的距离可以更好地隐藏延迟，但也更容易产生不准确的预取。

（3）预取启用/禁用：在极端情况下，完全关闭预取器。当预取精度持续低于某个下限时，关闭预取以避免性能损害。

节流机制的硬件实现

自适应节流需要硬件计数器来跟踪预取的运行时统计信息。典型的计数器配置包括：

• 总预取计数器（Total Prefetch Counter）：统计一个时间窗口内发出的总预取请求数。16位计数器，每$2^{16}$个预取请求归零。

• 有用预取计数器（Useful Prefetch Counter）：统计被demand访问命中的预取行数。需要在Cache行的元数据中增加1位“预取”标志（Prefetch bit），在命中时检查该标志并递增计数器。

• 延迟预取计数器（Late Prefetch Counter）：统计demand访问到达时预取请求已经发出但数据尚未返回的次数。需要检查MSHR中是否存在匹配的预取请求。

• 污染计数器（Pollution Counter）：统计被预取行替换的demand行随后又被demand再次访问的次数。这需要跟踪被驱逐行的地址并在后续缺失时检查——实现复杂度较高，通常使用采样近似。

精度的计算为$A = \text{有用计数} / \text{总计数}$；延迟性为$L = \text{延迟计数} / \text{有用计数}$。这些比值可以通过移位操作来近似计算（避免除法器的面积开销），例如精度$>$50%等价于有用计数$>$总计数$\gg 1$。

Feedback-Directed Prefetching (FDP)

Srinath等人于2007年提出的FDP是自适应节流的经典方案。FDP将预取器的激进度分为五个等级（非常保守、保守、中等、激进、非常激进），并使用三个度量指标——精度、延迟性（lateness）、污染率——来决定在等级之间的切换。

FDP的状态转移逻辑可以概括为：

• 精度高 $\land$ 延迟多 $\Rightarrow$ 提高激进度（预取需要更提前）。

• 精度高 $\land$ 延迟少 $\Rightarrow$ 维持当前激进度。

• 精度低 $\land$ 污染高 $\Rightarrow$ 降低激进度。

• 精度低 $\land$ 污染低 $\Rightarrow$ 小幅降低激进度。

性能分析 4 — 自适应节流的实际效果

实验表明，带有自适应节流的步幅预取器比固定激进度的步幅预取器平均提升3%$\sim$5%的IPC，且在最差情况下避免了高达10%的性能损失。在带宽敏感的多核场景下，自适应节流的价值更加显著，因为多个核心的预取器竞争共享带宽时，不加节制的预取可能导致严重的带宽拥塞。Intel从Haswell微架构开始引入了预取节流机制，根据带宽压力动态调整L2预取器的激进度。

多级预取的协调

现代高性能处理器通常在多个Cache层次都部署了预取器，例如L1有步幅预取器，L2有流预取器或BOP，LLC有时间预取器。这些多级预取器之间的协调是一个重要但常被忽视的设计问题。

典型的多级预取配置

以Intel的Golden Cove微架构为例，其预取子系统包含以下组件：

• L1 IP-stride预取器：基于load指令PC跟踪步幅，将预取数据取入L1 D-Cache。

• L1 流预取器（Streamer）：检测顺序/步幅访问流，可预取到L1或L2。

• L2 流预取器：在L2级别检测更长距离的流模式，预取数据到L2。

• L2 空间预取器（Adjacent Line Prefetcher, ALP）：对每个L2 demand缺失，预取相邻的Cache行。

协调问题

多级预取器之间的协调需要解决以下问题：

（1）预取目标层次：预取的数据应该放在哪一级Cache中？如果L1预取器将数据直接预取到L1，可能导致L1中有用的demand数据被驱逐（污染）。一种常见策略是L2预取器将数据预取到L2，只有当预取数据即将被使用时才将其提升到L1。

（2）冗余预取过滤：如果L1和L2的预取器同时检测到同一个模式，它们可能对同一个地址发出重复的预取请求。预取系统需要一个机制来检测和过滤这种冗余。常见的做法是在发出预取请求前检查该地址是否已经在上级Cache中或已有一个未完成的请求（通过查询MSHR）。

（3）优先级管理：当预取请求与demand请求竞争存储系统资源（带宽、MSHR、Bank）时，demand请求应该获得更高的优先级。典型的优先级排序为：

$$\text{Demand} > \text{L1 Prefetch} > \text{L2 Prefetch} > \text{LLC Prefetch}$$

预取队列与节流

每一级预取器通常有一个专用的预取队列（Prefetch Queue, PQ），用于缓冲待发出的预取请求。PQ的容量有限（通常8$\sim$32个表项），当PQ满时，新的预取请求被丢弃。PQ与MSHR共享对下一级Cache的访问端口，但其优先级低于demand请求。

在带宽压力较大时，可以动态减小PQ的有效容量来限制预取的发出速率：

$$\text{PQ}_{\text{effective}} = \text{PQ}_{\text{max}} \times \left(1 - \frac{\text{BW}_{\text{usage}}}{\text{BW}_{\text{max}}}\right)$$

这种简单的反馈机制可以在带宽充裕时允许积极预取，在带宽紧张时自动节流。

预取去重

在多级预取系统中，冗余预取是一个需要认真处理的问题。假设L1的步幅预取器和L2的流预取器同时检测到一个步幅为1的顺序流，它们都会对同一组地址发出预取请求。如果不加以控制，每个地址将被预取两次，浪费一半的预取带宽。

常见的去重机制包括：

• MSHR查询：在发出预取请求前，检查目标地址是否已在MSHR中有未完成的请求（demand或prefetch）。如果已有，则丢弃重复的预取。

• Cache查询：检查目标地址是否已经在上级Cache中。如果L2预取器要预取的地址已在L1中，则无需预取。

• 预取请求标记：在预取请求中携带来源标识（哪一级预取器发出的），当多个级别对同一地址发出预取时，只保留优先级最高的那个。

跨层预取协议

一种更精细的协调方案是跨层预取协议：L1预取器只处理"容易"的模式（短步幅、高置信度），而将"困难"的模式（长步幅、不规则模式、低置信度）交给L2预取器处理。这种分工避免了L1预取器发出不准确的预取而污染宝贵的L1 Cache空间。

跨层协议的一个实际实现方式是预取提示传递（Prefetch Hint Passing）：L1预取器在检测到一个模式但置信度不足时，将该模式的信息（如PC和初始步幅）传递给L2预取器。L2预取器可以继续跟踪该模式，在积累了更多的观察数据后再决定是否发出预取。这种方式利用了L2预取器可以容忍更长训练时间的优势——因为L2预取器的预取目标是L2（而非L1），即使训练期间错过了几个缺失，代价也只是L2缺失而非L1缺失。

多级预取器的仿真与调优

设计一个多级预取系统的最大挑战不在于单个预取器的算法设计，而在于多个预取器之间的参数联合调优。每个预取器有多个参数（表大小、预取深度、置信度阈值、节流水位线等），$K$个预取器的参数空间呈指数增长。

实践中，处理器设计团队使用以下方法来应对这一挑战：

（1）层次化调优。先独立调优每个预取器的参数（使用单一预取器的性能作为目标），然后在组合系统中微调各预取器之间的交互参数（如优先级、带宽分配比例）。

（2）自动化参数搜索。使用贝叶斯优化或遗传算法在大规模的参数空间中搜索最优组合。这需要高效的存储系统模拟器（如ChampSim）来快速评估每种参数组合的性能。

（3）DPC竞赛的经验法则。Data Prefetching Championship系列竞赛提供了大量关于预取器调优的经验知识。例如，L2预取器的最优深度通常是L3延迟的1.5$\sim$2倍除以每次缺失间隔；预取精度的下限阈值通常为50%（低于此值应关闭预取）。

多级预取器的层次化部署

预取对Cache污染的控制

预取引入的最主要的负面效应之一是Cache污染（Cache Pollution）：预取的数据占据了Cache中原本存放有用demand数据的位置，导致这些demand数据被驱逐，从而引发额外的Cache缺失。污染效应在Cache容量较小的L1层次尤为严重。

污染的量化

Cache污染可以通过以下指标来量化：

$$\text{Pollution} = N_{\text{miss\_with\_pf}} - N_{\text{miss\_no\_pf}} + N_{\text{eliminated}}$$

其中$N_{\text{miss\_with\_pf}}$是有预取时的demand缺失数，$N_{\text{miss\_no\_pf}}$是无预取时的demand缺失数，$N_{\text{eliminated}}$是被预取消除的缺失数。如果$\text{Pollution} > N_{\text{eliminated}}$，则预取造成的额外缺失比消除的缺失还多，预取器在整体上是有害的。

预取隔离

一种经典的Cache污染控制策略是预取隔离（Prefetch Isolation）。其基本思想是在Cache中为预取数据和demand数据分配独立的区域：

（1）独立的预取缓冲区（Prefetch Buffer）：在Cache旁边设置一个小型的全相联缓冲区，专门用于存放预取的数据。当demand访问需要的数据在预取缓冲区中找到时，将其移入主Cache；未被使用的预取数据只占用预取缓冲区的空间，不会影响主Cache。

（2）路划分（Way Partitioning）：在组相联Cache中，将一部分路专门留给demand数据，其余路用于预取数据。例如，在一个8路组相联Cache中，可以将6路分配给demand、2路分配给prefetch。

（3）插入策略调整：与其物理隔离，可以通过调整预取数据的Cache替换策略来降低其优先级。例如，将预取数据插入LRU栈的非MRU位置（如LRU位置），使其更容易被替换。当预取数据被demand访问命中（升级为demand数据）时，才将其提升到MRU位置。

保护距离

Wu等人提出的保护距离（Protection Distance）概念提供了一种优雅的Cache污染控制方法。保护距离$PD$定义为：在替换策略中，一个Cache行从插入到被替换之间至少需要经过的访问次数。通过为demand数据设置较长的保护距离、为预取数据设置较短的保护距离，可以确保预取数据更容易被替换而demand数据更容易被保留。

$$PD_{\text{demand}} > PD_{\text{prefetch}}$$

这种方法的优势在于它不需要物理划分Cache空间，而是通过替换策略的差异化来实现逻辑上的隔离。

预取感知的替换策略

预取触发的Cache行填充必然伴随着Cache替换——每一次预取填充都会驱逐一个现有的Cache行。因此，预取的效果直接受制于第 6.0 章中讨论的替换策略：一个好的替换策略能够优先驱逐低价值的行（如预取后长时间未被使用的行），从而为有用的demand数据和高价值的预取数据保留空间。现代Cache替换策略（如DRRIP、SHiP等）可以扩展为预取感知的版本。其核心修改是在Cache行的元数据中增加一个标志位，标识该行是由demand访问还是预取填充的。替换策略根据这个标志做出差异化决策：

• 预取数据以低优先级插入：新到达的预取数据被插入到替换优先级队列的高替换端（更容易被替换）。

• demand命中提升：如果一个预取数据被demand访问命中，将其优先级提升到正常的demand数据水平。

• 未使用的预取优先驱逐：在选择驱逐候选时，优先选择从未被demand访问命中的预取数据。

预取缓冲区的设计

预取缓冲区（Prefetch Buffer, PB）是一种在Cache旁边设置的小型全相联缓存，专门用于存放预取的数据。预取缓冲区的设计需要考虑以下要素：

（1）容量：典型的预取缓冲区有8$\sim$32个表项。过少的表项可能导致预取的数据在被使用之前就被替换出PB；过多的表项增加面积和搜索延迟。

（2）访问接口：当demand访问发生L1缺失时，需要同时查询L2和PB。PB的查询逻辑类似于Victim Cache——使用CAM对地址进行并行比较。如果PB命中，数据被移入L1（或L2），PB表项被释放。

（3）替换策略：PB通常使用FIFO替换——最早到达的预取数据最先被替换。这基于一个假设：越早预取的数据如果还没被使用，就越不太可能在未来被使用（可能是不准确的预取）。

（4）与预取器的交互：预取器发出的预取请求将数据填入PB而非直接填入Cache。只有当PB中的数据被demand访问命中时，数据才被“升级”到Cache中。这种两阶段的填充策略有效地隔离了不准确的预取对Cache的影响。

预取缓冲区的一个变体是在组相联Cache中预留一路作为“预取路”——预取数据被插入到该路中，而非与demand数据竞争所有路。这种方式不需要额外的独立结构，但降低了Cache对demand数据的有效相联度。

设计提示

在设计预取子系统时，一个有用的启发式原则是：预取数据应该是"有罪推定"（guilty until proven innocent）。也就是说，预取数据在被实际使用之前，应该被视为低价值数据，不应该驱逐已经被证明有用的demand数据。只有当预取数据被demand访问命中后，才将其"升级"为正常的demand数据。这一原则在Intel的Adaptive Replacement策略和AMD的Cache管理策略中都有体现。

基于机器学习的预取

随着机器学习在各个领域取得突破性进展，研究者们开始探索将机器学习技术应用于地址预测和数据预取。这一方向的核心思想是：将预取问题形式化为一个序列预测问题，利用深度学习模型的强大表示能力来学习复杂的、传统启发式方法难以捕捉的访问模式。

预取作为序列预测问题

问题形式化

给定一个历史的Cache缺失地址序列$(a_1, a_2, \ldots, a_t)$，预取问题可以被形式化为预测下一个（或下几个）缺失地址$a_{t+1}$的概率分布：

$$P(a_{t+1} \mid a_1, a_2, \ldots, a_t)$$

这与自然语言处理中的语言模型（预测下一个词）在数学形式上完全一致。区别在于，地址空间的"词汇量"远大于自然语言的词汇量——一个64位地址空间（以Cache行粒度）有$2^{58}$个可能的Cache行地址，直接建模全地址空间是不可行的。

预取问题与语言模型的本质区别

尽管预取和语言模型在数学形式上相似（都是序列预测），两者有几个本质区别决定了不能简单地将NLP模型搬到预取场景：

（1）词汇量差异。自然语言的词汇量约为50K$\sim$200K，而Cache行地址的"词汇量"高达$2^{34}\sim 2^{40}$。直接使用softmax输出层预测具体地址是不可行的。

（2）延迟约束。语言模型的推理延迟可以是毫秒级（用户可以等待），而预取器的推理必须在纳秒级完成（否则预取不够及时）。这意味着预取器只能使用极其简化的模型。

（3）硬件约束。语言模型运行在GPU/TPU上，有数十GB的显存和数百TFLOPS的算力。预取器只能使用数KB$\sim$数百KB的片上SRAM和简单的定点运算单元。

（4）在线适应的重要性。语言模型可以在大规模语料上离线训练一次并部署。预取器则需要适应运行时变化的访问模式——不同的程序、不同的输入数据、甚至同一程序的不同执行阶段都有截然不同的访问模式。

地址表示的简化

为了使问题变得可处理，研究者们采用了多种地址表示简化方法：

• Page offset编码：只预测页内偏移（6$\sim$12位），页号由当前访问确定。这将"词汇量"降低到$64 \sim 4096$。

• Delta编码：预测相邻访问之间的地址差值（delta），将无界的地址空间映射到有限的delta值集合。

• 分桶编码：将地址空间划分为若干"桶"（bucket），预测目标桶的编号。

• PC关联编码：将地址预测与产生该访问的指令PC关联，利用PC提供额外的上下文信息。

LSTM预取器

Hashemi等人于2018年在ISCA上发表了开创性的工作，将LSTM（Long Short-Term Memory）网络应用于地址预测。其模型以最近$k$个缺失地址的delta序列作为输入，预测下一个delta值：

$$\hat{\delta}_{t+1} = \text{LSTM}(\delta_{t-k+1}, \delta_{t-k+2}, \ldots, \delta_t)$$

LSTM的循环结构使其能够捕捉长距离的时间依赖关系，而遗忘门机制使其能够自适应地选择记忆或遗忘过去的信息。

LSTM预取器的具体配置

Hashemi等人提出的LSTM预取器使用以下具体配置：

• 输入编码：最近$k = 10$个缺失的delta值，每个delta值被编码为一个one-hot向量或嵌入向量。delta值的范围被量化为$[-128, +128]$的整数（以Cache行为单位），超出范围的delta被截断。

• 网络结构：单层LSTM，隐藏状态维度$h = 64$，输出层为全连接层 + softmax，输出257个类别（$[-128, +128]$对应的delta值加上一个“无预测”类别）。

• 参数量：$4 \times (h^2 + h \times d + h) + h \times 257 = 4 \times (4096 + 64d + 64) + 16448 \approx 33$K参数（$d$为输入维度，约等于嵌入维度32）。以8位定点数存储约需33 KB。

• 推理延迟：在专用的定点乘加阵列上，单次LSTM推理约需$4h^2 = 16384$次乘加操作。以每周期执行64次乘加的加速器计算，推理延迟约为256个周期。

在SPEC CPU2006基准上的评估表明，LSTM预取器在某些高度不规则的工作负载上（如omnetpp、mcf）显著优于传统预取器，覆盖率提升了20%$\sim$40%。然而，其准确率在某些工作负载上不如精心调优的传统预取器（如BOP）。

LSTM预取器的一个有趣发现是：模型规模的增加对性能的提升存在明显的边际递减。从$h = 32$增加到$h = 64$带来了约8%的覆盖率提升，但从$h = 64$增加到$h = 128$只带来了约2%的提升——而参数量增加了4倍。这暗示了预取问题的固有复杂度有限——不需要非常大的模型就可以捕获大部分可学习的模式。

LSTM预取器的动机与传统预取器的根本局限

传统预取器——无论是步幅预取器、SMS还是BOP——本质上都依赖于人工设计的规则来描述地址模式。步幅预取器假设地址以固定增量递增，SMS假设空间区域内的访问模式可以用位向量表示，BOP假设存在一个全局最优偏移。这些规则在它们各自的目标模式上非常有效，但它们有一个根本性的局限：无法适应规则设计者未曾预见的复杂模式。

考虑以下几种传统预取器难以处理的访问模式：

（1）图遍历。在广度优先搜索（BFS）或PageRank计算中，程序按照图的邻接表顺序访问邻居节点。由于图的拓扑结构不可预知，访问地址序列看起来几乎是“随机”的——但它们实际上蕴含着图结构的内在规律。例如，社交网络中的Power-law度分布意味着少数“超级节点”会被反复访问，而它们的邻居节点在物理内存中可能呈现出某种可学习的分布模式。

（2）数据库B+树遍历。B+树的索引查找从根节点开始，沿着中间节点逐级下降到叶节点。每一级节点的物理地址取决于被查找的键值，形成了一种“条件跳转”式的访问模式——下一级节点的地址隐藏在当前节点的内容中。当连续查询的键值之间存在某种分布（如时间局部性），B+树遍历的地址序列就可能包含可学习的时间模式。

（3）间接数组访问。A[B[i]]形式的访问中，B[i]的值序列可能遵循某种非平凡的统计分布。例如，在稀疏矩阵-向量乘法（SpMV）中，B数组存储的是非零元素的列索引。对于具有特定结构的稀疏矩阵（如有限元网格），列索引的序列虽然不是简单的步幅，但蕴含着网格拓扑的规律。

LSTM预取器的革命性在于它不预设任何特定的模式形式——它通过从数据中学习来自动发现这些规律。LSTM的遗忘门和输入门机制使其能够选择性地记忆历史中的关键信息（如“最近5次访问都在同一个页面内”），同时遗忘无关的细节（如“200次访问前的具体偏移值”）。这种自适应的记忆能力是LSTM相对于Markov预取器的核心优势——Markov预取器需要精确匹配完整的历史序列，而LSTM可以学习历史的“抽象表示”。

LSTM预取器的网络架构详解

LSTM预取器的完整网络架构由四个层次组成，每个层次执行特定的功能：

第一层：Delta编码器。将原始的缺失地址$a_t$转换为delta序列$\delta_t = a_t - a_{t-1}$（以Cache行为粒度）。Delta编码将无界的64位地址空间压缩为有界的差值空间，使得模型的“词汇量”从$2^{58}$降低到几百个有效delta值。delta值被量化为$[-128, +128]$的离散整数，超出范围的值被截断到$\pm 128$。在SPEC CPU工作负载中，约85%$\sim$95%的delta值落在$[-64, +64]$范围内，覆盖了绝大多数实际出现的地址差值。

第二层：嵌入层。将离散的delta值映射为稠密的$d$维向量（典型的$d = 32$）。嵌入层的本质是一个$257 \times d$的查找表——给定一个量化后的delta值（共257个可能的值），直接查表得到对应的嵌入向量。与one-hot编码相比，嵌入层通过学习到的低维表示捕捉了delta值之间的语义关系。例如，$\delta = +1$和$\delta = +2$的嵌入向量可能在向量空间中距离较近，因为它们都代表“正向小步长”访问。

第三层：LSTM层。核心的循环网络层。一个LSTM单元在每个时间步接收当前的嵌入向量$\mathbf{x}_t$和上一步的隐藏状态$\mathbf{h}_{t-1}$、记忆状态$\mathbf{c}_{t-1}$，通过四个门控机制计算新的隐藏状态和记忆状态：

$$\begin{aligned} \mathbf{f}_t &= \sigma(\mathbf{W}_f \mathbf{x}_t + \mathbf{U}_f \mathbf{h}_{t-1} + \mathbf{b}_f) & \text{（遗忘门）} \\ \mathbf{i}_t &= \sigma(\mathbf{W}_i \mathbf{x}_t + \mathbf{U}_i \mathbf{h}_{t-1} + \mathbf{b}_i) & \text{（输入门）} \\ \tilde{\mathbf{c}}_t &= \tanh(\mathbf{W}_c \mathbf{x}_t + \mathbf{U}_c \mathbf{h}_{t-1} + \mathbf{b}_c) & \text{（候选记忆）} \\ \mathbf{c}_t &= \mathbf{f}_t \odot \mathbf{c}_{t-1} + \mathbf{i}_t \odot \tilde{\mathbf{c}}_t & \text{（记忆更新）} \\ \mathbf{o}_t &= \sigma(\mathbf{W}_o \mathbf{x}_t + \mathbf{U}_o \mathbf{h}_{t-1} + \mathbf{b}_o) & \text{（输出门）} \\ \mathbf{h}_t &= \mathbf{o}_t \odot \tanh(\mathbf{c}_t) & \text{（隐藏状态）} \end{aligned}$$

其中$\sigma$为sigmoid函数，$\odot$为逐元素乘法，$\mathbf{W}_*$和$\mathbf{U}_*$为权重矩阵，$\mathbf{b}_*$为偏置。对于$h = 64$的配置，每个门需要两次矩阵-向量乘法（$\mathbf{W} \in \mathbb{R}^{64 \times 32}$和$\mathbf{U} \in \mathbb{R}^{64 \times 64}$），加上偏置和非线性激活——四个门共计$4 \times (64 \times 32 + 64 \times 64) = 4 \times (2048 + 4096) = 24576$次乘加操作。

对于更强的预测能力，可以堆叠两层LSTM。第二层LSTM以第一层的隐藏状态序列$\{\mathbf{h}^{(1)}_t\}$作为输入，捕捉更高层次的抽象模式。双层LSTM的参数量约为单层的2倍，推理延迟也近似翻倍（因为第二层的计算依赖于第一层的输出，无法并行）。实验数据表明，双层LSTM（$h = 64$）比单层LSTM（$h = 64$）在mcf工作负载上的覆盖率提升约5%$\sim$8%，但在步幅模式主导的工作负载上差异极小。

第四层：输出层。一个全连接层将LSTM的隐藏状态$\mathbf{h}_t \in \mathbb{R}^{h}$映射到257维的logit向量，再通过softmax归一化得到每个delta值的概率分布。选择概率最高的delta值$\hat{\delta}_{t+1}$，再加上当前地址$a_t$得到预取地址：$\hat{a}_{t+1} = a_t + \hat{\delta}_{t+1}$。

如果需要多路预取（multi-degree prefetching），可以选择概率排名前$k$的delta值（如top-3），同时发出多个预取请求。这种多路策略以更高的带宽消耗换取更高的覆盖率。

LSTM预取器的训练

LSTM预取器的训练使用标准的交叉熵损失（cross-entropy loss）作为目标函数：

$$\mathcal{L} = -\frac{1}{T} \sum_{t=1}^{T} \log P(\delta_{t+1} \mid \delta_1, \delta_2, \ldots, \delta_t; \theta)$$

其中$\theta$为模型的全部参数，$T$为训练序列的长度。优化使用Adam优化器（学习率$\sim$0.001），batch size为64个序列片段，每个片段包含100个连续的delta值。

一个关键的训练决策是在线训练还是离线训练：

离线训练：使用预先录制的访存trace（如通过Pin/DynamoRIO工具录制SPEC CPU的执行trace）进行监督学习。优点是训练可以使用浮点运算和GPU加速，不受硬件约束限制；缺点是训练好的模型在面对训练时未见过的访问模式时可能失效。离线训练的模型参数被固化到芯片的SRAM中，运行时只进行前向推理。

在线训练：在处理器运行时持续更新模型参数。理论上可以实现对新访问模式的自适应，但硬件实现极其困难——反向传播需要存储所有中间激活值，梯度计算需要高精度浮点运算。Hashemi等人在论文中提出了一种伪在线训练方案：在离线阶段使用多种工作负载的混合trace进行训练，使模型学习到泛化的地址模式表示，而非记忆特定程序的地址序列。实验表明，在1000种不同程序的混合trace上训练的模型，在未见过的新程序上仍然保持约80%$\sim$90%的相对预测精度。

LSTM预取器的推理延迟深度分析

LSTM前向传播的计算可以分解为以下几个步骤及其延迟估算（$h = 64$，$d = 32$，INT8精度）：

1. 嵌入查找：1次SRAM读取$\to$ 1周期

2. 矩阵-向量乘法（$\mathbf{W}\mathbf{x}$，4个门共享）：$4 \times 64 \times 32 = 8192$次MAC。在$16 \times 16$ MAC阵列上需要$8192 / 256 = 32$个周期

3. 矩阵-向量乘法（$\mathbf{U}\mathbf{h}$，4个门共享）：$4 \times 64 \times 64 = 16384$次MAC。需要$16384 / 256 = 64$个周期

4. 逐元素操作（加法、sigmoid、tanh、Hadamard积）：$\sim$256个操作。在64宽的SIMD单元上需要$\sim$4$\sim$8个周期（sigmoid/tanh使用LUT近似）

5. 输出层（$\mathbf{W}_{\text{out}}\mathbf{h}$）：$64 \times 257 = 16448$次MAC。需要$16448 / 256 = 65$个周期

6. Softmax + argmax：257个元素的max搜索和指数运算，约5$\sim$10个周期

总推理延迟约为$1 + 32 + 64 + 8 + 65 + 10 \approx 180$个周期。如果使用更大的$32 \times 32$ MAC阵列（每周期1024次MAC），延迟可降至约$1 + 8 + 16 + 8 + 17 + 10 \approx 60$个周期——但阵列面积增加了4倍。

这个延迟分析揭示了一个关键的设计权衡：更大的MAC阵列降低了延迟但增加了面积和功耗，而预取器不同于GPU——它不需要持续高吞吐计算，只需要在每次LLC缺失时进行一次推理。因此，一个小型的$16 \times 16$ MAC阵列在大多数场景下就足够了。

LSTM预取器的存储开销详解

LSTM预取器的存储需求可以精确计算如下（$h = 64$，$d = 32$，INT8权重，INT16激活）：

组件	元素数	存储(字节)	说明
嵌入表	$257 \times 32$	8224	delta词汇$\times$嵌入维度
$\mathbf{W}$矩阵（4个门）	$4 \times 64 \times 32$	8192	输入到门的权重
$\mathbf{U}$矩阵（4个门）	$4 \times 64 \times 64$	16384	隐藏到门的权重
偏置（4个门）	$4 \times 64$	256	每个门一个偏置向量
输出权重	$64 \times 257$	16448	隐藏到delta的映射
输出偏置	257	257	输出层偏置
权重总计		$\sim$49 KB	INT8存储
隐藏状态$\mathbf{h}_t$	64	128	INT16运行时状态
记忆状态$\mathbf{c}_t$	64	128	INT16运行时状态
中间激活	$\sim$512	1024	门计算的中间值
Sigmoid/Tanh LUT	$2 \times 256$	512	8位输入$\to$8位输出
总计		$\sim$51 KB

51 KB的存储需求是传统步幅预取器（$< 1$ KB）的50倍以上，但与L2 Cache的典型容量（256 KB$\sim$1 MB）相比仍然很小——约为L2容量的5%$\sim$20%。如果一个51 KB的LSTM预取器能够覆盖20%的原本无法预取的L2缺失，其对IPC的贡献可能相当于增加50$\sim$100 KB的L2 Cache容量。

LSTM预取器与传统预取器的定量对比

在SPEC CPU2006和SPEC CPU2017的评估中，LSTM预取器展现出以下特征：

工作负载	访问模式	步幅预取器	BOP	LSTM
		覆盖率/精度	覆盖率/精度	覆盖率/精度
lbm	规则步幅	95%/98%	90%/95%	88%/92%
bwaves	流式访问	92%/96%	88%/93%	85%/90%
mcf	图遍历	15%/60%	35%/70%	62%/75%
omnetpp	链表/指针	10%/50%	25%/65%	55%/72%
xalancbmk	树遍历	12%/55%	30%/68%	48%/70%
cactuBSSN	多维步幅	70%/88%	82%/90%	80%/85%

关键观察：在规则访问模式的工作负载（lbm、bwaves）上，传统预取器明显优于LSTM——简单模式不需要复杂模型，而LSTM的不完美泛化反而降低了精度。LSTM的优势集中体现在不规则模式的工作负载上：mcf的覆盖率从步幅预取器的15%跃升到LSTM的62%，omnetpp从10%跃升到55%。这些工作负载正是传统预取器的“盲区”。

硬件描述 1 — LSTM预取器的硬件架构

LSTM预取器的硬件实现可以组织为一条五级流水线，与LLC控制器并行工作：

Stage 1: Delta编码。接收来自LLC控制器的缺失地址$a_t$，计算$\delta_t = a_t - a_{\text{prev}}$，将$\delta_t$量化为$[-128, +128]$的整数索引。延迟：1周期。

Stage 2: 嵌入查找。使用量化后的delta索引从嵌入SRAM中读取$d$维嵌入向量。延迟：1$\sim$2周期（取决于SRAM访问延迟）。

Stage 3: LSTM前向计算。将嵌入向量和上一步的隐藏/记忆状态送入MAC阵列，计算四个门的输出和新的隐藏状态。这是延迟最长的阶段，约100$\sim$170周期（取决于MAC阵列大小）。在此阶段，MAC阵列按以下顺序执行：$\mathbf{W}\mathbf{x}$矩阵乘$\to$ $\mathbf{U}\mathbf{h}$矩阵乘$\to$偏置加法$\to$sigmoid/tanh LUT查找$\to$逐元素运算$\to$隐藏状态更新。

Stage 4: 输出映射。将新的隐藏状态送入输出全连接层，得到257维logit向量。延迟：约60$\sim$65周期。

Stage 5: 地址生成。对logit向量执行argmax（或top-$k$选择），将得到的delta值加上当前地址生成预取地址，并将预取请求插入预取队列。延迟：5$\sim$10周期。

总端到端延迟约为170$\sim$250周期，与一次LLC缺失的DRAM延迟（$\sim$200周期）在同一数量级。这意味着LSTM预取器需要“超前”工作——它的预测不是针对当前缺失，而是针对未来第2$\sim$3次缺失，为推理延迟留出足够的缓冲时间。

图图 7.10展示了LSTM预取器硬件流水线的详细架构。

LSTM预取器的硬件流水线架构

::: warning 性能分析 5 — LSTM预取器 vs. 步幅预取器：mcf工作负载的IPC对比

以SPEC CPU2006的mcf基准为例，定量分析LSTM预取器相对于步幅预取器的IPC提升。mcf是一个最小费用网络流求解器，其核心操作是在一个大型图结构上进行增广路径搜索，访问模式高度不规则。

步骤1：基线性能。无预取时，mcf的IPC约为0.35（在4 GHz处理器上），LLC MPKI（每千条指令的LLC缺失数）约为25。每次LLC缺失的平均延迟为200个周期（DRAM访问延迟）。

步骤2：步幅预取器的效果。步幅预取器在mcf上的覆盖率约为15%，精度约为60%。覆盖15%的LLC缺失意味着MPKI从25降到$25 \times (1 - 0.15) = 21.25$。但40%的无用预取消耗了额外带宽。有预取的IPC约为$0.35 \times \frac{25 \times 200}{21.25 \times 200 + 25 \times 0.15 \times 0.4 \times 50} \approx 0.40$。IPC提升约14%。

步骤3：LSTM预取器的效果。LSTM预取器在mcf上的覆盖率约为62%，精度约为75%。MPKI从25降到$25 \times (1 - 0.62) = 9.5$。25%的无用预取的带宽惩罚需要考虑，但覆盖率的巨大提升使得净收益仍然很大。有预取的IPC约为$0.35 \times \frac{25 \times 200}{9.5 \times 200 + 25 \times 0.62 \times 0.25 \times 50} \approx 0.70$。IPC提升约100%（翻倍）。

步骤4：硬件开销对比。步幅预取器的存储开销$< 1$ KB，无额外计算单元。LSTM预取器需要$\sim$51 KB存储和一个$16 \times 16$ MAC阵列（面积约0.05 mm$^2$@5nm）。

步骤5：性价比分析。LSTM预取器以约51 KB的额外存储（相当于增加约20%的L2 Cache面积）换取了86%的额外IPC提升（从0.40到0.70）。如果通过增加L2 Cache容量来获得同等的IPC提升，需要增加约256 KB$\sim$512 KB的L2容量——面积开销远大于LSTM预取器。这说明在不规则访问模式主导的工作负载上，ML预取器的“每平方毫米IPC收益”远高于简单的Cache容量增加。

:::

Transformer预取器

受Transformer在NLP中取得巨大成功的启发，研究者们也探索了将自注意力机制应用于地址预测。Transformer相比LSTM的优势在于：(1) 可以直接建模长距离依赖，无需通过循环传递；(2) 自注意力的并行化更适合硬件实现；(3) 注意力权重提供了可解释性——可以观察模型在预测时关注的是历史中的哪些访问。

Shi等人在2021年的TransFetch工作中展示了Transformer预取器在处理复杂的时间模式时的优势。TransFetch使用一个小型的Transformer编码器（2$\sim$4层，4$\sim$8头，嵌入维度64），处理最近128个缺失地址的编码序列，预测下一个缺失的delta或页内偏移。

Transformer预取器的网络架构

Voyager预取器

Voyager由Shakerinava和Bakhshalipour等人于2022年提出，是基于注意力机制的预取器中最具代表性的工作之一。Voyager的核心贡献在于设计了一种专门针对预取任务的注意力架构，而非简单地将通用的NLP模型搬运到预取场景。

核心设计

Voyager采用了以下关键设计选择：

（1）PC-localized预测：Voyager不在全局的缺失流上进行预测，而是按指令PC将缺失流分组。每个PC关联一个独立的地址历史序列，Voyager的模型为每个PC的历史序列分别进行预测。这一设计基于一个重要观察：同一条load指令在不同迭代中产生的缺失地址通常具有更强的规律性。

（2）多尺度嵌入：Voyager将地址编码为多个尺度（page级、block级、byte级）的嵌入向量，并通过注意力机制融合不同尺度的信息。这使得模型既能捕捉页级的粗粒度模式，也能捕捉行级的细粒度模式。

（3）轻量化注意力：为了降低硬件开销，Voyager使用了一种简化的注意力计算。它不使用完整的$QKV$矩阵乘法，而是使用地址差值的直接编码作为注意力权重的代理：

$$\alpha_{ij} = \text{softmax}\left(\frac{f(\delta_{ij})}{\sqrt{d_k}}\right), \quad \delta_{ij} = a_i - a_j$$

其中$f(\cdot)$是一个简单的查找表或小型多层感知机，$d_k$是缩放因子。

多头注意力捕获多粒度模式

Voyager的注意力机制使用多头（multi-head）结构来捕获不同粒度的访问规律。每个注意力头独立地学习一种关注模式，最终将各头的输出拼接（concatenate）后通过线性投影融合。典型配置使用4个头，每个头的维度$d_k = 16$（总嵌入维度$d = 64$）。

不同的注意力头倾向于学习不同类型的模式：

• 短程步幅头：关注距离当前最近的1$\sim$3次访问，捕捉局部的步幅变化。这个头的注意力权重集中在最近的时间步，类似于一阶或二阶Markov模型。

• 页级模式头：关注历史中与当前访问在同一物理页内的访问，捕捉页面内部的空间重用模式。由于Voyager的多尺度嵌入将页号和偏移分开编码，某些头会自然地学习到页级的相关性。

• 长程周期头：关注距离较远（30$\sim$100次访问之前）的历史位置，捕捉外层循环或周期性的访问模式。LSTM需要通过多步循环传递来“记忆”如此遥远的历史，信息在传递过程中可能衰减；注意力机制则可以直接建立跨越任意距离的连接，不存在信息衰减的问题。

• 关联模式头：关注历史中与当前delta值相似的访问位置，类似于Markov预取器的关联查找，但通过可学习的注意力权重实现了更灵活的“软匹配”。

注意力权重的可视化提供了有价值的可解释性——通过观察每个头在预测时关注历史中的哪些位置，可以理解模型学到了哪种类型的模式。这在传统预取器中是不可能的：步幅预取器只告诉你“检测到步幅为5”，但不解释为什么选择这个步幅；而Voyager的注意力权重可以直接展示“模型在关注30步之前的访问，因为存在周期为30的外层循环”。

Voyager vs. LSTM：长程依赖与计算开销

Voyager相对于LSTM预取器的核心优势在于处理长程依赖（long-range dependency）的能力。在LSTM中，距离$k$步之前的信息需要经过$k$次遗忘门的过滤才能影响当前预测——即使遗忘门被精心训练，在$k > 50$时信息的有效传递率已经显著衰减。在注意力机制中，距离为$k$的历史位置与当前位置之间的信息传递是直接的（一次注意力计算即可完成），不随$k$增大而衰减。

这一差异在以下工作负载上的表现尤为明显：

（1）嵌套循环。考虑一个三层嵌套循环，外层循环每次迭代产生200次内存访问。200步之前的访问模式将在下一次外层迭代中重现。LSTM在这种场景下需要记忆200步的历史，远超其有效记忆窗口（通常30$\sim$50步）。Voyager的注意力可以直接“看到”200步之前的历史，准确捕捉外层循环的周期。在这类workload上，Voyager比LSTM覆盖率高12%$\sim$18%。

（2）间歇性访问。某些数据结构被间歇性访问——例如每隔50$\sim$100次缺失才被再次访问。LSTM的遗忘门可能在中间的50$\sim$100步内将相关信息“遗忘”，而Voyager的注意力头可以跳过中间的无关访问直接关注上一次相关访问。

然而，Voyager的注意力计算开销高于LSTM。自注意力的时间复杂度为$O(n^2 \cdot d)$（$n$为序列长度，$d$为嵌入维度），而LSTM为$O(n \cdot h^2)$（$h$为隐藏维度）。当历史序列较长（$n > 64$）时，Voyager的计算量可能显著超过LSTM。为缓解这一问题，Voyager在实际实现中通常将历史窗口限制在$n = 64$，并使用稀疏注意力（Sparse Attention）模式——只计算最近$k$个位置和间隔$s$步采样的位置的注意力，将计算复杂度从$O(n^2)$降低到$O(n \cdot k)$。

维度	LSTM ($h=64$)	Voyager (4头, $d=64$)
有效记忆深度	30$\sim$50步	$\leq$序列长度（无衰减）
计算复杂度/步	$\sim$25K MAC	$\sim$40K MAC（含稀疏优化）
参数量	$\sim$50K	$\sim$200K
推理延迟	$\sim$180周期	$\sim$280周期
mcf覆盖率	62%	72%
规则步幅精度	92%	88%
可解释性	低（黑盒）	中（注意力可视化）

从设计的角度看，Voyager和LSTM并非简单的“谁优谁劣”关系，而是在记忆能力与硬件效率之间的不同取舍点。对于长程依赖占主导的工作负载（如嵌套循环、数据库事务重放），Voyager更优；对于短程模式占主导且硬件预算紧张的场景，LSTM的参数效率更高。一种有前途的混合方案是LSTM+稀疏注意力：使用LSTM捕捉短程模式，同时在LSTM之上叠加一个轻量的稀疏注意力层来补充长程依赖的覆盖。

Voyager与传统预取器的融合

Voyager的一个重要设计特点是它可以与传统预取器在同一个系统中共存。Voyager的作者提出了以下融合策略：

（1）互补激活：Voyager只在传统预取器（如stride预取器）未发出预取的缺失上激活推理。这确保了简单模式由低开销的传统预取器处理，Voyager的计算资源只用于真正需要的复杂模式。

（2）置信度仲裁：当Voyager和传统预取器同时对一个地址发出预取时，选择置信度更高的那个。Voyager的置信度可以用softmax输出概率的最大值来衡量——如果最高概率低于阈值（如0.3），说明Voyager对预测不确定，应该让传统预取器的结果优先。

（3）共享预取队列：两类预取器共享同一个预取请求队列和MSHR资源，通过优先级控制确保demand请求不被预取请求饿死。

训练与部署

Voyager的训练分为两个阶段：

（1）离线训练：使用应用程序的历史访存trace进行监督学习训练。训练目标是最小化预测delta与实际delta之间的交叉熵损失：

$$\mathcal{L} = -\sum_{t} \log P(\delta_{t+1} \mid a_{t-k+1}, \ldots, a_t; \theta)$$

（2）在线推理：将训练好的模型参数固化到硬件中。在运行时，模型根据实时的缺失流进行推理，输出预取地址。

性能评估

在DPC-3竞赛的trace上评估，Voyager的加权IPC加速比达到了1.35$\sim$1.40（取决于具体的模型配置），超过了BOP的1.302。Voyager在不规则访问模式（如graph500、randacc类trace）上的优势尤为明显，这正是传统预取器的弱点所在。

性能分析 6 — Voyager vs. 传统预取器

在具有高度规则访问模式的工作负载上（如矩阵乘法、流式访问），Voyager的性能与BOP或步幅预取器相当，有时甚至略低（因为简单模式不需要复杂模型）。Voyager的真正价值体现在那些传统预取器无法有效覆盖的复杂模式上：在mcf上Voyager比BOP提升18%，在omnetpp上提升25%，在图遍历trace上提升30%以上。这些结果验证了ML预取器作为传统预取器补充（而非替代）的定位。

实用性与硬件开销的权衡

尽管ML预取器在学术研究中展现了令人兴奋的潜力，将其部署到实际的处理器芯片中仍面临严峻的挑战。本小节分析这些挑战及相应的缓解策略。

面积开销

一个典型的LSTM预取器包含约100K$\sim$500K个参数（权重），以8位定点数存储约需100 KB$\sim$500 KB的SRAM。这远超传统预取器的存储预算（通常1$\sim$32 KB）。Transformer模型的参数量通常更大。

为了降低面积开销，研究者们探索了以下方向：

• 模型压缩：通过量化（8位甚至4位定点数）、剪枝、知识蒸馏等技术减小模型大小。

• 参数共享：多个PC共享同一个模型实例，仅通过不同的输入历史来区分。

• 混合架构：仅对传统预取器无法覆盖的缺失使用ML预取器，其余缺失由低开销的传统预取器处理。

推理延迟

ML预取器的推理延迟是其实用性的关键瓶颈。一个LSTM前向传播需要数百次乘加运算，即使在专用加速硬件上也需要50$\sim$200个时钟周期。Transformer由于自注意力的计算量更大，延迟可能更高。

推理延迟直接影响预取的及时性。如果推理完成时，被预测的缺失已经发生（甚至已经返回数据），那么预取就完全无用了。因此，ML预取器通常需要"超前预测"：预测的不是下一个缺失，而是未来第$k$个缺失（$k$足够大以覆盖推理延迟）。但超前预测又会降低准确率，形成另一层权衡。

功耗

即使在推理模式下，神经网络的计算也需要显著的功耗。一个100K参数的LSTM以2 GHz运行的功耗约为50 mW$\sim$200 mW，这在高性能桌面处理器中可能是可接受的，但在移动处理器中可能占到功耗预算的显著比例。

在线学习

一个理想的ML预取器应该能够在线学习（online learning），即在运行时根据实际的访问模式持续更新模型参数。然而，在硬件中实现反向传播和梯度下降面临严峻的挑战：(1) 需要存储中间激活值用于反向传播，增加存储需求；(2) 浮点梯度计算的硬件成本高；(3) 学习率调度等超参数需要自适应调整。

当前的实际方案通常采用离线训练+在线推理的模式：在设计阶段使用代表性工作负载的trace训练模型，将训练好的参数固化到芯片中。这种方案的问题是模型无法适应训练时未见过的新访问模式。

一种折中方案是轻量级在线适应：保持大部分模型参数固定，只允许最后一层（或几个关键参数）在运行时更新。这种方法可以用简单的在线学习规则（如指数移动平均）实现，避免了完整反向传播的开销： $$\label{eq:online-adapt} \mathbf{w}_{t+1} = (1 - \eta) \cdot \mathbf{w}t + \eta \cdot \mathbf{w}{\text{target}}$$ 其中$\eta$为学习率（通常极小，如$2^{-8}$），$\mathbf{w}_{\text{target}}$根据预测结果的正确性进行简单的调整。

与传统预取器的集成框架

一个值得考虑的实用架构是ML辅助的混合预取框架，其工作方式如下：

1. 传统预取器（步幅、BOP等）正常工作，处理大部分规则模式。

2. ML预取器并行运行，但只在传统预取器未发出预取的缺失上激活。

3. 一个仲裁器（arbiter）对比两类预取器的历史表现（精度、覆盖率），动态调整它们的相对优先级。

4. 在总预取带宽受限时，优先采用置信度更高的预取请求。

这种框架确保ML预取器只在其能提供增量价值的场景下消耗带宽，避免了与传统预取器的冗余竞争。

ML预取器的定点化和量化

将ML预取器部署到芯片上的一个关键步骤是定点化（Quantization）。训练时的模型使用32位浮点数（FP32），但在硬件中使用FP32的乘法器面积和功耗过大。定点化将模型参数和激活值从FP32转换为低位宽的定点数（如INT8或INT4）。

LSTM预取器的定点化分析如下：

（1）权重量化。LSTM的权重矩阵可以使用INT8量化而几乎不损失预测精度。8位量化的权重可以表示$[-128, +127]$的整数，经过缩放因子调整后映射回原始的浮点值范围。8位量化将参数存储从FP32的33 KB降低到约8.25 KB——节省了4倍的存储。

（2）激活值量化。LSTM的中间激活值（隐藏状态$h_t$和记忆单元$c_t$）通常使用INT16来保持足够的精度。激活值的动态范围比权重更大（因为累加操作），需要更多的位宽。

（3）Sigmoid和Tanh函数的近似。LSTM中的门控函数（sigmoid和tanh）在硬件中不能用标准的浮点函数库实现。常见的近似方法包括分段线性近似（Piecewise Linear Approximation）和查找表（LUT）。一个256项的LUT可以提供$<$0.5%误差的sigmoid近似，只需要256字节的存储。

（4）量化对预测精度的影响。实验数据表明，INT8权重 + INT16激活的量化方案与FP32基线相比，预取精度下降$<$2%、覆盖率下降$<$1%。INT4权重的进一步量化则可能导致5%$\sim$10%的精度下降，需要使用量化感知训练（Quantization-Aware Training）来缓解。

ML预取器的专用加速硬件

如果ML预取器被商用处理器采用，可能需要一个专用的微型推理加速器集成在L2或LLC控制器旁边。这个加速器的设计需求如下：

• 计算单元：一个$16 \times 16$或$32 \times 32$的INT8 MAC（乘加）阵列，每周期执行$256\sim1024$次乘加操作。

• 权重存储：8$\sim$32 KB的SRAM用于存储模型参数。

• 激活缓冲：1$\sim$2 KB的寄存器文件或SRAM用于存储中间激活值。

• 控制逻辑：一个简单的微控制器或有限状态机来编排推理流程（矩阵乘法$\to$激活函数$\to$输出解码）。

• 接口：与L2/LLC控制器的接口，接收缺失地址并输出预取地址。

这样一个加速器的面积估算约为$0.05\sim0.2\text{mm}^2$（5nm工艺），功耗约为$10\sim50$ mW——对于高性能桌面和服务器处理器来说是可以接受的，但对于移动处理器可能仍然偏大。

2030年展望

展望2030年代，ML预取器的实用性可能会因以下技术趋势而显著提升：

• 片上AI加速器的普及：随着NPU（Neural Processing Unit）成为处理器SoC的标配，ML预取器可以复用NPU的计算资源，无需额外的专用硬件。

• 存内计算（Processing-in-Memory）：新型存储技术（如ReRAM、MRAM）支持在存储阵列中直接进行矩阵运算，有望极大降低ML推理的延迟和功耗。

• 稀疏神经网络：稀疏化技术可以将模型的有效计算量降低10$\times$$\sim$100$\times$，使得在处理器预取引擎中部署神经网络变得更加可行。

• 混合方案的成熟：将ML预取器与传统预取器有机结合的混合方案（如只在传统预取器低置信度时启用ML预取器）可以在有限的硬件预算下最大化收益。

ML预取的硬件落地挑战

将ML预取器从学术论文部署到量产芯片，需要跨越一条巨大的“工程鸿沟”。学术评估中常用的指标（覆盖率、精度、IPC加速比）只是冰山一角——商用处理器的设计审查会关注一组远更严苛的约束，这些约束共同构成了ML预取器的硬件落地挑战。理解这些挑战有助于区分“有学术价值的ML预取研究”和“可部署的ML预取方案”。

功耗预算约束：1%$\sim$2%的铁律

一个经验性的设计准则是：预取器的功耗不应超过处理器核心总功耗的1%$\sim$2%。这一准则的来源是成本-收益分析：预取器的IPC贡献通常在15%$\sim$40%范围内（取决于工作负载），如果预取器本身消耗了5%以上的功耗预算，那么从性能功耗比（Performance per Watt）的角度看，这些功耗不如分配给更大的Cache、更宽的发射队列或更多的执行单元。

以具体数字为例：一个TDP 12.5W的高性能核心（8核服务器处理器中的单核），其ML预取器的功耗预算为$12.5 \times 0.01 \sim 12.5 \times 0.02 = 125 \sim 250$ mW。对照前文的分析，LSTM-Medium（$h=64$）的功耗约为80 mW，Voyager约为120 mW——二者均在预算内。但LSTM-Large（$h=128$）的200 mW已经接近预算上限，留给功耗裕度（power headroom）的空间不足。

对于功耗预算更为紧张的移动处理器（单核TDP约2$\sim$3W），1%的功耗预算仅为20$\sim$30 mW——这已经排除了大多数当前的ML预取器配置。移动平台上的ML预取器需要极其激进的功耗优化。

降低功耗的四大技术路径

为了将ML预取器的功耗控制在预算内，研究者和工程师探索了以下四条互补的技术路径：

（1）低精度量化推理（INT8/INT4）。前文在定点化小节中已经详细分析了量化的基本原理。这里进一步讨论INT4超低精度量化的前沿探索。INT4量化将每个权重只用4位表示（$[-8, +7]$的整数），参数存储降低到FP32的8倍。INT4乘法器的面积约为INT8的1/4（因为乘法器面积大致与位宽的平方成正比），功耗相应降低。

然而，INT4量化对预测精度的影响不容忽视。实验数据表明，直接将FP32权重量化到INT4（Post-Training Quantization, PTQ）会导致覆盖率下降8%$\sim$15%——这在某些工作负载上可能完全抹去ML预取器相对于传统预取器的优势。量化感知训练（Quantization-Aware Training, QAT）可以显著缓解这一问题：在训练过程中模拟INT4量化的效果，使模型的权重分布“适应”低精度表示。QAT后的INT4模型覆盖率下降可控制在3%$\sim$5%以内。

一种更激进的方案是混合精度（Mixed Precision）：对模型中不同层使用不同的量化精度。实验发现，LSTM的遗忘门和输入门对量化精度敏感（INT4会导致门控信号的微小偏差在长序列中累积），而输出层对量化不敏感。因此，一种实用的混合精度配置是：门控权重使用INT8，其余权重使用INT4——在保持精度的同时比均匀INT8减少约25%的功耗。

（2）稀疏网络剪枝。神经网络中相当比例的权重接近于零，对预测结果的贡献极小。非结构化剪枝将这些权重直接置零，使乘法运算可以被跳过（零乘以任何值等于零，不需要实际执行乘法）。典型的LSTM预取器可以承受80%$\sim$90%的权重被剪枝而覆盖率仅下降2%$\sim$5%——这意味着90%的乘加运算可以被跳过。

稀疏网络的硬件实现需要专门的稀疏MAC阵列，其核心组件是一个零检测电路（zero detector）。当检测到权重或激活值为零时，跳过对应的乘加操作并将该MAC单元的输出设为零。NVIDIA的Ampere GPU已经实现了2:4结构化稀疏的硬件加速（每4个权重中最多2个为零），但ML预取器所需的非结构化稀疏需要更灵活的跳过逻辑。

一种适合预取器的简化方案是块稀疏（Block Sparsity）：将权重矩阵划分为$4 \times 4$的小块，整块置零或保留。块稀疏的硬件实现比逐元素稀疏简单得多——只需要一个位图来标记哪些块为非零，MAC阵列按块调度计算。在75%的块稀疏率下，LSTM预取器的有效计算量降低到原始的25%，推理延迟从$\sim$180周期降低到$\sim$60周期（与$32 \times 32$ MAC阵列的效果类似，但面积远小于后者）。

（3）知识蒸馏。知识蒸馏（Knowledge Distillation）使用一个大型的“教师模型”（如$h=128$的双层LSTM）的预测结果来训练一个小型的“学生模型”（如$h=32$的单层LSTM）。学生模型不仅学习真实的delta标签，还学习教师模型的softmax输出分布（称为“软标签”），从而继承教师模型对模式的“理解”。

蒸馏的效果在预取场景中尤为显著：一个$h=32$的学生模型（参数量仅$\sim$10K，存储$\sim$10 KB）通过蒸馏可以达到$h=64$教师模型约85%$\sim$90%的覆盖率——而功耗仅为后者的1/4。这使得ML预取器在移动处理器上的部署成为可能：一个10 KB、15 mW的蒸馏LSTM预取器虽然覆盖率不如完整模型，但在传统预取器无法覆盖的不规则模式上仍然提供了可观的增量收益。

（4）条件激活与门控推理。并非每次LLC缺失都需要启动ML推理——如果传统预取器已经发出了高置信度的预取，ML推理就是浪费功耗。条件激活（Conditional Activation）机制在ML推理引擎前增加一个轻量级的“门控”逻辑，只有在以下条件都满足时才启动ML推理：（a）当前缺失未被任何传统预取器覆盖；（b）最近$N$次缺失的步幅预取器置信度低于阈值；（c）ML推理引擎当前空闲（不在处理上一次请求）。

条件激活的效果是将ML推理的平均功耗大幅降低。假设在典型工作负载中只有30%的LLC缺失需要ML推理（其余70%被传统预取器覆盖），则ML推理引擎的平均功耗为峰值功耗的30%——一个峰值200 mW的Voyager引擎在条件激活下的平均功耗仅为60 mW。

ML预取器与存储层次的交互

ML预取器的效果最终受限于存储层次的带宽。回顾第 5.0 章中讨论的Cache层次结构，预取请求与demand请求共享从L2到LLC、从LLC到DRAM的有限带宽通道。一个覆盖率70%但精度只有60%的ML预取器，每预取100个Cache行中有40个是无用的——这40个无用预取消耗的带宽等同于40次demand缺失的带宽。正如第 48.0 章中讨论的DRAM带宽约束所揭示的：在内存总线接近饱和的工作负载上，预取器（无论是传统的还是ML的）的净收益可能为零甚至为负。

此外，ML预取填入Cache的数据遵循与传统预取相同的替换策略规则（第 6.0 章）。如果ML预取的数据在被使用之前就被替换策略驱逐，预取就完全浪费了。因此，ML预取器需要与替换策略配合：预取数据应以低优先级插入Cache（正如前文在7.4.4 节中讨论的“有罪推定”原则），只有被demand命中后才提升优先级。

设计权衡 3 — ML预取准确率 vs. 硬件开销

ML预取器面临一个核心权衡：模型越大、越复杂，预测准确率越高，但硬件开销（面积、功耗、推理延迟）也越高。这一权衡可以用“准确率-面积曲线”来可视化：

模型配置	参数量	面积（@5nm）	覆盖率	功耗
步幅预取器	$<$1K	$<$0.001 mm$^2$	15%$\sim$40%	$<$1 mW
LSTM-Small ($h=32$)	$\sim$25K	$\sim$0.02 mm$^2$	45%$\sim$55%	$\sim$30 mW
LSTM-Medium ($h=64$)	$\sim$100K	$\sim$0.05 mm$^2$	55%$\sim$65%	$\sim$80 mW
LSTM-Large ($h=128$)	$\sim$400K	$\sim$0.15 mm$^2$	58%$\sim$68%	$\sim$200 mW
Voyager	$\sim$200K	$\sim$0.08 mm$^2$	60%$\sim$75%	$\sim$120 mW

从LSTM-Medium到LSTM-Large，参数量增加了4$\times$，但覆盖率仅提升3$\sim$5个百分点——边际收益急剧递减。Voyager通过注意力机制的结构化设计，在相似的参数量下取得了更高的覆盖率。

对于商用处理器，ML预取器的功耗不应超过核心总功耗的1%$\sim$2%。以一个TDP 100W的服务器处理器（8核，每核$\sim$12.5W）为例，ML预取器的功耗预算约为125$\sim$250 mW/核——这刚好覆盖LSTM-Medium或Voyager的功耗需求。降低功耗的解决方案包括：INT8/INT4量化推理（功耗减少3$\sim$8$\times$）、稀疏网络（剪枝80%$\sim$90%的权重后功耗减少5$\sim$10$\times$）、以及知识蒸馏（用大模型的预测监督训练更小的学生模型）。

设计权衡 4 — ML预取器的部署策略

当前阶段，ML预取器最现实的部署策略是作为L2或LLC级别的补充预取器，与传统的L1步幅/流预取器配合工作。其理由是：

（1）L1预取器需要极低的延迟（$<$5个周期）和极小的面积，不适合部署ML模型。L2/LLC预取器的延迟容忍度更高（10$\sim$50个周期），为ML推理提供了更多的时间窗口。

（2）L2/LLC缺失中包含了更多不规则模式（规则模式已被L1预取器覆盖），正是ML预取器擅长的领域。

（3）L2/LLC通常有更多的存储预算可用于ML模型的参数存储。

从成本效益角度看，一个200 KB的ML预取器如果能在当前无法预取的L2缺失中覆盖20%，其对IPC的贡献可能相当于增加几百KB的L2 Cache容量——后者在面积上可能更加昂贵。

表表 7.7总结了本章讨论的主要预取器在关键维度上的对比。

本章系统地讨论了超越基础步幅预取的高级预取技术。空间模式预取（SMS、VLDP、BOP）通过学习和利用地址空间中的结构化模式来实现精准预取；时间预取（Markov、STMS、ISB）通过记录和重播历史访问序列来覆盖不规则但可重复的模式；指针追踪预取（CDP、Runahead）尝试打破指针追踪固有的串行依赖；预取管理机制（节流、多级协调、污染控制）确保预取的收益大于其开销；基于机器学习的预取（LSTM、Transformer、Voyager）则代表了预取技术的新兴方向。

一个高性能处理器的预取子系统通常不会只使用单一的预取策略，而是将多种预取器组合部署，利用它们的互补优势来最大化覆盖率，同时通过精密的管理机制控制预取开销。

预取器的硬件资源预算

从硬件实现的角度看，预取器的资源预算是一个关键的设计约束。表表 7.8总结了本章讨论的各预取器的典型硬件资源需求。

从表中可以看出，传统预取器的存储开销通常在0.5$\sim$32 KB范围内，远小于Cache本身的容量。CAM搜索是预取器延迟的主要贡献者——SMS的AGT需要32项CAM搜索来检查新的缺失是否属于已跟踪的空间区域，这在高频设计中需要1$\sim$2个周期。

ML预取器的存储和计算开销比传统预取器高出1$\sim$2个数量级。这解释了为什么ML预取器目前仍处于研究阶段——它们的硬件成本尚未降低到商用处理器可以接受的水平。

预取器在处理器微架构中的位置

预取器在处理器微架构中的物理位置决定了它能“看到”什么信息以及它的预取请求如何进入存储层次。

L1级预取器

L1级预取器位于L1 D-Cache控制器内部，可以观察到所有的Load/Store请求（包括L1命中的请求）。这使得L1预取器能够在最早的时机检测到访问模式并发出预取。L1预取器的典型配置是IP-Stride预取器——以Load指令的PC为索引，跟踪每条Load指令的访问步幅。

L1预取器的一个独特优势是它可以获取指令的PC信息——这对于区分不同Load指令的访问模式至关重要。L2级预取器通常无法获取PC信息（因为L1到L2的缺失请求中通常不携带PC），只能基于地址模式进行预测。

L1预取器发出的预取请求可以直接将数据取入L1 D-Cache，提供最低的后续访问延迟。但风险也最大——如果预取不准确，直接污染了宝贵的L1空间。

L2级预取器

L2级预取器位于L2 Cache控制器内部，观察到的是L1缺失流（经过L1过滤后的残余缺失）。L2预取器看到的访问模式与L1预取器不同：简单的短步幅和顺序模式已经被L1预取器覆盖，L2看到的缺失流中更多是长步幅、不规则模式或L1预取器覆盖不了的复杂模式。

L2预取器发出的预取请求通常将数据取入L2（而非L1），以避免不准确的预取污染L1。只有当预取的数据确实被demand访问命中（产生L1缺失并命中L2中的预取行）时，数据才被提升到L1。这种“L2作为预取缓冲区”的策略是一种有效的Cache污染控制方法。

L2预取器的典型配置包括：流预取器（Streamer）、空间预取器（Adjacent Line Prefetcher）和/或BOP/SPP等高级预取器。

LLC级预取器

LLC级预取器比较少见，但在某些设计中存在。LLC看到的缺失流更加稀疏且不规则——L1和L2的预取器已经覆盖了大部分可预测的模式。LLC预取器通常使用时间预取（如STMS）来覆盖不规则但可重复的模式，或使用BOP的变体来捕获L2预取器遗漏的长距离步幅模式。

LLC预取器的一个特殊挑战是其预取的代价更高——LLC缺失意味着数据需要从DRAM取回，延迟可达100$\sim$300周期，带宽消耗也更大。因此，LLC预取器需要更高的精度门槛（通常要求精度$>$80%才启用预取）。

图图 7.12示意性地展示了不同预取器在覆盖不同类型缺失上的互补关系。

不同预取器覆盖范围的互补关系示意图

本章小结

本章系统地讨论了超越基础步幅预取的高级预取技术。从设计方法论的角度看，这些技术可以按照其对“不可预测性”的处理策略分为三大范式：

范式一：空间模式学习。SMS、VLDP和BOP代表了这一范式。它们的共同点是利用地址空间中的结构化规律——无论是空间区域内的访问位图（SMS）、delta序列中的重复模式（VLDP），还是全局最优的固定偏移（BOP）。这些预取器不需要记住具体的地址值，只需要学习地址之间的关系。因此它们的存储开销相对较小（0.5$\sim$32 KB），且在规则访问模式上有很高的精度。

范式二：时间序列重播。Markov、STMS和ISB代表了这一范式。它们的共同点是记录历史的地址序列，在检测到序列重现时重播后续地址。这些预取器能够处理任意不规则但可重复的访问模式——只要一个模式在过去出现过，就有可能在未来再次出现并被预取。代价是需要较大的存储空间来记录历史（64 KB$\sim$数MB），且对首次出现的新模式无能为力。

范式三：数据驱动预测。CDP（内容导向预取）和Runahead代表了这一范式。它们的共同点是利用当前数据的内容来发现未来的访问地址——CDP扫描Cache行中的指针值，Runahead通过预执行未来的指令来发现缺失。这些技术能够处理指针追踪等“地址隐藏在数据中”的模式，但精度通常较低（CDP的误判问题，Runahead的INV传播问题）。

ML预取可以视为第四种新兴范式，它试图通过强大的模型表示能力来统一上述三种范式的覆盖范围。然而，其硬件实现的面积、延迟和功耗开销目前仍是商用部署的主要障碍。

从实际的处理器设计角度看，以下几个要点值得总结：

1. 预取器的组合部署是必要的。没有单一的预取器能够有效覆盖所有类型的访问模式。现代处理器通常部署3$\sim$5个互补的预取器（L1 stride + L1 streamer + L2 spatial + L2 streamer + 可能的高级预取器），通过它们的协同工作最大化覆盖率。

2. 预取管理与预取算法同等重要。一个精度80%但有良好节流和去重机制的预取器，可能比一个精度90%但缺乏管理的预取器表现更好——因为后者可能在带宽紧张时仍然激进预取，或在多级系统中产生大量冗余请求。

3. 硬件预算是核心约束。预取器的存储和计算资源必须在有限的芯片面积预算内实现。BOP以不到0.5 KB的存储赢得了DPC-3冠军，证明了简洁高效的设计往往比复杂精密的设计更实用。

4. 预取与其他存储优化的交互不容忽视。预取器与MSHR、替换策略、一致性协议之间存在复杂的交互。预取器占用MSHR可能影响MLP；预取数据的插入策略影响替换策略的效果；跨核心的预取可能触发不必要的一致性流量。整体存储子系统的设计需要将这些交互纳入考虑。

面向2030年代的处理器设计，预取技术将继续与新的计算范式（近数据计算、领域专用加速器）和新的存储技术（CXL、HBM4）深度融合，成为弥合计算与存储鸿沟的核心机制。随着HBM（High Bandwidth Memory）提供更高的带宽但并未显著降低延迟，预取器的角色将从"减少缺失"扩展到"管理带宽分配"——在多TB/s的总带宽下，预取器需要智能地决定何时以及如何利用这些带宽来提前加载数据，同时避免干扰对延迟敏感的demand请求。CXL（Compute Express Link）引入的内存池化技术则带来了新的预取挑战：远端内存的延迟可能高达数微秒，这要求预取器具备更远的预见能力和更高的精度。

预取技术的未来发展方向还包括：

（1）工作负载感知的预取策略切换。根据程序的执行阶段动态切换预取算法——例如在数组遍历阶段使用简单的流预取器，在图遍历阶段切换到时间预取器或ML预取器。这种阶段性切换需要准确的工作负载特征检测机制。

（2）跨层级的预取协调。在chiplet架构中，不同die上的Cache层次需要协调预取策略。例如，CCD die上的L2预取器和IO die上的LLC之间需要交换预取状态信息，以避免跨die的冗余预取。

（3）异构内存感知的预取。在HBM + DDR5 + CXL内存的异构层次中，预取器需要考虑不同内存层级的延迟和带宽特性，将预取请求定向到最合适的内存层级。例如，对延迟敏感的预取请求应该优先使用HBM，而对带宽敏感的批量预取可以使用DDR5。

（4）安全性考虑。近年来，预取器的安全性受到了越来越多的关注。研究表明，预取器的行为可以被恶意程序利用来创建微架构侧信道攻击。例如，攻击者可以通过观察预取器的状态变化（如是否触发了特定模式的预取）来推断受害者程序的访问地址。未来的预取器设计需要在性能和安全性之间取得平衡——例如通过限制预取器的跨安全域信息泄露（如在进程切换时清除预取器状态）。

（5）预取器与新型加速器的集成。随着领域专用加速器（如NPU、DSA）成为SoC的标配组件，这些加速器的访存行为也需要预取支持。加速器的访存模式可能与通用处理器核心截然不同——例如，矩阵运算加速器的访问模式高度规则（可以用简单的多维步幅预取器覆盖），而图神经网络加速器的访问模式则高度不规则。为不同类型的加速器定制预取策略是一个新兴的研究方向。

DPC竞赛回顾与经验教训

Data Prefetching Championship（DPC）系列竞赛是学术界评估预取器性能的重要平台。三届竞赛（DPC-1/2/3）的冠军方案反映了预取技术的演进趋势：

• DPC-1（2009年）：冠军方案基于改进的GHB时间预取器，强调历史序列的记录和重播。

• DPC-2（2015年）：VLDP以其多级delta预测和精巧的存储管理赢得冠军。VLDP展示了delta-based预测可以覆盖步幅和部分不规则模式。

• DPC-3（2016年）：BOP以极低的硬件开销和出色的性能赢得冠军。BOP的成功传递了一个重要信息——简单的设计在实践中往往比复杂的方案更有效。

从DPC竞赛中可以提炼以下经验教训：

（1）硬件预算的重要性。DPC-3引入了严格的硬件预算限制（总存储不超过32 KB），这使得参赛方案必须在算法复杂度和资源效率之间取得平衡。BOP在不到0.5 KB的预算下击败了使用20$\sim$30 KB存储的复杂方案，证明了资源效率与绝对性能同等重要。

（2）评估方法论。DPC使用了多样化的trace集合（包括SPEC CPU、服务器工作负载和图计算trace），避免了在少数基准上过拟合的风险。这提醒预取器设计者在评估时需要使用足够多样化的工作负载。

（3）可实现性。虽然DPC的参赛方案是在模拟器（ChampSim）中实现的，但获奖方案通常具有清晰的硬件映射——它们的数据结构和操作可以直接映射到SRAM、CAM和简单的控制逻辑。那些依赖复杂的浮点运算或大规模存储的方案即使性能出色，也很难在实际处理器中部署。

（4）组合的力量。DPC-3的许多顶级方案（包括亚军SPP）都是多个预取器的组合——例如BOP + stride预取器、SPP + 流预取器。这验证了多级组合策略的有效性。

性能分析 7 — 从DPC竞赛看预取器的性能上限

DPC-3竞赛中，最佳方案（BOP）在20个trace上的加权IPC加速比为1.302（即平均30.2%的IPC提升）。这个数字可以作为“当前技术水平下L2预取器性能上限”的一个参考。

值得注意的是，不同trace之间的加速比差异巨大：在某些规则访问模式的trace上加速比超过2.0$\times$（即IPC翻倍），而在某些高度不规则的trace上加速比仅为1.01$\times$（几乎没有提升）。这个巨大的差异说明，预取技术在规则模式上已经接近极限，但在不规则模式上仍有很大的改进空间——这正是ML预取器和时间预取器的主要目标领域。

如果将L1级预取器（stride + streamer）与L2级预取器（BOP/SPP）组合使用，总的IPC提升可以达到35%$\sim$50%——这已经是一个处理器微架构中最大的单一性能提升来源之一，仅次于乱序执行本身的贡献。

预取器的验证与调试

预取器的验证是处理器设计中一个容易被忽视但极为重要的环节。预取器的行为不影响程序的正确性（因为预取是hint性质的），因此传统的功能验证方法（如对比黄金模型的结果）无法直接发现预取器的Bug。

预取器可能出现的问题包括：

（1）性能退化Bug：预取器在某些工作负载下反而降低了性能——通常因为过于激进的预取消耗了过多带宽或污染了Cache。这类Bug需要通过大量的性能基准回归测试来发现。

（2）死锁：预取请求占满了MSHR或请求队列，导致demand请求无法获得资源。如果设计中缺少足够的“需求保护”机制（如MSHR水位线），可能导致处理器挂起。

（3）预取-一致性交互Bug：预取请求可能与一致性协议产生复杂的时序交互。例如，一个预取请求正在从L3取数据，同时另一个核心修改了该行并发送了Invalidation请求。如果预取控制器没有正确处理这种竞争条件，可能导致一致性协议状态不一致。

（4）跨页面预取的安全问题：如果预取器生成的地址跨越了页面边界且下一个页面未映射或属于另一个进程，可能触发安全隐患。正确的实现应该在检测到跨页面预取时静默丢弃该预取请求。

在调试方面，现代处理器通常提供预取器性能计数器（Performance Counters）来帮助软件开发者和处理器设计者理解预取行为。典型的预取相关计数器包括：

• 总预取请求数（L1/L2/LLC分别统计）。

• 有用预取数（被demand访问命中的预取行数）。

• 延迟预取数（demand访问时预取数据尚未返回）。

• 因预取MSHR竞争导致的demand stall次数。

• 预取引起的Cache驱逐次数。

这些计数器不仅用于调试预取器硬件，也被性能分析工具（如Intel VTune、AMD uProf）用来帮助程序员优化代码——例如，通过观察预取精度计数器来决定是否需要插入软件预取指令或调整数据结构布局。

设计权衡 5 — 预取技术的20年发展回顾与展望

回顾从2005年到2025年的预取技术发展，可以观察到几个重要的趋势：

（1）从单一预取器到多级组合。早期处理器只有一个简单的流预取器，现代处理器则部署了5$\sim$8个不同类型的预取器。这种组合策略的收益已经接近上限——继续增加更多预取器的边际收益在递减。

（2）从规则模式到不规则模式。早期的预取器只能处理顺序和步幅模式，SMS（2006年）开始处理空间模式，ISB（2013年）和STMS处理时间模式，Voyager（2022年）开始使用ML处理任意模式。预取器的“表达能力”在不断增强。

（3）从固定策略到自适应策略。早期的预取器使用固定的参数（如固定的预取深度），FDP（2007年）引入了自适应节流，BOP（2016年）实现了自适应偏移选择。自适应能力使预取器能够在不同工作负载和执行阶段之间自动调整。

（4）从片上到近数据。随着3D堆叠和CXL技术的发展，预取器可能从处理器核心上移到内存控制器中（Near-Data Prefetching），利用更接近数据的位置来减少预取延迟和带宽消耗。

展望2030年代，预取技术的最大挑战可能不再是“预测什么地址”，而是“如何在有限的带宽和功耗预算下最有效地利用预取”——这是一个系统级的资源分配问题，而非纯粹的模式识别问题。这一挑战与第 48.0 章中讨论的DRAM带宽约束直接相关——预取器消耗的每一比特带宽都来自与demand请求共享的有限通道，预取效果的上限最终由内存子系统的带宽决定。

本章讨论了预取器如何通过“预测数据访问模式”来主动填充Cache。但预取只是内存层次结构优化技术的一环——下一章（第 8.0 章）将讨论内存层次结构中的另一个关键优化方向：非阻塞Cache和MSHR机制如何在Cache缺失时保持处理器的执行进度。预取和非阻塞Cache的结合体现了一个统一的设计哲学：前者通过预测来减少Cache缺失的数量，后者通过并行来减少每次缺失的代价。两者共同逼近了“所有数据访问都在L1命中”这一理想极限。