分支预测概述

考虑一个6-wide、20级流水线的超标量处理器：每次分支预测失败（mispredict），流水线中多达$6 \times 20 = 120$条指令作废。分支指令占动态指令流的约15%，假设预测准确率97%——看似很高——但每1000条指令中约有$1000 \times 0.15 \times 0.03 = 4.5$次mispredict。每次mispredict浪费约20个周期，4.5次共浪费约90个周期。1000条指令在理想6-wide机器上只需$1000/6 \approx 167$个周期，加上90个周期的惩罚后变为257个周期，IPC从6.0降到$1000/257 \approx 3.9$——损失了35%。如果准确率降到95%，IPC进一步跌至$\sim$3.0。分支预测准确率直接决定超标量处理器能否达到设计目标。

从本书的统一视角审视：处理器设计的本质是在有限的晶体管预算和功耗约束下，通过投机（speculation）和并行（parallelism）的层层叠加来逼近指令吞吐率的理论上限。分支预测是最纯粹的"投机"形式——在没有任何确定性信息的情况下，完全基于历史统计做概率判断。它与第 1.0 章中推导的$\text{CPI}_{\text{branch}} = f_b \cdot m \cdot P$公式直接对应：分支预测的投机质量（准确率$1-m$）乘以投机失败的代价（惩罚$P$，由第 2.0 章中讨论的流水线深度决定），决定了这一项对总CPI的贡献。流水线越深、发射越宽，投机失败的代价越大——这正是"投机与并行的张力"在分支预测中的具体体现。

读完本章，你将理解分支预测从定量分析到硬件机制的完整框架，掌握预测准确率与IPC之间的数学关系，以及BHT、BTB、RAS等核心结构的设计原理。

在超标量处理器的深流水线中，分支指令是影响性能的最关键因素之一。一条分支指令从取指到最终解析出正确方向，可能跨越15$\sim$20个流水段。在此期间，处理器前端每个周期都在持续取指和解码——如果这些指令来自错误的路径，则在分支解析后必须全部丢弃，浪费的周期数等于分支解析所在流水段的深度。在一个6-wide、20级流水线的处理器中，一次分支预测失败可能浪费上百条已经进入流水线的指令所占用的资源。因此，现代高性能处理器在分支预测器上投入了大量的硬件资源和设计精力，力图将预测准确率提高到97%以上。

本章作为第三篇"分支预测"的开篇，首先从第一性原理出发，量化推导深流水线中分支指令导致的性能损失，说明为什么分支预测是超标量处理器中不可或缺的机制；然后对分支指令进行分类，分析不同类型对预测器的需求差异；接着介绍静态预测和基于饱和计数器的动态预测等基本方法，为后续章节的高级算法做铺垫；再讨论分支历史表（BHT）的索引设计与别名问题；随后深入分析BTB的结构和查找时序、RAS的设计和推测操作；最后讨论分支预测器在流水线中的接口设计——预测的时机、输出格式以及更新策略。后续各章将分别深入讨论方向预测（第第 14.0 章章）、目标地址预测（第第 15.0 章章）、高级预测算法（第第 16.0 章章）以及预测器的工程实现（第第 17.0 章章）。

为什么需要分支预测

要理解分支预测的重要性，必须从处理器流水线的基本工作原理出发。在一个理想的标量流水线中，每个时钟周期完成一条指令的一个阶段处理，整条流水线在稳态下每周期产出一条指令。但这个理想状态有一个前提：流水线的每一级在每个周期都能接收到有效的输入。分支指令是破坏这一前提的最主要因素。

深流水线中的控制冒险

当处理器取指阶段遇到一条分支指令时，它面临一个根本性的困境：分支的方向和目标地址要在若干个流水段之后的执行阶段才能确定，但取指阶段在每一个周期都需要知道下一个取指地址。这就是经典的控制冒险（control hazard）。

在一个$N$级流水线中，假设分支指令在第$s_p$级被取指，在第$s_r$级被解析（分支条件计算完成、目标地址确定），则从取指到解析之间有$s_r - s_p$个流水段。在这段时间内，处理器有三种基本策略：

（1）停顿等待（stall）。取指阶段暂停，直到分支指令的结果在第$s_r$级被解析。这种策略最简单，但性能代价巨大——每条分支指令都引入$s_r - s_p$个周期的流水线气泡。

（2）总是预测不跳转（always predict not-taken）。取指阶段假设分支不跳转，继续从PC+4取指。如果猜对，没有任何惩罚；如果猜错，需要丢弃已经进入流水线的错误指令并从正确地址重新取指。

（3）分支预测（branch prediction）。使用专门的硬件预测器来猜测分支的方向和目标地址，在预测结果的指导下持续取指。预测正确时没有惩罚，预测错误时的代价与策略（2）相同。

对于现代15$\sim$25级的深流水线处理器而言，策略（1）完全不可接受——即使不考虑超标量的问题，仅仅是停顿就会导致CPI从1.0退化到接近2.5$\sim$4.0（取决于分支频率）。策略（2）是策略（3）的一个特例（最简单的静态预测器）。因此，分支预测不是一个可选的优化，而是深流水线处理器正常工作的必要条件。

流水线深度与Flush代价的量化

为了精确量化分支预测对性能的影响，需要建立一个数学模型。设处理器的关键参数如下：

• $N$：流水线总级数

• $W$：取指/发射宽度（每周期最多取$W$条指令）

• $f_b$：分支指令在动态指令流中的比例

• $P$：分支预测失败惩罚（从预测到解析之间的周期数）

• $m$：分支预测失败率（misprediction rate）

• $\mathrm{IPC}_{\text{ideal}}$：理想IPC（无分支惩罚、无cache miss等）

首先考虑停顿策略。每条分支指令引入$P$个周期的停顿，每$1/f_b$条指令遇到一次分支，因此每$1/f_b$条指令就有$P$个周期的气泡。总CPI为： $$\label{eq:ch13-cpi-stall} \mathrm{CPI}{\text{stall}} = \frac{1}{\mathrm{IPC}{\text{ideal}}} + f_b \cdot P$$

对于一个$W=6$的超标量处理器，$\mathrm{IPC}_{\text{ideal}} \approx 4.0$（受限于各种结构冒险和数据冒险），$f_b = 0.15$，$P = 18$（20级流水线），停顿策略下的CPI为： $$\mathrm{CPI}_{\text{stall}} = 0.25 + 0.15 \times 18 = 2.95$$ 对应$\mathrm{IPC}_{\text{stall}} = 1/2.95 = 0.34$——一个6-wide的处理器居然只达到0.34的IPC，效率不到理想值的9%，这是完全不可接受的。

现在考虑分支预测。只有预测失败的分支才产生惩罚，因此额外的CPI开销变为： $$\label{eq:ch13-cpi-bp} \mathrm{CPI}_{\text{branch}} = f_b \cdot m \cdot P$$

这个公式是分支预测性能分析的基础。将其与停顿策略的$\mathrm{CPI}_{\text{stall\_penalty}} = f_b \cdot P$对比，可以看到分支预测将惩罚降低了$1/m$倍——如果预测准确率为97%（$m=0.03$），则惩罚降低为停顿策略的3%，这是一个巨大的改进。

现在可以推导完整的IPC损失公式。设理想CPI（无任何分支惩罚）为$\mathrm{CPI}_0 = 1/\mathrm{IPC}_{\text{ideal}}$，则有分支预测的实际CPI为： $$\label{eq:ch13-full-cpi} \mathrm{CPI}{\text{actual}} = \mathrm{CPI}0 + \mathrm{CPI}{\text{branch}} = \frac{1}{\mathrm{IPC}{\text{ideal}}} + f_b \cdot m \cdot P$$

实际IPC为$\mathrm{CPI}_{\text{actual}}$的倒数： $$\label{eq:ch13-full-ipc} \mathrm{IPC}{\text{actual}} = \frac{1}{\mathrm{CPI}{\text{actual}}} = \frac{1}{\dfrac{1}{\mathrm{IPC}{\text{ideal}}} + f_b \cdot m \cdot P} = \frac{\mathrm{IPC}{\text{ideal}}}{1 + \mathrm{IPC}_{\text{ideal}} \cdot f_b \cdot m \cdot P}$$

IPC的相对损失（relative IPC loss）为： $$\label{eq:ch13-ipc-loss} \text{IPC_loss} = \frac{\mathrm{IPC}{\text{ideal}} - \mathrm{IPC}{\text{actual}}}{\mathrm{IPC}{\text{ideal}}} = \frac{\mathrm{IPC}{\text{ideal}} \cdot f_b \cdot m \cdot P}{1 + \mathrm{IPC}_{\text{ideal}} \cdot f_b \cdot m \cdot P}$$

这个公式揭示了一个重要的结构性特征：IPC损失是$\mathrm{IPC}_{\text{ideal}} \cdot f_b \cdot m \cdot P$这个乘积的单调递增函数。四个因子中的任何一个增大，都会导致更大的IPC损失。特别地，$\mathrm{IPC}_{\text{ideal}}$出现在损失公式中意味着：理想IPC越高的处理器（更宽的发射宽度、更好的乱序调度），对分支预测失败越敏感。

硬件描述 1 — penalty \times branch_freq \times mispredict_rate \to IPC损失的完整推导

将上述公式应用到一个具体的20级流水线、6-wide处理器设计中：

已知参数：$W=6$，$\mathrm{IPC}_{\text{ideal}}=4.0$，$f_b=0.15$，$P=18$

步骤1：计算损失因子 $\Phi = \mathrm{IPC}_{\text{ideal}} \cdot f_b \cdot P = 4.0 \times 0.15 \times 18 = 10.8$

步骤2：对于不同的预测失败率$m$，计算IPC和损失：

失败率$m$	$\Phi \cdot m$	$\mathrm{IPC}_{\text{actual}}$	IPC损失	等效于
0%	0	4.00	0%	—（理想）
1%	0.108	3.61	9.8%	损失约0.4 IPC
2%	0.216	3.29	17.8%	损失约0.7 IPC
3%	0.324	3.02	24.5%	损失约1.0 IPC
5%	0.540	2.60	35.0%	超过1/3性能损失
10%	1.080	1.92	52.0%	过半性能损失
20%	2.160	1.27	68.4%	近2/3性能损失

关键观察：在$m=3\%$时（对应97%准确率），IPC损失已达24.5%——一个6-wide处理器因分支预测不完美而损失了近四分之一的性能。这就是为什么现代处理器的分支预测器动辄占用50$\sim$200 KB的SRAM资源——这些投入在IPC回报上是完全合理的。

性能分析 1 — 从停顿到预测：深流水线的"生死线"

下面用一个完整的数值例子来展示分支预测对深流水线处理器的决定性意义。

考虑一个参数为$W=6$, $\mathrm{IPC}_{\text{ideal}}=4.0$, $f_b=15\%$, $P=18$的处理器。表表 13.1对比了停顿策略和不同准确率的分支预测下的IPC。

策略	额外CPI	总CPI	IPC
停顿（不预测）	$0.15 \times 18 = 2.70$	2.95	0.34
总是预测不跳转 ($\sim$60%准确)	$0.15 \times 0.40 \times 18 = 1.08$	1.33	0.75
简单两位计数器 ($\sim$85%准确)	$0.15 \times 0.15 \times 18 = 0.405$	0.655	1.53
gshare ($\sim$93%准确)	$0.15 \times 0.07 \times 18 = 0.189$	0.439	2.28
TAGE ($\sim$97%准确)	$0.15 \times 0.03 \times 18 = 0.081$	0.331	3.02
TAGE-SC-L ($\sim$99%准确)	$0.15 \times 0.01 \times 18 = 0.027$	0.277	3.61
理想预测（100%准确）	0	0.25	4.00

从停顿策略的IPC=0.34到TAGE预测器的IPC=3.02，性能提升了近9倍——这就是分支预测对深流水线处理器的决定性意义。即使是最简单的两位计数器预测器，也能将IPC从0.34提升到1.53，提升4.5倍。

图图 13.1以可视化方式展示了预测准确率与IPC之间的非线性关系——注意在高准确率区间，每提高一个百分点所带来的IPC增益反而更大。

分支预测准确率与IPC的关系：三种不同配置的超标量处理器

::: warning 性能分析 2 — 解读准确率–IPC曲线

图图 13.1揭示了三个关键洞察：

（1）宽机器对预测精度更敏感。红色虚线（$W{=}8$）的斜率在高准确率区间远大于绿色点线（$W{=}4$）——这意味着8-wide处理器从97%提升到99%所获得的IPC增益（约1.5），远大于4-wide处理器的同等增益（约0.5）。

（2）高准确率区间的边际收益递增。从95%到96%的IPC增益小于从98%到99%的增益——这是因为公式$\mathrm{IPC}= \mathrm{IPC}_{\text{ideal}} / (1 + \Phi \cdot m)$中，当$m$很小时，$m$的减少对$\mathrm{IPC}$的影响是超线性的。这解释了为什么处理器设计者愿意投入巨大的硬件资源（如TAGE-SC-L的$\sim$200 KB SRAM）来追求最后1–2个百分点的提升。

（3）准确率是超标量扩展的前提。如果分支预测准确率停留在95%，从4-wide扩展到8-wide只能将IPC从2.18提升到2.75——投入了一倍的解码/发射/执行资源，却只获得了26%的性能回报。只有在准确率达到99%以上时，宽机器的优势才能真正发挥。

:::

超标量宽度放大Flush损失

在超标量处理器中，分支预测失败的代价被进一步放大。原因在于：超标量处理器每个周期可以取指和发射$W$条指令，一次flush不仅浪费了$P$个周期的时间，还浪费了这$P$个周期中本应执行的$W \times P$条指令的执行机会。

更精确地说，一次分支预测失败导致的有效指令损失为： $$\label{eq:ch13-wasted-ops} L_{\text{ops}} = \mathrm{IPC}_{\text{actual}} \times P$$

其中$\mathrm{IPC}_{\text{actual}}$是处理器的实际IPC。注意这里使用实际IPC而不是理想IPC，因为flush期间本应执行的指令受到其他性能限制（cache miss、数据依赖等）的制约。

例如，在一个实际$\mathrm{IPC}= 3.0$、$P = 18$的处理器上，一次预测失败导致$3.0 \times 18 = 54$条有效指令的执行机会被浪费。如果每200条指令就有一次预测失败（MPKI=5），则处理器的执行效率损失约为$54 / (200 + 54) \approx 21\%$。

这种"宽度放大效应"意味着：超标量处理器的发射宽度越宽，对分支预测准确率的要求越高。一个8-wide处理器即使达到了与4-wide处理器相同的预测准确率，其因预测失败导致的相对性能损失也更大，因为每个周期浪费的执行机会更多。

设计提示

