预测 taken 的分支实际 not-taken 时，前端如何快速恢复？

Arm 分支预测专利解析 · 04
上一篇：BTB 多分支命中要排序，单分支命中能否走捷径？ · 下一篇：不清空 GHR，如何按历史长度分级阻断 BHI？

专利：US 11,086,629 B2，Misprediction of Predicted Taken Branches in a Data Processing Apparatus
申请人及受让人：Arm Limited
发明人：Yasuo Ishii、Muhammad Umar Farooq、Chris Abernathy
申请号：16/185,073；申请日：2018-11-09；授权日：2021-08-10
原文：Google Patents（授权专利全文） · US 2020/0150967 A1 申请公开 · 授权 PDF

这项专利把一个 subsequent branch status indicator 附在 block 内第一条 predicted-taken conditional branch 上。该分支后来解析为 not-taken 时，前端查看这一位：后面没有 predicted-taken branch，就让预测从顺序后继 block 继续；后面还有 predicted-taken branch，就转向那条后续分支的 target block。

状态位保存的是当前 block 中原本已经生成、却会因第一条 taken prediction 而被丢弃的信息。

1. 第一条 predicted-taken branch 会遮住后面的预测

前端一次为一个 instruction block 中的所有分支并行生成方向预测。假设 block 内有三条分支：

B0：not-taken
B1：taken
B2：taken

B1 是程序序中的第一条 predicted-taken branch。前端选择 B1 的 target 作为下一 fetch 地址，B2 在这条推测路径上不可达，B2 的预测通常不会继续传递。

如果 B1 执行后确实 taken，丢掉 B2 没有影响。如果 B1 实际 not-taken，正确路径会落回 B1 后面的指令，B2 又变成即将遇到的控制流。此时从头重做整个 block 的预测会增加恢复延迟。

专利给 B1 的记录增加一位：

subsequent branch status = 0：B1 后面没有 predicted-taken branch
subsequent branch status = 1：B1 后面至少还有一条 predicted-taken branch

位值的编码可以反过来；授权 Claim 1 只要求 first value 和 second value，Claim 3 才明确 status indicator 可以是 1 bit。

2. Fig. 3：0x110 的 BEQ 后面没有 taken prediction

Fig. 3A 使用一个从 0x100 开始、32B 对齐的 instruction block：

地址 指令 方向预测
0x100 LDR -
0x104 CBZ NT
0x108 STR -
0x10C NOP -
0x110 BEQ T，block 内第一条 predicted taken
0x114 ADD -
0x118 BNE NT
0x11C BGT NT

下一 block 从 0x120 开始。Fig. 3B 为 0x110 BEQ 建立 predicted-taken entry，并写入：

PREDICTED TAKEN FOLLOWS IN BLOCK = 0
BRANCH TARGET INFO = --

Fig. 3A/3B：0x110 BEQ 为第一条 taken prediction，后续 BNE/BGT 均预测 not-taken

若 0x110 BEQ 后来解析为 not-taken，0x114-0x11C 继续顺序执行，预测器从 0x120 block 开始继续生成后续预测。status=0 已经说明当前 block 余下部分没有另一条 taken redirect，无需重新搜索一个本来就不存在的后续 target。

3. status=1 时，恢复目标从哪里来

后续状态为 1 只说明“后面还有 predicted-taken branch”，没有编码 target address。说明书给出三种 target 信息保存方式：

  1. 在 predicted-taken branch storage 中直接保存后续分支的 target；
  2. 保存足够重建 target 的信息；
  3. 保存 target 在 BTB 中的位置，例如 index/way。

64 位系统的一个示例需要保存 49-bit virtual address 及其位置，直接复制完整 target 的存储成本不低。若 index 能从 branch address 计算，表项只保存 BTB way 即可。

