按指令位置学习步长的预取预测

形式陈述

同一条加载指令在循环中先访问块 1，再访问块 3、5。若这个规律继续，下次很可能需要块 7。预取器可以先提出这个地址，让缓存趁当前计算尚未结束时去取。但“最近两次步长相同”并不能证明下一次一定如此，因此接口应先给出提示，再由独立的缓存机制决定是否接收。

设可访问内存恰有 $B\ge1$ 个块，每块 $K$ 个四字节字。合法真实观察由指令字节地址 $p$ 和数据字节地址 $a$ 组成，二者四字节对齐； $0\le p\le2^{32}-4$ ， $0\le a<4BK\le2^{32}$ 。根据地址的块与偏移分解，数据块号为 $b=\lfloor a/(4K)\rfloor$ ，指令字地址为 $u=p/4$ 。

预测表有 $E$ 个直接映射槽， $E$ 是正的二次幂，槽号为 $u\bmod E$ 。每项保存完整指令字地址 $u$ 、上次观察到的块 $b_{\rm old}$ 、有符号步长 $d$ 和饱和证据计数 $c\in\{0,1,2,3\}$ 。完整 PC 用于识别冲突，不能只记索引。选择阈值 $\theta\in\{2,3\}$ 和最大提示数量 $D\ge1$ 。

observe(p,a) 先完整验证输入，再按下述转移返回一个块号元组：