这一效应是处理器架构设计中的基本权衡之一：增加发射宽度$W$可以提高理想IPC，但同时也要求更高的分支预测准确率来维持效率。Intel从Skylake（4-wide decode、6-wide后端）到Golden Cove（6-wide decode、12-wide后端）的演进中，分支预测器的存储容量从约40 KB增长到超过100 KB，正是为了在更宽的机器上维持可接受的预测失败损失。

流水线深度选择与分支预测的博弈

流水线深度$N$与分支预测之间存在根本性的张力。更深的流水线允许更高的时钟频率（每级的逻辑更简单），但也意味着更大的分支惩罚$P$。历史上，Intel Pentium 4（NetBurst微架构，2000年）将流水线深度推到了31级的极端，其分支预测失败惩罚高达20$\sim$30个周期——即使配备了当时最先进的预测器，性能也受到严重制约。

可以用一个简单的模型来分析流水线深度的最优选择。假设时钟频率$f$与流水线深度$N$近似成线性关系（$f \propto N$），而分支惩罚$P$也与$N$近似成正比（$P \approx \alpha N$，其中$\alpha < 1$是预测到解析的比例因子）。处理器的吞吐量（每秒执行指令数）为： $$\label{eq:ch13-throughput-vs-depth} \text{Throughput} = f \times \mathrm{IPC}= \beta N \times \frac{1}{\dfrac{1}{\mathrm{IPC}_{\text{ideal}}} + f_b \cdot m \cdot \alpha N}$$ 其中$\beta$是频率与深度的比例系数。

对$N$求导并令其为零，可以找到吞吐量最大化的最优深度： $$\label{eq:ch13-optimal-depth} N_{\text{opt}} = \frac{1}{\mathrm{IPC}_{\text{ideal}} \cdot f_b \cdot m \cdot \alpha}$$

这个结果揭示了一个关键关系：预测准确率越高（$m$越小），最优流水线深度越大。换言之，更好的分支预测器不仅直接提高IPC，还间接允许处理器采用更深的流水线和更高的时钟频率。这正是为什么分支预测器的研究在过去三十年中从未停歇——每一次预测器的进步，都在打开流水线深度设计的新空间。

案例研究 1 — Pentium 4与Pentium M：深度与宽度的经典对比

Intel Pentium 4（NetBurst，2000–2006年）和Pentium M（Banias/Dothan，2003–2006年）提供了一个经典的工程案例。

Pentium 4采用31级超深流水线，时钟频率高达3.8 GHz（Prescott），但分支预测失败惩罚约为20$\sim$30周期。即使使用了当时先进的跟踪缓存（Trace Cache）和BTB设计，其整数工作负载的IPC仍然较低。

Pentium M回归了较短的流水线（约14级），时钟频率仅1.6$\sim$2.1 GHz，但分支预测失败惩罚仅约10$\sim$13周期。Pentium M的每时钟周期执行能力（IPC）明显优于Pentium 4，在许多整数工作负载上，较低频率的Pentium M性能反而优于高频率的Pentium 4。

这个案例深刻说明：流水线深度并非越深越好，最优深度取决于分支预测器的能力。从Pentium M演化而来的Core微架构最终取代了NetBurst，成为Intel后续十多年处理器设计的基础——这一架构选择的背后，分支预测的限制是核心考量之一。

分支指令的分类

在讨论分支预测之前，首先需要明确"分支指令"这个概念的边界。从预测器的角度看，所有能够改变程序控制流的指令都属于"分支"范畴，但不同类型的分支对预测器提出的挑战截然不同。以RISC-V的RV64I基本指令集为例，控制流转移指令可以分为四类，如表表 13.2所示。

分类	典型指令	方向是否确定	目标是否确定	预测难度
条件分支	beq, bne, blt, bge	否	是	中–高
无条件直接跳转	jal	是（总跳转）	是	低
间接跳转	jalr（通用）	是（总跳转）	否	高
函数返回	jalr（rd=x0, rs1=ra）	是（总跳转）	否$^*$	低$^*$

RISC-V中控制流转移指令的分类

$^*$函数返回虽然目标地址不在指令编码中，但可通过返回地址栈（RAS）高精度预测。

条件分支

条件分支（conditional branch）是分支预测器面对的最主要挑战。在典型的SPEC CPU 2017整数基准测试中，条件分支占全部动态指令的12%$\sim$18%，在某些控制流密集的程序（如编译器、数据库查询引擎）中这一比例可以超过20%。

条件分支需要预测两个信息：方向（direction）和目标地址（target address）。其中方向预测——即分支是否跳转（taken vs. not-taken）——是核心难题，也是后续章节讨论各种预测算法的焦点。目标地址虽然在指令编码中以PC相对偏移的形式给出，但在取指阶段尚未完成解码之前，处理器无法从指令位流中直接提取偏移量，因此也需要通过BTB（Branch Target Buffer）来预测目标地址。

以RISC-V的B-type指令为例，其编码格式如图图 13.2所示。

imm
[12] imm[10:5] rs2 rs1 funct3 imm[4:1] imm
[11] opcode

RISC-V B-type条件分支指令的编码格式。立即数被分散到多个字段中，目标地址 = PC + sign-extend(imm)。

条件分支可以根据跳转行为进一步细分为几种模式：

（1）强偏向性分支（biased branches）。在很多程序中，大量的条件分支具有极强的方向偏好——例如循环的回边（back edge）通常99%以上的时间跳转（taken），错误检查分支几乎总是不跳转（not-taken）。对于这类分支，即使是最简单的两位饱和计数器预测器也能达到非常高的准确率。根据实测数据，在SPEC CPU 2017的整数子集中，约有60%$\sim$70%的条件分支具有超过90%的方向偏好。

（2）交替型分支（alternating branches）。某些分支按照规律的模式在taken和not-taken之间交替，例如循环展开后的DAXPY代码中，每隔固定次数交替一次。这类分支可以被具有历史信息的预测器（如全局历史预测器）精确捕获。

（3）相关型分支（correlated branches）。分支的方向取决于前面其他分支的结果。例如：

if (x > 0)       // 分支A
    y = 1;
if (x > 0)       // 分支B: 方向与A完全相同
    z = y + 1;

在上面的例子中，分支B的方向与分支A完全相同——如果A跳转，则B也一定跳转。利用全局分支历史（global branch history）可以捕获这种分支间的关联性，这是现代预测器（如TAGE）的核心优势之一。

（4）数据依赖型分支（data-dependent branches）。分支方向取决于输入数据的值，没有可利用的历史模式。例如在排序算法中，比较操作的结果完全取决于两个元素的相对大小，对于随机输入数据，预测准确率理论上不会超过50%。这类分支是所有预测器的"软肋"，需要极长的历史信息或者专门的数据值预测机制才能提高预测率。

性能分析 3 — 条件分支的方向偏向性分析

表表 13.3给出了SPEC CPU 2017中部分整数基准测试的条件分支偏向性统计。这里的"偏向度"定义为$\max(p_{\text{taken}},\, 1 - p_{\text{taken}})$，即分支向多数方向跳转的概率。

基准测试	分支占比	平均偏向度	偏向度$>$90%的分支占比
500.perlbench	16.2%	0.82	62%
502.gcc	19.4%	0.79	58%
505.mcf	13.1%	0.84	65%
520.omnetpp	17.8%	0.76	54%
523.xalancbmk	18.5%	0.77	56%
531.deepsjeng	14.2%	0.88	71%
541.leela	15.7%	0.81	63%
557.xz	12.8%	0.91	74%

可以看到，即使在控制流密集的程序中，超过一半的条件分支具有强偏向性（偏向度$>$90%），这为简单预测器提供了一个良好的基线。但那些偏向度较低的分支（约30%$\sim$45%）才是决定预测器优劣的关键。

无条件直接跳转

无条件直接跳转（unconditional direct jump）在RISC-V中由**jal**指令实现。其方向始终为"跳转"（taken），无需方向预测；目标地址由PC加上20位有符号偏移量得到，编码在指令本身中（J-type格式）：

imm
[20] imm[10:1] imm
[11] imm[19:12] rd opcode

RISC-V J-type指令（jal）的编码格式

虽然**jal的目标地址"确定"（可以从指令编码中计算得到），但处理器在取指阶段通常尚未完成对指令的解码——取指单元从I-Cache中取出的是原始的字节流，需要在后续的预解码或解码阶段才能识别出jal**指令并提取偏移量。而分支预测必须在取指的第1$\sim$2个周期就给出下一个取指地址，此时解码尚未完成。因此，即使是无条件直接跳转，也需要通过BTB来提供预测的目标地址。

BTB的工作原理类似于Cache：以分支指令的PC为索引，存储该分支的目标地址。当取指地址命中BTB中的某个表项时，就使用存储的目标地址作为下一个取指地址。对于**jal指令来说，只要该指令曾经执行过一次并填入BTB，后续的预测就能100%正确命中。BTB缺失只会在jal**指令第一次执行（cold miss）或者被其他表项替换后再次执行（conflict miss/capacity miss）时发生。

设计提示

在某些简单的处理器实现中（如顺序标量流水线），可以通过在取指阶段增加一个简单的**jal检测器来避免对BTB的依赖：只需在取指输出的指令字中检查opcode字段是否匹配jal**（opcode = 1101111），如果匹配则直接从指令中提取偏移量计算目标地址。但在宽发射的超标量处理器中，每个周期可能同时取4$\sim$8条指令，对每条指令都进行这种并行检测的硬件开销较大，因此通常还是依赖BTB来统一处理所有类型的分支。

间接跳转

间接跳转（indirect jump）的目标地址由寄存器的值决定，在指令编码中不包含完整的目标地址信息。在RISC-V中，**jalr**指令实现间接跳转，其目标地址为$\text{rs1} + \text{imm}$，其中rs1是一个通用寄存器，是一个12位的有符号偏移。

间接跳转的目标地址在取指阶段完全未知（需要等到寄存器读取和地址计算完成后才能确定），因此对预测器提出了更高的挑战。间接跳转主要出现在以下场景中：

（1）虚函数调用（virtual function call）。在C++等面向对象语言中，虚函数调用通过虚表（vtable）中的函数指针实现。由于运行时对象的实际类型可能不同，同一条**jalr**指令在不同的调用中可能跳转到不同的目标地址。例如：

class Animal { virtual void speak(); };
class Dog : public Animal { void speak() override; };
class Cat : public Animal { void speak() override; };

void make_sound(Animal* a) {
    a->speak();   // 间接跳转：目标取决于a的实际类型
}

（2）switch-case分支表。编译器在优化switch语句时，如果case值比较密集，会生成一个跳转表（jump table），通过**jalr**跳转到对应的处理代码：

# switch(x) 的跳转表实现
    slli  t0, a0, 3       # t0 = x * 8 (每个表项8字节)
    la    t1, jump_table   # t1 = 跳转表基地址
    add   t0, t0, t1       # t0 = &jump_table[x]
    ld    t0, 0(t0)        # t0 = jump_table[x]
    jalr  zero, t0, 0      # 跳转到目标地址

（3）函数指针回调。C语言中大量使用函数指针，如qsort的比较函数、信号处理器（signal handler）等，目标地址在编译时完全不可确定。

（4）解释器分派（interpreter dispatch）。Python、Java等解释型语言的字节码解释器通常使用一个核心的dispatch循环，通过间接跳转分派到不同字节码的处理函数。每次dispatch的目标地址取决于当前字节码的值，变化非常频繁。

对于间接跳转的预测，简单的BTB只能记住该PC上次跳转的目标地址——如果目标地址每次都不同（如虚函数调用中对象类型交替变化），BTB就会持续预测失败。现代处理器使用间接分支预测器（Indirect Branch Predictor）来解决这个问题，其核心思想是利用全局历史路径信息来区分同一条间接跳转在不同上下文中的目标。例如Intel Haswell引入了基于全局历史的间接分支目标缓冲区（IBTB），可以根据到达该间接跳转的历史路径来预测不同的目标地址。这些技术将在第第 15.0 章章中详细讨论。

性能分析 4 — 间接跳转的目标集中度

间接跳转虽然"理论上"可以跳转到任意地址，但在实际程序中，同一条间接跳转指令的目标地址通常集中在少数几个值上。表表 13.4给出了SPEC CPU 2017中部分基准的间接跳转目标集中度统计。

基准测试	间接跳转占比	平均不同目标数	前3目标覆盖率
502.gcc	2.1%	4.2	78%
520.omnetpp	3.4%	6.8	65%
523.xalancbmk	2.8%	5.1	72%
531.deepsjeng	1.5%	3.1	89%
541.leela	1.8%	2.4	93%

"前3目标覆盖率"表示仅靠记住最常见的3个目标地址就能覆盖的执行比例。大多数间接跳转的有效目标数量在2$\sim$7个之间，前3个目标通常覆盖65%$\sim$93%的执行。这意味着，只需一个能区分少数几种上下文的间接预测器，就能获得很大的准确率提升。

函数调用与返回

函数调用（call）和函数返回（return）是间接跳转的一种特殊形式，但由于其具有严格的后进先出（LIFO）匹配模式，可以用一个简单而高效的硬件结构——返回地址栈（Return Address Stack，RAS）——来精确预测。

在RISC-V中，函数调用和返回都通过**jalr**指令实现，编译器通过寄存器操作数的选择来区分它们的语义：

• 函数调用：jal ra, offset（直接调用）或**jalr ra, rs1, offset**（间接调用），将返回地址（PC+4）保存到ra（x1）中。

• 函数返回：jalr zero, ra, 0（或等价的伪指令**ret**），跳转到ra中保存的返回地址，且不保存返回地址（rd=zero）。

RAS的工作原理如图图 13.4所示：当检测到函数调用指令时，将当前PC+4（返回地址）压入RAS栈顶；当检测到函数返回指令时，从RAS栈顶弹出地址作为预测目标。由于函数调用和返回天然形成LIFO匹配，RAS可以达到极高的预测准确率——在正常的函数调用模式下，准确率通常超过99%。

返回地址栈（RAS）的操作：call时push返回地址，ret时pop作为预测目标

RAS预测失败的主要原因包括：

（1）栈溢出。RAS的深度有限（通常8$\sim$64项），当函数调用深度超过RAS容量时，最早的返回地址会被覆盖，导致后续对应的返回预测失败。在递归深度较大的程序中这个问题尤为突出。

（2）推测性破坏。当分支预测错误时，错误路径上的call/ret指令可能已经对RAS进行了push/pop操作，导致RAS内容被错误地修改。在分支恢复时需要将RAS也恢复到正确的状态。常用的方法包括：在每次预测时记录RAS的栈顶指针（TOS），恢复时将TOS回退到保存的值；或者使用"影子RAS"（shadow RAS），在提交阶段才对正式的RAS进行更新。

