Yeh-Patt 1991 — 用最近 12 条分支的历史给 CPU 算命

是什么

CPU 在执行 if (x > 0) ... 这类条件分支时，得在「条件还没算完」之前先决定下一条该取哪行指令——猜对了流水线不停，猜错了要清空十几级流水线重新来。Yeh-Patt 1991 提出了一套两级自适应预测算法：

第一级：一个叫 BHR（Branch History Register）的小寄存器，记下最近 12 条分支的取/不取，用 1/0 表示，得到一个 12 位串。
第二级：一张叫 PHT（Pattern History Table）的小表，用那串 12 位历史当索引（共 4096 种可能），每格存一个 2 位计数器。
预测时：查 BHR 拿到位串，去 PHT[位串] 看计数器最高位——0 就猜不取、1 就猜取。
训练时：分支真实结果出来后，把那一格计数器朝结果 ±1（有上下界，叫饱和计数器），并把这个结果挪进 BHR 把最旧那位挤出去。

日常类比：你不是只看「这个路口我以前走哪条」，而是看「最近 12 个路口我的选择序列」，对每种序列分别学一个习惯。

为什么重要

1991 年是流水线深度从 5 级飙到 14 级的拐点。猜错代价从 1-2 周期涨到 10-20 周期，预测准确率每升 1% 都直接换性能。当时主流是 Smith 1981 的 2 位饱和计数器（按 PC 索引），SPEC89 上停在 80-93%。Yeh-Patt 把准确率推到 97%，误判数砍掉一半到三分之二。

更关键的是这套算法骨架 30 多年没换过。今天 Intel、AMD、ARM 的现代核里跑的 TAGE-SC-L、感知机预测器，本质都是「拿历史上下文当索引去查一张计数器表」，只是历史更长、表更多、索引更花哨。

核心要点

1. 关键洞察：分支不是独立事件

if (x == 0) ...; if (x == 0) ... 后一个分支结果 100% 相关于前一个。Smith 1981 把每个分支独立看，丢掉了这个相关性。Yeh-Patt 把前面 12 条分支结果记下来当上下文，对每种上下文分别学一个 2 位计数器——单一计数器扩成 2^12 = 4096 个，按上下文分桶。

更直白的类比：Smith 1981 是「不管你最近怎么走的，每个路口看习惯」；Yeh-Patt 是「先看你最近 12 步怎么走的，再决定这步习惯」。同一个路口在不同上下文里有不同习惯，分别学。

2. 为什么 2 位而不是 1 位

1 位计数器在循环出口被打错一次后立刻翻转，下一轮进入循环又错一次。2 位有「弱猜/强猜」两档缓冲，被打错一次只从「强猜」退到「弱猜」，预测方向不变。

3. 三个变体（论文同时给出）

GAg（本论文主推）：全局 BHR + 全局 PHT，省硬件
PAg：每条分支地址有自己的 BHR + 全局 PHT
PAp：每条分支地址有自己的 BHR + 自己的 PHT

变体差异在「上下文是全局共享还是分支私有」，硬件成本和准确率随之 trade-off。

4. 硬件成本

BHR 12 位 + PHT 4096 项 × 2 bit ≈ 1KB SRAM。1991 年算极小代价，今天的 L1 cache 角落塞得下几十张。

5. 命中率随历史长度的关系

论文给的实验数：

k=4：约 93%
k=8：约 96%
k=12：约 97%（论文推荐点）
k=16：约 97.3%（边际收益已经几乎为零）

历史长度的边际收益递减速度，定义了「该投多少硬件」的最优点。

实践案例

案例 1：循环退出的预测灾难

for (int i = 0; i < 10; i++) { ... }

每轮分支序列：取 9 次、不取 1 次。

1 位预测器：进入和退出各错 1 次，每轮错 2 次
2 位 Smith 计数器：只在退出时错 1 次（缓冲挡住了进入那次）
Yeh-Patt k=12：模式 111111111110 在 PHT 里就有专格，0 次错——它学到的是「连续 9 个取之后必然不取」

案例 2：相关分支

if (x == 0) handle_zero();
// ... 几行代码 ...
if (x == 0) log_zero();

第二个 if 的结果完全由第一个决定。Yeh-Patt 的 BHR 把第一个 if 的结果记进位串，第二个 if 查 PHT 时上下文已经包含「x==0 的真相」，几次训练后 PHT 里那一格收敛到强猜对，准确率冲到接近 100%。

案例 3：误判的真实代价

现代 CPU 流水线 14-20 级 @ 4GHz，单次误判要清空整条流水线 + 重新取指 + L1 i-cache 重新对齐。实测 15-25 ns。准确率从 97% 升到 99% 看起来只 2 个百分点，但误判数砍 2/3，整体 IPC 能涨 5-10%。

