计算机体系结构 · 第12课

分支预测与前端投机:预测Taken,为什么CPU仍可能取不到下一条指令?

2026年10月31日|第2周第5课|约18分钟

承接第11课: Load可以在Store地址未知时预测没有依赖,之后检测并Replay。分支也面临类似矛盾:条件结果还未知,前端却不能一直等待。今天研究方向、目标、历史、恢复、性能五个彼此独立的环节。

一、动机:怎样让流水线不断粮?(约2分钟)

考虑一个按程序顺序执行的循环:

loop:
    ADD  s0, s0, a0
    ADDI a0, a0, -1
    BNE  a0, zero, loop
    ADDI t0, s0, 1       # 退出后的下一条

如果处理器必须等待BNE的寄存器值到达、比较完成并算出下一PC后才继续Fetch,取指就会空等若干周期。对取指宽度为4或8的前端来说,每个气泡都可能丢失多个取指机会;ROB现有独立指令也会逐渐耗尽。

但预测Taken并不等于知道下一PC。一条条件分支至少涉及两项信息:

  • 方向:走Taken还是Not Taken?若Not Taken,通常选择该指令的Fall-through PC。
  • 目标:若Taken,取哪个地址?直接分支可以在较晚阶段由立即数计算;间接跳转还需要寄存器或目标预测。

方向可能正确,而目标未知或预测错误。正确的性能统计因此不能只看“方向准确率”。

flowchart TD
    PC["当前Fetch PC"] --> DIR["方向预测:BHT/PHT"]
    PC --> TAR["目标预测:BTB"]
    PC --> RAS["返回预测:RAS(若适用)"]
    DIR --> DEC{"Taken?"}
    TAR --> DEC
    RAS --> DEC
    DEC -->|N| F["Fall-through PC"]
    DEC -->|T且目标有效| T["Target PC"]
    DEC -->|目标缺失| L["稍晚计算目标/前端重定向"]
    F --> FETCH["继续Fetch与Decode"]
    T --> FETCH
    FETCH --> EX["分支最终Execute解析"]
    EX --> CHECK{"方向和目标均正确?"}
    CHECK -->|是| KEEP["保留正确路径"]
    CHECK -->|否| REPAIR["Squash错误年轻指令、恢复GHR/RAT、Redirect"]

[交互动画标记:Branch-Predictor-Timeline]:依次观察Fetch PC、方向/目标预测、错误路径进入ROB、分支解析和Redirect。注意错误路径上的Execute不等于已Commit。

二、两位饱和计数器:为什么只记上一次结果不够?(约2分钟)

最简单的1位BHT记录一条分支上次是T还是N。一个多数迭代Taken、退出时Not Taken的循环,在退出时误预测后,下一次重新进入循环也可能因为记住了N而再次误预测。两位计数器通过滞后(hysteresis)避免一次反向结果就立刻改变预测方向。

令计数状态 (c\in{0,1,2,3}),真实结果 (y=1) 代表T,(y=0) 代表N:

状态 二进制 解释 预测
0 00 强不跳 SN N
1 01 弱不跳 WN N
2 10 弱跳 WT T
3 11 强跳 ST T

[ \widehat y=\mathbf1[c\ge2],\qquad c’=\min\bigl(3,\max(0,c+2y-1)\bigr). ]

即T使计数+1、N使计数−1,超出边界则饱和。先用旧状态预测,再按真实结果更新。

真实T:00 → 01 → 10 → 11 → 11
真实N:11 → 10 → 01 → 00 → 00
预测N:00 / 01       预测T:10 / 11

完整数值例:初始00,真实序列为T、T、T、N、N:

次数 预测前状态 预测 真实 方向错误? 更新后
1 00 N T 是 01
2 01 N T 是 10
3 10 T T 否 11
4 11 T N 是 10
5 10 T N 是 01

当循环长期T、退出一次N且前一状态为11时,退出会误预测一次,状态降为10但仍预测T;下次进入循环首个T可预测正确。然而这需要同一表项不被其他分支干扰、状态保持并且循环足够长等前提,不是所有循环永远只错一次。

反例:严格交替T、N的分支可能让局部两位计数器表现很差;一个拥有足够相关历史的预测器却可能学习到交替规律。两位计数器只是对局部趋势增加惯性,并非万能规律识别器。

三、BHT、BTB、RAS分别回答什么?(约2分钟)

