分支预测与恢复：猜错以后怎样取消副作用

五级流水线在 EX 才比较分支操作数。此时 IF 和 ID 已经处理了更年轻的指令。若取指必须一直等到比较完成，取指速率会下降；预测允许先选择一个后继地址，但必须能够撤销错误路径上的操作。

中心问题包含两个部分：怎样给出预测，以及预测错误时哪些状态必须恢复。本篇使用静态不跳转和标准两位饱和计数器，对固定结果序列计算误预测次数，再执行带错误路径 store 的 .hex。证据等级为“手算”和“教学时序模型”；没有测量真实芯片的分支预测率，也不声称复现某款商业预测器。

方向与目标是两份不同的信息

预测方向回答是否跳转，预测目标回答跳到哪里。知道“会跳转”但不知道目标 PC，仍然不能从正确位置取指。直接条件分支的目标可以从指令 PC 与立即数算出；间接跳转需要的目标则可能来自寄存器或内存中的运行时值。

本模型只支持 beq/bne/blt/bge，IF 取得指令字后就解码 B-immediate，以原始分支 PC 加偏移得到候选目标。预测为不跳转时选择 PC+4。这样无需建立 BTB，就能单独观察方向预测；它没有模拟实际前端得到指令字、识别分支和查预测表的组合延迟。

BTB 通常缓存分支地址对应的目标信息。若要研究容量、索引冲突或目标未命中，必须把查表结果和目标可用时间加入模型。不能把本实验的“目标总能从指令直接算出”写成真实 CPU 的普遍性质。间接跳转、返回地址栈与压缩指令也不在本篇支持范围内。

两位状态提供一次反向结果的缓冲

静态不跳转每次都选择顺序地址。两位饱和计数器有 0、1、2、3 四个状态，0/1 预测不跳转，2/3 预测跳转。实际跳转则加一，不跳转则减一，数值在两端饱和。

原状态 本次预测 实际 N 后 实际 T 后
0，强不跳转 N 0 1
1，弱不跳转 N 0 2
2，弱跳转 T 1 3
3，强跳转 T 2 3

这里按分支 PC 保存一个计数器，每项初始为 1，没有容量上限和别名冲突。预测读取更新前的状态，分支在 EX 确定实际结果后才更新。这个更新时点属于本模型；更深的乱序前端还要处理多条未决分支及投机历史恢复。

BOOM 的后备预测器文档解释了两位状态以及为存储实现调整状态转移的方法。BOOM 的某些弱状态遇到反向结果时采用不同的转移，以适配 SRAM 组织。因此本篇四行表明确称为“标准饱和计数器”，不能把它当作 BOOM 源码逐行复现。

固定序列必须连同初始状态一起给出

令同一 PC 的实际结果依次为 T T T N T T T N，每四次中最后一次退出。标准计数器从弱不跳转 1 开始，逐步结果为：

次序 实际 更新前状态 预测 更新后状态 是否错误
1 T 1 N 2 是
2 T 2 T 3 否
3 T 3 T 3 否
4 N 3 T 2 是
5 T 2 T 3 否
6 T 3 T 3 否
7 T 3 T 3 否
8 N 3 T 2 是

静态不跳转错六次，两位计数器错三次。第 4 次的 N 把状态从 3 降到 2，下一次仍预测 T，这就是本序列中保留方向倾向的作用。若初始为强不跳转 0，开头可能连续错两次；如果序列以 N 为主，静态策略也可能更好。离开实际结果串、初始状态、索引方法和更新时点，单独的“准确率”没有可复现含义。

手算表与脚本每步状态共同保存在 prediction-transitions.txt。它是一组预测器输入，不是从真实 CPU 采集的 branch trace。

误预测时，PC 和有效位必须一起改变

本模型在 EX 比较实际 next_pc 与取指时保存的 prediction。相等则继续；不相等则把取指 PC 改为正确后继，取消 ID 包，并取消当拍的 IF 机会。下一拍开始取正确路径。