（3）非标准调用模式。某些编程模式（如setjmp/longjmp、协程切换、异常处理的栈展开）不遵循标准的call/ret配对，会导致RAS中残留错误的返回地址。

案例研究 2 — RISC-V中的call/ret识别

RISC-V ISA规范（Section 2.5, Control Transfer Instructions）明确建议硬件通过以下规则来区分不同类型的**jalr**指令，以便驱动RAS操作：

rd	rs1	RAS操作	语义
$\neq$ link	$\neq$ link	无	普通间接跳转
$=$ link	$\neq$ link	push	间接函数调用
$\neq$ link	$=$ link	pop	函数返回
$=$ link	$=$ link, rd$=$rs1	push	递归调用
$=$ link	$=$ link, rd$\neq$rs1	push后pop	协程切换/尾调用

其中link寄存器为x1（ra）或x5（t0，用于millicode调用）。这种基于寄存器操作数的隐式编码方式是RISC-V的一个优雅设计——无需额外的opcode位就能向硬件传达调用/返回的语义。

静态分支预测

在讨论基于硬件状态机的动态预测器之前，有必要先了解不依赖运行时历史的静态预测（static prediction）方法。静态预测器不维护任何运行时状态，其预测结果完全由分支指令的固有属性（如指令类型、目标地址方向等）决定。尽管静态预测的准确率远低于现代动态预测器，但它在以下场景中仍然具有工程价值：

• 作为BTB缺失时的后备预测策略——当分支指令首次执行（cold start），BTB和方向预测器中没有该分支的历史记录，此时退化为静态预测。

• 在面积和功耗极度受限的嵌入式处理器中，作为唯一的预测机制。

• 在编译器辅助下，通过分支提示（branch hint）指令或指令编码中的提示位，向处理器传达静态预测信息。

总是预测不跳转

最简单的静态预测策略是总是预测不跳转（always predict not-taken, APNT）：假设所有条件分支都不跳转，处理器继续从PC+4（或PC+2对于压缩指令）取指。这种策略的硬件实现成本为零——不需要任何预测器硬件，处理器前端只需默认顺序取指即可。

APNT在实际程序中的准确率大约为55%$\sim$65%。这看起来不高，但背后有合理的统计依据。在许多程序中，条件分支的not-taken比例略高于taken比例，原因包括：

• 错误处理分支通常不跳转（"正常路径"是fall-through）。

• 条件检查（如空指针检查、边界检查）在大多数情况下条件不成立，分支不跳转。

• 编译器倾向于将"常见路径"安排为fall-through路径（不跳转），将"异常路径"安排为跳转目标。

但APNT对循环回边（loop back-edge）的预测效果极差：循环回边几乎总是跳转（除了最后一次退出循环），而APNT会在每次迭代都预测错误。对于一个执行100次的循环，APNT在99次迭代中预测错误，只在最后一次退出时预测正确——准确率仅1%。

总是预测跳转

与APNT相反的策略是总是预测跳转（always predict taken, APT）：假设所有条件分支都跳转。这种策略在实际程序中的准确率约为55%$\sim$70%，通常略高于APNT。原因在于，程序中有大量的循环回边，这些回边几乎总是跳转——APT在所有循环回边上都预测正确（除了最后一次退出）。

APT的硬件实现比APNT稍复杂：虽然不需要方向预测器，但需要知道分支的目标地址才能跳转——这要么需要BTB来提供目标地址，要么需要在取指阶段进行部分解码以提取目标地址偏移量。如果没有BTB，APT策略实际上退化为APNT（因为不知道往哪里跳转，只能继续顺序取指）。

BTFNT：向后跳转预测跳转，向前跳转预测不跳转

BTFNT（Backward Taken, Forward Not-Taken）是一种更精细的静态预测策略，它利用分支目标地址相对于分支指令PC的方向来做出不同的预测：

• 如果目标地址 $<$ PC（向后跳转，backward branch）：预测为跳转（taken）。

• 如果目标地址 $>$ PC（向前跳转，forward branch）：预测为不跳转（not-taken）。

这种策略的依据来自编译器生成代码的统计特性：

向后跳转通常是循环回边。在几乎所有编译器中，循环体的代码排列在循环条件判断之前，循环回边是一条向后跳转的分支指令。循环回边在除最后一次退出外的所有迭代中都跳转，因此将向后跳转预测为taken可以获得极高的准确率。对于一个执行$n$次的循环，BTFNT的回边准确率为$(n-1)/n$。

向前跳转通常是if-then的条件分支。编译器通常将if条件不成立时的跳转安排为向前跳转（跳过then块），而在许多程序中，条件不成立（分支不跳转）是更常见的情况——例如错误处理、边界检查等。

性能分析 5 — BTFNT在典型工作负载上的准确率

表表 13.5给出了三种静态预测策略在SPEC CPU 2017部分整数测试上的预测准确率。

基准测试	APNT	APT	BTFNT
500.perlbench	57%	61%	72%
502.gcc	53%	58%	68%
505.mcf	62%	64%	74%
520.omnetpp	55%	60%	69%
531.deepsjeng	59%	67%	76%
541.leela	58%	63%	73%
557.xz	64%	68%	78%
平均	58%	63%	73%

BTFNT的平均准确率（73%）显著高于APNT（58%）和APT（63%），说明利用分支方向信息可以有效提高静态预测的准确率。但与现代动态预测器（96%$\sim$99%）相比，差距仍然巨大。

BTFNT策略的硬件实现需要在取指阶段获知分支的目标地址方向——这可以通过BTB获得，也可以通过在预解码阶段提取指令中的偏移量来判断。对于RISC-V的B-type指令，立即数的最高位（bit[12]）就是符号位：如果为1，则目标地址在PC之前（向后跳转）；如果为0，则在PC之后（向前跳转）。因此，只需检查一个比特就能实现BTFNT。

设计提示

BTFNT策略在现代处理器中仍有实际应用：当一条分支指令首次执行（BTB cold miss），动态预测器中没有该分支的历史记录时，许多处理器使用BTFNT作为默认策略。例如ARM Cortex-A77的文档中提到，在BTB缺失时使用"静态预测：向后分支预测跳转"作为回退策略。

编译器辅助的静态预测

某些ISA提供了分支提示（branch hint）机制，允许编译器或程序员向处理器传达静态预测信息。例如：

• PowerPC的条件分支指令中有2位的"BO"字段用于提示分支方向。

• Intel Pentium 4支持分支提示前缀（0x2E表示not-taken，0x3E表示taken），但后续处理器不再使用这些提示。

• C/C++编译器可以通过__builtin_expect()内置函数来提示分支方向，但这只影响代码布局（将"热路径"安排为fall-through），不会生成特殊的分支提示指令。

RISC-V ISA目前没有定义专门的分支提示位，但其标准文档中预留了这种可能性。在实践中，RISC-V编译器通过代码布局优化来间接实现静态预测的效果——将likely路径安排为fall-through，使BTFNT策略恰好与likely路径一致。

静态预测的历史地位与现代角色

静态预测在处理器发展史上扮演了重要角色。早期的RISC处理器（如MIPS R2000/R3000, 1985–1988年）只有5级流水线，分支惩罚仅1个周期，使用简单的"延迟槽"（delay slot）或"总是预测不跳转"策略就足以维持可接受的性能。随着流水线加深到10级以上（如MIPS R10000, 1996年），静态预测的准确率不再足够，动态预测器成为标配。

在现代处理器中，静态预测退居幕后，但仍在以下三个角色中发挥作用：

（1）冷启动期的回退预测。当分支指令首次执行或在长时间未执行后重新出现时，动态预测器中没有该分支的历史记录。此时BTB缺失，处理器退化为静态预测——通常是BTFNT或简单的"不跳转"。冷启动问题在大型工作负载中尤为突出，因为代码足迹远超预测器容量。

（2）编译器优化的基础假设。编译器的代码布局优化（如basic block reordering、function placement）隐含地假设处理器使用BTFNT或类似的静态预测作为回退策略。编译器将likely路径安排为fall-through，使得即使在动态预测器缺失时，处理器也能以较高概率正确预测。

（3）PGO（Profile-Guided Optimization）中的静态注入。基于剖析数据的编译器优化可以在分支指令中嵌入预测提示（对于支持的ISA），使处理器即使在动态预测器冷启动期间也能获得较好的预测。GCC和LLVM都支持通过__builtin_expect_with_probability()将具体的概率信息传达给编译器。

基于饱和计数器的动态预测

静态预测的根本局限在于它不能适应分支的运行时行为。一条在编译时看起来"应该跳转"的分支，在实际运行中可能大部分时间不跳转，反之亦然。动态预测（dynamic prediction）通过在运行时观察分支的历史行为来进行预测，能够自适应地追踪每条分支的实际模式。

最基本的动态预测机制是基于饱和计数器（saturating counter）的预测器。其核心思想极为简单：为每条分支维护一个小的计数器，记录该分支最近的行为倾向——如果最近多次跳转，就预测跳转；如果最近多次不跳转，就预测不跳转。

1位预测器

最简单的动态预测器是1位预测器（1-bit predictor）：为每条分支维护一个1位的状态，记录该分支上一次的方向。预测时，使用上一次的方向作为本次的预测。

1位预测器的状态转换图极为简单：

1位预测器的状态转换图。状态就是上一次的实际方向，每次分支解析后更新。

1位预测器对强偏向性分支效果很好：如果一条分支99%的时间跳转，1位预测器的准确率接近98%（只在方向发生变化的两次都预测错误——变化那次和变回来的那次）。

但1位预测器有一个严重缺陷：一次偶然的方向变化会导致两次预测失败。考虑一个循环执行10次的场景，分支方向序列为：

T T T T T T T T T NT T T T T T T T TN ...

在1位预测器下，每次循环退出（N）和下一次循环进入（T）都会预测错误：

1. 第9次迭代后循环退出：预测T，实际N $\to$ 错误，状态更新为N

2. 新的循环第1次迭代：预测N，实际T $\to$ 错误，状态更新为T

3. 第2$\sim$9次迭代：预测T，实际T $\to$ 正确

因此每个循环实例（10次迭代）产生2次预测错误，准确率为$8/10 = 80\%$。如果循环只执行3$\sim$5次，准确率更低。这就是1位预测器的根本缺陷：它对分支方向的"噪声"过于敏感。

2位饱和计数器

2位饱和计数器（2-bit saturating counter）是对1位预测器的关键改进。其核心思想是：一次方向的偶然变化不应该立即改变预测。只有当分支连续两次向同一方向跳转后，预测才改变。

2位计数器有四个状态，编码为0$\sim$3：

• 00 – 强不跳转（Strongly Not-Taken, SNT）：预测不跳转

• 01 – 弱不跳转（Weakly Not-Taken, WNT）：预测不跳转

• 10 – 弱跳转（Weakly Taken, WT）：预测跳转

• 11 – 强跳转（Strongly Taken, ST）：预测跳转

预测由最高位（bit[1]）决定：0表示预测不跳转，1表示预测跳转。更新规则如下：分支实际跳转时，计数器加1（饱和于最大值3）；分支实际不跳转时，计数器减1（饱和于最小值0）。

2位饱和计数器的状态转换图。虚线左侧的两个状态预测不跳转，右侧的两个状态预测跳转。从SNT到WT需要连续两次taken才能翻转预测，这提供了对偶然方向变化的"惯性"。

2位计数器为什么优于1位预测器

2位计数器的关键优势在于其滞回特性（hysteresis）：预测方向的改变需要两次连续的反方向结果，而不是一次。这使得预测器能够容忍一次偶然的方向变化而不改变预测。

回到前面的循环例子，方向序列为T T T T T T T T T N T T T T T ...，初始状态假设为ST（11）。

迭代	实际方向	更新前状态	预测	正确？
1$\sim$9	T	ST(11)	T
退出	N	ST(11) $\to$ WT(10)	T	$\times$
新循环第1	T	WT(10) $\to$ ST(11)	T
2$\sim$9	T	ST(11)	T
退出	N	ST(11) $\to$ WT(10)	T	$\times$

2位计数器在每个循环实例中只产生1次预测错误（循环退出时），而1位预测器产生2次（退出时和重新进入时）。对于10次迭代的循环，2位计数器准确率为$9/10 = 90\%$，而1位预测器仅为$8/10 = 80\%$。

这个差异在短循环中更为显著。表表 13.6对比了不同循环长度下两种预测器的准确率。

循环迭代次数$n$	1位预测器准确率	2位计数器准确率
3	$1/3 = 33\%$	$2/3 = 67\%$
5	$3/5 = 60\%$	$4/5 = 80\%$
10	$8/10 = 80\%$	$9/10 = 90\%$
20	$18/20 = 90\%$	$19/20 = 95\%$
100	$98/100 = 98\%$	$99/100 = 99\%$

1位预测器与2位饱和计数器在不同循环长度下的回边预测准确率

从表中可以看出，循环越短（$n$越小），2位计数器的优势越明显。由于短循环在实际程序中非常常见（尤其是展开后的内循环），2位计数器的这一优势在实践中非常有价值。

2位计数器对不同类型分支的行为可以更系统地分析。对于一条偏向度为$p$（即$p$的概率跳转、$1-p$的概率不跳转）的分支，2位饱和计数器的稳态预测准确率为：

$$\text{Accuracy}(p) = p^2 + (1-p)^2 + 2p^2(1-p) + 2(1-p)^2 p$$

其中前两项对应计数器处于强状态（ST或SNT）时的正确预测概率，后两项对应处于弱状态（WT或WNT）时的正确预测概率。化简可得： $$\label{eq:ch13-2bit-accuracy-simplified} \text{Accuracy}(p) = 1 - 2p(1-p) + 2p^2(1-p) + 2p(1-p)^2 = 1 - 2p(1-p)(1 - p - (1-p)) + \ldots$$

对于强偏向性分支（$p$接近0或1），准确率迅速趋近1。对于$p=0.5$（完全随机）的分支，2位计数器的准确率约为50%——和随机猜测一样，因为没有任何历史模式可以利用。

硬件描述 2 — 2位饱和计数器的硬件实现

2位饱和计数器的更新逻辑可以用以下简洁的组合逻辑实现（$C_1C_0$为当前计数器值，$d$为实际方向，1=taken，0=not-taken）：

操作	逻辑表达式
递增（$d=1$）:	$C_1' = C_1 \lor C_0$, $C_0' = \overline{C_0} \lor C_1$
递减（$d=0$）:	$C_1' = C_1 \land C_0$, $C_0' = \overline{C_0} \land \overline{C_1}$
统一表达:	$C_0' = (d \oplus C_0) \lor (d \oplus C_1)$
	$C_1' = (d \land (C_1 \lor C_0)) \lor (\overline{d} \land C_1 \land C_0)$

