误判代价惊人
111 条指令的例子说明为什么分支预测如此重要
CS152 · 第 15 课
这一讲直接量化了"控制冒险为什么是乱序执行的头号敌人"：现代流水线取指和分支真正解出结果之间可能隔着十几级流水，一次误判丢弃的工作量可以轻松超过一百条指令。分支预测正是把这份代价压到最低的关键技术。
关于资料来源的说明：这份幻灯片的标题页明确写着"客座讲者今日主讲——以下幻灯片沿用去年同一讲的内容"，其内部页眉标注为"Lecture 12 – Branch Prediction, Krste Asanovic"——这是课程组主动重用的一份往年讲义，编号上的错位（"12"而非"15"）是重用旧文件的自然结果，并非真正的课程排期错误。另外，第 16 课的回顾幻灯片提到"上一讲还涉及 Perceptron 和 TAGE 这两种更先进的分支预测结构"，但这两个术语在本份幻灯片实际内容中并未出现——这可能是客座讲者当场口头补充的内容，也可能是回顾模板本身的泛化表述，本页如实按幻灯片实际内容撰写，不臆测未出现的具体机制细节。
现代处理器的取指和分支真正被执行、解出结果之间，可能隔着超过 10 级流水线。控制流代价大致正比于"循环长度 × 流水线宽度 + 缓冲区大小"。
误判代价的具体数字（重新验算）：假设一台 4 发射超标量、取指到派发之间有 8 级流水线、80 项 ROB、发射到分支解出需要 3 个周期。误判会丢弃：8×4 + (80−1) = 32 + 79 = 111 条指令——重新验算与幻灯片一致。如果预测准确率从 90% 提升到 95%，误判率恰好减半（10%→5%，降低了 50%）；假设每 6 条指令中有 1 条是分支，10% 误判率下平均每 1/((1/6)×0.10)=60 条指令发生一次误判，准确率提升到 95% 后变为每 1/((1/6)×0.05)=120 条指令一次——两次重新计算都与幻灯片给出的 60/120 完全吻合。这组数字直观说明了：预测准确率哪怕只提升 5 个百分点，两次误判之间能多跑的指令数就能直接翻倍。
整体上分支被采纳（taken）的概率约 60-70%，但方向不同差异很大：向后分支（循环）约 90% 被采纳，向前分支约 50% 被采纳（接近抛硬币）。两种 ISA 级静态预测机制：在操作码本身附带首选方向提示（Motorola MC88110：bne0表示倾向预测采纳，beq0表示倾向预测不采纳）；或者让编译器为每条分支静态选定一个方向（HP PA-RISC、Intel IA-64），据称准确率约 80%。
动态预测依赖两种相关性：时间相关性（一条分支自己过去的结果预测它未来的结果）与空间相关性（多条分支的结果彼此相关，反映"偏好的执行路径"）。1 位分支历史预测器只记住上一次的结果——对于循环收尾的向后分支，这会导致每次循环执行都误判两次：一次在循环入口（因为上次退出了循环，预测不采纳），一次在循环出口（因为上次继续循环了，预测采纳）。
解决办法是2 位饱和计数器：四个状态（"预测采纳-上次对/错"、"预测不采纳-上次对/错"）构成一个 FSM，只有连续两次预测错误才会真正翻转预测方向——这给了预测器抵御偶发异常的"惯性"。分支历史表（BHT）用取指 PC 的低若干位作为索引，查一张 2 位计数器表。真实规格：4K 项 BHT，每项 2 位，准确率约 80-90%。
引用 Yeh and Patt (1992) 的例子：if(x[i]<7) y+=1; if(x[i]<5) c-=4;——如果第一个条件为假，第二个条件必然也为假，这就是空间相关性。引入历史寄存器 H，记录处理器最近 N 条分支的方向。Pentium Pro 用最近两条分支的结果（2 位）在 4 组 BHT 之间做选择，据称达到约 95% 的准确率——2 位历史选 4 组（2²=4）在数字上是自洽的。
幻灯片明确讨论并否定了"两个方向都推测执行"这个替代方案：所需资源随并发推测执行的路数线性增长，却只有一半的资源真正做了有用功——如果预测足够准，把全部资源押注在预测方向上明显更划算。
BHT 只能预测方向，取指流要重新对齐还需要知道目标地址。分支目标缓冲区（BTB）同时存储分支 PC 和预测目标 PC；只存储被采纳的分支和跳转；BTB 命中让下一条取指的目标在分支本身被译码之前就能确定——这是它相对纯 BHT 设计的关键优势。BTB 每项存储代价更高，但能更早改变取指方向、还能加速间接跳转（JR）；BHT 存储的项数多得多、更准确；真实设计中二者结合，BTB 在流水线早期起作用，BHT 在稍后阶段纠正。
寄存器跳转（JR）的三种典型用途——switch 语句、动态函数调用（如 C++ 虚函数）、子程序返回——各自的 BTB 命中率取决于"是否总是跳到同一个目标"；子程序返回的弱点在于"同一个函数可能被许多不同的调用点调用"。专用的返回地址栈（通常 8-16 项的 LIFO）比通用 BTB 准确得多：函数调用时压入返回地址，识别到子程序返回时弹出——因为调用/返回天然遵循严格的嵌套规律。
顺序发射机器只有推测取指，没有推测执行（分支总是先于后续指令完成，已完成的值保留在旁路网络中直到提交）；乱序发射机器则连执行本身也是推测性的——分支可能在程序顺序上更晚的指令已经完成之后才被解出，已完成的值保存在 ROB 或统一物理寄存器堆的重命名寄存器里，直到提交才算数。乱序恢复因此更复杂：多条分支可能同时处于"尚未解出"状态。真实例子：MIPS R10K 用 4 个掩码位为指令标记它依赖于最多 4 条未解出的推测分支中的哪几条，某条分支解出后清除对应掩码位、腾出来给下一条分支复用；重命名表的恢复方式与第 12、13 课讨论异常恢复时完全一致——MIPS R10K 相应地只保留 4 份快照（与 4 个掩码位一一对应），Alpha 21264 则保留 80 份（每条 ROB 指令一份）。
推测式乱序机器的性能常常受限于取指带宽：推测执行可能取指的数量是最终提交数量的 2-3 倍；误判代价主要取决于重新填满指令窗口所需的时间；被采纳的分支尤其麻烦，因为它们会打断指令缓存行的连续读取。整数代码大约每 6-9 条指令就有一条被采纳的分支——要继续扩展性能，机器必须能每周期处理多条被采纳的分支，这意味着每周期预测多条分支、每周期取指多个不连续的指令块。Trace Cache（真实例子：Intel Pentium 4，用于缓存已译码的微操作）正是为此而生：把实际执行路径上多个不连续的基本块，打包进一条连续的 trace cache 行里，这样一次取指就能取到跨越多条已采纳分支的指令序列。
问题 1：一台 4 发射超标量、取指到派发 8 级流水线、80 项 ROB 的机器，一次分支误判最多会丢弃多少条已经进入流水线的指令？
问题 2：为什么"2 位饱和计数器"比"1 位历史预测器"更能避免循环收尾分支的重复误判？
问题 3：为什么仅凭分支历史表（BHT）还不够，还需要分支目标缓冲区（BTB）？
111 条指令的例子说明为什么分支预测如此重要
连续两次错误才翻转，解决 1 位预测器的循环收尾问题
提供目标地址，子程序返回靠 LIFO 结构远比 BTB 准确
掩码位/快照机制选择性撤销尚未提交的推测执行结果
sp23/lecture_slides/L15_Guest_Branch_Prediction.pdf（内部标注 "Lecture 12 – Branch Prediction," Krste Asanovic）