只修改 PC 不够。已经进入 ID 的年轻指令若继续向下执行，仍可能写寄存器或内存。反过来，只把 ID 清空却不改 PC，也会继续沿错误地址取指。每个阶段携带的有效状态决定后续写使能是否能够生效。

错误路径案例是：

1
2
3
4
5
addi x1, x0, 9
beq  x1, x1, +12
sw   x1, 160(x0)
addi x3, x0, 99
addi x3, x0, 7

内存 160 预先置为 123。分支从 PC=4 跳到 PC=16；PC=8 的 store 和 PC=12 的 addi 都不应提交。静态不跳转时，store 确实在第三拍 IF 被取入，第四拍到 ID；同拍分支在 EX 发现预测错误，把它取消。PC=12 那条在该拍的 IF 机会被取消，并没有形成有效 Packet。

执行后的 mem160=123、x3=7，提交中没有错误路径的两条指令。详细记录见 flush-stages.txt 与 flush-commits.txt。另一个 flush_fault 案例把无效指令字放在错误路径，验证它会被取消而不形成架构错误。

这个正确性依据依赖顺序五级的年龄关系：分支在 EX 决议时，较年轻 store 最多在 ID，不会已经到 MEM 写入。更深流水线、提前执行的 store 或乱序设计需要缓冲与提交机制；不能把“清空 ID 即可”直接移植过去。

预测次数、恢复代价与总周期

累计求和循环在 PC=28 的分支结果为 T T T T N。默认静态不跳转错四次，两位计数器从 1 起步错两次。该程序共有 29 条提交指令、五个 load-use 气泡；每次误预测在本模型中损失两个取指机会，因此：

1
2
静态：29 + 4 + 5 + 4×2 = 46 拍
两位：29 + 4 + 5 + 2×2 = 42 拍

对照产物见 sum-prediction-comparison.txt。flushed 计已经存在而被取消的 ID 包，不能把这个数量当作丢失周期：当拍 IF 被取消时尚无动态包，仍损失取指机会。对于短程序、末尾、其他停顿重叠的情况，也应直接读取阶段表，不把罚时公式无条件套用。

若方向判断更晚，误预测可能需要清除更多年轻工作；若正确路径取指又受缓存或端口阻塞，恢复时间还会变化。预测准确率相同，并不保证执行时间相同。

复跑与验收

下载 pipeline-lab.zip，解压后运行：

1
2
3
4
python3 examples/computer-architecture/pipeline/src/verify.py
python3 examples/computer-architecture/pipeline/src/run.py \
  examples/computer-architecture/base/programs/sum.hex \
  --two-bit --cycles /tmp/sum-prediction.jsonl

verification.json 包含七种配置的完整差分验收范围。模型独立读取 .hex，C 参考只参与逐提交比较。预测器没有接受 C 的预先结果串来决定当前跳转；分支实际条件由 EX 使用真实寄存器操作数计算。

练习一：把固定序列初始状态改为 0，按同一张转移表重新计算。前两次 T 均预测 N，最终共四次错误；饱和到 3 以后的行为与原例相同。

练习二：如果把分支决议从 EX 移到 MEM，错误路径 store 可能处于什么阶段？应重新列出所有较年轻阶段，检查数据写入的时点，不能只修改恢复周期常量。此题验收的是恢复边界与副作用顺序，不要求当前代码已实现延迟决议。

本篇验收要求逐项复算预测状态、区分方向与目标、定位错误路径指令首次被取消的拍，并证明错误路径没有寄存器或内存提交。硬件预测表容量、BTB 延迟、投机缓存副作用以及侧信道仍未验证；架构结果恢复并不等于所有微架构痕迹都被清除。

阅读衔接

前一篇：计算机体系结构 10：数据与结构冒险。

参考资料

  • BOOM: The Backing Predictor：预测器组织、两位状态的实现差异与恢复背景。
  • BOOM: Execution Stages：执行阶段分支解析与重定向机制，不能用于证明本文模型等价于 BOOM。
  • RISC-V RV32I，Version 2.1：条件分支比较与 PC 相对目标语义。
  • 附件的 predictor.py、core.py 和执行记录：标准转移表、具体计数与副作用取消证据。