BHT(Branch History Table)/ PHT(Pattern History Table)常通过PC、历史或二者混合索引,输出条件分支的Taken/Not Taken方向。某些设计把BHT和BTB组合,名称不能脱离实现理解。

BTB(Branch Target Buffer)主要保存分支PC和已观察的目标PC、类型等信息,以便在Decode计算真正目标之前帮助下一周期取指。命中BTB仍不保证方向正确;目标也可能过期或有别名冲突。

RAS(Return Address Stack)利用调用栈的规律:CALL保存返回地址,RET多数情况下回到最近的对应调用之后。它能改善返回目标预测,但栈深有限;非成对调用/返回、异常控制流、错误投机和恢复处理可能影响准确性。

特别区分两种失败:

  1. BHT预测Taken正确,但BTB没找到目标;前端可能暂停、取默认路径或稍后重定向。
  2. BTB目标地址本来正确,但BHT预测Not Taken;前端先走Fall-through,仍要恢复。

BOOM实例:RISC-V BOOM的前端采用快速Next-Line Predictor(融合BTB、BIM方向信息和RAS)以及可更复杂、更高容量的Backing Predictor。较快层保证尽量连续取指,更复杂方向预测可在后续阶段修正。具体级数、延迟与更新策略是BOOM实现选择,不能把它写成所有CPU的唯一结构。

四、Bimodal与GShare:两个PC为什么会互相影响?(约2分钟)

只有PC索引的Bimodal计数表不直接使用其他分支的近期结果。若当前分支与之前的分支高度相关,就需要历史。

令长度为 (h) 的GHR(Global History Register)保存最近 (h) 个预测分支结果,最低位表示最近一次。本课教学GShare采用:

[ \operatorname{index}=((PC\gg2)\oplus GHR)\ \&\ (2^h-1). ]

假设指令地址4字节对齐,所以右移2位;实际指令集可能支持压缩指令,取指地址低位和预测器哈希的处理由硬件决定。

历史更新:

[ GHR’=((GHR\ll1)\,|\,y)\ \&\ (2^h-1). ]

独立手算例:当 (h=2)、GHR=10(二进制),PC右移2位后最低两位为01,异或索引为11;若本次预测T,下一次用于取指的投机GHR变为01。这里移入的是预测结果,不是已经Commit的事实。

GShare可以表示一部分跨分支关联,但也有两类不同的缺陷:

  • 索引别名(aliasing):不同PC和历史组合索引同一个计数器,互相污染训练。
  • 历史不足:即使没有表项冲突,若需要依赖更早的分支结果,2位历史也无法表达这段规律。

扩大PHT可以缓解前一问题,但不自动补足历史。盲目加长历史可能引入更大的训练空间、存储和恢复开销。

五、为什么GHR在Fetch投机更新,Checkpoint却要随分支保存?(约2分钟)

宽乱序CPU中,几十条分支可能同时尚未解析。如果所有历史都等到Retire才更新,前端依据的将是很旧的信息,难以利用刚刚预测出来的相关性。

因此GHR常在Fetch预测时投机更新。设某分支A预测前历史为H:

保存 H(A的预测前检查点)
预测 A 为 Taken → 投机移入 1
沿错误路径预测 B、C → GHR继续投机前进
A执行发现实际Not Taken:
  Squash分支A之后的错误路径指令
  恢复GHR = H
  移入A的真实结果0
  从A的正确下一PC继续Fetch

若错误路径B/C的预测位保留,后续正确路径即使PC正确也会用错误历史索引PHT,形成二次错误。

GHR与RAT是两份不同状态:GHR负责预测上下文;RAT/Free List负责真实数据版本与物理寄存器所有权;ROB与分支标签负责确定哪条年轻指令属于错误路径。恢复必须到同一个有效分支边界。

投机更新GHR并不等于立刻训练PHT。 一个设计可以在Fetch投机移入GHR位,同时在Commit阶段才更新方向计数表。BOOM官方文档描述GHR必须及时投机更新,Backing Predictor通常在Commit训练,FTQ保存训练所需元数据;错误路径预测历史在误预测时必须恢复。这是具体微架构策略,不是语言/ISA强制规定所有训练必须只在Commit进行。

六、从误预测率到真正的CPI:推导性能公式(约2分钟)