target 已缓存时，B1 误预测后可直接把 fetch 重定向到 block 内第一条后续 predicted-taken branch 的 target block。只有 1-bit、没有 target 信息时，前端把 mispredicted branch 的后继地址及顺序地址推入 fetch address queue，重新预测 block 余下部分，随后再把后续分支 target 推入队列。

所以这项方案有两档恢复能力：

保存内容 B1 实际 not-taken 后的动作
status bit + 后续 target 信息 直接转到后续 predicted-taken branch 的 target block
只有 status bit 已知余下部分存在 taken redirect，重新预测余下部分以恢复 target

4. Fig. 4：是否缓存后续 target 由 confidence 控制

Fig. 4 中，branch prediction generator 80 包含 global history buffer 84 和 prediction confidence generator 86。predicted taken branch control 82 内部有 table 88：每项保存第一条 PTB、后续 PTB 状态以及可选 target 信息。target storage control 90 根据 threshold 92 决定要不要为后续 PTB 保留 target。

Fig. 4：prediction confidence 与 target storage control 决定是否保存后续分支 target

专利采用的策略是：

  • 第一条 PTB 的 confidence 不高于阈值：保存后续 PTB target，因为第一条分支更可能误预测；
  • confidence 高于阈值：阻止保存后续 target，把容量留给更可能用到的记录；
  • unconditional branch 可直接视为高 confidence；
  • 多线程实现还可以结合执行 agent 或 thread priority，高优先级线程更积极地保留恢复 target。

status bit 仍可保留，受 confidence 控制的是更昂贵的后续 target 信息。Claim 5-8 覆盖 confidence threshold，Claim 9-11 覆盖 agent/thread priority。

5. Fig. 5：32B block pair 中的具体恢复地址

实施例一次为两个相邻 32B block 生成预测，形成 64B prediction pair：

0x100 + 0x120：一组 prediction pair
0x140 + 0x160：下一组 prediction pair

Fig. 5 的 BEQ 位于 0x170，预测 taken 到 0x228。0x228 属于从 0x220 开始的 32B block，因此新的 prediction pair 从 0x220 + 0x240 开始。

Fig. 5：0x170 BEQ 预测跳到 0x228，目标落在以 0x220 开始的 block

若 0x170 BEQ 实际 not-taken，正确执行应回到 BEQ 的顺序后继。缺少后续分支状态时，按 64B prediction-pair 对齐重新启动可能退回 0x140，重复生成已经算过的预测。保存状态后，前端先判断 0x170 后面是否存在另一条 predicted-taken branch：

  • 没有：当前 pair 的余下控制流可按顺序推进；
  • 有且 target 已保存：直接跳到该后续分支的 target block；
  • 有但 target 未保存：从 BEQ 后继地址重新预测余下部分，取回 target。

这个例子中的 32B block 来自 Claim 15，两个 block 一起预测来自 Claim 12。Claim 1 本身没有限定 block 大小，也没有要求一定成对处理。

6. Fig. 6：状态位在预测时如何生成

Fig. 6 给出完整决策：

  1. step 100 取下一 block；
  2. step 102 判断 block 内是否有分支；
  3. step 106 判断是否存在 predicted-taken branch；
  4. step 108 检查第一条 PTB 后面是否还有 PTB；
  5. 没有后续 PTB：step 110 把第一条 PTB 标为 NO；
  6. 有后续 PTB：step 114 标为 YES；
  7. step 116 检查第一条 PTB 的 confidence；
  8. confidence 不高于阈值：step 118 把后续 PTB target 放入 branch target storage；
  9. 下一预测 block 由第一条 PTB 的 target 决定。

Fig. 6：找到第一条 predicted-taken branch 后，记录后面是否还有 taken prediction

这张图也说明一个范围边界：状态针对“第一条 predicted-taken branch 之后、同一 block 内”的分支。跨 block 的分支不计入该 bit。

7. Fig. 7：误预测后的两条恢复路径