每个2位计数器的更新只需要约6$\sim$8个逻辑门，面积极小。一个包含4096个2位计数器的预测表只需要$4096 \times 2 = 8192$位（1 KB）的存储和少量的读写控制逻辑，非常适合作为简单预测器的基本构建块。

$n$位计数器的收益递减

自然的问题是：如果2位比1位好，那3位、4位甚至更多位的计数器是否更好？

答案是：收益迅速递减。Smith在1981年的经典论文[^1]中通过大量模拟实验得出结论：2位饱和计数器几乎总是最优选择，3位或更多位的计数器带来的准确率提升可以忽略不计。

原因在于：2位计数器已经提供了足够的"惯性"来过滤掉偶然的方向变化。对于一条强偏向性分支（如99%的时间跳转），2位计数器的计数值大部分时间停留在ST（11）状态，偶尔掉到WT（10），很少到达WNT（01）或SNT（00）。3位计数器只是增加了更多的中间状态，但在统计上并不会改善预测，反而增加了从"另一侧"跳转到正确预测所需的转换次数，可能在分支模式变化时适应更慢。

更关键的是，增加计数器位宽直接增加存储开销。在固定的面积预算下，3位计数器意味着同样的存储只能容纳原来2/3的表项数——而表项数量的减少（导致更多的aliasing冲突）对准确率的负面影响通常超过了额外1位带来的正面效果。因此，2位饱和计数器成为了分支预测领域公认的"甜点"配置，几乎所有现代预测器都以2位或3位计数器作为基本单元。

设计权衡 1 — 计数器位宽 vs. 表项数量

设预测器的总存储预算为$S$位。使用$n$位计数器时，可以容纳$S/n$个表项。假设程序有$B$条活跃分支，则平均每个表项被$B \times n / S$条分支共享。别名冲突率近似正比于共享度。

考虑$S = 8192$位（1 KB）的预算：

$n$	表项数	平均共享度	别名引起的
准确率损失	额外惯性
带来的增益
1位	8192	低	小	无（1位无滞回）
2位	4096	中	中	大（解决双错问题）
3位	2730	中高	中高	极小（相对2位）
4位	2048	高	高	可忽略

从1位到2位，"额外惯性的增益"远大于"别名增加的损失"——净效果为正。从2位到3位，增益微小而别名损失增加——净效果接近零或为负。这就是2位计数器成为最优选择的根本原因。

值得一提的是，在某些现代预测器（如TAGE）中使用了3位计数器。这不是因为3位的方向预测更好，而是因为TAGE利用额外的位来编码"有用性"（usefulness）信息，用于表项替换策略——这是计数器位宽的另一种用途，与方向预测的滞回性无关。

分支历史表的索引与别名问题

2位饱和计数器需要组织成一个表格结构——分支历史表（Branch History Table, BHT），也称为模式历史表（Pattern History Table, PHT）。BHT以某种方式将分支指令的PC映射到对应的计数器表项。索引方式的设计直接决定了预测器的有效性。

PC低位直接索引

最简单的BHT索引方式是使用PC的低$k$位直接索引一个$2^k$项的计数器表：

$$\text{index} = \text{PC}[k+1:2]$$

这里跳过PC的最低2位（对于32位定长指令的ISA如RISC-V，最低2位总是00），使用接下来的$k$位作为索引。例如，一个4096项（$k=12$）的BHT使用PC[13:2]作为索引。

PC低位直接索引BHT。PC的低$k$位选择一个2位计数器，计数器的最高位即为预测方向。

别名问题（Aliasing）

PC低位直接索引的根本问题是别名冲突（aliasing）：多条不同的分支指令可能映射到BHT的同一个表项，从而相互干扰。当两条或多条分支指令的PC低$k$位相同时，它们共享同一个2位计数器——一条分支的更新会影响另一条分支的预测。

别名冲突有两种类型：

（1）构造性别名（constructive aliasing）。两条别名分支恰好具有相同的方向模式——例如都是强偏向taken。此时共享计数器不会降低准确率，甚至可能加速训练（因为两条分支的训练信息相互强化）。

（2）破坏性别名（destructive aliasing）。两条别名分支具有不同的方向模式——例如一条强偏向taken，另一条强偏向not-taken。此时共享计数器会在两个方向之间来回振荡，导致两条分支的预测都变差。这是BHT准确率下降的主要原因。

别名冲突的概率与BHT的大小和程序中活跃分支的数量有关。设BHT有$2^k$个表项，程序中有$B$条活跃的分支指令（在一个时间窗口内被频繁执行的分支），假设PC低位均匀分布，则发生别名冲突的概率可以用"生日问题"模型近似：

$$P(\text{至少一次冲突}) \approx 1 - e^{-B^2 / (2 \times 2^k)}$$

例如，对于一个4096项的BHT和200条活跃分支，冲突概率为$1 - e^{-200^2/8192} \approx 1 - e^{-4.88} \approx 99.2\%$——几乎必然发生冲突。当BHT增大到16384项时，冲突概率降为$1 - e^{-200^2/32768} \approx 1 - e^{-1.22} \approx 70.4\%$。

性能分析 6 — 别名冲突对预测准确率的影响

为了量化别名冲突的影响，考虑一个简化模型：200条活跃分支，其中70%是强偏向性（偏向度$>$95%），30%是非偏向性的。在一个4096项的BHT中：

场景	无别名准确率	有别名准确率
强偏向$\leftrightarrow$强偏向（同向）	97%	97%（无影响）
强偏向$\leftrightarrow$强偏向（异向）	97%	50%$\sim$70%
强偏向$\leftrightarrow$非偏向	97% / 70%	70%$\sim$85%
非偏向$\leftrightarrow$非偏向	70%	50%$\sim$60%

当两条方向相反的强偏向分支发生别名冲突时，准确率可以从97%暴跌到50%$\sim$70%。虽然这种情况只影响少数分支，但由于这些分支的预测失败次数大幅增加，对整体MPKI的影响显著。

减轻别名冲突的方法

减轻别名冲突有多种技术手段：

（1）增大BHT容量。最直接的方法，但存储开销线性增长，且收益递减。

（2）标签比较（tagged BHT）。在BHT的每个表项中增加一个标签字段（PC的高位），只有标签匹配时才使用该表项的计数器值。标签不匹配时使用默认预测（如BTFNT）。这完全消除了别名冲突，但增加了约50%$\sim$100%的存储开销（标签字段的面积），且需要比较逻辑，增加了访问延迟。

（3）哈希索引。使用PC的多个位段进行XOR哈希来生成索引，而不是直接使用低位。例如将PC的高16位与低16位进行XOR： $$\label{eq:ch13-xor-hash} \text{index} = \text{PC}[k+1:2] \oplus \text{PC}[k+k:k+2]$$

XOR哈希使得PC高位不同的分支更不容易映射到同一表项，有效降低了别名冲突的概率。

（4）多bank/多路。将BHT组织成多路组相联结构，每个索引对应多个计数器，通过标签选择正确的那一个。这类似于组相联Cache的设计，可以在有限的面积增加下显著降低冲突。

（5）全局历史索引。这是从根本上解决别名问题的方向——将全局分支历史与PC一起用于索引，使得同一条分支指令在不同的历史上下文中映射到不同的表项。这就是gshare、gselect和TAGE等高级预测器的基础思想，将在第第 14.0 章章详细讨论。

案例研究 3 — 别名冲突的具体例子

考虑一个4096项（$k=12$）的BHT，使用PC[13:2]作为索引。以下两条分支指令发生了别名冲突：

分支	PC	PC[13:2]（索引）
分支A	0x0040_1234	0x48D（= 1165）
分支B	0x0040_5234	0x48D（= 1165）

两条分支的PC低12位相同（差异在更高位），因此映射到BHT的同一个表项。假设分支A是一个循环回边（95%跳转），分支B是一个错误检查（5%跳转）。它们交替访问同一个2位计数器：

1. 分支A执行：实际T $\to$ 计数器递增

2. 分支A执行：实际T $\to$ 计数器递增（饱和在ST=11）

3. 分支B执行：实际N $\to$ 计数器递减到WT=10

4. 分支B执行：实际N $\to$ 计数器递减到WNT=01

5. 分支A执行：预测N（因为计数器=01），实际T $\to$ 预测错误！

在没有别名冲突时，分支A的准确率应该在95%以上。但由于与分支B共享计数器，分支A的准确率可能下降到70%$\sim$80%——这就是破坏性别名的具体表现。

设计提示

在实际处理器设计中，BHT的别名问题通常不是孤立解决的——现代预测器（如TAGE）通过多个不同长度历史的表来天然地分散别名冲突的影响。TAGE的最短历史表相当于一个传统的BHT，而更长历史的表由于索引空间更大（PC与长历史XOR），别名概率更低。因此，别名问题在现代预测器中更多地表现为"最短历史表的噪声"，可以被更长历史表的正确预测所覆盖。

分支目标缓冲区（BTB）的结构与时序

前面讨论的BHT/方向预测器只解决了"分支往哪个方向走"的问题，但还有一个同样重要的问题：分支跳转到哪里。分支目标缓冲区（Branch Target Buffer, BTB）正是用来回答这个问题的硬件结构。

BTB的基本组织

BTB本质上是一个以分支指令PC为键（key）、以分支目标地址为值（value）的全相联或组相联缓存。其基本结构如图图 13.8所示。

BTB的基本结构。每个表项包含有效位、标签（PC高位）、目标地址和分支类型。

一个BTB表项通常包含以下字段：

• 有效位（Valid, V, 1位）：指示该表项是否包含有效数据。

• 标签（Tag, 10$\sim$20位）：分支指令PC的高位，用于在组相联结构中消除别名冲突。

• 目标地址（Target, 40$\sim$64位）：分支的预测目标地址。在某些实现中，为了节省存储可以只存储目标地址相对于PC的偏移量。

• 分支类型（Type, 2$\sim$3位）：区分条件分支、无条件跳转、间接跳转、函数调用、函数返回等。类型信息用于驱动不同的预测机制（方向预测器、RAS等）。

• 偏移量（Offset, 3$\sim$6位，可选）：分支指令在取指块中的位置。在宽取指的处理器中（每周期取32$\sim$64字节），一个取指块中可能包含多条指令，需要知道分支在哪个位置以确定哪些指令在分支之后需要被丢弃。

BTB的容量与组织方式

BTB的容量选择需要权衡三个因素：（1）覆盖率——BTB需要足够大以容纳程序工作集中的所有活跃分支；（2）访问延迟——更大的BTB访问更慢，可能无法在一个周期内完成查找；（3）面积和功耗——BTB存储以SRAM实现，占用宝贵的芯片面积。

现代处理器的BTB通常采用多级层次结构：

L0 BTB（也称NLP或micro-BTB）：64$\sim$256项，直接映射或2路组相联，单周期访问。L0 BTB存储最近使用的分支目标，命中率较低（70%$\sim$85%），但速度极快，保证取指流水线不停顿。

L1 BTB（主BTB）：4K$\sim$8K项，4路组相联，2$\sim$3周期访问。L1 BTB是主要的分支目标存储，命中率通常在95%$\sim$99%。L1 BTB miss时要么退化为静态预测（BTFNT），要么从L2 BTB获取。

L2 BTB（部分处理器具有）：8K$\sim$16K项，4$\sim$8路组相联，3$\sim$5周期访问。L2 BTB用于覆盖分支工作集特别大的程序（如大型数据库引擎、编译器），减少cold miss和capacity miss。

处理器	L0 BTB	L1 BTB	L2 BTB	总存储
Intel Golden Cove	128项	12K项	—	$\sim$50 KB
AMD Zen 4	64项	6.5K项	12K项	$\sim$60 KB
Apple Firestorm	128项	8K项	16K项	$\sim$80 KB
ARM Cortex-X4	64项	8K项	12K项	$\sim$55 KB
香山昆明湖	128项	4K项	8K项	$\sim$40 KB

现代处理器BTB层次结构对比

BTB的查找时序

BTB查找是取指流水线的关键路径，其时序直接影响处理器的取指吞吐量。在最理想的情况下，BTB查找应该在一个时钟周期内完成——以当前PC为输入，产生下一个PC（如果BTB命中且预测taken）。

但在高频率处理器中（4$\sim$6 GHz），一个时钟周期只有150$\sim$250 ps的时间预算。BTB查找需要完成以下操作：

1. 地址计算：从PC中提取索引位和标签位

2. SRAM读取：以索引访问BTB阵列，读出对应的表项（通常包含多路的数据）

3. 标签比较：将读出表项的标签与PC的标签位进行比较

4. 路选择：在组相联结构中，选择标签匹配的那一路

5. 目标地址输出：将匹配表项的目标地址送到取指地址多路选择器

对于一个4096项、4路组相联的BTB，SRAM阵列的大小约为20$\sim$30 KB（取决于表项宽度），读取延迟约为150$\sim$200 ps——这已经接近甚至超过了一个时钟周期的预算。因此，L1 BTB通常无法在一个周期内完成查找。

设计提示

L0 BTB（micro-BTB）的关键设计目标就是单周期查找。为了满足时序要求，L0 BTB通常使用以下技术：

• 直接映射：避免多路标签比较的延迟。部分设计甚至省略标签（tagless BTB），依赖L1 BTB来纠正别名。

• 极小容量：64$\sim$128项，SRAM阵列极小，读取延迟仅50$\sim$80 ps。

• 下一行预测器（Next Line Predictor, NLP）：一种极端简化的L0 BTB设计——每个表项只存储"下一个取指块的地址"，不区分分支类型，不需要方向预测器。NLP的准确率约为85%$\sim$92%，但延迟极低。

BTB查找的另一个时序挑战来自宽取指。在一个每周期取4$\sim$8条指令的处理器中，一个取指块中可能包含多条分支指令。BTB需要识别出取指块中第一条taken的分支，因为该分支之后的指令都不应该被执行。这需要对取指块中每个可能的分支位置并行查找BTB，然后选择最早的那个taken分支——这个"最早taken分支选择"逻辑是BTB时序的另一个瓶颈。

硬件描述 3 — BTB单周期查找的时序分解

以一个5 GHz处理器（周期=200 ps）的L0 BTB查找为例，分解各阶段的延迟：

阶段	延迟	累积
PC索引位提取	10 ps	10 ps
SRAM阵列读取（128项直接映射）	60 ps	70 ps
标签比较（14位比较器）	25 ps	95 ps
命中/缺失判断 + 类型解码	15 ps	110 ps
目标地址多路选择器	20 ps	130 ps
走线延迟（输出到取指地址寄存器）	30 ps	160 ps
取指地址寄存器建立时间	20 ps	180 ps
总计		180 ps