设 (CPI_0) 为不含额外分支误预测惩罚时的基线CPI,(f_b) 为每退休指令中分支指令比例(branch/instruction),(r_m) 为方向误预测率(mispredict/branch),(P) 为一次误预测额外损失周期。在简化的非重叠、独立固定惩罚模型中:

[ \Delta CPI=f_b r_m P,\qquad CPI\approx CPI_0+\Delta CPI. ]

如果改用MPKI(每千退休指令中的分支误预测次数):

[ MPKI=1000f_b r_m,\quad \Delta CPI=\frac{MPKI}{1000}P. ]

数值例:(CPI_0=0.95)、分支比例20%、方向错误率5%、平均额外惩罚12周期,则:

[ \Delta CPI=0.2\times0.05\times12=0.12,\quad CPI\approx1.07. ]

为什么不是“准确率提升1个百分点就一定更快”? 一方面分支密度和各类失误的关键路径损失可能不同;另一方面复杂预测器可能增加前端访问级数或时钟关键路径。若预测器需要多周期、增加取指气泡,减少错误恢复的收益可能被预测延迟抵消。

还应留意:方向误预测、目标误取指、BTB miss以及前端供给不足可能相互重叠。不能把各自名义周期简单相加;错误路径指令不应算进退休指令分母,却可能占用资源和能量。

七、三个容易混淆的边界与反例(约2分钟)

边界一:方向正确不代表下一PC正确。 一个间接跳转可以不需要条件方向预测,但仍可能因目标预测错误而Redirect。只看条件分支方向准确率会遗漏这种延迟。

边界二:2位比1位更稳健不代表对所有模式更准。 单分支交替T/N、短循环、PHT表项冲突或上下文改变,都可能让2位滞后机制不合适。

边界三:ROB按序退休保证架构正确,不保证错误路径无微架构影响。 Squash能撤销错误路径的架构数据效果,但错误路径访问可能改变Cache/TLB/预测器资源状态,可能形成侧信道;精确异常不是完整安全性证明。

另外,不要把预测器在Commit训练的设计与所有实现混淆:有些预测器在分支解析时训练或做投机训练并提供回滚;只要保证架构正确并正确处理污染与恢复,都属于可讨论的设计空间。

八、一个可复现的预测器验证实验(约1分钟)

为了发现GShare状态恢复bug,至少记录以下事件字段:

Branch PC / 取指顺序
GHR_before(预测前快照)
PHT索引、读取到的旧计数器
预测方向、预测目标/来源
预测后的speculative GHR
解析出的真实方向、目标
Squash/Redirect事件与恢复后的GHR
该分支是否最终Commit
Commit训练使用的原始索引与新计数器

对于一个按Commit训练PHT的教学实现,错误路径分支不得改变最终PHT。对于GHR,每次恢复后应只含正确路径上已知实际结果和允许保留的投机预测结果,不含被Squash分支的位。软件参考模型可按一条事件一条事件复算,发现历史移位顺序或Checkpoint偏一位的问题。

九、总结与下一讲(约1分钟)

Fetch PC
  ├─ 方向:BHT/PHT 或历史相关预测
  ├─ 目标:BTB / 直接目标计算 / 间接目标预测
  └─ Return:可能使用RAS
       ↓
按预测PC继续Fetch,并投机更新GHR
       ↓
Execute解析真实方向与目标
       ├─ 一致:保留正确路径,按设计时机训练
       └─ 错误:Squash年轻指令,恢复RAT/资源/GHR,Redirect
       ↓
ROB按序退休,统计MPKI、CPI和真实运行时间

今天应牢牢记住:方向与目标是两个输出;投机历史不等于已提交训练;内部恢复架构状态不等于没有微架构副作用。

下一讲(第13课,2026年11月1日,第2周第6课):前端与后端如何形成性能上限——Fetch宽度、预测延迟、ROB窗口、分支恢复及LSQ竞争。第14课(11月2日)为第2周复盘,不因测验成绩改变课号。

实现参考(非本课手算数据来源): RISC-V BOOM Branch Prediction · BOOM Next-Line Predictor · BOOM Backing Predictor / GHR / FTQ。


十、四级分级测评(总分100;首次不提供标准答案)

前三题由交互测评客观判分;Lv4需要人工或自评,不能将开放设计伪装为全自动证明。提示可选择展开;标准答案与解析不在本讲义中出现。