branch resolution unit 返回结果后，predicted taken branch control 查询对应 entry：

  1. step 150 确认该分支是否 predicted taken、实际 not-taken；
  2. 没有这类误预测：step 152 把 entry 标为 complete/invalid；
  3. 发生误预测：step 154 读取后续 PTB 标志；
  4. 标志为 NO：step 156 把 fetch/prediction 重定向到顺序后继 block；
  5. 标志为 YES：step 158 重定向到 block 内第一条后续 PTB 的 target block；
  6. 恢复动作发出后，step 160 使原 entry 完成并失效。

Fig. 7：status=NO 走顺序后继，status=YES 走后续 predicted-taken branch 的 target

Fig. 7 的 step 158 表示目标可用时的直接重定向。说明书同时保留了只有 1-bit 的实现；该实现先把 mispredicted branch 后继地址送回预测队列，再恢复后续 target。

8. 授权 Claim 1-17 覆盖什么

Claim 1-3：状态位与两条恢复路径

Claim 1 要求 instruction fetch circuitry 为一个 block 取指，branch prediction circuitry 为 block 内每条 branch 生成预测，并在识别第一条 predicted-taken conditional branch 后修改其 prediction indication，加入 subsequent-branch status。后面存在 predicted-taken branch 时用 first value，否则用 second value。

Claim 2 写入恢复动作：第一条分支解析为 not-taken 后，second value 从顺序后继 block 继续，first value 从后续 branch 指向的 target block 继续。Claim 3 明确状态可采用 1 bit。

Claim 4-11：后续 target 的选择性保存

  • Claim 4：把后续 predicted-taken branch 的 target 放入 branch target storage；
  • Claim 5-7：根据第一条分支的 confidence 决定保存，低 confidence 保存，高 confidence 不保存；
  • Claim 8：unconditional branch 可生成高于阈值的 confidence；
  • Claim 9-10：target 保存取决于执行 agent 的相对优先级，agent 可以是多线程环境中的 thread；
  • Claim 11：thread priority 参与 confidence 生成，低于阈值时保存 target。

Claim 12-17：block 组织与不同权利要求形式

  • Claim 12：instruction fetch 一次处理一对 block；
  • Claim 13：一个周期内为 block 中每条 branch 生成预测；
  • Claim 14-15：block 按固定字节边界对齐，具体可为 32B；
  • Claim 16：方法权利要求；
  • Claim 17：means-plus-function 装置权利要求。

专利一共 17 项授权 Claim。Fig. 4 的 GHB、Fig. 5 的地址序列和 49-bit virtual address 都是说明书实施例，不是 Claim 1 的固定数值。

9. 实现时要注意的三个区别

status bit 不等于 target

状态为 1 只确认存在后续 taken prediction。直接跳到 target 还需要完整地址、可重建信息或 BTB index/way。仅保存 1 bit 的实现仍会重跑 block 余下部分，但能提前选择正确恢复流程。

顺序恢复以 block 为预测单位

0x110 BEQ 实际 not-taken 后，处理器仍执行 0x114-0x11C。status=0 让 branch prediction 从 0x120 的下一 block 继续，含义不是跳过当前 block 的剩余指令。

保存后续 target 有容量成本

第一条 PTB 大多预测正确时，后续 target 很少被使用。confidence threshold 和 thread priority 用来把存储留给误预测概率更高或服务等级更高的情形。

结语

前端已经为一个 block 的所有分支生成过方向预测。第一条 predicted-taken branch 让程序流提前离开 block，后面的预测因此被遮住。这项专利把“后面是否还有 predicted-taken branch”附到第一条分支的记录中，并可选择保存后续 target。

第一条分支实际 not-taken 时，状态 0 选择顺序后继 block，状态 1 选择后续 taken 分支的 target 路径。目标已经缓存时可以直接 redirect；只保存一位时则重新预测 block 余下部分。恢复决策不再从空白状态开始。

原文与文件