槽空或完整 PC 不同：覆盖为 $(u,b,0,0)$ ，返回空提示
PC 相同而 $b=b_{\rm old}$ ：状态不变，返回空提示。同一块内换字也属于此分支
其余情况令 $\delta=b-b_{\rm old}\ne0$ 。若 $\delta=d$ ，令 $c'=\min(3,c+1)$ ；否则令 $c'=1$ 。写回 $(u,b,\delta,c')$
若 $c'<\theta$ ，返回空；否则按 $i=1,\ldots,D$ 的顺序，返回其中满足域限制的块号 $b+i\delta$ ，即 $0\le b+i\delta<B$

这是一份明确的计数教学变体。Chen–Baer 的原始 RPT 使用 initial、transient、steady、no-prediction 四状态，且某些错误转移会保留旧步长；它不是这里的饱和证据计数器。本文没有实现原论文的 lookahead PC、跨循环关联器或它的全部预取发出规则。

能证明的是条件命题。对同一 PC，从最近一次分配以后，先把连续的同块观察压成一次，得到不同相邻块的序列 $b_0,b_1,\ldots$ 。若没有表冲突，当前末尾已有至少 $\theta$ 个相同非零差值 $d$ ，本接口会达到提示阈值。再假定未来相应的不同块观察确实继续以 $d$ 推进，则每个返回的 $b_j+id$ 恰是第 $i$ 个这样的未来块。这个未来前提不可由计数值推出；提示不携带命中概率、正确性认证或加载完成承诺。

直觉

为什么按 PC 分组，而不只对整个访问流求相邻差？一个循环可能交替读两个数组，例如一条指令走块 $1,3,5$ ，另一条走块 $40,41,42$ 。混在一起的差值是 $39,-37,38,-36,\ldots$ ，把同一条指令的历史分开才能看见两种各自稳定的步长。

步长表按PC保存块序列与饱和计数，达到阈值后发出提示，提示经过独立缓存接收后才可能成为驻留数据 — 历史证据、地址提示和真实填充是三个阶段

完整 PC 标记防止一个简单的索引冲突冒充同一条指令。比如 $E=4$ 时， $p=0x100$ 与 $p=0x110$ 都落在槽 0，却分别对应字地址 $0x40$ 、 $0x44$ 。第二条指令第一次出现应冷启动；若忽略标记，它会借用第一条指令的步长和计数。

计数的精确含义也能归纳。冷启动时没有非零差值，计数为零。第一个非零差值建立长度一的相同差值后缀。后续差值相同，后缀增长一，存储值饱和在三；差值不同，后缀重新从一开始。同块重复不改变压缩后的序列。因此 $c$ 等于当前相同非零差值后缀长度与三的较小者。达到阈值只证明过去有这些证据。

给定未来仍按 $d$ 推进这个额外条件，再对未来步数 $i$ 归纳，便得到 $b_{j+i}=b_j+id$ ；域检查保留的每个值也因此是合法未来块。若规律在第三次刚好结束，所有历史条件仍然成立，未来结论却不再可用。这不是预测器违反合同，而是条件命题的前提消失了。

例子与边界

取 $B=16,K=4,E=4,\theta=2,D=2$ 。持续观察 PC 0x100，只列数据块号，得到：

本次块	写回步长	计数	返回提示
1	0	0	无
3	2	1	无
5	2	2	7、9
5	2	2	无，状态不变
7	2	3	9、11
2	−5	1	无
4	2	1	无
6	2	2	8、10

第六行是一次相位变化。虽然前一行计数已饱和，真实下一块仍可以突然变成 2。原有提示 9、11 此刻没有理由继续被视为可靠。

下降流也完全合法。例如阈值二、次数二、块序列 $7,5,3$ 得到步长 $-2$ ，候选为 $1,-1$ ，只返回块 1。取 $B=8$ ，上升序列 $3,5,7$ 的两个候选都越界，返回空元组而保留已学历史。这里不对地址作 32 位回绕，因为回绕会把越界猜测伪装成另一合法块。

重复同块被压缩，因而不能把这个模型误读成字节步长识别器。依次读同一行的字 0、1、2、3 时，数据字节地址虽然每次加四，本页只看到同块重复，不发提示。跨行以后才形成块序列。真正按字节地址学习步长的预取器有另一种分辨率与触发频率。

表冲突会忘记规律，但完整标记保证不会把别人的历史当成本人的证据。直接映射不是唯一选择，可以改成组相联或更复杂的历史关联；那会增加替换、容量和训练规则，不属于本接口的隐含保证。

推论与应用

参考程序把 StridePredictor 与缓存对象分开。observe 只改预测表并返回块号，不读内存、不创建 MSHR。issue_hints(cache, blocks) 则把选中的合法块首字作为 origin='prefetch' 的普通读取交给非阻塞缓存接口；每条提示可能 HIT、MERGE、MISS 或 RETRY；消费者也接受 BeatCache，若所需首字已在尚未完成的填充缓冲中，则返回 FORWARD。该消费者不训练预测器，也不凭一个提示直接生成数据值。

如果是 MISS，真实填充仍要随后由驱动器完成。需求读取遇到尚未完成的同块预取，若所需字尚未到达，就只能申请合并，目标列表满时重试；逐字模式中该字已到时可以 FORWARD，但两者都不能被记成整行已驻留的 HIT。即使预取结果最终被调用者丢弃，它也付过目标、事务、路和传输的成本；预测为错不会改变只读返回值的正确性，却可能使有用数据更晚到达。

两个可复现实验说明这种区别。共同采用 $K=1,S=2$ 、阈值二、每次最多一个提示，并额外规定：每次发出的填充都在下一次需求读取前完成。这是给预取充分提前量的事件调度，不是测出的周期性能。

规则流。 每组两路，依次需求块 $0,1,\ldots,7$ ，域恰为八块。不开预取，八次需求全 MISS，共八次填充。开预取后，前三次需求仍 MISS；从块 2 学到两次 $+1$ 后，提示块 3，之后同样逐步推进。后五次需求为 HIT，总填充仍为八次。这里只改变需求等待发生的位置，没有凭空省掉必需的下层数据。
污染流。 每组一路，需求块 $0,2,4,4$ 。不开预取，前三次 MISS，最后一次 HIT，共三次填充。开预取时，读完块 4 后发出的块 6 与块 4 同组，填充会逐出块 4；紧接着再次需要块 4，反而再次 MISS。需求四次全 MISS，加上块 6 的预取，共五次填充。两次访问同一块 4 不会再次训练一个虚假的零步长。

两项实验使用同一正确缓存协议，效果却相反。不能从第一项的五次需求命中推出“一般会更快”，也不能忽略第二项多出的带宽和替换。

预测表初始化为 $O(E)$ 时间与空间。按可容纳地址、块号和有符号差值的机器字计，一次观察及转移为 $O(1)$ ，枚举最多 $D$ 个候选需 $O(D)$ 时间和至多 $O(D)$ 输出空间。槽中固定保存四个字段，二位的是计数，绝不是整个表项；完整 PC、上次块号和步长都要收费。Python 精确整数避免溢出，位复杂度随配置整数的长度计算。

消费者还要支付每条真正调用 read 的缓存事件成本，并为新 MISS 支付完整填充成本；它不是 $O(D)$ 生成提示以后就能免费把这些块放进缓存。参考批次先验证所有块号，因此非法后项不会在报错前偷偷发出前面的有效项；合法批次中的资源 RETRY 则各自独立返回，不承诺整批接收或整批回退。

六项终点任务分别提交提示、接收和完成日志，保留明确的计数分母。这个拆分让预测技巧可以更换，而“任何实际返回值都必须有正确数据来源”的缓存合同保持稳定。

参考资料

Tien-Fu Chen and Jean-Loup Baer, “Effective Hardware-Based Data Prefetching for High-Performance Processors,” IEEE Transactions on Computers 44(5), 1995, pp.609–623：作者提供的原文。§III.B 的 PC 索引 RPT、地址和步长字段、四状态机；§III.C 讨论预取时机与 lookahead PC。本文采用块粒度与另行定义的饱和计数规则，不转述原实验结果为本程序性能。
gem5 项目，Classic Caches 官方文档。未决请求资源提供独立的缓存侧背景；本页没有复制 gem5 的预取实现。

形式陈述 ​

反向链接

形式陈述