踩过的坑

冷启动慢：BHR 越长越准，但工作集换了（比如 OS 切换进程、JIT 编译完新代码）BHR 里全是旧上下文，要训几千次分支才回到位。现代 CPU 在线程切换时不专门保存 BHR，赌的就是「几十万周期内会自训回来」。
别名污染（aliasing）：不同分支映射到同一 PHT 项时互相覆盖。McFarling 1993 的 gshare 用 BHR XOR PC 缓解，但治本要 PAp（每分支私有 PHT，硬件涨数倍）。
不规则分支：随机数据驱动的分支（哈希查表、加密的 S-box）历史无规律，Yeh-Patt 准确率掉到 50-60%——和瞎猜差不多。这类场景要么靠编译器 hint、要么靠预译码改成无分支代码（cmov）。
历史太长反而变差：k > 16 时 PHT 项数 65536+，多数项学不满训练数据就被 evict，准确率反降。Seznec 2006 TAGE 的解法是多张不同长度的历史表并存、按标签选最准的那张。

适用 vs 不适用

适用：

所有乱序、超标量、深流水线 CPU 的条件分支预测
JIT / 解释器的间接分支预测（变种：BTB + 历史索引）
任何「下一步行为强相关于近期序列」的场景——预取器、cache 替换都借鉴了这个思路

不适用：

极简顺序核（部分嵌入式 / 教学用 RISC-V 玩具核）省掉预测器
GPU 走 SIMT，分支处理是「让所有 lane 都执行两条路径」（warp 分歧）而不是预测
数据相关性极弱的工作负载——预测器不如直接用 cmov / 谓词执行

历史与后续

直接前身：Smith 1981 的 2 位饱和计数器（即两级预测的第二级）
同期对手：Pan-So-Rahmeh 1992 独立提出 correlation predictor，思路相近
直接后继：McFarling 1993 gshare（BHR XOR PC 索引，硬件减半）
当代王者：Seznec 2006 TAGE（多历史长度并存 + 标签匹配），现代 Intel/AMD 用 TAGE-SC-L 变体，准确率冲到 99% 以上
侧支流派：Jiménez-Lin 2001 感知机预测器，把 PHT 换成线性分类器，捕获更长历史
侧信道流派：2018 Spectre 漏洞利用 BHR 训练注入，让攻击者诱导分支预测器猜错，借乱序执行的瞬态指令读到秘密数据。这暴露了「全局共享 BHR」在安全语义上的隐患，现代 CPU 加了 IBRS、IBPB 等指令隔离 BHR

学到什么

「上下文索引一张小表」是个万能架构模式——分支预测、cache 替换、prefetcher、TLB 预测都在用
2 位饱和计数器是工程上的最优点：1 位太脆、4 位以上边际收益递减
算法可以 30 年不变，硬件可以涨 1000 倍——Yeh-Patt 1991 的骨架今天还在跑
「相关性」是预测器的核心资产——能记下多少相关上下文 = 能预测多准
训练和推理在同一硬件里同步发生——分支真实结果一出来立刻回写计数器和 BHR，不存在「先训练再部署」这种离线分段，每次预测都同时在更新模型。这种「在线学习硬件化」思路启发了后来的很多硬件预测器
可证伪的工程主张——论文不只给一个数字，给的是「k=4/8/12 vs 命中率」的曲线。曲线告诉你拐点在哪、边际收益什么时候消失，下游的 gshare、TAGE 都是沿这条曲线挑更优点

关联

amdahl-law-1967 —— Amdahl 定律：分支预测准确率每升 1%，本质是把「停流水线」这段串行开销往下压
ssa —— SSA：编译器优化的中间表示，影响生成的分支密度
hotspot-server-compiler —— HotSpot：JIT 在运行时根据 profile 重排分支，与硬件预测器协作
tracemonkey —— TraceMonkey：只编译走过的路径，间接减少难预测分支
self-pic —— Self / PIC：内联缓存也是「拿历史调用上下文索引一张小表」的思路在间接分支上的体现

反向链接

amdahl-law-1967 —— Amdahl 定律 — 串行比例决定并行加速比的上界
hotspot-server-compiler —— HotSpot Server Compiler — JVM 在运行时把热点 Java 代码翻译成飞快的本地码
kocher-spectre-2019 —— Spectre 攻击 — 推测执行偷看别人的内存
mcfarling-bp-1993 —— McFarling 1993 — 用 XOR 把全局历史和 PC 拧在一起，再让两个预测器打擂台
self-pic —— Self / PIC — 内联缓存的诞生
ssa —— SSA — 静态单赋值形式
tracemonkey —— TraceMonkey — 只编”真的走过的那一条路”