180 ps在200 ps的周期中只留出20 ps的余量——这非常紧张。如果使用4路组相联而非直接映射，仅多路标签比较和路选择就会增加约30$\sim$40 ps，超出周期预算。这就是为什么L0 BTB几乎总是直接映射或2路组相联的原因。

有些处理器采用了流水线化的BTB查找来缓解时序压力。具体做法是将BTB查找分成2个流水段：第1段完成SRAM读取，第2段完成标签比较和目标地址选择。这种设计使得每段的延迟仅为半个周期左右，放宽了时序约束，代价是BTB查找需要2个周期——如果预测为taken，取指地址在2个周期后才能改变，产生1个周期的取指气泡。这种"1-bubble BTB"设计在某些情况下是可接受的折中，特别是当L0预测器（NLP）能够覆盖大部分taken分支时。

BTB存储优化

BTB的存储开销主要来自目标地址字段（40$\sim$64位/项），对于数千项的BTB，这是一个可观的面积。有几种常用的存储优化技术：

（1）偏移量压缩。对于条件分支和直接跳转，目标地址通常与分支PC之间的距离较小（在$\pm$4 KB$\sim$$\pm$1 MB的范围内）。因此可以只存储目标地址相对于PC的偏移量（12$\sim$20位），而不是完整的64位地址。这可以将目标地址字段的存储缩减60%$\sim$80%。但间接跳转的目标地址范围可能很大，需要完整存储——因此某些设计对不同类型的分支使用不同宽度的目标字段。

（2）目标地址分离。将BTB分为"标签+类型"部分和"目标地址"部分，分别存储在不同的SRAM阵列中。标签+类型部分用于快速判断BTB是否命中和分支类型，目标地址部分只在确认命中且分支预测为taken时才读取。这种分离设计可以降低标签比较阶段的SRAM读取延迟（因为阵列更窄），从而改善时序。

（3）区域BTB（Regional BTB）。观察到一个程序的分支通常聚集在少数几个代码区域中（热循环、频繁调用的函数）。区域BTB为每个区域维护一个基地址，BTB表项只存储目标地址在区域内的偏移量。这可以大幅减少目标地址的存储位数。

硬件描述 4 — BTB表项存储开销的完整分析

考虑一个4096项、4路组相联的L1 BTB，采用偏移量压缩方案。每个表项的位宽如下：

字段	完整地址方案	偏移量压缩方案
有效位 (V)	1 bit	1 bit
标签 (Tag)	14 bits	14 bits
目标地址/偏移量	48 bits	20 bits
分支类型	3 bits	3 bits
取指块内偏移	4 bits	4 bits
每项总计	70 bits	42 bits
4096项总计	35 KB	21 KB

偏移量压缩将BTB存储从35 KB缩减到21 KB，节省40%的面积。但需要注意：20位偏移量只能表示$\pm$512 KB范围内的跳转目标。对于目标距离更远的分支（如跨模块调用），需要额外的"长跳转"表项（存储完整64位地址），或者在BTB缺失后在解码阶段计算完整目标地址。

实际的混合方案通常将BTB分为两部分：大部分表项使用压缩偏移量（覆盖95%以上的分支），少量表项使用完整地址（覆盖长跳转和间接跳转）。例如，3584项$\times$42位（压缩）+ 512项$\times$70位（完整）= 18.4 KB + 4.4 KB = 22.8 KB，在面积和覆盖率之间取得平衡。

返回地址栈（RAS）的设计

返回地址栈（RAS）的基本原理在13.2.4 节节已经介绍——call时push返回地址，ret时pop作为预测目标。本节深入讨论RAS的工程设计细节，包括栈溢出处理、推测性操作与恢复、以及与流水线其他组件的交互。

RAS的基本结构

RAS本质上是一个硬件栈（LIFO缓冲区），其核心参数包括：

• 深度（depth）：栈的最大容量，通常16$\sim$64项。深度决定了RAS能处理的最大嵌套调用深度。

• 项宽度：每项存储一个返回地址（通常为64位虚拟地址或压缩后的地址）。

• 栈顶指针（TOS，Top-of-Stack pointer）：指向栈顶元素，$\lceil \log_2(\text{depth}) \rceil$位。

RAS的存储通常以寄存器阵列（register file）而非SRAM实现，原因是RAS的容量很小（16$\sim$64项），但需要在单周期内完成读写操作，寄存器阵列在小容量下的速度优于SRAM。

栈溢出的处理：环形缓冲区

当函数调用深度超过RAS容量时，会发生栈溢出。最简单的处理方式是将RAS实现为环形缓冲区（circular buffer）：push操作时如果栈满，TOS指针回绕（wrap around），覆盖最旧的表项。pop操作时如果栈空，也回绕到另一端。

环形缓冲区的优点是：当嵌套深度超过RAS容量$D$后，最近$D$层调用的返回地址仍然保存在RAS中。当函数返回从最深层开始逐层退出时，前$D$次返回可以正确预测（因为对应的返回地址没有被覆盖）。只有当退出深度超过$D$时，才开始遇到被覆盖的表项，产生预测错误。

性能分析 7 — RAS深度对预测准确率的影响

RAS深度对预测准确率的影响取决于程序的调用深度分布。表表 13.8给出了不同RAS深度在SPEC CPU 2017整数测试上的返回预测准确率。

RAS深度	平均准确率	最差准确率	溢出频率
8项	94.2%	82%	6.1%
16项	98.5%	93%	1.8%
32项	99.5%	97%	0.4%
64项	99.8%	99%	0.05%

从8项到32项，准确率从94.2%提升到99.5%——这对应着从MPKI $\approx$ 1.2降低到MPKI $\approx$ 0.1（假设返回指令占2%的动态指令）。32$\sim$64项是现代处理器的常见选择，提供了较好的面积-准确率平衡。

推测性RAS操作与恢复

RAS面临的最大工程挑战是推测性操作与恢复。在超标量乱序处理器中，分支预测器在取指阶段就对RAS进行push/pop操作——这些操作是推测性的，因为取指阶段的指令尚未被解码确认为call/ret指令，也可能位于一条预测错误的分支的错误路径上。

当一条被预测错误的分支被检测到时（通常在执行阶段），错误路径上的所有指令都被丢弃。但此时，错误路径上的call/ret指令可能已经对RAS进行了push/pop操作，导致RAS状态被错误地修改。如果不恢复RAS到正确状态，后续的返回预测将全部出错——一次RAS破坏可能导致后续大量返回指令的连锁预测失败。

常用的RAS恢复机制包括以下几种：

（1）TOS指针恢复法（TOS checkpoint）。这是最简单和最常用的方法。核心思想是：每次执行分支预测时，保存当前的TOS指针值；当检测到预测失败时，将TOS恢复到保存的值。

TOS指针恢复法：(a)初始状态，TOS=2；(b)错误路径上的call导致错误push；(c)恢复TOS到保存的值2，RAS回到正确状态。注意addr\_WRONG仍留在物理存储中，但由于TOS已恢复，不会被访问。

TOS指针恢复法的优点是极为简单——只需在每次预测时保存一个$\lceil \log_2(D) \rceil$位的TOS值。对于32项的RAS，每次保存5位即可。其缺点是：如果错误路径上有push操作覆盖了RAS中的有效返回地址（在环形缓冲区中，push会覆盖最旧的表项），仅恢复TOS指针无法恢复被覆盖的数据。

（2）完整RAS快照（full RAS checkpoint）。在每次预测时保存整个RAS的内容，恢复时完整恢复。这可以处理push覆盖的情况，但存储开销巨大——对于32项$\times$64位的RAS，每个checkpoint需要256字节。如果同时有64个飞行中的分支，需要16 KB的checkpoint存储，这在实践中不可接受。

（3）混合方法。结合TOS恢复和有限的数据恢复。例如，当push操作发生溢出时（即将覆盖旧数据），额外保存被覆盖的数据到一个小的备份缓冲区中。恢复时先恢复TOS，再从备份缓冲区中恢复被覆盖的数据。这种方法以少量额外存储换取更好的恢复精度。

案例研究 4 — 香山处理器的RAS恢复设计

开源RISC-V处理器香山（XiangShan）的RAS采用了一种优化的恢复策略：

• RAS深度为32项，采用环形缓冲区实现。

• 每次分支预测时保存TOS指针（5位）和栈顶计数器（counter，用于处理同一地址被多次push的情况）。

• 预测失败恢复时，仅恢复TOS指针，不恢复RAS内容。这在极端情况下可能损失一些返回预测准确率，但避免了复杂的数据恢复逻辑。

• 在提交阶段维护一份"架构RAS"（architectural RAS），只有已提交的call/ret指令才更新架构RAS。当发生严重的预测失败连锁反应时，可以从架构RAS完全重建推测RAS。

这种"推测RAS + 架构RAS"的双轨设计在正常运行时使用推测RAS的快速预测，在最坏情况下可以回退到架构RAS进行完全恢复，是一种实用的工程折中。

RAS预测失败的来源分析

RAS预测失败的来源可以归纳为以下几类，按照在实际工作负载中的影响从大到小排列：

（1）推测性破坏。如前所述，错误路径上的call/ret指令对RAS的错误修改是RAS预测失败的最主要原因。在控制流密集的程序（如编译器、解释器）中，推测性破坏可能占RAS预测失败总量的40%$\sim$60%。

（2）栈溢出。当函数调用深度超过RAS容量时，最旧的返回地址被覆盖。这在递归密集的程序中较常见（如深度优先搜索、某些分治算法）。对于32项的RAS，栈溢出导致的预测失败约占总失败的20%$\sim$30%。

（3）非标准调用模式。包括：

• setjmp/longjmp：longjmp跳过多层函数返回，导致RAS中残留的返回地址与实际执行路径不匹配。

• 协程切换（coroutine switch）：协程之间的控制流转移不遵循标准的call/ret配对。

• 异常处理的栈展开（stack unwinding）：C++异常抛出时会跳过多层函数，类似longjmp。

• 尾调用优化（tail call optimization）：编译器将尾递归优化为循环跳转，ret指令被消除，但RAS中的push记录没有对应的pop。

（4）call/ret识别错误。在BTB冷缺失或别名冲突时，处理器可能无法正确识别一条指令是call还是ret。例如，一条普通的间接跳转被BTB错误地标记为ret，会导致RAS的错误pop操作。

性能分析 8 — RAS预测失败来源分布

在一个采用32项环形RAS、TOS指针恢复的处理器上，SPEC CPU 2017整数子集的RAS预测失败来源分布（近似值）如下：

失败来源	占比
推测性破坏（TOS恢复不完全）	45%
栈溢出（调用深度$>$32）	25%
非标准调用模式	15%
BTB冷缺失/类型识别错误	10%
其他（上下文切换后RAS失效等）	5%

推测性破坏是最大的失败来源，这也是为什么RAS恢复机制的设计如此关键——更好的恢复策略可以将近一半的RAS预测失败消除。

RAS与BTB的交互

RAS的操作需要BTB的配合——处理器需要从BTB的分支类型字段中判断当前取指块中是否包含call或ret指令，才能决定是否进行push或pop操作。这引出了一个微妙的设计问题：BTB的分支类型信息必须在RAS操作之前可用。

在多级预测架构中，这个时序约束通常如下满足：

1. L0 BTB/NLP在Cycle 0查找，输出分支类型信息。

2. 基于分支类型，在Cycle 0的后半周期或Cycle 1的前半周期进行RAS操作：如果类型为call，push当前PC+4；如果类型为ret，pop栈顶作为预测目标。

3. RAS的pop输出与BTB的目标地址通过多路选择器合并，产生最终的预测目标地址。

一个特殊情况是BTB冷缺失——当一条ret指令首次执行时，BTB中没有该指令的记录，处理器无法知道它是一条ret指令，也就不会触发RAS pop操作。此时预测结果是"顺序取指"（PC+4），必然错误。只有在该指令被解码并执行后，才能将其记录到BTB中。从下一次执行开始，BTB才能正确识别它为ret指令并触发RAS操作。

设计权衡 2 — RAS深度与面积功耗

RAS虽然容量小，但由于需要在单周期内完成读写，通常以高速寄存器阵列实现，其每比特面积和功耗都高于SRAM。对于一个64项$\times$64位的RAS：

• 寄存器阵列存储：$64 \times 64 = 4096$位 $\approx$ 0.5 KB

• TOS指针和控制逻辑：$\sim$100位

• checkpoint存储（假设64个飞行分支，每个保存6位TOS）：$64 \times 6 = 384$位

• 总计：$\sim$4580位 $\approx$ 0.56 KB

虽然绝对容量不大，但寄存器阵列的面积效率约为SRAM的3$\sim$5倍（每比特面积更大），因此64项的寄存器RAS在面积上相当于1.5$\sim$2.5 KB的SRAM。是否值得从32项增加到64项，取决于目标工作负载中深度递归/嵌套调用的频率——对于大多数通用处理器，32项已经足够。

分支预测对性能的影响

分支预测对超标量处理器性能的影响可以从定性和定量两个层面来理解。定性上，分支预测失败导致流水线刷新（pipeline flush），丢弃错误路径上的所有指令，浪费已经消耗的取指带宽、解码资源和执行能力。定量上，可以通过分支惩罚周期数、MPKI（每千条指令的预测失败次数）以及IPC的损失来精确衡量。

分支惩罚的计算

当分支预测失败被检测到时，处理器需要：（1）丢弃错误路径上所有流水段中的指令，（2）将前端重定向到正确的目标地址，（3）重新从正确地址开始取指。从分支预测失败被检测到（通常在执行阶段或写回阶段）到新指令开始进入执行阶段之间的周期数，称为分支惩罚（branch misprediction penalty）或前端重填延迟（front-end refill latency）。

分支惩罚的大小取决于流水线中从分支预测到分支解析之间的级数。设分支预测在第$s_p$级完成，分支结果在第$s_r$级解析，则最小分支惩罚为： $$\label{eq:ch13-penalty-basic} P_{\text{min}} = s_r - s_p$$

在现代超标量处理器中，分支预测通常在流水线的第1$\sim$2级完成（BTB查询），而分支条件的解析需要经过取指、解码、重命名、发射、寄存器读取、ALU执行等阶段才能完成。因此分支惩罚通常在12$\sim$20个周期之间，如表表 13.9所示。

处理器	流水线级数	分支预测失败惩罚
Intel Golden Cove	$\sim$20	15–17 cycles
Intel Lion Cove	$\sim$22	17–19 cycles
AMD Zen 4	$\sim$19	13–14 cycles
AMD Zen 5	$\sim$20	13–15 cycles
Apple Firestorm (M1)	$\sim$16	12–14 cycles
Apple Everest (M4)	$\sim$17	12–14 cycles
ARM Cortex-X4	$\sim$17	11–13 cycles
香山昆明湖	$\sim$18	13–15 cycles