Lv1|预测方向与取指目标的区别|15分|单选|预计2分钟

一条条件分支的方向预测器给出Taken,但快速BTB没有可用的目标地址。以下哪种说法最准确?

A. 只要方向预测正确,前端必然已经知道下一条应取的目标PC。

B. 方向与目标是不同信息;目标尚未知时可能需要等待较晚的目标计算或重定向,即使Taken方向预测正确。

C. BTB只预测条件是否成立,与目标地址无关。

D. 只要有ROB,前端下一PC就不需要任何分支目标信息。

可选提示(不泄露答案) 把“是否跳转”和“跳到哪里”写成两个独立输出;考虑立即数目标与间接跳转。

Lv2|两位饱和计数器逐步Trace|20分|数值|预计4分钟

单个条件分支使用独立的2位饱和计数器,编码00强不跳(0)、01弱不跳(1)、10弱跳(2)、11强跳(3);计数≥2预测T,否则预测N;真实T计数+1、真实N计数−1,均在0到3饱和。初始计数01。真实结果依次为T、T、N、N、T、T、T;每次预测后立即按真实结果更新。累计发生多少次方向误预测?只填整数。

填写数值,单位次。

可选提示(不泄露答案) 先写每次预测发生在更新之前;按“旧状态→预测→真实结果→新状态”逐行填表。

Lv3|BHT/BTB、历史恢复与性能边界|25分|多选|预计5分钟

考虑有2位计数器、BTB、全局历史GHR及返回地址栈RAS的可恢复投机处理器。哪些说法在所描述模型中正确?(多选)

A. 两位计数器在强跳状态11遇到一次N后,会立即改为预测N。

B. BHT/PHT可预测条件分支方向,BTB主要提供可用于提前取指的目标信息;具体实现可能将二者组合。

C. 如果GHR按预测结果投机更新,误预测时应恢复正确路径历史,不能保留被冲刷路径的历史位。

D. BTB没有命中,所有微架构都必须将该分支最终预测为Not Taken,且不得使用其他预测层。

E. RAS利用调用/返回的结构规律预测返回目标,但非规范调用返回、溢出及错误投机可影响预测准确率或恢复。

F. 即使方向准确率相同,只要分支频率、预测目标失误或恢复代价不同,对程序CPI的影响仍可能不同。

可选提示(不泄露答案) 分别判断一个反向结果能否立即跨过强状态、历史是否存在错误路径、目标预测是否等同方向预测,并检查性能公式的分母。

Lv4|GShare索引、错误路径历史恢复及Commit训练|40分|开放推导|预计10分钟

一个教学GShare有2位GHR、4项PHT,索引i=((PC»2) XOR GHR)&3;PHT计数编码0/1预测N、2/3预测T,真实T饱和加1、N饱和减1。初始GHR=01(二进制),PHT[0..3]=[01,10,01,10]。约定预测时先以旧GHR索引,随后将预测方向位按GHR’=((GHR«1) bit)&3投机移入;每个分支保存预测前GHR,误预测恢复该快照再移入真实结果。PHT只在真实正确路径分支按程序顺序退休时更新其预测时索引,错误路径不训练。执行次序:(A) PC=0x100预测分支,真实N但暂未揭晓,预测Taken指向0x200;(B) 在错误路径PC=0x204又预测一个条件分支,但它最终被Squash;(C) A解析为N后恢复,并在正确顺序路径PC=0x104预测分支C,C真实T。请完成:①A与B的索引、预测方向及各自预测后的投机GHR(12分);②A误预测时恢复的GHR、恢复后C的索引/预测、C的真实结果移入后的GHR(12分);③A与C退休后PHT[0..3]最终状态,B为何不能训练(10分);④给一条关于错误路径历史与物理寄存器重命名状态分别恢复的必要不变量,并指出“准确率更高但程序更慢”的一个有条件反例(6分)。
可选提示(不泄露答案) 所有索引均用PC>>2的最低两位参与XOR;二进制历史只有两位。严格区分“预测时移入的bit”“真实结果恢复后移入的bit”和“退休时训练计数器”。

作答模板: Lv1:……;Lv2:……;Lv3:字母组合;Lv4:①……②……③……④……。

评分和进度:≥80分继续既定专题;60–79分补一题针对性案例;<60分复习预测与恢复机制后再练。补练不改变后续课号。