1 / 4概念
Branch Prediction
分支结果要到流水线后段才能算出,取指单元却不能等。分支预测用历史信息提前猜出方向和目标,让前端持续供指。现代深流水线一次预测错误要清空十几个周期的工作,因此预测准确率直接决定前端有效带宽。读完应能区分方向预测与目标预测,读懂 BHT、BTB、TAGE 与 RAS 的分工。
1 概念
1.1 一句话定义
分支预测是前端根据 PC 与历史信息,在分支执行前猜测它是否跳转、跳到哪里,并沿预测路径继续取指的机制。
1.2 它解决什么问题
- 控制依赖:分支结果在流水线后段才解析,前端不能停下来等。
- 流水线深度:现代核有 10–20 级流水,等待一次分支要停十几个周期。
- 取指带宽:每个周期要取够多条指令,预测错则整条前端空转。
- 间接跳转:函数指针、虚调用与返回地址的目标不固定,单靠 PC 无法确定。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 推测执行的状态恢复与清空 | Speculative Execution |
| 异常与中断的处理 | Pipeline Hazards and Exceptions |
| 编译器分支布局与 if-conversion | Compiler-ISA Contract |
| 分支预测侧信道攻击 | Speculative Execution |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| BHT | 分支历史表,存方向预测状态 | 不存目标地址 |
| BTB | 分支目标缓冲,PC 到目标的缓存 | 不决定跳不跳 |
| 2-bit 计数器 | 四状态饱和计数器 | 两次相反结果才翻转 |
| GHR | 全局历史寄存器,记录最近分支结果 | 不是通用寄存器 |
| gshare | PC 与 GHR 异或后索引 | 一种索引方式,不是独立结构 |
| TAGE | 多张不同历史长度的预测表 | 不是单一 BHT |
| RAS | 返回地址栈,预测 ret 目标 | 与调用深度绑定 |
2 机制
2.1 心智模型
预测器回答两个问题:跳不跳,跳去哪。 方向由历史计数器回答,目标由 BTB 或间接预测器回答,返回地址由 RAS 回答。三者命中得越早,前端越不会断流。
2.2 机制拆解
- 2-bit 饱和计数器:状态为强不跳、弱不跳、弱跳、强跳;命中则加强,未命中则减弱,两次相反结果才翻转。
- 双模态预测:用 PC 低位索引 BHT,实现简单,但对与历史相关的分支无能为力。
- 全局历史:GHR 记录最近若干分支的结果;gshare 用 PC 与 GHR 异或索引,捕捉分支之间的相关性。
- TAGE:多张表使用不同长度的历史,选择命中的最长历史;usefulness 计数器抑制被污染的长历史项。
- BTB 与 RAS:BTB 以 PC 索引目标,组相联;RAS 在
call时压栈、ret时弹出,深度通常为 16–64。 - 间接跳转:ITTAGE 或多目标 BTB 按历史选择目标,虚调用与 switch 是主要来源。
- 解析与更新:分支在执行级算出真实方向与目标,比较预测;错误则重定向 PC、清空前端并更新预测器。
2.3 完整枚举
| 结构 | 索引依据 | 保存状态 | 解决的问题 | 典型代价 |
|---|---|---|---|---|
| 双模态 BHT | PC 低位 | 2-bit 计数器 | 局部方向 | 表项少时别名多 |
| gshare | PC 异或 GHR | 2-bit 计数器 | 全局相关 | 历史长度固定 |
| 局部历史 | PC 加局部历史 | 计数器或历史 | 规律性强的分支 | 需两级表 |
| TAGE | PC 加不同长度历史 | 带标签的计数器 | 多尺度相关 | 面积与功耗 |
| BTB | PC | 目标地址与类型 | 目标地址 | 相联度与别名 |
| RAS | 栈顶 | 返回地址 | ret 目标 | 深度有限 |
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| BHT 表项 | 4K–64K | 越大别名越少,但访问越慢 |
| 历史长度 | 8–1000 bit | TAGE 用几何级数覆盖多尺度 |
| TAGE 表数 | 4–12 | 每张表历史长度不同 |
| BTB 表项 | 512–4K | 组相联,常与 BHT 并行访问 |
| 预测准确率 | 95–99% | 整数负载,分支越规则越高 |
| 预测错误惩罚 | 10–25 周期 | 深流水线与恢复路径决定 |
| 分支 MPKI | 1–10 | 每千条指令的分支缺失 |
3 实践
3.1 最小示例
# 先量分支密度与缺失率,再决定是改代码还是调预测策略。
perf stat -e branches,branch-misses,cycles,instructions ./app
# 用真实分支概率做 PGO,让编译器把热路径排成直落。
gcc -O2 -fprofile-generate -o app app.c && ./app
gcc -O2 -fprofile-use -o app app.c
如果 branch-misses 集中在少数间接跳转,优先查虚调用与函数指针;如果集中在数据相关分支,宜改成无分支选择或重排数据。预测器无法理解数据语义,只能利用历史与相关性。
3.2 常用操作与参数
| 操作 | 参数 | 说明 |
|---|---|---|
| 选静态或动态 | 编译期固定、运行时学习 | 嵌入式可省面积,服务器用动态 |
| 设表大小 | 4K–64K 项 | 与访问延迟、别名率折中 |
| 设历史长度 | 8–1000 bit | 长历史适合相关分支 |
| 设 RAS 深度 | 16–64 项 | 递归深时需更大 |
| 开 PGO | -fprofile-generate/use | 改善布局与静态预测 |
3.3 标准流程
- 取指阶段用 PC 并行查 BTB 与方向预测器。
- 组合出下一取指地址,沿预测路径继续取指。
- 分支进入执行级后解析真实方向与目标。
- 比较预测结果,更新计数器、历史与目标项。
- 预测错误时重定向 PC、清空年轻指令,并从正确路径重新取指。
3.4 与相邻技术的组合
预测让前端不断供指,ROB 让预测路径上的指令可以执行,错误时两者一起清空;PGO 与代码布局改变分支密度与直落概率;循环展开减少每轮分支数;RAS 依赖 ABI 的调用约定,尾调用会破坏栈平衡假设。
3.5 选型维度
| 场景 | 首选 | 理由 |
|---|---|---|
| 通用服务器 | TAGE + 大 BTB + RAS | 单线程性能与分支多样性 |
| 移动 SoC | 中等 TAGE + 低功耗 | 能效与面积优先 |
| 嵌入式顺序核 | 静态预测或小 BHT | 面积小,实时性可分析 |
| 安全加固 | 受限预测 + 屏障 | 降低 Spectre 面 |
3.6 决策规则
- 先看
branch-misses的分布:集中在小段代码才值得改预测器。 - 数据相关且不可预测的分支,宜改成无分支选择,而不是加大预测表。
- 间接跳转多时,先查虚调用与函数指针,再考虑 ITTAGE。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 静态预测 | 无状态、可分析 | 准确率低 | 嵌入式、实时 |
| 延迟槽 | 硬件简单 | 填满槽位困难 | 早期 RISC |
| 谓词执行 | 消除短分支 | 多做无用功 | VLIW、DSP |
| 无分支代码 | 时序稳定 | 可能多算 | 密码学 |
3.8 何时不该用
- 硬实时路径需要可证明的最坏执行时间,动态预测会引入不确定分支。
- 常数时间密码代码不应让秘密影响分支方向与预测器状态。
- 分支完全随机且无法改写时,加大预测表只会增加功耗,收益接近零。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 准确率突然下降 | BTB 或 BHT 别名抖动 | 调整索引与相联度 |
| 长历史被污染 | 无关分支写入 TAGE 表项 | 用 usefulness 与标签过滤 |
| 返回连续预测错 | RAS 溢出或调用栈错配 | 加深 RAS,检查尾调用 |
| 间接跳转命中低 | 多目标共享一个 BTB 项 | 用 ITTAGE 或多目标项 |
| 攻击者训练预测器 | 跨上下文共享预测状态 | 隔离预测器,启用缓解 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
只加 __builtin_expect 不做 PGO | 提示与真实分布不符 | 用 PGO 校准 |
| 在热循环放不可预测分支 | 每次迭代都清空前端 | 改成无分支选择 |
| 把准确率当唯一指标 | 忽略缺失代价与分布 | 看 MPKI 与惩罚 |
4.3 可观测信号
perf stat -e branches,branch-misses;br_misp_retired.all_branches 与 br_inst_retired.conditional 区分条件与间接;perf record -e branch-misses 加 perf annotate 定位热点分支;llvm-mca 可估算分支密集循环的前端压力。
4.4 安全 / 性能 / 一致性边界
- 安全:预测器状态是跨上下文共享的微架构状态,Spectre v1 利用条件分支,v2 利用 BTB 注入;隔离与屏障只能缓解,不能把预测器变成安全边界。
- 性能:预测准确率高不等于性能好,还要看缺失分布、恢复延迟与前端带宽。
- 功耗:TAGE 与多目标 BTB 的访问与训练消耗可观,移动核常按负载调整预测强度。