现代处理器的分支预测失败惩罚（近似值）

需要注意的是，表表 13.9中的惩罚是"最小惩罚"——即假设重定向后I-Cache立即命中、无其他阻塞因素。在实际运行中，如果重定向后的目标地址在I-Cache中缺失（I-Cache miss），或者I-TLB缺失，实际惩罚会更大。在极端情况下（如I-Cache miss需要访问L2），分支预测失败的实际惩罚可以达到30$\sim$50个周期。

案例研究 5 — 分支惩罚的细分：前端惩罚与后端惩罚

分支预测失败的总惩罚可以细分为两部分：

前端重填惩罚（front-end refill penalty）：从预测失败被检测到，到正确路径的第一条指令进入后端（发射队列）。这部分包括：

• 错误检测和重定向（1$\sim$2周期）

• I-Cache/I-TLB访问（2$\sim$4周期，假设命中）

• 预解码和解码（2$\sim$3周期）

• 重命名和分发（1$\sim$2周期）

前端重填惩罚通常为6$\sim$11周期。

后端排空惩罚（back-end drain penalty）：错误路径上的指令可能已经占据了ROB、发射队列、物理寄存器等后端资源。这些资源在flush时被释放，但如果后端在flush前已经接近饱和，新的正确指令可能因为资源不足而无法立即进入后端，需要等待资源释放。后端排空惩罚在0$\sim$5周期之间，取决于flush时刻后端的占用率。

总惩罚$P$为前端重填惩罚与后端排空惩罚中较大的那个： $$\label{eq:ch13-penalty-detailed} P = \max(P_{\text{front-end}}, P_{\text{back-end}})$$

在大多数情况下，前端重填惩罚是主导因素（$P_{\text{front-end}} > P_{\text{back-end}}$），因为乱序处理器通常有足够的ROB和发射队列深度来吸收后端排空延迟。但在极度资源紧张的场景（如SMT共享模式下），后端排空惩罚可能成为瓶颈。

减小分支惩罚的一种重要技术是提前分支解析（early branch resolution）。对于某些类型的分支，不必等到执行阶段才能确认预测是否正确：

• 无条件跳转：在解码阶段就能确认目标地址（通过提取指令中的立即数）。如果解码结果与BTB预测一致，则确认正确；不一致则在解码阶段就进行重定向，惩罚仅3$\sim$5周期。

• 已知条件的条件分支：如果分支的条件操作数已经就绪（例如通过前面的比较指令已经更新了条件码），某些处理器可以在发射阶段而非执行阶段解析分支，减少1$\sim$2周期的惩罚。

分支惩罚对有效IPC的影响可以用以下模型来量化。设理想IPC为$\mathrm{IPC}_{\text{ideal}}$（假设分支预测完美），分支指令在全部指令中的比例为$f_b$，预测失败率为$m$，分支惩罚为$P$个周期，则由分支预测失败导致的额外CPI开销为： $$\label{eq:ch13-cpi-branch} \mathrm{CPI}_{\text{branch}} = f_b \times m \times P$$

实际IPC与理想IPC的关系为： $$\label{eq:ch13-ipc-actual} \mathrm{IPC}{\text{actual}} = \frac{1}{\frac{1}{\mathrm{IPC}{\text{ideal}}} + \mathrm{CPI}{\text{branch}}} = \frac{1}{\frac{1}{\mathrm{IPC}{\text{ideal}}} + f_b \cdot m \cdot P}$$

性能分析 9 — 分支惩罚的量化示例

考虑一个6-wide乱序超标量处理器，参数如下：

• 理想IPC（无分支惩罚）：$\mathrm{IPC}_{\text{ideal}} = 4.0$

• 分支指令比例：$f_b = 15\%$

• 分支预测失败惩罚：$P = 15$个周期

对于不同的预测准确率，由式 (13.17)可得：

准确率	失败率$m$	$\mathrm{CPI}_{\text{branch}}$	实际IPC
100%	0	0	4.00
99%	1%	0.0225	3.66
98%	2%	0.045	3.38
97%	3%	0.0675	3.14
96%	4%	0.090	2.93
95%	5%	0.1125	2.74
90%	10%	0.225	2.13
85%	15%	0.3375	1.73

可以看到，预测准确率从97%提高到99%——仅仅2个百分点——就可以使IPC从3.14提升到3.66，提升幅度达16.6%。而准确率从95%下降到90%——5个百分点——就导致IPC从2.74暴跌到2.13，损失22%。这体现了分支预测准确率对超标量处理器性能的巨大杠杆效应。

图图 13.10更直观地展示了预测准确率与IPC之间的非线性关系。

分支预测准确率与IPC的关系：不同的惩罚周期和分支比例下的曲线。流水线越深（惩罚越大）或分支越密集，曲线下降越陡，对预测准确率的敏感度越高。

从图图 13.10中可以得出几个重要结论：

（1）在准确率较高的区间（95%$\sim$100%），曲线斜率较大——每提高1个百分点的准确率，IPC的提升非常显著。这解释了为什么现代处理器愿意投入大量硬件资源来将准确率从96%提高到98%。

（2）更深的流水线（$P=20$ vs. $P=15$）使曲线整体下移，且在低准确率区间下降更快。这意味着深流水线处理器对分支预测器的要求更高——Intel的Pentium 4（31级流水线，惩罚约20$\sim$30周期）正是因为分支预测器无法弥补超深流水线的惩罚而在IPC上表现不佳。

（3）分支密集的程序（$f_b=20\%$）对预测准确率更加敏感。这也是为什么编译器优化中要尽量减少分支指令的数量（例如通过if-conversion将条件分支转换为条件移动指令**cmov**或条件选择指令）。

MPKI

MPKI（Misses Per Kilo Instructions，每千条指令的预测失败次数）是衡量分支预测器性能的最常用指标。与预测准确率相比，MPKI直接反映了预测失败对指令流吞吐量的影响，更具有工程上的直观性。

MPKI的定义为： $$\label{eq:ch13-mpki-def} \text{MPKI} = \frac{\text{分支预测失败次数}}{\text{总指令数}} \times 1000 = f_b \times m \times 1000$$

其中$f_b$为分支指令占比，$m$为预测失败率。例如，若$f_b = 15\%$，$m = 3\%$，则MPKI $= 0.15 \times 0.03 \times 1000 = 4.5$。

表表 13.10给出了一些现代处理器和预测器在SPEC CPU 2017上的典型MPKI数据。

预测器/处理器	SPEC CPU INT平均	最好	最差
简单两位计数器（4K项）	12–15	5	25+
gshare（64K项）	6–9	3	18
TAGE（32KB）	3–5	1.5	10
TAGE-SC-L（64KB）	2.5–4	1.0	8
Intel Golden Cove	3–5	1.5	9
AMD Zen 4	3–5	1.5	9
Apple Firestorm	2.5–4	1.0	8

现代处理器在SPEC CPU 2017部分基准上的分支MPKI（近似值）

MPKI与IPC之间的关系可以进一步推导。将式 (13.18)代入式 (13.17)： $$\label{eq:ch13-ipc-mpki} \mathrm{IPC}{\text{actual}} = \frac{1}{\dfrac{1}{\mathrm{IPC}{\text{ideal}}} + \dfrac{\text{MPKI}}{1000} \cdot P}$$

这个公式清晰地表明：降低MPKI和减小分支惩罚$P$是提高实际IPC的两条途径。降低MPKI依赖于更好的预测算法和更大的预测器存储，减小$P$则取决于流水线设计——缩短前端级数或者在更早的阶段进行分支解析（如在解码阶段就处理无条件跳转，减少其惩罚）。

MPKI作为设计指标相比准确率有一个重要优势：它直接量化了对指令流的影响。考虑两个程序，程序A的分支比例为8%，预测准确率为94%（MPKI=4.8）；程序B的分支比例为20%，预测准确率为97%（MPKI=6.0）。虽然程序B的准确率更高，但由于分支更密集，其MPKI反而更高——意味着分支预测对程序B性能的影响更大。

性能分析 10 — MPKI的分解：方向预测 vs. 目标预测

总MPKI可以分解为多个来源的贡献：

$$\text{MPKI}_{\text{total}} = \text{MPKI}_{\text{dir}} + \text{MPKI}_{\text{BTB}} + \text{MPKI}_{\text{RAS}} + \text{MPKI}_{\text{indirect}}$$

其中各项分别表示方向预测失败、BTB缺失/错误、RAS预测失败和间接跳转目标预测失败的贡献。在现代处理器上的典型分布如下：

MPKI来源	绝对值	占比
方向预测失败（MPKI$_{\text{dir}}$）	2.5$\sim$3.5	65%$\sim$75%
BTB缺失/错误（MPKI$_{\text{BTB}}$）	0.3$\sim$0.8	8%$\sim$15%
RAS预测失败（MPKI$_{\text{RAS}}$）	0.1$\sim$0.3	3%$\sim$8%
间接跳转目标失败（MPKI$_{\text{indirect}}$）	0.5$\sim$1.0	12%$\sim$20%
总计	3.5$\sim$5.5	100%

方向预测失败是最大的贡献者，这就是为什么后续章节用最大篇幅讨论方向预测算法。但间接跳转目标预测的贡献也不可忽视——在面向对象的C++程序（如omnetpp）和解释器工作负载中，间接跳转的MPKI贡献可以超过方向预测。

设计权衡 3 — 预测器大小与MPKI的边际收益

增加预测器的存储容量可以降低MPKI，但收益是递减的。以TAGE预测器为例，图图 13.11展示了存储容量与MPKI的关系。

从图中可以看到：（1）从4KB增加到16KB，TAGE的MPKI从9.5降到5.2，降幅达45%——收益非常显著。（2）从32KB增加到128KB，MPKI仅从4.0降到2.9，降幅仅27%——收益明显递减。（3）在给定的面积预算下，选择更先进的算法（TAGE vs. gshare）比单纯增加容量更有效：16KB的TAGE（MPKI=5.2）优于128KB的gshare（MPKI=5.2），而所需面积仅为后者的1/8。

预测精度与IPC的关系

在上一小节的分析基础上，可以进一步量化"每提高1%的预测准确率能带来多少IPC提升"。这个数字并非固定值，它取决于当前的准确率水平、流水线深度和工作负载特征。

设当前预测准确率为$a$，则预测失败率$m = 1 - a$。对式 (13.17)中的$\mathrm{IPC}_{\text{actual}}$关于$a$求导，可以得到预测准确率变化对IPC的敏感度：

$$\frac{\partial \mathrm{IPC}}{\partial a} = \frac{f_b \cdot P}{\left(\dfrac{1}{\mathrm{IPC}_{\text{ideal}}} + f_b(1-a)P\right)^2}$$

由于分母中含有$(1-a)$项，当$a$越接近1（准确率越高），分母越小，$\partial \mathrm{IPC}/ \partial a$越大——即在高准确率区间，每提高1%准确率带来的IPC提升更显著。这一数学性质解释了为什么处理器设计者在已经达到96%$\sim$97%准确率后，仍然愿意投入大量资源来追求每一个百分点的提升。

为了给出具体的数值感受，表表 13.11计算了不同准确率区间下每提高1个百分点准确率所带来的IPC变化（参数：$\mathrm{IPC}_{\text{ideal}}=4.0$，$f_b=15\%$，$P=15$）。

准确率区间	IPC变化	相对提升	说明
90%$\to$91%	$2.13 \to 2.22$	+4.2%	提升显著但基数低
93%$\to$94%	$2.52 \to 2.65$	+5.2%	中等提升
95%$\to$96%	$2.74 \to 2.93$	+6.9%	高准确率区间边际收益上升
97%$\to$98%	$3.14 \to 3.38$	+7.6%	边际收益持续上升
98%$\to$99%	$3.38 \to 3.66$	+8.3%	接近理想IPC
99%$\to$100%	$3.66 \to 4.00$	+9.3%	最大边际收益

每提高1个百分点预测准确率所带来的IPC变化

表表 13.11的结果看似违反直觉——通常认为越接近极限，边际收益越低。但对于分支预测而言，情况恰好相反：准确率从99%提高到100%的IPC收益（9.3%）是从90%提高到91%的IPC收益（4.2%）的两倍多。这是因为分支预测的性能模型不是线性的——每次预测失败都会导致一个固定周期数的"气泡"（bubble）插入流水线，而在高IPC情况下，每个气泡浪费的有效指令更多。

为什么从97%提升到99%的影响远大于从90%提升到92%？虽然两者都是2个百分点的改进，但它们的效果完全不同。可以用相对改进的视角来理解：

从90%到92%，失败率从10%降到8%，相对降低了20%。 从97%到99%，失败率从3%降到1%，相对降低了67%。

失败率的相对降幅决定了CPI$_{\text{branch}}$的相对降幅（因为$\mathrm{CPI}_{\text{branch}} = f_b \cdot m \cdot P$是$m$的线性函数）：

• 90%$\to$92%：$\mathrm{CPI}_{\text{branch}}$从0.225降到0.180，绝对降低0.045

• 97%$\to$99%：$\mathrm{CPI}_{\text{branch}}$从0.0675降到0.0225，绝对降低0.045

有趣的是，两者的$\mathrm{CPI}_{\text{branch}}$绝对降幅相同（都是0.045）！但由于CPI$_{\text{branch}}$在97%时的基线值更小（总CPI更低、IPC更高），同样的CPI绝对降低对IPC的相对提升更大。用数学语言表达，IPC的相对变化为： $$\label{eq:ch13-relative-ipc-change} \frac{\Delta \mathrm{IPC}}{\mathrm{IPC}} \approx \frac{f_b \cdot \Delta m \cdot P}{\frac{1}{\mathrm{IPC}{\text{ideal}}} + f_b \cdot m \cdot P} \cdot \mathrm{IPC}{\text{actual}}$$

在$m$较小时（高准确率区间），分母更小，因此同样的$\Delta m$带来更大的相对IPC提升。这一数学性质的工程含义是：在预测器已经很好的基础上再提升1个百分点，其投资回报率远高于在预测器较差时提升1个百分点。这就是为什么顶级处理器设计团队愿意投入数十人年的工程努力和数百KB的芯片面积来追求最后1$\sim$2个百分点的准确率提升。

性能分析 11 — 分支预测准确率的"复利效应"

一个有趣的类比是分支预测的"复利效应"。考虑一个4-wide的处理器，假设没有其他性能瓶颈，当MPKI=5时（每200条指令一次预测失败），每次失败浪费15个周期，等效于$15 \times 4 = 60$条指令的执行机会。平均来看，处理器每200条有效指令就浪费60条指令的产能，效率为$200/(200+60) \approx 77\%$。

如果将MPKI降低到2.5（每400条指令一次失败），同样的15周期惩罚只浪费60条指令的产能，效率提高到$400/(400+60) \approx 87\%$。MPKI减半，效率提升了13%——这就是非线性效应的体现。

进一步，当MPKI降低到1（每1000条指令一次失败），效率为$1000/(1000+60) \approx 94.3\%$。从MPKI=5到MPKI=1，MPKI降低了80%，而效率从77%提升到94.3%，绝对提升达17.3个百分点。

分支预测器的基本接口

分支预测器作为超标量处理器前端的关键组件，需要与流水线的其他部分紧密协作。本节从工程实现的角度讨论三个核心问题：预测发生在流水线的哪个阶段？预测器输出什么信息？预测器如何被训练和更新？

预测的时机

分支预测器必须尽早给出结果，因为它直接决定了下一个周期要取指的地址。在理想情况下，分支预测应该在取指的第一个时钟周期内完成，使得每个周期都能连续不断地取指，不产生取指气泡（fetch bubble）。但是，随着预测器的复杂度增加（如TAGE需要多次表查询和比较逻辑），单周期完成预测变得越来越困难。

现代高性能处理器普遍采用多级预测（multi-level prediction）策略：在流水线的不同阶段部署多个预测器，复杂度和精度逐级递增，如图图 13.12所示。

多级分支预测架构。L0预测器在单周期内给出快速预测，L1预测器在后续周期给出更精确的预测。如果L1的结果与L0不同，则覆盖（override）L0的预测并重定向取指。

L0预测器（也称为快速预测器或"下一行预测器"）。在流水线的第1个周期工作，必须在一个时钟周期内给出结果。由于时间预算极紧（在5 GHz频率下仅200 ps），L0预测器通常非常简单——例如一个小型BTB配合一个简单的方向预测器（如两位计数器）。L0预测器的准确率可能只有85%$\sim$90%，但它保证了取指流水线不会出现气泡。ARM Cortex系列处理器广泛使用的NLP（Next Line Predictor，下一行预测器）就是一种典型的L0预测器，它只预测下一个取指地址是顺序的下一行还是一个分支目标。

L1预测器（也称为主预测器或慢速预测器）。在流水线的第2$\sim$3个周期工作，有更充裕的时间预算来执行复杂的预测算法。现代处理器的主预测器通常采用TAGE或者TAGE-SC-L算法，包含多个不同历史长度的表，需要多次hash和比较操作。L1预测器的准确率可以达到96%$\sim$99%。

当L1预测器的结果与L0预测器不同时，L1会覆盖（override）L0的预测，并将取指前端重定向到L1预测的地址。这次覆盖本身会引入一个小的惩罚——通常1$\sim$2个周期的取指气泡——但这比等到执行阶段才发现预测错误（15$\sim$20周期惩罚）要好得多。覆盖的频率取决于L0和L1的精度差距：如果L0很准确，覆盖就很少发生；如果L0较简单，覆盖会较频繁，但每次覆盖只有小的惩罚。

设计提示

多级预测器的一个关键设计决策是L0和L1的精度/延迟权衡。如果L0太简单（如只有一个方向位），频繁的覆盖会导致取指带宽的有效利用率下降。如果L0太复杂，其延迟会增加，可能无法在一个周期内完成，反而引入更大的取指气泡。实践中，L0的准确率达到90%$\sim$93%是一个较好的平衡点——此时覆盖率约为7%$\sim$10%，平均每10$\sim$14个取指块有一次覆盖，对取指带宽的影响有限。

某些处理器还部署了L2预测器或后端校验器（back-end verifier）。例如AMD Zen系列的"TAGE校验"机制：在解码阶段检查指令类型是否与BTB记录的类型一致（例如BTB记录为条件分支，但解码后发现是无条件跳转），如果不一致则进行更正。Intel的部分设计中也有类似的在解码阶段纠正无条件跳转目标地址的机制——由于无条件跳转的目标可以从指令编码中直接计算得到，在解码阶段就能验证BTB中的目标是否正确，比等到执行阶段验证减少了10个周期以上的惩罚。

多级预测中的覆盖率（override rate）是一个关键的性能指标。覆盖率定义为L1预测器与L0预测器结果不同的次数占总预测次数的比例。覆盖率过高意味着L0预测器太不准确，频繁的覆盖导致取指带宽浪费；覆盖率过低则可能意味着L1预测器没有显著优于L0，不值得增加L1的面积和功耗。

性能分析 12 — 多级预测的带宽效率分析

考虑一个具有L0和L1预测器的系统，参数如下：

• L0准确率：$a_0 = 90\%$

• L1准确率：$a_1 = 97\%$

• L0延迟：1周期（无取指气泡）

• L1延迟：3周期（覆盖时产生2周期气泡）

L1覆盖L0的概率为L0预测错误但L1预测正确的概率加上两者预测不同且L1正确的概率。近似地，覆盖率$\approx a_1 - a_0 = 7\%$。每次覆盖产生2周期气泡，等效于每100个取指块有7次覆盖，共14个周期的气泡。

取指带宽效率为： $$\eta_{\text{fetch}} = \frac{100}{100 + 14} \approx 87.7\%$$

与纯L1预测器（每次3周期延迟，即只有$100/300 = 33\%$的带宽效率）相比，多级设计的带宽效率高得多。与纯L0预测器（100%带宽效率但10%的方向错误率）相比，多级设计以12.3%的带宽损失换取了7个百分点的方向准确率提升——这是一个非常有利的权衡。

图图 13.13展示了一个典型的多级预测时序。

多级预测的三种时序场景：正确预测（无开销）、L1覆盖（1个气泡）和预测失败（需要清除整个流水线）

预测结果的格式

分支预测器每个周期需要向取指单元输出完整的预测信息。一个预测结果通常包含以下字段：

（1）下一个取指地址（Next Fetch Address）。这是最核心的输出，直接送到I-Cache和I-TLB。如果预测当前取指块中没有taken的分支，则下一个取指地址为当前地址加上取指宽度（如+32字节或+64字节）；如果预测存在taken分支，则为该分支的预测目标地址。

（2）方向预测（Direction Prediction）。对于当前取指块中的每条分支指令，给出taken或not-taken的预测。在宽取指的处理器中（如每周期取8条指令），取指块中可能包含多条分支指令，需要对每一条都给出方向预测。通常使用一个位向量来表示，每个比特对应取指块中一个可能的分支位置。

（3）分支类型（Branch Type）。BTB中通常存储分支指令的类型信息，包括：条件分支、无条件直接跳转、间接跳转、函数调用、函数返回等。不同类型的分支需要使用不同的预测机制（方向预测器、BTB、间接分支预测器、RAS），类型信息用于驱动正确的预测源。

（4）预测目标地址（Predicted Target Address）。当分支被预测为taken时，BTB提供目标地址。对于函数返回指令，目标地址来自RAS。

（5）置信度（Confidence）。部分高级预测器还输出预测的置信度信息——表示预测器对自身预测正确性的估计。高置信度表示预测器"确信"当前预测是正确的，低置信度表示预测器不确定。置信度信息可以用于多种优化：

• 选择性流水线刷新（selective flushing）：对于低置信度的分支，可以提前准备两条路径的指令（dual-path execution或eager execution），当分支解析后只丢弃错误路径。

• 资源分配优化：对于低置信度分支后的指令，可以减少为其分配的执行资源（如不向Load/Store Queue写入），降低预测失败时恢复的开销。

• 线程调度（在SMT处理器中）：低置信度的分支表明该线程即将发生预测失败，可以将执行资源优先分配给其他线程。

图图 13.14展示了一个预测器输出的完整数据结构。

分支预测器的输出格式。$N$为取指块中可能包含的最大分支数。

需要特别注意的是，预测器在每个周期产生预测时，还需要生成一个预测标签（prediction tag）或预测元信息（prediction metadata），用于后续的训练更新。这些元信息通常包括：使用了哪个预测表、匹配了哪个表项、当前的全局历史值等。这些信息需要随指令一起在流水线中传递，直到分支指令被执行并解析出正确方向后，才能用来更新预测器的状态。元信息的存储开销不可忽视——在TAGE预测器中，每条分支的元信息可能需要20$\sim$40位。

硬件描述 5 — 预测元信息的存储开销分析

考虑一个TAGE预测器，包含5个不同历史长度的预测表。每条分支指令的预测元信息需要记录：

元信息字段	位数
提供预测的表编号（provider）	3 bits
备选提供者表编号（alt-provider）	3 bits
provider表项的索引	12 bits
provider表项的标签	10 bits
provider计数器值	3 bits
alt-provider计数器值	3 bits
预测时的全局历史指纹（用于恢复）	8 bits
总计	42 bits

在一个乱序窗口中最多可能有64$\sim$128条未解析的分支指令同时存在于流水线中。如果每条需要42位的元信息，总存储开销为$128 \times 42 = 5376$位 $\approx$ 672字节。这些元信息通常存储在一个专门的分支队列（Branch Queue）或与ROB合并存储。

预测更新的时机

分支预测器的训练（training）或更新（update）是指在分支的实际方向被确定后，将结果反馈给预测器以修正其内部状态。更新的时机是预测器设计中最微妙的问题之一，主要有两种策略：推测更新（speculative update）和提交后更新（commit-time update），各有优劣。

推测更新（speculative update）是指在分支解析完成后立即更新预测器，无需等待该分支指令从ROB提交。其优点是训练信息反馈速度快——从分支执行到预测器更新之间的延迟最小，后续遇到相同模式的分支可以更快地受益于更新后的状态。其缺点是：如果后续发现有更早的分支预测失败，需要对流水线进行恢复（squash），此时已经做出的推测更新可能是基于错误路径上的分支结果，需要撤销。撤销推测更新（undo speculative update）需要额外的硬件支持，增加了设计复杂度。

提交后更新（commit-time update 或 retire-time update）是指只有当分支指令从ROB正式提交后，才更新预测器状态。其优点是简单且正确——只有已提交的指令是确定正确的，不存在撤销的需要。其缺点是训练延迟较大——分支从执行到提交可能经过多个周期（尤其是当前面有长延迟指令阻塞提交时），这段时间内如果同一个分支再次被取指，预测器使用的仍然是旧的状态。

两种预测器更新策略：推测更新（分支执行后立即更新）和提交后更新（分支提交后更新）

表表 13.12对比了两种更新策略的特性。

特性	推测更新	提交后更新
训练延迟	低（执行后立即）	高（需等到提交）
正确性	需要撤销机制	天然正确
硬件复杂度	高（需要checkpoint/undo）	低
对紧密循环的效果	好（快速适应）	较差（可能错过）
对乱序提交的影响	无（不依赖提交）	有（长延迟指令阻塞）

推测更新与提交后更新的对比

在实践中，现代处理器通常对预测器的不同组件采用不同的更新策略：

• 方向预测器（如TAGE的计数器）：多数采用提交后更新。理由是计数器的更新只是简单的加减操作，即使延迟几个周期影响也不大；而且TAGE表中一个计数器可能被多个分支别名（alias）共享，推测更新后撤销的逻辑非常复杂。

• 全局历史寄存器（GHR）：必须采用推测更新。GHR是方向预测器的索引输入，如果等到提交才更新，后续所有分支预测都会使用过时的历史信息，严重影响准确率。当预测失败需要恢复时，通常使用checkpoint机制来恢复GHR到正确状态。

• BTB：通常采用提交后更新。BTB中存储的是目标地址，对于直接跳转来说目标地址不会变化，更新延迟不影响正确性。间接跳转的目标地址可能变化，但也通常在提交后更新。

• RAS：采用推测更新，即在预测阶段就进行push/pop操作。原因是RAS的状态直接影响函数返回的预测目标，如果延迟更新会导致嵌套调用中的返回地址不正确。恢复时通过保存的TOS指针来回退。

案例研究 6 — 全局历史寄存器的推测更新与恢复

全局历史寄存器（GHR）记录了最近$N$条分支的方向（taken=1, not-taken=0），是TAGE等预测器的关键索引输入。由于每个周期可能取出多条分支指令，GHR必须在预测时就推测性地更新——将当前预测的方向追加到GHR中，供下一次预测使用。

考虑以下场景：

1. 周期$t$：分支A被预测为taken，GHR从$H_0$更新为$H_1 = (H_0 \ll 1) | 1$

2. 周期$t+1$：分支B使用$H_1$进行预测，被预测为not-taken，GHR更新为$H_2 = (H_1 \ll 1) | 0$

3. 周期$t+5$：分支A执行完毕，发现预测错误，实际方向为not-taken

此时需要恢复GHR。常用的方法是：在每条分支进入流水线时，保存当时的GHR值（作为checkpoint）。恢复时，将GHR回退到分支A的checkpoint值$H_0$，然后用正确的方向更新：$H_{\text{correct}} = (H_0 \ll 1) | 0$。分支B及其后所有推测分支的影响被自动消除。

这种checkpoint方法的存储开销为：每个飞行中的分支需要保存一份GHR副本。如果GHR长度为128位、同时最多有64个飞行中的分支，则需要$128 \times 64 = 8192$位（1 KB）的checkpoint存储。为了减小开销，某些实现使用压缩checkpoint或者只为每个取指块（而非每条分支）保存一个checkpoint。

硬件描述 6 — GHR的折叠哈希（Folded History）

当GHR长度$L$很长（如128$\sim$512位）时，直接将GHR用作预测表的索引会导致索引位数过多，需要极大的表。实际中使用折叠哈希（folded history）来将长GHR压缩为较短的索引。

最简单的折叠方法是将GHR分成$\lceil L/k \rceil$个$k$位的段，然后逐段进行XOR： $$\label{eq:ch13-folded-hash} H_{\text{fold}}[k{-}1:0] = \text{GHR}[k{-}1:0] \oplus \text{GHR}[2k{-}1:k] \oplus \text{GHR}[3k{-}1:2k] \oplus \cdots$$

例如，将128位的GHR折叠为12位的索引，需要$\lceil 128/12 \rceil = 11$次XOR操作。但每次XOR只是$k$位的按位操作，硬件开销极小（$k$个2输入XOR门级联）。

折叠哈希的关键性质是增量更新（incremental update）：当GHR追加一个新的分支结果时，折叠哈希可以通过以下步骤更新，而不需要重新计算整个XOR链：

1. 将旧的折叠值左移1位（环形移位）

2. XOR上新追加的分支方向位（在最低位）

3. XOR上被移出GHR末尾的最旧分支方向位（在对应位位置）

增量更新只需2次单位XOR操作和1次环形移位，延迟极低（约1个门延迟），使折叠哈希可以在每个周期内完成更新，不影响预测器的时序关键路径。这一技术在TAGE等多表预测器中被广泛使用——每个表使用不同折叠长度的哈希，从而利用不同长度的历史信息。

设计权衡 4 — 更新延迟与预测准确率

更新延迟对预测准确率的影响取决于工作负载的特征。对于分支密集的紧密循环（如链表遍历、二叉树搜索），同一条分支指令在短时间内被多次执行。如果使用提交后更新，训练延迟可能导致预测器在循环的前几次迭代中使用的仍是过时状态，产生不必要的预测失败。

考虑一个10次迭代的循环，循环体只有5条指令（包含1条回边分支）。在一个4-wide处理器中，循环体约需2个周期执行完，整个循环需要约20个周期。如果提交延迟为8个周期，则训练信息需要约10个周期（执行+提交）才能反馈到预测器。这意味着循环的第1$\sim$5次迭代的训练信息可能在循环结束前才反馈到预测器——对于这个特定的循环实例，这些训练信息完全没有用。

相比之下，推测更新可以在分支执行后2$\sim$3个周期内完成反馈，使后续迭代能够受益。在实测中，推测更新全局历史相比提交后更新可以降低MPKI约5%$\sim$10%。

分支预测器的总体架构

将前面讨论的各个组件整合在一起，图图 13.16展示了一个现代超标量处理器分支预测子系统的总体架构。

现代超标量处理器分支预测子系统的总体架构

分支预测的完整工作流程如下：

Step 1: 预测查询。以当前取指地址（PC）和全局历史寄存器（GHR）为输入，同时查询四个组件：BTB、方向预测器、RAS和间接分支预测器。这些查询在同一个周期内并行进行。

Step 2: 结果选择。BTB的查询结果包含分支的目标地址和类型信息。根据类型信息选择正确的预测源：如果是条件分支，使用方向预测器的结果来决定是否跳转；如果方向为taken，使用BTB中的目标地址。如果是函数返回，使用RAS栈顶的地址。如果是间接跳转，使用间接分支预测器的目标地址。

Step 3: 生成下一取指地址。综合所有预测结果，生成下一个周期的取指地址。如果当前取指块中没有匹配BTB的分支（即BTB miss），则下一取指地址为顺序地址（PC + 取指宽度）。

Step 4: 更新GHR。将当前预测的分支方向推测性地追加到GHR中，供下一次预测使用。

Step 5: 训练更新。当分支在执行阶段解析出正确方向后（或在提交阶段），将实际结果反馈给各预测组件进行训练。

表表 13.13给出了各预测组件在现代处理器中的典型存储资源分配。

组件	典型容量	存储开销	说明
L0 BTB	64–256项	2–4 KB	快速路径，1周期延迟
L1 BTB	4K–8K项	16–40 KB	主BTB，多周期延迟
L2 BTB	8K–16K项	32–64 KB	部分处理器有
方向预测器	—	16–64 KB	TAGE: 多个表+计数器
RAS	16–64项	0.5–2 KB	含checkpoint开销
间接分支预测器	1K–4K项	4–16 KB	路径历史索引
GHR	128–512位	$<$0.1 KB	含checkpoint
合计	—	70–190 KB	—

现代处理器中分支预测子系统的典型资源分配

从表表 13.13可以看出，分支预测子系统的总存储开销在70$\sim$190 KB之间——这已经接近甚至超过了L1 I-Cache的容量（通常32$\sim$64 KB）。在Apple M系列处理器中，分支预测器的存储资源甚至超过了L1 I-Cache，这体现了Apple对分支预测的极端重视。这些存储资源都需要在芯片上以SRAM或寄存器阵列的形式实现，占用了可观的面积和功耗预算。

不同分支类型的预测流程

前面已经分别介绍了各个预测组件，现在将它们串联起来，说明不同类型的分支指令在预测子系统中的完整处理流程。

条件分支（如**beq**, blt）的预测流程：

1. BTB以PC为索引查找，命中后返回：目标地址 + 类型="条件分支"

2. 方向预测器以PC和GHR为索引，输出taken/not-taken

3. 如果方向预测为taken：下一取指地址 = BTB提供的目标地址

4. 如果方向预测为not-taken：下一取指地址 = PC + 取指宽度（顺序取指）

5. GHR推测性更新：追加预测方向

无条件直接跳转（如**jal**）的预测流程：

1. BTB命中后返回：目标地址 + 类型="无条件跳转"

2. 无需方向预测（总是taken）

3. 下一取指地址 = BTB提供的目标地址

4. 如果BTB缺失：退化为顺序取指，在解码阶段检测到**jal**后重定向

间接跳转（如**jalr**用于虚函数调用）的预测流程：

1. BTB命中后返回：类型="间接跳转"

2. 间接分支预测器以PC和全局路径历史为索引，查找预测的目标地址

3. 下一取指地址 = 间接分支预测器的目标地址（若命中），或BTB的上次目标地址（若间接预测器缺失）

函数返回（如**ret**）的预测流程：

1. BTB命中后返回：类型="函数返回"

2. RAS pop操作：从栈顶弹出返回地址

3. 下一取指地址 = RAS pop的返回地址

4. 注意：BTB中虽然也存储了上次的返回目标地址，但优先使用RAS的结果，因为RAS能准确追踪调用栈的动态变化

设计提示

在实际硬件中，上述四种流程的"选择"是通过BTB的类型字段驱动的。BTB的类型字段决定了后续使用哪个预测源（方向预测器、间接预测器、RAS），以及是否需要更新GHR。这使得BTB成为了整个预测子系统的"调度中心"——BTB缺失不仅意味着目标地址未知，还意味着处理器无法判断当前指令是什么类型的分支，可能导致所有预测机制都无法正确工作。这就是为什么BTB的命中率对整体预测性能至关重要。

分支预测与现代工作负载

随着处理器架构的演进和软件生态的变化，分支预测面临的挑战也在不断变化。本节简要讨论现代工作负载对分支预测器的新需求。

服务器工作负载的分支特征

数据中心的服务器工作负载（如Web服务器、数据库查询、RPC框架）具有与传统桌面/HPC工作负载不同的分支特征：

• 指令足迹巨大。一个典型的Web服务栈（含HTTP解析、应用逻辑、数据库查询、序列化/反序列化）的热代码区域可能跨越数十MB的指令，远超BTB和方向预测器的容量。这导致频繁的容量缺失（capacity miss），预测器的"有效准确率"低于其在SPEC基准上的表现。

• 间接跳转比例高。面向对象的Java/C++服务框架大量使用虚函数和接口调用，间接跳转的比例可以达到动态指令的3%$\sim$5%（而SPEC INT中通常只有1%$\sim$2%）。

• 上下文切换频繁。服务器进程之间的上下文切换会清空（或污染）分支预测器的状态，导致切换后的"冷启动"期间预测准确率大幅下降。

性能分析 13 — SPEC vs. 服务器工作负载的MPKI对比

表表 13.14给出了同一处理器在SPEC CPU 2017和典型服务器工作负载上的MPKI对比。

工作负载	方向MPKI	总MPKI
SPEC CPU INT（平均）	3.5	4.5
MySQL (OLTP)	5.2	7.0
Nginx (Web serving)	4.8	6.5
Clang (编译)	6.1	8.2
Python解释器	7.5	10.0

服务器工作负载的MPKI普遍高于SPEC基准50%$\sim$100%，说明SPEC基准可能低估了分支预测在实际部署中的挑战。这也是近年来处理器厂商越来越重视BTB容量扩展和间接跳转预测的原因之一。

安全性考虑：Spectre攻击与分支预测

2018年披露的Spectre漏洞系列[^2]揭示了分支预测器可能被攻击者利用来泄露敏感数据。Spectre v1（bounds check bypass）利用条件分支的预测错误来执行越界内存访问；Spectre v2（branch target injection）通过训练BTB/间接分支预测器来将受害进程的控制流重定向到攻击者选择的"gadget"代码。

这些安全威胁对分支预测器的设计产生了深远影响：

• BTB隔离：现代处理器在不同安全域（如用户态/内核态、不同进程、不同虚拟机）之间隔离BTB的内容，防止跨域BTB注入攻击。这通常通过在BTB标签中包含安全域标识符（如PCID或VMID）来实现。

• 预测器清洗：在安全域切换时（如系统调用、上下文切换），可以选择清洗（flush）预测器状态，代价是切换后的预测冷启动。

• 推测执行限制：在某些高安全需求的场景下，可以通过微码或指令屏障（如Intel的LFENCE、ARM的CSDB）来阻止推测执行跨越安全边界。

设计提示

Spectre缓解措施与分支预测性能之间存在根本性的权衡。BTB隔离增加了BTB的有效容量需求（因为不同域的表项不能共享），预测器清洗导致冷启动的性能损失，推测执行限制直接降低了IPC。处理器设计者需要在安全性和性能之间找到平衡——这也是近年来BTB容量快速增长的原因之一（需要更大的BTB来在隔离的同时维持覆盖率）。

分支预测与取指带宽

分支预测不仅影响流水线的正确性（预测错误导致flush），还直接影响取指阶段的有效取指带宽（effective fetch bandwidth）。在一个每周期取$W$条指令的处理器中，实际的有效取指带宽往往低于$W$，原因之一就是分支指令的存在。

当取指块中包含一条被预测为taken的分支时，该分支之后的指令不应该被执行。这意味着一个取指块中实际有效的指令数可能少于$W$——taken分支"截断"了取指块的有效部分。设取指宽度为$W$条指令，taken分支在取指块中的平均位置为$W/2$（均匀分布假设），则平均每个包含taken分支的取指块只有$W/2$条有效指令。

取指块包含taken分支的概率可以估算为： $$\label{eq:ch13-taken-prob} P_{\text{taken_in_block}} = 1 - (1 - f_b \cdot p_t)^W$$

其中$f_b$为分支比例，$p_t$为分支跳转概率（taken rate）。对于$f_b = 0.15$、$p_t = 0.6$（条件分支的平均taken率约60%）、$W = 8$的处理器： $$P_{\text{taken\_in\_block}} = 1 - (1 - 0.15 \times 0.6)^8 = 1 - 0.91^8 \approx 1 - 0.47 = 53\%$$

即超过一半的取指块被taken分支截断，平均有效指令数从8条降到约$0.47 \times 8 + 0.53 \times 4 = 5.88$条。这意味着即使分支预测完全正确，取指带宽的有效利用率也只有$5.88/8 \approx 73.5\%$。

设计权衡 5 — 取指块对齐与分支预测

taken分支截断取指块的问题可以通过多种技术缓解：

• 跟踪缓存（Trace Cache）：存储已解码的指令跟踪（trace），跨越taken分支将连续执行的指令序列拼接在一起，消除taken分支的取指块截断效应。Intel Pentium 4使用了跟踪缓存，但由于面积开销巨大（需要存储解码后的微操作），后续处理器放弃了这一技术。

• 取指目标队列（Fetch Target Queue, FTQ）：预测器提前生成多个取指目标地址，缓存在FTQ中。即使当前取指块被taken分支截断，前端可以立即从FTQ中的下一个目标地址开始新的取指，减少因跳转导致的取指"空档期"。

• 多窗口取指（Multi-Window Fetch）：在一个周期内从多个不连续的地址取指。例如，在taken分支的目标地址和当前取指块之间跨越了取指块边界时，从两个地址同时发出I-Cache请求。这需要多端口或多bank的I-Cache设计，硬件开销较大。

在实践中，FTQ是最常用的方案。现代处理器的FTQ通常有16$\sim$32项，可以缓冲数十个取指周期的预测结果，使前端取指单元能够在BTB查找的气泡期间仍然持续取指。

本章小结

本章作为分支预测篇的总览，从第一性原理出发，系统地建立了分支预测的理论基础和工程框架。

首先，通过量化分析深流水线中的控制冒险，证明了分支预测是15$\sim$25级流水线处理器正常工作的必要条件——没有分支预测的停顿策略会将6-wide处理器的IPC从4.0降低到0.34，效率损失超过90%。超标量宽度进一步放大了预测失败的代价，而流水线深度与分支预测之间的张力决定了最优流水线深度的选择。

其次，介绍了分支指令的四种类型——条件分支、无条件直接跳转、间接跳转和函数调用/返回——阐明了每种类型对预测器的不同需求。

第三，从最简单的静态预测（APNT、APT、BTFNT）出发，逐步演进到基于饱和计数器的动态预测。通过严格的状态机分析，证明了2位饱和计数器为什么优于1位预测器——其滞回特性使得一次偶然的方向变化不会改变预测，将循环回边的预测错误从每个循环2次减少到1次。同时指出了$n$位计数器在$n \geq 3$时的收益递减。

第四，深入讨论了BHT的索引设计与别名冲突问题，分析了PC低位直接索引的局限性，并介绍了标签比较、XOR哈希、多路结构和全局历史索引等解决方案。

第五，详细阐述了BTB的多级层次结构和查找时序约束，以及RAS的推测性操作与多种恢复机制（TOS指针恢复、完整快照、混合方法），特别是"推测RAS + 架构RAS"的双轨设计。

最后，建立了分支预测准确率与IPC之间的数学关系，证明了在高准确率区间每提升1个百分点准确率对IPC的边际收益反而更大——这一"反直觉"的特性解释了为什么处理器设计者愿意投入巨大的硬件资源来追求最后几个百分点的提升，同时讨论了分支预测器在流水线中的接口设计，包括多级预测策略、预测输出格式、以及推测更新与提交后更新的权衡。

后续章节将分别深入讨论各个预测组件的具体算法和实现：第第 14.0 章章讨论方向预测的经典算法（两位计数器、gshare、锦标赛预测器等），第第 15.0 章章讨论目标地址预测（BTB、RAS、间接分支预测器），第第 16.0 章章讨论现代高级预测算法（TAGE、TAGE-SC-L、感知机预测器），第第 17.0 章章讨论预测器的工程实现问题（时序优化、面积/功耗权衡、验证方法等）。

本章建立了分支预测的定量分析框架（$\text{CPI}_{\text{branch}} = f_b \cdot m \cdot P$）和核心硬件组件（BHT、BTB、RAS）的基本概念。下一章（第 14.0 章）将深入方向预测算法的演进——从最简单的两位饱和计数器出发，经过gshare的全局历史引入、锦标赛预测器的自适应选择，到TAGE的几何级数历史长度分配。本章图图 13.1中95%到99.5%之间的IPC差异，正是第 14.0 章中每一代算法改进所追求的目标。理解本章的定量框架，将帮助你在后续章节中判断每种算法改进的"性价比"——哪些百分点的提升值得额外的硬件投入，哪些已经接近收益递减的拐点。

[^1]: J. E. Smith, “A study of branch prediction strategies,” Proc. 8th Annual Symposium on Computer Architecture, 1981.

[^2]: P. Kocher et al., “Spectre attacks: Exploiting speculative execution,” Proc. IEEE S&P, 2019.