分支方向预测：基本方法

1993年，DEC的Alpha 21064处理器引入了一个看似简单的想法——用一个2 KB的表记录每条分支指令过去的行为，来预测它未来的走向。这个想法的效果出人意料地好：仅用2位饱和计数器，预测准确率就达到了85%$\sim$90%。但随后二十年的研究表明，从90%到99%的每一个百分点都需要指数级增长的硬件资源。分支预测是“投机”思想最纯粹的体现——处理器投机地假设分支将按历史模式执行，用极小的存储代价换取了流水线吞吐率的巨大提升。而整个分支预测技术的演进史，就是一部在有限晶体管预算下不断逼近预测理论极限的工程史。

从本书的统一视角来看——处理器设计的本质是在有限的晶体管预算和功耗约束下，通过投机和并行的层层叠加来逼近指令吞吐率的理论上限——分支方向预测是“投机”这一核心思想最纯粹的体现。处理器在尚未执行一条分支指令时，就投机地假定它的结果并沿着假定路径全速推进取指、译码和执行。如果投机正确，处理器在零额外开销下获得了等价于“未来信息”的收益；如果投机失败，代价是一次流水线刷新——在20级以上的流水线中约15$\sim$20周期的惩罚。整个分支预测领域的演进，就是在这两个极端之间寻找最优投机策略的过程：从2位饱和计数器的朴素投机，到TAGE的多尺度自适应投机，再到感知机的线性模型投机——每一代方案都在“投机收益 $\div$ 投机成本”这一比率上取得了新的突破。

在第 13.0 章中，我们了解到分支预测对超标量处理器性能的关键影响：在一个典型的6-wide乱序核心中，分支预测精度从95%提升到97%可能带来15%$\sim$20%的IPC提升。分支预测由两个子问题组成——方向预测（Direction Prediction）和目标预测（Target Prediction）。对于条件分支而言，方向预测回答的是"这条分支是否跳转"（taken or not-taken）的问题，其预测精度直接决定了处理器推测执行的正确率。本章聚焦于分支方向预测的基本方法，从最简单的静态预测开始，逐步深入到基于饱和计数器、局部历史和全局历史的动态预测方案，最后讨论竞争预测器和预测表的更新策略。这些基本方法构成了第 15.0 章中讨论的高级预测器（如TAGE）的理论基础。

静态预测

静态预测（Static Prediction）是最早出现的分支预测方法，其核心思想是在不考虑程序运行时行为的情况下，仅凭指令本身的属性做出固定的预测。静态预测不需要任何运行时状态的存储和更新，硬件开销为零或极小，因此在资源极其受限的嵌入式处理器和早期流水线处理器中得到广泛使用。虽然在现代高性能处理器中静态预测已不再作为主要预测机制，但它仍然在以下场景中发挥作用：（1）作为动态预测器的fallback，当动态预测器未命中（cold start或容量不足）时使用；（2）作为编译器优化的基础——编译器通过分支提示位与处理器的静态预测策略配合。

固定方向预测

最简单的静态预测策略是对所有条件分支做出相同的预测：要么预测所有分支都跳转（Always Taken），要么预测所有分支都不跳转（Always Not-Taken）。

Always Not-Taken

预测所有条件分支不跳转，即处理器总是顺序地取下一条指令。这种策略的优点是实现极其简单：不需要任何分支目标的计算或存储，PC的递增逻辑只需要$\text{PC}_{\text{next}} = \text{PC} + 4$（对于32位定长指令集）。在早期的五级流水线RISC处理器中，如MIPS R2000（1985年），采用了这种策略加上分支延迟槽的组合，分支惩罚仅为1个周期。

Always Not-Taken策略的预测精度取决于程序中分支的实际行为。大量统计数据表明，在SPEC CPU等基准测试中，条件分支的taken比例大约为60%$\sim$70%（因为循环的回跳分支通常是taken的，而循环次数往往远大于1）。因此，Always Not-Taken的平均预测精度仅为30%$\sim$40%，这对于现代超标量处理器而言是完全不可接受的。

要量化Always Not-Taken策略对性能的影响，我们可以使用第 13.0 章中推导的分支惩罚公式。设流水线的分支误预测惩罚为$P$个周期，分支指令占比为$f_b$，误预测率为$m$，则每条指令的平均惩罚为$f_b \cdot m \cdot P$个周期。对于一个20级流水线的处理器（$P \approx 15$），分支占比$f_b = 20\%$，Always Not-Taken误预测率$m = 65\%$： $$\label{eq:always-nt-penalty} \text{惩罚} = 0.20 \times 0.65 \times 15 = 1.95 \text{ 周期/指令}$$ 这意味着即使忽略所有其他停顿，$\mathrm{CPI}$也至少为$1 + 1.95 = 2.95$，$\mathrm{IPC}$不超过0.34——仅为理论峰值的5.7%（6-wide处理器）。

Always Taken

预测所有条件分支都跳转。由于分支的taken比例通常高于not-taken比例，Always Taken策略的平均预测精度约为60%$\sim$70%，优于Always Not-Taken。但这种策略需要在预测阶段就获得分支目标地址，否则即使预测了taken也不知道应该跳转到哪里。这意味着Always Taken策略需要与BTB配合使用——只有当BTB命中时才能提供目标地址。对于BTB未命中的分支，处理器仍然只能按照顺序取指。

从信息论的角度来看，固定方向预测的预测精度上限取决于程序中分支的整体偏向性（Global Bias）。设所有分支的平均taken概率为$p_t$，则Always Taken的精度为$p_t$，Always Not-Taken的精度为$1 - p_t$，最优固定预测的精度为$\max(p_t, 1 - p_t)$。这个上限通常在60%$\sim$70%左右，远不能满足现代处理器的需求。

性能分析 1 — 固定方向预测的精度

表表 14.1给出了固定方向预测策略在几个典型SPEC CPU基准测试上的预测精度。数据表明，Always Taken在大多数整数程序上的表现均优于Always Not-Taken，但在某些以条件判断为主的程序（如gcc）中，两者的差距不大，因为这些程序中存在大量偏向not-taken的条件分支（如错误检查、边界判断等）。

基准测试	Always Not-Taken (%)	Always Taken (%)
gcc	42	58
mcf	25	75
gobmk	45	55
bzip2	31	69
hmmer	18	82
sjeng	40	60
平均	33.5	66.5

基于操作码的预测

一个简单但有效的改进是根据分支指令的操作码和偏移方向来做出不同的预测。这种策略利用了一个关键的经验观察：后向分支（Backward Branch，目标地址小于分支指令地址，即偏移量为负）几乎总是循环的回跳，而循环的回跳在绝大多数迭代中都是taken的（只有最后一次迭代时才是not-taken）。相反，前向分支（Forward Branch，偏移量为正）通常用于if-else结构中的跳过逻辑，其taken比例较低。

基于这个观察，操作码预测策略（也称BTFN策略：Backward Taken, Forward Not-taken）的规则是：

• 如果分支的偏移量为负（后向分支）$\Rightarrow$ 预测taken；

• 如果分支的偏移量为正或零（前向分支）$\Rightarrow$ 预测not-taken。

在RISC-V ISA中，条件分支指令（BEQ、BNE、BLT、BGE、BLTU、BGEU）使用B-type编码，偏移量由指令中的立即数字段直接编码，且符号位在指令的最高位（inst[31]）。因此，BTFN策略在RISC-V中的实现极其简单：只需要检查指令的第31位即可判断偏移方向。

// RISC-V B-type: imm[12] = inst[31] 是立即数的符号位
// 符号位为 1 表示偏移量为负（后向分支）
wire is_branch    = (inst[6:0] == 7'b1100011);
wire backward     = inst[31];  // 立即数符号位
wire predict_taken = is_branch & backward;  // BTFN策略

BTFN策略的预测精度通常在65%$\sim$75%之间。对于循环密集的科学计算程序（如SPEC FP），由于后向分支占比较高且几乎总是taken（循环次数通常为几十到几百），BTFN策略的精度可达80%以上。但对于控制流密集的整数程序（如编译器、数据库查询），前向分支的比例较高且行为不规律，BTFN策略的精度较低。

我们可以用一个简单的模型来定量分析BTFN策略的精度上界。设程序中后向分支占比$f_b$，后向分支taken比例$p_b$；前向分支占比$1 - f_b$，前向分支not-taken比例$p_f$。BTFN的精度为： $$\label{eq:btfn-accuracy} A_{\mathrm{BTFN}} = f_b \cdot p_b + (1 - f_b) \cdot p_f$$ 典型值为$f_b \approx 0.4$，$p_b \approx 0.95$（循环平均迭代20次），$p_f \approx 0.55$，代入得$A_{\mathrm{BTFN}} = 0.4 \times 0.95 + 0.6 \times 0.55 = 0.71$，即约71%的预测精度。

设计提示

BTFN策略虽然简单，但它揭示了分支预测的一个重要原则：利用程序结构的先验知识来提高预测精度。循环产生后向分支、if-else产生前向分支——这种高级语言结构与机器码之间的对应关系是分支预测可以利用的"免费信息"。更高级的预测器（如TAGE）本质上也是在利用类似的结构信息，只是它们通过自适应学习来发现更复杂的模式。

编译器提示

如果编译器拥有程序的性能剖析信息（Profile Data），它可以精确地知道每条分支在特定输入下的跳转概率，从而为处理器提供远比BTFN策略更准确的静态预测提示。这种编译器引导的静态预测（Compiler-Directed Static Prediction）通过在指令编码中嵌入预测提示位来实现。

GCC __builtin_expect

在C/C++编程中，程序员可以使用GCC提供的__builtin_expect内建函数向编译器提供分支概率提示：

// 提示编译器：条件大概率为真
if (__builtin_expect(ptr != NULL, 1)) {
    process(ptr);  // 编译器会将此路径作为 fall-through
} else {
    handle_error();
}

// Linux 内核中的宏定义
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

if (likely(skb != NULL)) { ... }
if (unlikely(err < 0)) { ... }

编译器收到__builtin_expect提示后，会进行两方面的优化：（1）代码布局优化——将大概率执行的路径安排为顺序执行（fall-through），将不太可能执行的路径安排为跳转目标，使得处理器在使用BTFN策略或Always Not-Taken策略时更容易做出正确预测；（2）指令调度优化——优先为大概率路径安排寄存器和调度指令，减少该路径的延迟。

RISC-V的分支提示位

RISC-V ISA在其条件分支指令中预留了分支预测提示（Branch Prediction Hint）的编码空间。在RISC-V Zihintntl扩展和C.NOP hint空间中，可以通过特定编码向处理器暗示分支的预期方向。在实际实现中，RISC-V处理器可以选择性地利用这些提示信息来初始化动态预测器的状态，或者在动态预测器未命中时作为fallback预测。

静态预测的局限性

尽管编译器提示可以提高静态预测的精度，但静态预测存在根本性的局限：

（1）无法适应运行时行为变化。一条分支的跳转概率可能随着输入数据和程序执行阶段的变化而变化。例如，一个排序算法中的比较分支，在排序初期可能偏向taken（大量数据需要交换），在排序末期则偏向not-taken（已趋近有序）。静态预测无法捕捉这种动态变化。

（2）Profile数据的代表性。__builtin_expect所依赖的Profile数据通常来自特定的训练输入。如果实际输入与训练输入的特征差异较大，基于Profile的静态预测可能反而降低精度。

（3）编码空间的限制。指令中只能编码1位的预测提示（taken或not-taken），无法表达置信度或概率信息。

这些局限性促使处理器设计者发展出了动态分支预测技术——根据程序运行时的实际分支行为来自适应地调整预测策略。下面几节将详细讨论各种动态预测方法。

基于两位饱和计数器的分支预测

动态分支预测的基本思想是：记录每条分支在过去执行中的跳转行为，并据此预测其未来的行为。最经典的动态预测方案是两位饱和计数器（2-bit Saturating Counter），由James Smith于1981年提出。两位饱和计数器之所以成为分支预测领域的基石，是因为它在极小的硬件代价（每个分支2位存储）下实现了远超静态预测的精度，并且其状态转换机制具有"滞后性"，能有效抵抗分支行为的偶然波动。

两位计数器的状态机

一个两位饱和计数器有4种状态，可以用一个2位的值$c \in \{0, 1, 2, 3\}$来表示：

• SN（Strongly Not-Taken，$c = 0$）：强烈预测不跳转；

• WN（Weakly Not-Taken，$c = 1$）：弱预测不跳转；

• WT（Weakly Taken，$c = 2$）：弱预测跳转；

• ST（Strongly Taken，$c = 3$）：强烈预测跳转。

预测规则是：当$c \geq 2$时预测taken，当$c < 2$时预测not-taken。也就是说，计数器的最高位（MSB）直接就是预测结果。

状态转换规则如下：

• 当分支实际跳转（taken）时：$c \gets \min(c + 1, 3)$（计数器递增，但不超过3）；

• 当分支实际不跳转（not-taken）时：$c \gets \max(c - 1, 0)$（计数器递减，但不低于0）。

"饱和"（Saturating）的含义正是指计数器在达到最大值3或最小值0后不再继续增减，即不会发生回绕（Wrap-around）。图图 14.1展示了两位饱和计数器的完整状态转换图。

两位饱和计数器的状态转换图。蓝色状态（SN、WN）预测不跳转，红色状态（WT、ST）预测跳转。T表示分支实际跳转，NT表示分支实际不跳转。

两位饱和计数器的关键优势在于其滞后特性（Hysteresis）：一个处于ST状态的计数器需要连续两次not-taken才会翻转预测方向（从ST经WT到WN）。这种滞后性对于循环分支特别有效。考虑一个执行$N$次的循环：其回跳分支在前$N-1$次迭代中是taken的，只在最后一次退出循环时是not-taken的。如果使用一位计数器（只有T和NT两个状态），那么在循环退出时计数器翻转为NT，下次进入循环时第一次迭代就会预测错误；再翻转为T后，接下来的$N-2$次迭代预测正确，最后一次迭代又预测错误。这样每次循环执行都会产生两次误预测。

而使用两位饱和计数器时，循环退出时计数器从ST变为WT（一次not-taken），但仍然预测taken。下次进入循环时第一次迭代预测正确（WT仍预测taken），计数器回到ST。这样每次循环执行只产生一次误预测（即最后一次退出循环时的误预测），将循环分支的误预测率从$2/N$降低到$1/N$。

性能分析 2 — 一位与两位计数器的比较

考虑一个循环迭代100次的分支，其执行序列为99个T后跟1个NT，不断重复： $$\underbrace{T, T, \ldots, T}_{99}, \mathrm{NT}, \underbrace{T, T, \ldots, T}_{99}, \mathrm{NT}, \ldots$$

一位计数器：每次循环产生2次误预测（进入时1次 + 退出时1次），误预测率 $= 2/100 = 2\%$。

两位饱和计数器：每次循环产生1次误预测（仅退出时1次），误预测率 $= 1/100 = 1\%$。

在循环迭代次数较少时差距更为显著。对于迭代5次的循环：

• 一位计数器：误预测率 $= 2/5 = 40\%$

• 两位饱和计数器：误预测率 $= 1/5 = 20\%$

两位计数器的优势正是来源于其"对单次异常行为的容忍"。

从数学角度来分析两位饱和计数器的预测精度。设一条分支的taken概率为$p$（$0 < p < 1$），且每次执行之间相互独立（这是一个简化假设，但有助于理解计数器的稳态行为）。在稳态下，计数器处于各状态的概率可以通过求解马尔可夫链的稳态方程得到。设$\pi_0, \pi_1, \pi_2, \pi_3$分别为处于SN、WN、WT、ST状态的概率，稳态方程为： $$\begin{aligned} \pi_0 &= \pi_0 (1-p) + \pi_1 (1-p) \label{eq:mc-sn} \ \pi_1 &= \pi_0 p + \pi_2 (1-p) \label{eq:mc-wn} \ \pi_2 &= \pi_1 p + \pi_3 (1-p) \label{eq:mc-wt} \ \pi_3 &= \pi_2 p + \pi_3 p \label{eq:mc-st} \end{aligned}$$ 加上归一化条件$\pi_0 + \pi_1 + \pi_2 + \pi_3 = 1$。

求解该方程组，预测精度（正确预测的概率）为： $$\label{eq:2bit-accuracy} A_{2\text{bit}} = (\pi_0 + \pi_1)(1-p) + (\pi_2 + \pi_3)p$$

对于$p = 0.7$（分支70%的时间taken），求解可得$A_{2\text{bit}} \approx 82\%$；而对于$p = 0.95$的强偏向分支，$A_{2\text{bit}} \approx 99.5\%$。两位饱和计数器对偏向性强的分支预测效果极好，但对于$p \approx 0.5$的分支（如均匀随机分支），精度仅约75%——仍优于50%的随机猜测，这得益于滞后特性的"惯性"。

考虑一条分支的执行序列为$\{T, T, T, \mathrm{NT}, T, T, \mathrm{NT}, T, T, T, T, \mathrm{NT}\}$，初始状态为WN（$c=1$）。逐步追踪两位计数器的状态变化和预测结果：

步骤	实际	当前状态	预测	正确?	更新后状态
1	T	WN ($c\!=\!1$)	NT	错	WT ($c\!=\!2$)
2	T	WT ($c\!=\!2$)	T	对	ST ($c\!=\!3$)
3	T	ST ($c\!=\!3$)	T	对	ST ($c\!=\!3$)
4	NT	ST ($c\!=\!3$)	T	错	WT ($c\!=\!2$)
5	T	WT ($c\!=\!2$)	T	对	ST ($c\!=\!3$)
6	T	ST ($c\!=\!3$)	T	对	ST ($c\!=\!3$)
7	NT	ST ($c\!=\!3$)	T	错	WT ($c\!=\!2$)
8	T	WT ($c\!=\!2$)	T	对	ST ($c\!=\!3$)
9	T	ST ($c\!=\!3$)	T	对	ST ($c\!=\!3$)
10	T	ST ($c\!=\!3$)	T	对	ST ($c\!=\!3$)
11	T	ST ($c\!=\!3$)	T	对	ST ($c\!=\!3$)
12	NT	ST ($c\!=\!3$)	T	错	WT ($c\!=\!2$)

12次执行中预测正确8次，精度$8/12 = 66.7\%$。注意第4、7、12步的NT出现后，计数器从ST降到WT但不翻转预测方向——这正是两位计数器"容忍偶发异常"的滞后特性在起作用。如果使用一位计数器，这3次NT之后的3次T都会被误预测（因为一位计数器在NT后立即翻转为预测NT），总误预测将从4次增加到7次。

两位饱和计数器的更新逻辑极其简单，可以用纯组合逻辑实现：

// 输入：当前计数器值 cnt[1:0]，实际分支结果 taken
// 输出：新的计数器值 cnt_next[1:0]
always_comb begin
  case ({taken, cnt})
    3'b1_00: cnt_next = 2'b01;  // SN + T -> WN
    3'b1_01: cnt_next = 2'b10;  // WN + T -> WT
    3'b1_10: cnt_next = 2'b11;  // WT + T -> ST
    3'b1_11: cnt_next = 2'b11;  // ST + T -> ST (饱和)
    3'b0_00: cnt_next = 2'b00;  // SN + NT -> SN (饱和)
    3'b0_01: cnt_next = 2'b00;  // WN + NT -> SN
    3'b0_10: cnt_next = 2'b01;  // WT + NT -> WN
    3'b0_11: cnt_next = 2'b10;  // ST + NT -> WT
  endcase
end

// 预测结果 = 计数器的最高位
assign prediction = cnt[1];

BHT

两位饱和计数器解决了"如何为单条分支做出自适应预测"的问题，但一个处理器需要同时跟踪成百上千条不同的分支。分支历史表（Branch History Table，BHT）提供了一种简单而高效的方式来组织大量的两位饱和计数器。

BHT的基本结构是一个由$2^k$个两位饱和计数器组成的数组（表），使用分支指令的PC（程序计数器）的低$k$位作为索引来选择对应的计数器。图图 14.2展示了一个包含$2^k$项的BHT结构。

分支历史表（BHT）的基本结构。PC的低$k$位用于索引$2^k$个两位饱和计数器。预测时读出计数器的最高位作为预测结果；分支执行完毕后，根据实际结果更新对应的计数器。

BHT的工作流程如下：

（1）预测阶段：当前端取到一条分支指令时，使用该指令PC的低$k$位索引BHT，读出对应的两位计数器值，其最高位即为预测结果（1=taken，0=not-taken）。这一操作可以在1个时钟周期内完成。

（2）更新阶段：当分支指令在后端执行完毕（或退休时），将分支的实际结果（taken/not-taken）反馈到BHT，使用相同的PC低位索引找到对应的计数器，按照饱和计数器的规则进行更新。

BHT的容量通常在1K$\sim$16K项之间。一个4K项的BHT需要$4096 \times 2 = 8192$位$= 1$ KB的存储空间——这是非常经济的硬件开销。表表 14.2列出了不同规模BHT的存储需求和典型预测精度。

BHT项数	索引位数 $k$	存储 (bit)	SPEC INT精度 (%)
256	8	512	80$\sim$82
1024	10	2048	83$\sim$85
4096	12	8192	85$\sim$88
16384	14	32768	87$\sim$90

不同规模BHT的存储开销与典型预测精度

BHT的一个重要特征是它不存储Tag——只使用PC的低$k$位作为索引，不检查该项是否确实属于当前分支。这意味着不同的分支如果其PC低$k$位相同，就会共享同一个计数器。这种现象称为别名（Aliasing），将在下一小节中详细讨论。不存储Tag的好处是节省了大量的存储空间（每项只需2位），并且不需要Tag比较逻辑，访问延迟最低。

值得一提的是，BHT有时也被称为PHT（Pattern History Table）或简单地称为"计数器表"。在本书的后续章节中，当BHT仅使用PC索引时称其为BHT，当使用历史信息（或历史与PC的组合）索引时称其为PHT，以示区别。

硬件描述 1 — BHT的SRAM实现

BHT在硬件上使用单端口或双端口SRAM实现。预测时进行读操作，更新时进行写操作。如果预测和更新可能同时发生（指向同一个表项），需要处理读写冲突。常见的做法有两种：

（1）读优先：如果同一周期内预测请求和更新请求的索引相同，则优先响应预测读请求，更新写操作延迟一个周期。这种策略保证了预测延迟不受更新的影响，但可能导致使用旧值预测。

（2）写转发（Write Forwarding）：检测到读写地址相同时，将更新后的新值直接转发给预测输出，而非从SRAM读出旧值。这种策略使预测使用最新值，但增加了一层旁路逻辑。

在实际的高性能处理器中，由于每周期可能取到多条分支指令（在宽取指块中），BHT通常需要支持多个并行的读端口。一种常见的优化是将BHT设计为多Bank结构——将$2^k$项分成$B$个Bank（如$B=4$或8），不同Bank可以并行读取。Bank的选择使用PC低位的不同子集，使得连续的取指块中的分支大概率落在不同的Bank中。

地址索引的方式

BHT使用PC的低位作为索引，但具体取哪些位存在不同的选择。在RISC-V中，由于指令是4字节对齐的（或在C扩展下是2字节对齐的），PC的最低2位（在无C扩展时）总是00，不携带任何信息。因此，实际索引通常使用PC[$k$+1:2]（跳过最低2位）。

别名问题

当BHT的项数$2^k$远少于程序中的分支数量时（在实际程序中几乎总是如此），多条不同的分支必然会映射到同一个BHT表项。这种别名（Aliasing）会导致一条分支的行为"污染"另一条分支的计数器状态，降低预测精度。

别名可以分为两类：

（1）中性别名（Neutral Aliasing）：共享同一计数器的多条分支恰好具有相同或相似的跳转行为。这种别名不会降低预测精度，甚至可能带来正面效果——如果一条新出现的分支与另一条已训练好的分支共享计数器，它可以"继承"已有的训练结果。

（2）破坏性别名（Destructive Aliasing）：共享同一计数器的分支具有相反的跳转行为。例如，分支A倾向于taken而分支B倾向于not-taken，当它们共享同一个计数器时，计数器会在WT和WN之间振荡，导致两条分支的预测精度都大幅下降。

别名对预测精度的影响可以用以下公式近似估计。设程序中有$N_b$条活跃分支，BHT有$M$项，假设分支的PC均匀分布在BHT中，则每个BHT项平均被$N_b / M$条分支共享。根据生日问题（Birthday Problem）的分析，当$N_b \approx \sqrt{M}$时，约50%的BHT项会发生别名。对于一个4096项的BHT（$M = 4096$），当活跃分支数超过64条时就会出现显著的别名。在SPEC CPU基准测试中，活跃分支数通常在数百到数千条，远超这个阈值。

为了更直观地理解别名的影响，考虑以下具体场景：

假设一个1024项BHT（$k=10$），有两条分支$B_A$和$B_B$：

• $B_A$的PC = 0x8000_1400，PC[11:2] = 0b01_0000_0000 = 索引256

• $B_B$的PC = 0x8000_5400，PC[11:2] = 0b01_0000_0000 = 索引256

两条分支PC的低12位相同（因为地址差为0x4000 = 16384，而索引只用了10位，$16384 / 4 = 4096 \equiv 0 \pmod{1024}$），因此它们映射到BHT的同一项。

如果$B_A$的taken率为90%，$B_B$的taken率为10%，共享计数器将在ST和SN之间频繁振荡。假设$B_A$和$B_B$交替执行（$B_A, B_B, B_A, B_B, \ldots$），计数器的状态序列可能为： $$\mathrm{WT} \xrightarrow{B_A: T} \mathrm{ST} \xrightarrow{B_B: \mathrm{NT}} \mathrm{WT} \xrightarrow{B_A: T} \mathrm{ST} \xrightarrow{B_B: \mathrm{NT}} \mathrm{WT} \cdots$$ 此时$B_A$总是被正确预测（WT和ST都预测T），但$B_B$总是被错误预测（WT和ST都预测T，而$B_B$大多数时候是NT）。$B_B$的预测精度从独立使用计数器时的90%（由SN正确预测NT）暴跌至约10%。

设计权衡 1 — BHT容量与别名

增大BHT可以减少别名，但收益递减。在SPEC CPU INT测试中，将BHT从1K项增大到4K项可以将预测精度提高约3%；但从4K项增大到16K项，精度仅提高约2%。这是因为：（1）大部分破坏性别名已被消除，剩余别名多为中性别名；（2）BHT仅使用PC低位索引，无法利用分支的历史行为信息。即使BHT无限大（无别名），纯饱和计数器方案的预测精度也受限于其只能捕捉每条分支的"静态偏向"，无法预测具有周期性或相关性模式的分支。这个根本限制促使了基于历史的预测方法的发展。

图图 14.3定性展示了BHT容量与预测精度的关系，以及别名和"信息不足"两种因素对预测精度上限的制约。

基于局部历史的分支预测

纯BHT方案的根本局限在于它只记录了每条分支的全局偏向性（倾向taken还是not-taken），而没有利用分支的历史行为模式。许多分支表现出明显的局部模式。例如，一个每4次迭代执行一次特殊处理的循环，其内部分支的行为序列为$\{T, T, T, \mathrm{NT}, T, T, T, \mathrm{NT}, \ldots\}$，具有周期为4的循环模式。纯BHT无法捕捉这种模式——它只知道这条分支大约75%的时间是taken的，但无法预测具体哪次是NT。

基于局部历史（Local History）的预测方法通过记录每条分支最近若干次的执行结果来发现这种周期性模式，从而实现更精确的预测。

局部历史寄存器

局部历史寄存器（Local History Register，LHR）是一个$n$位的移位寄存器，记录某条分支最近$n$次执行的结果。每次分支执行后，其结果（1=taken，0=not-taken）被移入LHR的最低位，最高位被移出。例如，一个8位的LHR值0b11101110表示该分支最近8次执行的结果依次为$\{T, T, T, \mathrm{NT}, T, T, T, \mathrm{NT}\}$（从最近到最远）。

为了同时跟踪多条分支的局部历史，需要一个局部历史表（Branch History Register Table，BHRT），使用分支的PC索引来存储每条分支的LHR。BHRT的每一项是一个$n$位的移位寄存器。一个具有$T$项、每项$n$位的BHRT需要$T \times n$位的存储空间。例如，一个1024项、10位历史的BHRT需要$1024 \times 10 = 10240$位$\approx 1.25$ KB。

两级自适应预测器

仅有局部历史寄存器还不够——LHR记录了分支的历史模式，但如何利用这个模式来做出预测呢？答案是使用一个模式历史表（Pattern History Table，PHT）：将LHR的值作为索引查询一个由两位饱和计数器组成的表，从而实现"对于特定的历史模式，预测下一次的结果"。

这种由局部历史寄存器（第一级）和模式历史表（第二级）组成的预测器称为两级自适应预测器（Two-Level Adaptive Predictor），由Tse-Yu Yeh和Yale Patt于1991年提出。根据第一级历史的类型（局部/全局）和第二级PHT的组织方式（每分支私有/所有分支共享），两级预测器可以分为多种变体。本节讨论基于局部历史的两种典型结构：PAg和PAp。

PAg（Per-Address History, Global PHT）

PAg结构中，第一级是一个以PC索引的局部历史表（每条分支有自己的LHR），第二级是一个全局共享的PHT。所有分支的LHR值都索引同一个PHT。

PAg两级自适应预测器。第一级BHRT使用PC索引存储每条分支的局部历史，第二级PHT使用局部历史值作为索引，输出预测结果。

PAg的工作过程以一个具体例子说明。假设某条分支$B$的10位局部历史为0b1110111011，表示其最近10次执行的结果为$\{T,T,\mathrm{NT},T,T,T,\mathrm{NT},T,T,T\}$。将这个10位值（十进制955）作为索引查询PHT，读出PHT[955]的2位计数器值。如果PHT[955]=ST，则预测$B$在历史模式1110111011之后的下一次执行将是taken。

当$B$实际执行后，根据实际结果更新PHT[955]的计数器，同时将实际结果移入$B$的LHR（LHR变为1101110111或1101110110，取决于实际结果）。

PAp（Per-Address History, Per-Address PHT）

PAp结构中，每条分支不仅有自己的LHR，还有自己私有的PHT。这意味着不同分支的相同历史模式不会共享PHT表项，消除了PHT中的别名问题。

PAp的精度通常高于PAg，因为相同的历史模式对不同的分支可能意味着不同的预测方向。例如，分支$A$的历史1110之后通常是NT（周期性模式$\{T,T,T,\mathrm{NT}\}$），而分支$B$的历史1110之后通常是T。在PAg中，两者共享PHT[1110]，会产生冲突；在PAp中，它们使用各自的PHT，互不干扰。

考虑以下C代码片段：

for (int i = 0; i < 4; i++) {  // 分支 B1: 周期 TTTN
    if (i % 2 == 0) {          // 分支 B2: 周期 TNTN
        process_even(i);
    }
}

分支$B_1$（循环回跳）的行为序列为$\{T, T, T, \mathrm{NT}, T, T, T, \mathrm{NT}, \ldots\}$，周期为4。 分支$B_2$（条件判断）的行为序列为$\{T, \mathrm{NT}, T, \mathrm{NT}, T, \mathrm{NT}, T, \mathrm{NT}, \ldots\}$，周期为2。

使用4位局部历史的PAg预测器来跟踪这两条分支。

**分支$B_1$**的局部历史寄存器在达到稳态后，会在以下模式间循环： $\texttt{1110} \to \texttt{1101} \to \texttt{1011} \to \texttt{0111} \to \texttt{1110} \to \cdots$

对于每个模式，PHT中学习到的预测为：

• PHT[1110]：下一次为T $\Rightarrow$ 预测T（$\checkmark$）

• PHT[1101]：下一次为T $\Rightarrow$ 预测T（$\checkmark$）

• PHT[1011]：下一次为T $\Rightarrow$ 预测T（$\checkmark$）

• PHT[0111]：下一次为NT $\Rightarrow$ 预测NT（$\checkmark$——但此处是循环退出，然后下次进入循环时$B_1$为T，会导致首次误预测，因为之后0111的后继变为T）

关键问题出在0111这个模式上：它有时后跟T（进入新一轮循环的第一次迭代），有时后跟NT（循环退出后没有再进入），导致PHT[0111]的计数器在T和NT之间振荡。这个例子说明，即使使用了局部历史，对于模式内部存在歧义（同一历史模式对应不同结果）的情况，预测精度仍然受限。

但PAp的硬件开销远大于PAg。如果BHRT有$T$项，每项历史$n$位，则PAp需要$T$个独立的PHT，每个PHT有$2^n$项，每项2位。总存储为$T \times 2^n \times 2$位。例如，$T=1024$，$n=10$时，PAp需要$1024 \times 1024 \times 2 = 2$ Mbit $= 256$ KB，这在实际处理器中通常是不可接受的。因此，实际实现中更常见的是折中方案——使用较小的$T$和$n$，或者使用PAg结构并接受一定程度的别名。

另一种折中方案是PAs（Per-Address history, per-Set PHT）：将所有分支分成若干组，每组共享一个PHT。例如，将1024个BHRT项分成16组（每组64个分支），每组共享一个$2^n$项的PHT，总存储为$T \times n + 16 \times 2^{n+1}$。这种方案在PAg和PAp之间取得折中，减少了同组PHT中的别名，同时将存储开销控制在可接受的范围内。

设计提示

两级自适应预测器的设计空间可以用一个三元组$(H, I, P)$来描述：$H$表示历史的来源（Per-Address即局部，或Global即全局），$I$表示索引方式，$P$表示PHT的组织方式（Global共享、Per-Address私有、Per-Set分组）。Yeh和Patt在1991年的原始论文中系统地枚举了所有组合，形成了一个2级预测器的分类框架。本章讨论的PAg、PAp属于局部历史系列；下一节讨论的GShare、GSelect属于全局历史系列（GAg、GAs等变体）。理解这个分类框架有助于分析任何特定预测器设计属于哪种类型。

结构	BHRT	PHT	总计
PAg	$T \times n$	$2^n \times 2$	$T \cdot n + 2^{n+1}$
PAp	$T \times n$	$T \times 2^n \times 2$	$T \cdot n + T \cdot 2^{n+1}$

PAg与PAp的存储开销对比（$n$位局部历史，$T$项BHRT）

循环分支的处理

对于循环分支这一特殊但极其常见的分支类型，上述通用的两级自适应预测器并不是最优方案。一个固定迭代$N$次的循环，其回跳分支的行为序列是完全确定的：$N-1$个T后跟1个NT。如果能识别出这种模式并直接预测循环的迭代次数，就可以实现几乎完美的预测。

循环预测器（Loop Predictor）正是为此而设计的专用预测器。其核心思想是为每条可能的循环分支维护一个循环计数器（Loop Counter），记录循环的迭代次数。循环预测器的每个表项通常包含以下字段：

• Tag：分支PC的部分高位，用于确认表项属于正确的分支；

• LoopCount：学习到的循环迭代次数（即循环体执行的总次数）；

• CurrentIter：当前迭代的计数（从0开始递增）；

• Confidence：置信位，表示学习到的LoopCount是否可靠。

循环预测器的工作流程：

（1）学习阶段：当一条分支首次被识别为可能的循环分支时（连续多次taken后出现一次not-taken），记录从上次not-taken到本次not-taken之间的taken次数作为候选LoopCount。如果连续多次观察到的LoopCount相同，则将Confidence设为高，表示该循环的迭代次数已被可靠学习。

（2）预测阶段：如果Confidence为高，则在CurrentIter $<$ LoopCount时预测taken，在CurrentIter $=$ LoopCount时预测not-taken（循环退出）。每次预测taken时，CurrentIter递增。

（3）重置：当预测not-taken（循环退出）后，CurrentIter重置为0，准备下一轮循环。

循环预测器的精度在其适用范围内几乎是完美的：对于固定迭代次数的循环，误预测率为零（一旦学习完成）。图图 14.5展示了循环预测器的状态转换逻辑。

循环预测器的状态转换逻辑。循环预测器需要经过学习阶段来确定循环的迭代次数，一旦学习成功（进入CONFIDENT状态），即可实现近乎完美的预测。

但循环预测器有以下局限：（1）无法处理可变迭代次数的循环——如果循环的迭代次数在每次调用时不同，循环预测器会不断地"重新学习"，导致学习阶段的误预测；（2）存储开销较大——每个表项需要存储LoopCount（通常14$\sim$16位）、CurrentIter（等宽）、Tag和Confidence，远大于一个两位饱和计数器；（3）嵌套循环的处理——在多层嵌套循环中，内层循环的LoopCount可能取决于外层循环的变量（如三角循环），这使得单一的LoopCount字段无法准确描述循环行为。

性能分析 3 — 循环预测器的收益量化

在SPEC CPU 2017 INT基准测试中，约10%$\sim$15%的分支是循环回跳分支，其中约60%$\sim$70%具有固定的迭代次数。对于这些固定迭代循环：

不使用循环预测器时（仅依赖两位饱和计数器），每次循环退出产生1次误预测，每次循环进入可能产生0$\sim$1次误预测。设平均迭代次数为$\bar{N}$，则循环分支的误预测率约为$1/\bar{N}$到$2/\bar{N}$。

使用循环预测器后（学习完成），固定迭代循环的误预测率降为0。假设$\bar{N} = 20$，循环分支占比$f_l = 12\%$，其中固定迭代占65%：

MPKI降低量 $\approx f_l \times 0.65 \times (1/\bar{N}) \times 1000 = 0.12 \times 0.65 \times 0.05 \times 1000 = 3.9$

这意味着循环预测器可以将MPKI降低约3$\sim$4点——对于MPKI在5$\sim$10范围的基准测试，这是非常显著的改善。

因此，循环预测器通常与其他预测器配合使用，仅覆盖被识别为固定迭代循环的分支。在现代处理器中（如Intel Skylake及后续微架构），循环预测器作为TAGE预测器的辅助组件存在，当TAGE和循环预测器给出不同预测时，由额外的选择逻辑决定最终结果。

基于全局历史的分支预测

局部历史预测器利用每条分支自身的历史行为来做出预测，但忽略了一个重要的信息源：不同分支之间的相关性。在实际程序中，一条分支的行为往往取决于前面其他分支的执行结果。考虑以下代码片段：

if (x > 0)         // 分支 B1
    y = 1;
if (x > 0)         // 分支 B2（与 B1 完全相关）
    z = y + 1;

分支$B_2$的方向与$B_1$完全相同——如果$B_1$是taken，$B_2$必然也是taken。局部历史预测器无法利用$B_1$对$B_2$结果的信息，因为它们维护各自独立的历史寄存器。但如果我们记录最近所有分支（包括$B_1$）的结果作为"全局历史"，并用这个全局历史来预测$B_2$，就可以发现$B_1$=taken意味着$B_2$=taken的关联关系。

这种现象不仅限于完全相同的条件。更复杂的相关性广泛存在于实际程序中：

if (x < 10)          // B1
    ...
if (x < 20)          // B2: 如果 B1=taken, B2 必然 taken
    ...
if (x < 10 && y > 0) // B3: 如果 B1=not-taken, B3 必然 not-taken
    ...

这种分支间相关性（Inter-Branch Correlation）是全局历史预测器的理论基础。Pan、So和Rahmeh于1992年的研究表明，SPEC基准测试中约有30%$\sim$50%的分支与其他分支存在显著的相关性。

从信息论的角度来看，当前分支$B_c$的结果$Y$可以建模为一个随机变量，而最近$n$条分支的结果序列$H = (B_{-1}, B_{-2}, \ldots, B_{-n})$提供了关于$Y$的互信息$I(Y; H)$。全局历史预测器试图最大化条件概率$P(Y | H)$的估计精度。当分支之间存在强相关性时，$I(Y; H) > 0$，全局历史能提供超越仅使用$B_c$自身历史时所能获得的信息。

全局历史寄存器

全局历史寄存器（Global History Register，GHR）是一个$n$位的移位寄存器，记录最近$n$条分支的执行结果，不区分这些分支的PC地址。每当一条分支执行完毕，其结果被移入GHR的最低位，最高位被移出。GHR是所有分支共享的——整个处理器核心只有一个GHR。

例如，假设最近4条分支的执行序列为$B_1$=T、$B_2$=NT、$B_3$=T、$B_4$=T，则4位GHR的值为0b1101（$B_4$在最低位）。

GHR的长度$n$是一个关键的设计参数。较短的GHR（如$n=4\sim8$）能记录的历史有限，可能无法捕捉较长距离的分支相关性；但如果GHR过长（如$n=32$或更长），$2^n$种可能的历史模式过多，每种模式在程序执行中出现的频率过低，导致PHT中对应的计数器无法得到充分训练——这就是所谓的冷启动问题（Cold Start Problem）。在实际处理器中，全局历史长度通常在10$\sim$20位之间（对于简单的GShare），而更先进的TAGE预测器通过使用多个不同长度的历史表来同时利用短期和长期历史信息。

GHR与BHT中的两位计数器结合，就构成了基于全局历史的两级预测器。其基本结构是：使用GHR的值（或GHR与PC的某种组合）作为索引来查询一个PHT，PHT中的每一项仍然是一个两位饱和计数器。下面讨论两种经典的索引方案：GSelect和GShare。

GShare预测器

GShare预测器由Scott McFarling于1993年提出，是全局历史预测器中最经典且影响最深远的设计。GShare的核心创新是使用PC与GHR的异或（XOR）来索引PHT：

$$\text{index} = \text{PC}[k\!+\!1:2] \oplus \text{GHR}[k\!-\!1:0]$$

其中$k$是PHT的索引位数，$\oplus$表示按位异或。图图 14.6展示了GShare预测器的完整结构。

GShare预测器结构。PC低位与GHR进行异或运算后索引PHT。

GShare为什么使用XOR而不是简单的拼接（Concatenation）？关键在于信息分散。XOR运算将PC和GHR的信息均匀地"混合"到索引的每一位中，使得PHT中的表项分布更加均匀。假设PC有$p$位有效信息，GHR有$g$位，PHT有$2^k$项。如果使用拼接，索引为$\{\text{PC}[p\!-\!1:0], \text{GHR}[g\!-\!1:0]\}$，需要$k = p + g$位来完全利用两者的信息，PHT需要$2^{p+g}$项——这在$p$和$g$都较大时是不可行的。而使用XOR，只需要$k = \max(p, g)$位的索引就能让PC和GHR同时参与每一位的生成，在PHT大小固定的情况下实现了更好的信息利用率。

McFarling在原始论文中通过实验证明，在相同的存储预算下，GShare的预测精度显著优于GSelect（将在下一小节讨论）。在SPEC CPU INT基准测试上，使用12位索引（4K项PHT）的GShare预测器可以达到约91%$\sim$93%的预测精度。

XOR索引的另一个微妙优势是其可逆性：给定索引值和GHR，可以唯一确定PC低位（$\text{PC} = \text{index} \oplus \text{GHR}$），反之亦然。这意味着XOR不会将两个具有不同PC且不同GHR的分支映射到同一个索引（除非它们的PC差异恰好等于GHR的差异，这在统计上概率较低）。相比之下，拼接索引只保留了PC和GHR各自的部分位，丢弃的信息是无法恢复的。

GShare预测器的一个重要设计参数是GHR的长度$n$与PHT的大小$2^k$之间的关系。通常$n = k$（GHR长度等于索引位数），但也有$n > k$的变体——此时GHR的多余位通过折叠（Fold）混入索引： $$\label{eq:gshare-fold} \text{index} = \text{PC}[k!+!1:2] \oplus \text{GHR}[k!-!1:0] \oplus \text{GHR}[2k!-!1:k]$$ 这种折叠技术允许在PHT大小有限的情况下使用更长的历史，不过随着折叠次数增多，索引冲突的概率也会增大。

表表 14.4展示了GShare预测器在不同参数配置下的预测精度，揭示了PHT大小和历史长度之间的权衡关系。

PHT项数	GHR长度
2-5	8位	12位	16位	20位
1K	10.2	10.5	11.1	12.3
4K	8.5	7.8	8.2	9.1
16K	7.9	6.7	6.3	6.8
64K	7.5	6.2	5.5	5.2

GShare预测器在不同配置下的MPKI（SPEC CPU 2006 INT平均）

从表表 14.4可以观察到：（1）在PHT较小时（1K$\sim$4K项），较短的历史（8$\sim$12位）反而优于较长的历史，因为长历史导致$2^n$远大于PHT大小，每个PHT项被大量不同的历史模式共享，别名严重；（2）在PHT足够大时（64K项），较长的历史（16$\sim$20位）可以进一步提升精度，因为更多的历史信息有助于区分更复杂的分支行为模式；（3）最优的GHR长度大约等于$\log_2(\text{PHT项数})$，这与$n = k$的设计直觉一致。

假设一个8位GShare预测器（$k=8$，PHT有256项），当前PC=0x8010_1234，GHR=0b10110011。

PC[9:2] = 0b00001101（取0x1234的bit[9:2]）， GHR = 0b10110011。

索引 = 0b00001101 $\oplus$ 0b10110011 = 0b10111110 = 190。

查询PHT[190]的2位计数器，假设值为0b11（ST），则预测taken。

如果分支实际结果为not-taken，则：

1. 更新PHT[190]：ST $\to$ WT（$\texttt{0b11} \to \texttt{0b10}$）；

2. 更新GHR：将0移入最低位，GHR变为0b01100110。

GSelect预测器

GSelect预测器（也称为GAg或Gshare的拼接变体）使用PC低位和GHR的拼接（Concatenation）来索引PHT：

$$\text{index} = \{\text{PC}[p\!+\!1:2],\; \text{GHR}[g\!-\!1:0]\}$$

其中$p$位来自PC，$g$位来自GHR，总索引位数$k = p + g$。

图图 14.7展示了GSelect的索引方式。

GSelect预测器结构。PC低位与GHR拼接后索引PHT，索引宽度为$p+g$位。

GSelect的优点是PC和GHR的信息完全独立，不存在XOR可能带来的信息损失。但其缺点是在固定的PHT大小下，PC和GHR必须分享索引位——增加PC的位数$p$就意味着减少GHR的位数$g$，反之亦然。例如，对于12位索引的PHT（4K项），GSelect可以选择$p=6, g=6$，或$p=8, g=4$，等等。无论如何选择，都意味着要么PC信息不足（增加别名），要么历史信息不足（降低模式识别能力）。

而GShare使用XOR，12位索引可以同时使用12位PC信息和12位GHR信息——虽然XOR会损失一些信息（两个不同的PC-GHR组合可能产生相同的索引），但总体上信息利用效率更高。McFarling的实验表明，在相同存储预算下，GShare的MPKI（Mispredictions Per Kilo-Instructions）比GSelect低约10%$\sim$20%。

性能分析 4 — GShare与GSelect的比较

考虑一个14位索引（16K项PHT）的预测器。

GSelect：假设$p=7, g=7$。PC提供7位信息（区分$2^7 = 128$条不同分支），GHR提供7位历史（记忆最近128种历史模式）。如果程序中活跃分支超过128条，PC信息不足将导致严重别名。

GShare：PC和GHR各14位参与异或。能区分的分支数和历史深度都达到$2^{14}$级别，但XOR可能导致不同的(PC, GHR)组合"碰撞"到同一索引。

实测结果（SPEC CPU 2006 INT，16K项PHT）：

预测器	平均精度 (%)	MPKI
GSelect (7+7)	91.5	8.2
GSelect (10+4)	90.8	8.9
GShare (14-bit XOR)	93.1	6.7

GShare在所有配置下都优于GSelect，验证了XOR索引在信息利用效率上的优势。

路径历史

标准的GHR只记录每条分支是taken还是not-taken（1位信息），但不记录这些分支的地址。这意味着，如果两条不同路径上的分支序列恰好产生了相同的GHR值，预测器无法区分它们——即使这两条路径后续的分支行为可能完全不同。

路径历史（Path History）通过在历史中编码分支的目标地址信息来解决这个问题。具体做法是：每当一条分支被执行时，不仅将其方向（T/NT）移入GHR，还将其目标地址的低若干位混入历史信息中。

一种典型的实现是维护一个路径历史寄存器（Path History Register，PHR），每次分支执行时将分支目标地址的低$m$位与PHR进行XOR或折叠操作。然后在索引PHT时，将PHR也参与到索引计算中：

$$\text{index} = \text{PC}[k\!+\!1:2] \oplus \text{GHR}[k\!-\!1:0] \oplus \text{PHR}[k\!-\!1:0]$$

路径历史对于区分不同调用上下文（Call Context）特别有效。考虑一个函数$f()$在不同的调用点被调用：从$A$调用$f()$时内部分支倾向taken，从$B$调用时倾向not-taken。标准GHR可能在两种情况下产生相同的值（如果$f()$前面的分支序列碰巧相同），但PHR会不同，因为调用指令的目标地址不同。

Nair于1995年的研究表明，加入路径历史可以将GShare预测器的误预测率降低5%$\sim$15%，尤其是在面向对象程序（如C++/Java）中效果更为显著，因为这些程序中存在大量的虚函数调用，导致同一段代码可能从不同路径到达。

考虑一个虚函数调度的场景：

void process(Shape* s) {
    if (s->area() > threshold) { ... }  // 分支 B
}
// 调用点 A: process(circle);  // circle->area() 通常大
// 调用点 B: process(line);    // line->area() 总是 0

分支$B$的地址（PC）在两次调用中相同，且如果之前的分支序列碰巧生成了相同的GHR值，标准GShare无法区分这两种情况。但路径历史能捕捉差异：从调用点A到达$B$时，**JAL或JALR**指令的目标地址与从调用点B到达时不同，PHR的值因此不同，索引也随之不同。

这一效果在面向对象的程序中尤为突出。在gcc基准测试中，路径历史将GShare的MPKI从7.2降低到6.1（约15%的改善）；在xalancbmk（大量XML解析和虚函数调用）中，改善幅度达到20%以上。

设计提示

路径历史的引入体现了分支预测设计中的一个普遍原则：在索引函数中混入更多的上下文信息来减少别名。从BHT（仅PC）到GShare（PC+GHR），再到路径历史（PC+GHR+PHR），预测器利用的上下文信息逐步丰富。这个方向的极致发展就是TAGE预测器（第 15.0 章），它使用多种不同长度的历史来同时匹配不同粒度的上下文。

竞争的分支预测

前面讨论的各种预测器各有所长：基于局部历史的预测器擅长捕捉具有周期性模式的分支（如循环分支），基于全局历史的预测器擅长利用分支间的相关性（如连续的条件判断）。表表 14.5具体说明了这两种预测器在不同类型分支上的表现差异。

分支类型	局部历史	全局历史
固定偏向分支（90%+taken）	优	优
周期性循环分支（TTTTN…）	优	中
分支间相关性（if-if链）	差	优
数据依赖分支（随机性强）	差	差
嵌套条件分支	中	优

局部历史与全局历史预测器在不同分支类型上的表现

在实际程序中，上述各类分支同时存在，单独使用任何一种预测器都无法在所有分支上取得最优精度。

竞争预测器（Tournament Predictor，也称混合预测器，Hybrid Predictor）的核心思想是：同时维护多个基础预测器，动态选择表现最好的那个。这个概念由McFarling于1993年正式提出，他在同一篇提出GShare的论文中证明了竞争预测器可以在相同的存储预算下显著超越任何单一预测器。

双模态选择器

竞争预测器由三个部分组成：

1. 预测器P1（通常是基于局部历史的预测器）；

2. 预测器P2（通常是基于全局历史的预测器，如GShare）；

3. 元预测器（Meta Predictor），也称选择器（Chooser），决定对于每条分支应该使用P1还是P2的预测。

元预测器本身也是一个由两位饱和计数器组成的表，使用某种PC/历史的组合来索引。其计数器的含义不再是"预测分支方向"，而是"预测哪个基础预测器更准"：

• $c \geq 2$：选择P1的预测；

• $c < 2$：选择P2的预测。

元预测器的更新规则基于两个基础预测器的表现差异：

• 如果P1预测正确而P2预测错误：$c \gets \min(c + 1, 3)$（增强对P1的信任）；

• 如果P2预测正确而P1预测错误：$c \gets \max(c - 1, 0)$（增强对P2的信任）；

• 如果两者都正确或都错误：$c$不变（无信息增益）。

注意，元预测器只在两个基础预测器给出不同预测时才有意义。如果两者预测一致，无论选择哪个结果都相同，元预测器不起作用。

图图 14.8展示了竞争预测器的总体结构。

竞争预测器的总体结构。两个基础预测器（P1和P2）同时给出预测，元预测器选择其中一个作为最终预测。

竞争预测器的有效性基于一个重要的经验观察：对于大多数分支，局部预测器和全局预测器中至少有一个能给出高精度的预测，而元预测器能够在运行时学会对每条分支选择更准确的那个。McFarling的实验表明，竞争预测器的精度通常高于任何单一组件预测器，即使其总存储预算等于两个组件预测器加上元预测器的总和。

图图 14.9展示了元预测器中两位选择计数器的状态转换图。

元预测器中选择计数器的状态转换。蓝色转换表示P1（局部）表现更好，红色转换表示P2（全局）表现更好。只有当两个预测器给出不同预测时，选择才有意义。

::: warning 性能分析 5 — 竞争预测器的增益分析

假设局部预测器P1的总体精度为93%，全局预测器P2的总体精度为94%。如果两者的误预测在分支层面是互补的——即P1预测错误的分支中有较大比例被P2预测正确，反之亦然——则竞争预测器的精度将显著高于两者中任何一个。

设P1和P2同时预测错误的比例为$e_{12}$。则竞争预测器的误预测率为： $$\label{eq:tournament-err} e_{\text{tournament}} = e_{12} + e_{\text{meta}} \cdot (e_1 + e_2 - 2e_{12})$$ 其中$e_1 = 0.07$（P1的误预测率），$e_2 = 0.06$（P2的误预测率），$e_{\text{meta}}$是元预测器的选择错误率。

如果$e_{12} = 0.02$（两者仅2%的分支同时预测错误），且$e_{\text{meta}} = 0.1$（元预测器在两者不一致时有10%的选择错误率），则： $$\begin{aligned} e_{\text{tournament}} &= 0.02 + 0.1 \times (0.07 + 0.06 - 2 \times 0.02) \ &= 0.02 + 0.1 \times 0.09 = 0.029 = 2.9% \end{aligned}$$ 竞争预测器的精度为$97.1\%$，显著超过P1（93%）和P2（94%）。

:::

Alpha 21264的竞争预测器

DEC（后被Compaq和HP收购）的Alpha 21264（1998年发布）是第一款在商用高性能处理器中采用竞争预测器的处理器，其分支预测器的设计由Seznec和Michaud分析并成为后续研究的重要参考点。Alpha 21264的竞争预测器由以下三个部分组成：

局部预测器

Alpha 21264的局部预测器使用1024项的BHRT（局部历史表），每项10位历史，以及一个1024项的局部PHT（每项3位饱和计数器——这是对标准2位计数器的扩展，3位计数器有8种状态，提供了更强的滞后性）。局部预测器的索引方式是PAg：先用PC低10位索引BHRT获得10位局部历史，再用这10位历史索引1024项的PHT。

局部预测器的存储开销：

• BHRT：$1024 \times 10 = 10240$位

• 局部PHT：$1024 \times 3 = 3072$位

• 合计：$\approx 1.6$ KB

全局预测器

Alpha 21264的全局预测器使用一个12位的GHR和一个4096项的PHT（每项2位饱和计数器）。索引方式类似GSelect，使用PC低位和GHR的拼接。

全局预测器的存储开销：$4096 \times 2 = 8192$位$= 1$ KB。

元预测器

元预测器是一个4096项的表，每项2位饱和计数器，使用PC低12位索引。

元预测器的存储开销：$4096 \times 2 = 8192$位$= 1$ KB。

Alpha 21264的竞争预测器的总存储开销约为$1.6 + 1 + 1 = 3.6$ KB——在1998年的工艺节点下（EV6核心，350 nm工艺），这是一个精心优化的存储预算。其在SPEC CPU 95上的预测精度达到了约95%$\sim$96%，在当时属于顶尖水平。

Alpha 21264的竞争预测器确立了一个重要的设计范式——不同类型的预测器各有所长，组合使用优于单一使用。这一思想被后续大量处理器继承。表表 14.6列出了几款历史上重要的处理器所使用的分支方向预测器。

从表表 14.6可以看到分支预测器的发展历程：从不需要存储的静态预测（1985年），到几十字节的BHT（1993年），到数KB的竞争预测器（1998年），再到数十KB的TAGE预测器（2013年至今），预测精度从40%提升到超过98%。预测器的存储开销也增长了数百倍，但与同期处理器面积的增长相比，预测器存储仍然只占芯片面积的很小一部分。

案例研究 1 — Alpha 21264的分支预测器设计决策

Alpha 21264的设计团队在选择竞争预测器时面临以下权衡：

（1）局部历史的长度。团队测试了6位到14位的局部历史长度。10位历史（记忆1024种模式）在精度和PHT大小之间取得了最佳平衡。6位历史过短，无法捕捉长周期的循环模式；14位历史需要16K项的PHT，存储开销过大。

（2）3位vs. 2位计数器。在局部PHT中使用3位计数器而非标准的2位，是因为局部历史预测器面对的模式更加复杂——同一历史模式对应的分支结果可能在taken和not-taken之间频繁切换，3位计数器的更强滞后性有助于过滤这种噪声。实测表明，3位计数器比2位计数器在局部预测器上提高了约0.5%的精度。而全局预测器使用2位计数器，因为全局历史的信息已经足够丰富，不需要额外的滞后性。

（3）元预测器的索引。Alpha 21264的元预测器仅使用PC低位索引（不使用GHR）。这是因为元预测器的任务是判断"哪个基础预测器更擅长预测这条分支"，而这个属性主要取决于分支本身（即PC地址），与最近的全局历史关系不大。使用PC索引也使得元预测器的学习更加稳定，不会因为GHR的变化而频繁"翻转"选择。

Alpha 21264的竞争预测器在当时的SPEC CPU 95基准测试上实现了约4.5$\sim$5.5 MPKI的表现。按照第 13.0 章中的公式，在Alpha 21264的15$\sim$20级流水线和4-wide发射宽度下，这对应约$0.95 \times 4 \approx 3.8$的平均IPC（理想情况），而实际的SPEC CPU 95 IPC约为2.5$\sim$3.5。分支预测的贡献占总IPC损失的约30%$\sim$40%，说明即使是95%$\sim$96%的预测精度，对于深流水线宽发射处理器仍然是一个显著的性能瓶颈。

分支预测表的更新

分支预测器的精度不仅取决于预测算法本身，还受到更新策略的显著影响。更新策略回答的是"何时用什么信息来更新预测表"的问题。看似简单，实则涉及推测执行中的深层次矛盾。

推测更新与非推测更新

在现代乱序处理器中，分支从预测到最终确认结果之间可能经过几十个周期（取决于流水线深度和后端拥塞情况）。在这段时间内，处理器会继续推测执行大量指令，其中可能包含更多的分支。这就引出了预测表更新的两种策略：

非推测更新（Non-Speculative Update）

只在分支退休（Retire/Commit）时才更新预测表。退休意味着分支的结果已经被最终确认为正确（在提交阶段，处理器确保所有之前的指令都已正确完成，没有异常或更早的分支误预测）。

非推测更新的优点是更新信息绝对准确——只有正确路径上的分支才会更新预测表，不存在错误路径信息"污染"预测状态的风险。其缺点是更新延迟较大——从分支预测到退休可能经过30$\sim$50个周期，在这段时间内如果同一条分支再次被取到（例如在循环中），它仍然使用旧的预测状态，无法受益于上一次执行的学习结果。

推测更新（Speculative Update）

在分支执行完毕时就立即更新预测表，甚至在分支刚被预测时就推测性地更新GHR（以便后续分支能使用最新的全局历史）。

推测更新的优点是最小化学习延迟——分支的执行结果几乎立即反映在预测状态中，紧密循环中的同一分支可以在下一次迭代就使用更新后的预测。其缺点是：

（1）错误路径污染。如果一条分支被误预测，处理器在检测到误预测之前已经沿错误路径执行了若干条分支，这些"幽灵分支"的结果也已被用于推测更新预测表。当误预测被检测后，流水线被清空，但预测表中已经被错误路径的信息修改了。恢复预测表到正确状态需要额外的硬件支持（如保存预测表更新的checkpoint或undo log）。

（2）GHR的恢复。GHR的推测更新尤其复杂。每次预测分支时，预测结果立即被移入GHR（以便下一条分支使用最新历史）。如果发生误预测，GHR中包含了错误的推测结果，必须恢复到误预测点的正确状态。

GHR恢复的典型实现方式有两种：

方式一：Checkpoint恢复。为每条推测中的分支保存一份GHR的快照（Checkpoint）。当分支退休时释放快照；当检测到误预测时，用对应分支的快照恢复GHR，然后将该分支的正确结果移入恢复后的GHR。这种方式恢复速度快（1周期），但需要与ROB中的分支数量成正比的存储空间。

方式二：移位恢复。由于GHR是移位寄存器，如果记录了每条推测分支的预测结果和实际结果，可以通过反向移位来"撤销"错误的推测更新。这种方式存储开销较小，但恢复延迟与需要撤销的分支数量成正比。

图图 14.10以时序图的方式展示了GHR推测更新与Checkpoint恢复的过程。

GHR推测更新与Checkpoint恢复的时序示意。B3被误预测后，B4和B5在错误路径上执行，它们对GHR的更新通过Checkpoint恢复机制被撤销。

module ghr_with_checkpoint #(
  parameter GHR_LEN = 12,
  parameter NUM_CKPT = 32  // 最多同时推测的分支数
)(
  input  logic              clk, rst_n,
  // 预测接口
  input  logic              predict_valid,
  input  logic              predict_taken,    // 推测的方向
  output logic [GHR_LEN-1:0] ghr_out,         // 当前GHR
  output logic [$clog2(NUM_CKPT)-1:0] ckpt_id, // 分配的checkpoint ID
  // 更新/恢复接口
  input  logic              update_valid,
  input  logic              update_mispredict,
  input  logic              update_taken,      // 实际方向
  input  logic [$clog2(NUM_CKPT)-1:0] update_ckpt_id
);

  logic [GHR_LEN-1:0] ghr;
  logic [GHR_LEN-1:0] checkpoints [NUM_CKPT];
  logic [$clog2(NUM_CKPT)-1:0] alloc_ptr;

  assign ghr_out = ghr;
  assign ckpt_id = alloc_ptr;

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      ghr <= '0;
      alloc_ptr <= '0;
    end else if (update_valid && update_mispredict) begin
      // 误预测恢复：从checkpoint恢复GHR，移入正确结果
      ghr <= {checkpoints[update_ckpt_id][GHR_LEN-2:0],
              update_taken};
    end else if (predict_valid) begin
      // 推测更新：保存checkpoint，移入推测结果
      checkpoints[alloc_ptr] <= ghr;
      ghr <= {ghr[GHR_LEN-2:0], predict_taken};
      alloc_ptr <= alloc_ptr + 1;
    end
  end
endmodule

设计权衡 2 — 推测更新vs.非推测更新

推测更新的收益取决于两个因素的博弈：

正面效果：更快的学习速度。在一个紧密循环中（如迭代10次），非推测更新的延迟可能导致循环分支在前3$\sim$4次迭代中使用过时的预测状态；推测更新则可以在第2次迭代就使用第1次的结果。

负面效果：错误路径污染。当分支预测精度为$p$时，平均每$1/(1-p)$条分支就有一次误预测。误预测期间执行的所有分支的推测更新都是噪声。对于95%精度的预测器，每20条分支中有1条误预测，误预测到恢复之间平均执行约10$\sim$20条错误路径上的指令（取决于流水线深度），其中约2$\sim$4条是分支。这些"幽灵分支"会产生错误的更新。

实测结果表明，对于GHR的推测更新（即在预测时就移入推测结果），收益通常大于代价，因为GHR的正确性直接影响后续所有分支的索引。但对于PHT计数器的推测更新，收益与代价大致平衡——部分研究甚至表明非推测更新在某些工作负载下更好。因此，大多数现代处理器对GHR采用推测更新、对PHT采用非推测更新或延迟推测更新。

更新时机对精度的影响

更新时机的选择对预测精度有可量化的影响。设更新延迟为$d$个周期（从分支执行到预测表被更新），循环的迭代周期为$L$个周期（每次迭代需要的周期数），则在一个循环中，分支预测器能利用的最新信息滞后了$\lceil d/L \rceil$次迭代。

考虑一个具体的场景：

性能分析 6 — 更新延迟对循环分支的影响

假设一个循环迭代20次，每次迭代需要5个周期，循环体末尾的回跳分支的行为为19个T后跟1个NT。

场景一：推测更新（$d = 2$周期）。更新延迟仅2个周期，远小于迭代周期5个周期，因此下一次迭代时预测器已使用了上一次的结果。两位饱和计数器在第一次进入循环时从初始状态（假设WN）开始：

• 第1次迭代：预测NT，实际T——误预测。更新：WN $\to$ WT。

• 第2次迭代：预测T（WT），实际T——正确。更新：WT $\to$ ST。

• 第3$\sim$19次迭代：预测T（ST），实际T——正确。

• 第20次迭代：预测T（ST），实际NT——误预测。

总误预测：2次/20次 $= 10\%$。

场景二：非推测更新（$d = 30$周期）。更新延迟30周期，覆盖了$\lceil 30/5 \rceil = 6$次迭代，因此前6次迭代的分支使用相同的（初始/过时的）预测状态。假设初始状态为WN：

• 第1$\sim$6次迭代：预测NT，实际T——6次误预测（第1次的更新在第7次才生效）。

• 第7次迭代：第1次的更新生效（WN $\to$ WT），预测T——正确。

• 但此后来自第2$\sim$6次的更新陆续到达，可能导致计数器振荡。

• 总误预测约为7$\sim$8次/20次 $= 35\%\sim40\%$。

可以看到，更新延迟对短循环的影响远大于长循环。对于迭代1000次的循环，即使更新延迟为30周期，也只有前6次迭代受影响，总误预测率$\approx 7/1000 = 0.7\%$，可以忽略。

更新延迟的影响不仅限于循环分支。对于具有相关性的分支序列（如连续的if-else链），全局历史的更新延迟会导致后续分支在做预测时使用过时的GHR，从而无法利用前面分支的最新结果。在深流水线的现代处理器中（前端到后端20$\sim$25级），非推测更新的延迟可达30$\sim$50周期，这会显著降低全局历史预测器的有效历史深度。

为了量化更新时机的整体影响，我们定义有效历史深度的概念：

$$h_{\text{eff}} = h - \left\lfloor \frac{d}{L_{\text{avg}}} \right\rfloor$$

其中$h$是GHR的物理长度（位数），$d$是更新延迟（周期），$L_{\text{avg}}$是两条分支之间的平均间隔周期。当$d / L_{\text{avg}} > h$时，$h_{\text{eff}} \leq 0$，意味着GHR中的所有历史位都是过时的，全局历史预测器退化为简单的BHT。

在实际处理器中，$L_{\text{avg}} \approx 5\sim7$周期（每5$\sim$7条指令中有一条分支，且CPI $\approx 1$），若$d = 30$周期，则$d / L_{\text{avg}} \approx 5$。对于一个12位的GHR，$h_{\text{eff}} = 12 - 5 = 7$——有效历史深度损失了约40%。这是推动GHR推测更新的主要动力。

更新策略	平均精度 (%)	MPKI
推测更新（GHR+PHT）	93.8	5.9
推测更新GHR，非推测更新PHT	93.2	6.5
非推测更新（GHR+PHT）	91.5	8.2

更新策略对GShare预测器精度的影响（SPEC CPU INT，12位GHR，4K项PHT）

表表 14.7的数据清楚地表明：（1）GHR的推测更新对精度的影响最为显著（91.5% $\to$ 93.2%，降低了MPKI约21%），因为GHR影响所有后续分支的索引；（2）PHT的推测更新带来较小的额外收益（93.2% $\to$ 93.8%），且增加了错误路径污染的风险和恢复的复杂性。

综合以上分析，现代高性能处理器中的分支预测更新策略通常遵循以下原则：

1. GHR推测更新：在预测阶段就将推测的分支方向移入GHR，配合Checkpoint机制在误预测时恢复。这是对预测精度影响最大的设计决策。

2. PHT延迟更新：在分支执行完毕（但不必等到退休）时更新PHT计数器，平衡学习速度和正确性。部分设计在分支退休时才更新PHT以避免错误路径污染。

3. 元预测器非推测更新：在分支退休时更新元预测器的选择计数器，保证元预测器的学习基于完全正确的信息。元预测器的错误选择只影响两个基础预测器不一致时的少数分支，因此其更新延迟的影响较小。

硬件描述 2 — 分支预测更新的流水线集成

在实际的处理器流水线中，分支预测的更新涉及多个阶段的协同工作：

预测阶段（前端，周期$T$）：

• 读取BHT/PHT获得预测

• 推测更新GHR（移入预测结果）

• 保存GHR的Checkpoint到ROB或专用缓冲区

• 记录预测信息（PHT索引、预测值等）用于后续更新

执行阶段（后端，周期$T + d_1$，$d_1 \approx 10\sim20$）：

• 分支条件计算完毕，确定实际方向

• 与预测方向比较，如果不匹配则触发清空

• 如果清空：从Checkpoint恢复GHR，重定向前端

• 可选：此时立即更新PHT（延迟推测更新）

退休阶段（提交，周期$T + d_2$，$d_2 \approx 20\sim50$）：

• 分支从ROB头部退休

• 使用确认的（非推测的）分支结果更新PHT

• 更新元预测器的选择计数器

• 释放Checkpoint资源

更新信息从后端流向前端涉及较长的物理距离（在芯片上，前端和后端可能相隔数毫米），因此更新写操作通常需要额外1$\sim$2个周期的线延迟。这进一步增加了有效更新延迟。

下面通过一个综合算法来展示如何实现一个完整的GHR推测更新与恢复流程。

超标量处理器中的分支预测

前面几节讨论的分支预测算法都隐含假设每个周期只处理一条分支指令。然而，在现代超标量处理器中，前端每周期从I-Cache取出一个取指组（Fetch Group）——通常包含4$\sim$8条指令。这个取指组中可能包含0条、1条甚至多条分支指令。如何在一个周期内对取指组中的所有分支指令都进行预测，以及如何正确地保存和恢复预测状态，是超标量分支预测设计中最具挑战性的问题。本节将深入讨论这些实现细节。

取指组中的多分支问题

假设处理器的取指宽度为$W$条指令（如$W = 4$），每周期取出对齐到$W \times 4$字节边界的一个取指块。统计表明，在SPEC CPU INT基准测试中，分支指令约占所有指令的15%$\sim$25%。对于$W = 4$的取指组，平均每个取指组包含0.6$\sim$1.0条分支。虽然平均值不到1，但由于分支分布不均匀（分支指令倾向于聚集在控制流密集的代码区域），约15%$\sim$25%的取指组包含2条或更多分支。

取指组中存在多条分支时，核心问题是：哪条分支是第一条taken分支？因为一旦某条分支被预测为taken，该分支之后的所有指令都不应该被发射——它们属于"被跳过的"指令。因此，处理器需要在一个周期内完成以下操作：

1. 对取指组中的每一条指令判断它是否是分支指令；

2. 对每一条分支指令查询BHT/PHT获得方向预测；

3. 找到取指组中第一条被预测为taken的分支；

4. 将该分支之前（含该分支本身）的指令标记为有效，之后的指令标记为无效；

5. 使用BTB获取taken分支的目标地址，作为下一个取指周期的PC。

分支在取指组中的偏移量

每条分支指令在取指组中的位置由其PC的低位决定。对于4-wide取指（每条指令4字节，取指块对齐到16字节边界），分支在取指组中的位置为： $$\label{eq:fetch-offset} \text{offset} = \text{PC}[3:2]$$ offset $\in \{0, 1, 2, 3\}$，表示该分支是取指组中的第0、1、2、3条指令。

BTB中需要记录这个偏移信息。当BTB命中时，不仅返回目标地址，还返回分支在取指组中的偏移量。处理器根据偏移量生成一个有效掩码（Valid Mask）：

// 4-wide fetch, offset 为第一条 taken 分支的位置
// 有效掩码：offset 及之前的指令有效，之后无效
always_comb begin
  case (first_taken_offset)
    2'd0: valid_mask = 4'b0001;  // 仅第 0 条有效
    2'd1: valid_mask = 4'b0011;  // 第 0,1 条有效
    2'd2: valid_mask = 4'b0111;  // 第 0,1,2 条有效
    2'd3: valid_mask = 4'b1111;  // 全部有效
  endcase
  // 如果没有 taken 分支，全部有效
  if (!any_taken) valid_mask = 4'b1111;
end

并行预测的硬件实现

对取指组中的多条分支同时进行预测，需要BHT/PHT支持多个并行读端口。直接使用多端口SRAM代价高昂——一个双端口SRAM的面积约为单端口的1.5$\sim$2倍，四端口更是不可接受。实际处理器通常采用以下两种方案之一：

方案一：Banking。将BHT分成$B$个Bank（$B \geq W$），每个Bank是一个单端口SRAM。取指组中的$W$条指令根据其PC的某几位被分配到不同的Bank。由于取指组中的指令PC是连续的，使用PC[3:2]（对4-wide取指）作为Bank选择位可以保证4条指令分别落在4个不同的Bank中，避免Bank冲突。

// 4-Bank BHT, 每 Bank 1K 项 (总 4K 项)
// Bank 选择: PC[3:2], Bank 内索引: PC[13:4]
wire [1:0] bank_sel [3:0];  // 每条指令的 bank
wire [9:0] bank_idx [3:0];  // 每条指令的 bank 内索引

genvar i;
generate
  for (i = 0; i < 4; i++) begin : gen_bank
    assign bank_sel[i] = fetch_pc[3:2] + i[1:0]; // 连续指令落不同 bank
    assign bank_idx[i] = {fetch_pc[13:4]};
  end
endgenerate

方案二：复制（Replication）。维护$W$份完全相同的BHT副本。每份副本是单端口SRAM，分别服务于取指组中的一条指令。所有副本在更新时同步写入相同的数据，保持一致性。这种方案的存储开销是Banking方案的$W$倍，但完全消除了Bank冲突，且不需要复杂的Bank仲裁逻辑。

在实际设计中，Banking方案更为常用，因为它在面积效率和冲突概率之间取得了良好的平衡。对于4-wide取指的连续PC地址，Banking方案不会产生Bank冲突（因为连续地址的PC[3:2]不同）。只有在非连续的取指（如taken分支后的目标地址与之前的取指组有相同的Bank映射）时才可能冲突，但此时两个取指组分属不同周期，不存在并行读取的需求。

只预测第一条taken分支

大多数现代处理器采用的简化方案是：每周期只识别和预测取指组中的第一条taken分支。这条分支之后的指令全部被丢弃（标记为无效），下一周期从taken分支的目标地址开始取指。如果取指组中没有任何分支被预测为taken，则所有指令都有效，下一周期从顺序地址继续取指。

这种方案大幅简化了硬件设计——只需要一个"优先编码器"（Priority Encoder）来找到取指组中第一条被预测为taken的分支：

// 输入：每条指令是否为分支、是否预测 taken
// 输出：第一条 taken 分支的位置、是否存在
logic [3:0] is_branch;      // 每条指令是否为分支
logic [3:0] pred_taken;     // 每条分支是否预测 taken
logic [3:0] branch_taken;   // 是分支且预测 taken
logic [1:0] first_taken_pos;
logic       any_taken;

assign branch_taken = is_branch & pred_taken;

// 优先编码器：找第一个为 1 的位
always_comb begin
  casez (branch_taken)
    4'b???1: begin first_taken_pos = 2'd0; any_taken = 1'b1; end
    4'b??10: begin first_taken_pos = 2'd1; any_taken = 1'b1; end
    4'b?100: begin first_taken_pos = 2'd2; any_taken = 1'b1; end
    4'b1000: begin first_taken_pos = 2'd3; any_taken = 1'b1; end
    default: begin first_taken_pos = 2'd0; any_taken = 1'b0; end
  endcase
end

这种方案的代价是取指带宽的浪费：如果取指组中的第一条指令就是一条taken分支，那么该取指周期实际只提供了1条有效指令（其余3条被丢弃），取指带宽利用率仅为25%。在分支密集的代码中（如switch-case语句），这种浪费可能非常显著。

性能分析 7 — 取指带宽利用率分析

设取指宽度$W = 4$，程序中分支指令占比$f_b = 20\%$，其中taken比例$p_t = 65\%$。则每个取指周期中期望的有效指令数为：

当取指组中没有taken分支时，4条指令全部有效。设取指组中至少有一条taken分支的概率为$P_{\text{taken}}$，第一条taken分支的期望位置为$E[\text{pos}]$。

对于均匀分布的分支，每条指令是taken分支的概率为$q = f_b \times p_t = 0.2 \times 0.65 = 0.13$。则取指组中没有taken分支的概率为$(1-q)^4 = 0.87^4 \approx 0.57$。

当存在taken分支时，第一条taken分支的期望位置： $$E[\text{pos} | \text{taken存在}] = \frac{q(1-q)^0 \cdot 1 + q(1-q)^1 \cdot 2 + q(1-q)^2 \cdot 3 + q(1-q)^3 \cdot 4}{1 - (1-q)^4}$$ $$\approx \frac{0.13 \cdot 1 + 0.113 \cdot 2 + 0.098 \cdot 3 + 0.086 \cdot 4}{0.43} \approx \frac{0.977}{0.43} \approx 2.27$$

因此，平均每周期有效指令数为： $$E[\text{valid}] = 0.57 \times 4 + 0.43 \times 2.27 \approx 2.28 + 0.98 = 3.26$$

取指带宽利用率为$3.26 / 4 = 81.5\%$。即使在这种简化方案下，取指带宽损失也控制在约20%以内。对于8-wide取指，损失比例会更高——这也是为什么极宽取指设计（如8-wide或更宽）需要更复杂的多分支预测方案。

多分支并行预测的深度分析

前面的讨论建立了“只预测第一条taken分支”的基本框架。然而，随着超标量处理器的取指宽度不断增加，多分支并行预测的问题变得更加复杂和重要。本节将从分支密度分析、硬件组织、预解码协同三个维度进行深入讨论。

分支密度的统计分析

理解取指组中多分支问题的第一步是量化分支指令在代码中的分布密度。表表 14.8给出了不同工作负载类别下的分支密度统计。

工作负载	分支占比	指令/分支	taken率	6-wide组含$\geq$2分支	6-wide组含$\geq$3分支
SPEC INT	20%$\sim$25%	4$\sim$5	60%$\sim$70%	30%$\sim$40%	8%$\sim$15%
SPEC FP	10%$\sim$15%	7$\sim$10	55%$\sim$65%	10%$\sim$20%	2%$\sim$5%
Server	18%$\sim$22%	4.5$\sim$5.5	55%$\sim$65%	25%$\sim$35%	6%$\sim$12%
Browser	22%$\sim$28%	3.5$\sim$4.5	60%$\sim$70%	35%$\sim$45%	10%$\sim$18%

不同工作负载的分支密度统计

上表揭示了几个关键事实。首先，平均每5$\sim$7条指令就有一条分支指令，这意味着在6-wide取指的处理器中，一个取指组平均包含约1$\sim$2条分支。其次，分支密度因工作负载而异：控制流密集的整数程序（如编译器、浏览器引擎）的分支密度显著高于科学计算程序。第三，对于6-wide取指，约30%$\sim$40%的取指组包含2条或更多分支——这一比例不容忽视。

分支的空间分布并非均匀。在控制流密集的代码区域（如if-else链、switch-case），连续数条指令都可能是分支；而在循环体内部的计算密集区域，可能十几条指令中才有一条分支。这种聚集效应使得“取指组包含多条分支”的概率比均匀分布假设下的计算值更高。

我们可以用更精确的模型来分析这一问题。设取指宽度为$W$条指令，分支密度为$\rho$（每条指令是分支的概率），但分支在代码中服从一个参数为$(\rho, \sigma)$的聚集分布（而非均匀Bernoulli分布）。一种简单的聚集模型是负二项分布：取指组中包含$k$条分支的概率为： $$\label{eq:branch-cluster} P(k | W, \rho, r) = \binom{k + r - 1}{k} \left(\frac{\rho}{\rho + r/W}\right)^k \left(\frac{r/W}{\rho + r/W}\right)^r$$ 其中$r$为聚集参数——$r$越小，分支越倾向于聚集。实测数据表明，SPEC INT工作负载的$r \approx 3$（显著聚集），而SPEC FP的$r \approx 8$（接近均匀分布）。

为什么超标量需要一个周期预测多条分支

超标量处理器的前端性能瓶颈本质上是取指带宽问题。一个6-wide乱序处理器的后端每周期最多可以发射6条指令（受发射队列宽度限制），要维持接近峰值的IPC，前端必须以接近每周期6条指令的速率持续供给已译码的指令。

如果前端每周期只能处理取指组中的第一条taken分支，那么每次遇到taken分支，该分支之后的指令都被浪费。在分支密度高的代码中，有效取指带宽可能降至标称取指宽度的60%$\sim$70%。更严重的是，如果处理器遇到一段“分支风暴”——连续多个取指组都在前几条指令就遇到taken分支——前端的有效供给率可能暂时降至每周期1$\sim$2条指令，导致后端严重饥饿。

量化这一影响需要考虑取指组中taken分支的位置分布。设取指宽度$W = 6$，分支密度$\rho = 0.20$，taken率$p_t = 0.65$。定义有效取指率（Effective Fetch Rate, EFR）为每周期平均送入解码器的有效指令数与$W$之比： $$\label{eq:efr} \text{EFR} = \frac{E[\text{有效指令数}]}{W}$$

当只处理第一条taken分支时，EFR取决于第一条taken分支的位置。对于6-wide取指：

分支密度 $\rho$	taken率 $p_t$	EFR（4-wide）	EFR（6-wide）
0.15	0.60	84.2%	79.5%
0.20	0.65	81.5%	75.8%
0.25	0.70	77.3%	70.2%
0.30	0.75	73.1%	65.4%

可以看到，随着取指宽度从4增加到6，EFR的下降更为显著。这是因为更宽的取指组有更高的概率包含多条分支，且第一条taken分支的期望位置并不随取指宽度线性增长。对于8-wide或更宽的取指设计，EFR可能降至60%以下——此时前端的有效供给率远低于后端的消费能力，成为整体性能的瓶颈。

Fetch Group中分支的识别机制

在取指组中识别哪些指令是分支指令，有两种基本方法：

方法一：BTB/FTB查询。如16.1 节中将详细讨论的，BTB（Branch Target Buffer）或FTB（Fetch Target Buffer）以取指块地址为索引，记录了该取指块中所有分支指令的位置、类型和目标地址。取指阶段通过查询BTB/FTB来识别分支，无需进行任何指令译码。这种方法的优点是速度快（与I-Cache访问并行，1周期内完成），缺点是依赖BTB的覆盖率——BTB未记录的分支（如首次执行的分支）无法被识别。

方法二：预解码标记。在指令从L2 Cache或主存填充到L1 I-Cache时，硬件进行预解码（Pre-decode），为每条指令附加若干标记位，指示该指令是否为分支指令及其类型。预解码标记存储在I-Cache的额外位中（通常每条指令2$\sim$4位）。取指阶段读取I-Cache时，同时获得指令数据和预解码标记，不需要进行完整的指令译码就能识别分支。这种方法的优点是覆盖率为100%（只要指令在I-Cache中，其预解码标记就可用），缺点是需要I-Cache存储额外的预解码位，增加了I-Cache的面积开销。

在实际处理器中，两种方法通常结合使用：BTB/FTB提供分支的目标地址和方向预测，预解码标记作为BTB的补充，确保即使BTB未命中也能在取指阶段识别分支指令的存在。第 22.0 章将详细讨论预解码的实现机制。

6-wide取指组中多分支的识别与预测流程。取指组包含两条分支（slot 1的BEQ和slot 4的BNE），预解码标记和BTB/FTB并行提供分支识别信息，BHT/PHT提供方向预测，优先编码器找到第一条taken分支（slot 4的BNE），生成有效掩码并跳转到目标地址。

多端口BHT/PHT与Multi-bank组织

当取指组中包含多条分支时，BHT/PHT需要在一个周期内为所有分支提供方向预测。这对预测表的读带宽提出了很高的要求。

对于6-wide取指，取指组中最多可能有6条分支指令（尽管这种情况极为罕见）。最坏情况下需要BHT/PHT支持6个并行读端口。但多端口SRAM的面积和延迟开销随端口数的增加而急剧增长，6端口SRAM通常不可接受。

实际设计中采用的方案是Multi-bank组织，其核心思想是：取指组中的连续指令必然有不同的PC低位，因此它们在BHT/PHT中的索引天然落在不同的Bank中。

硬件描述 3 — 多分支预测的Multi-bank BHT硬件实现

以6-wide取指为例，设计一个6-bank的BHT用于并行预测：

Bank分配策略。BHT被分为$B = 8$个Bank（取2的幂以简化地址解码），每个Bank为单端口SRAM。指令在取指组中的位置为$\text{slot} \in \{0, 1, \ldots, 5\}$，对应的PC为$\text{PC}_{\text{base}} + 4 \times \text{slot}$。Bank选择使用PC的低位：$\text{Bank\_ID} = \text{PC}[4:2]$（对于4字节指令）。由于取指组中6条指令的$\text{PC}[4:2]$是连续的模8值，当取指块8字节对齐时，6条指令恰好落在6个不同的Bank中，不存在Bank冲突。

处理未对齐取指。当取指块的起始地址不是$8 \times 4 = 32$字节对齐时（例如跳转目标落在取指块的中间位置），取指组中的指令可能会出现Bank冲突。解决方案是使用$B = 8$个Bank而非$B = 6$个，为未对齐情况留出冗余Bank，确保任意连续6条4字节对齐的指令都不会产生Bank冲突。

全局历史的处理。如果BHT使用GShare方式（PC $\oplus$ GHR作为索引），不同slot的分支需要使用不同的GHR值——因为在取指组内部，前面分支的预测结果应该影响后面分支的GHR。但在并行预测中，前面分支的预测结果尚未产生。解决方案有两种：（1）所有slot使用相同的GHR值（忽略取指组内的历史依赖），接受少量预测精度损失；（2）使用提前计算（ahead computation），为每个slot预计算假设前面分支分别taken和not-taken时的GHR值，然后根据前面分支的实际预测结果选择正确的GHR值——但这增加了组合逻辑延迟。

存储开销。8-bank BHT的总存储量与等容量的单bank BHT相同（SRAM总位数不变），额外开销只有Bank选择逻辑和交叉开关（crossbar）——将各Bank的输出路由到对应slot的方向预测结果。对于8个Bank、6个slot的配置，交叉开关为$8 \times 6$的部分交叉矩阵，面积约为BHT SRAM面积的5%$\sim$10%。

“只预测第一条taken分支”的工程权衡

前面分析表明，“只预测第一条taken分支”的简化方案会导致取指带宽的浪费。那么，为什么大多数现代处理器仍然采用这一方案，而不是实现更激进的多分支预测？

论据一：复杂度成本。如果要预测取指组中的第二条taken分支（即处理完第一条taken分支后，继续取指该分支的目标地址处的下一个取指块），处理器需要在一个周期内进行两次BTB查询——第一次查询当前取指块，第二次查询第一条taken分支的目标地址所在的取指块。两次BTB查询意味着要么BTB需要双读端口（面积翻倍），要么两次查询串行进行（延迟翻倍，需要额外的流水线级）。

论据二：收益有限。从统计角度看，取指组中第一条taken分支之后的指令只占总指令的一个相对较小的比例。假设EFR = 80%，这意味着20%的取指带宽被浪费。但这20%的带宽损失并不直接转化为20%的IPC损失——取指瓶颈只在前端供给率持续低于后端消费率时才会影响IPC。在实际运行中，后端也经常因为Cache缺失、长延迟操作等原因而空闲，此时前端的带宽浪费不会造成额外的性能损失。

论据三：FTB/FTQ的缓冲。现代处理器使用取指目标队列（Fetch Target Queue, FTQ）来解耦预测和取指。即使某个周期的预测带宽较低（只预测到一条taken分支），FTQ中缓冲的多个预测结果可以让取指单元在后续周期“追赶”回来。FTQ的深度通常为16$\sim$32项，足以平滑短期的预测带宽波动。

设计权衡 3 — 多分支预测的方案比较

表表 14.9对比了三种多分支处理方案。

方案	每周期处理	硬件代价	EFR
只处理第一条taken分支	1个取指块的部分指令	单端口BTB，简单优先编码器	75%$\sim$85%
处理第一条taken分支+跳转到目标	当前块+目标块各一次	双端口BTB或多周期BTB	85%$\sim$92%
FTB + FTQ	当前块的全部有效指令	FTB结构+FTQ队列	80%$\sim$90%

在实际的商业处理器中，FTB + FTQ方案已成为主流选择，因为它在不增加BTB端口数的前提下，通过取指块级别的预测和队列缓冲实现了较高的EFR。第 17.0 章将详细讨论FTQ的设计和超标量前端的完整预测系统。

分支密度与取指宽度的交互影响

取指宽度的选择与分支密度之间存在一个深层的工程权衡。加宽取指可以增加峰值取指带宽，但分支对取指的“截断效应”也随之放大：

$$\text{EFR}(W) = \frac{E[\min(W, \text{第一条taken分支的位置})]}{W}$$

当取指宽度$W$增加时，分子（有效指令数的期望）增长速度慢于分母（$W$），因此EFR随$W$递减。这意味着从4-wide到8-wide的取指宽度翻倍，有效取指带宽的增长远不到2倍。

性能分析 8 — 取指宽度与有效带宽

对于一个分支密度$\rho = 0.20$、taken率$p_t = 0.65$的程序，不同取指宽度的EFR和有效取指带宽如下：

取指宽度 $W$	EFR	有效带宽（指令/周期）	边际增量
4	81.5%	3.26	—
6	75.8%	4.55	+1.29
8	71.2%	5.70	+1.15
12	65.3%	7.84	+2.14
16	60.8%	9.73	+1.89

从4-wide到6-wide，取指宽度增加50%，有效带宽增加39.6%——收益接近线性。但从8-wide到16-wide，取指宽度翻倍，有效带宽仅增加70.7%——边际收益明显递减。这一分析帮助解释了为什么绝大多数高性能处理器的取指宽度停留在6$\sim$8-wide：更宽的取指在面积和功耗上的成本增长近乎线性，但有效带宽的收益增长次线性。

上述分析呼应了第 2.0 章中关于取指宽度选择的讨论——取指宽度不仅受I-Cache带宽和解码宽度的约束，还受分支截断效应的约束。在三者之中，分支截断效应往往是最根本的限制因素。第 17.0 章中将从系统集成的角度，讨论如何通过FTQ（取指目标队列）和解耦前端来缓解分支截断效应对超标量取指带宽的限制。而第 22.0 章中讨论的预解码机制正是本节中分支识别方法（预解码标记）的完整硬件实现。

分支预测的流水线组织

在高频超标量处理器中，分支预测不是在单个周期内完成的——BTB查找、方向预测、目标地址计算等操作往往需要多个流水线阶段来完成。这个"预测流水线"的设计直接影响处理器的取指吞吐量和分支预测延迟。

单周期预测与多周期预测

最简单的方案是将分支预测压缩在一个周期内完成：BTB查找、方向预测和目标地址选择全部在同一周期的组合逻辑中完成。这种方案的优点是零预测泡沫（Zero-Bubble Prediction）——每周期都能产生一个预测结果，取指不会因为等待预测而停顿。

但在高频设计中（如3 GHz以上），单周期内完成所有预测操作可能违反时序约束。以一个4K项BTB为例，BTB的访问延迟约为0.3$\sim$0.5 ns（取决于工艺和SRAM的实现），加上方向预测器的PHT访问（0.2$\sim$0.3 ns）和MUX选择逻辑（0.1 ns），总延迟可达0.6$\sim$0.9 ns。在3.5 GHz的时钟频率下，时钟周期仅为0.286 ns，根本无法在一个周期内完成。

因此，高频处理器通常将分支预测分成2$\sim$3个流水线阶段：

阶段BP1（BTB + 快速方向预测）：

• BTB查找：确认当前取指块中是否存在分支指令

• 快速方向预测器（如BHT或bimodal预测器）给出初步方向预测

• 结果在本周期末输出

阶段BP2（精确方向预测 + 目标选择）：

• 使用GHR/全局历史的复杂方向预测器（如GShare、TAGE）给出精确预测

• 如果精确预测与快速预测不同，覆盖快速预测的结果

• 计算下一个取指地址

这种两阶段设计意味着如果精确预测器在BP2阶段覆盖了BP1的预测，就会产生1个周期的预测修正泡沫（prediction correction bubble）——BP1已经用错误的预测启动了一轮取指，这轮取指需要被丢弃。统计表明，快速预测器与精确预测器不一致的概率约为3%$\sim$8%，因此平均泡沫率约为0.03$\sim$0.08个周期/取指。

BTB与方向预测器的协同

BTB和方向预测器必须紧密配合。BTB回答"这个取指块中是否有分支以及分支的目标是什么"，方向预测器回答"这条分支是否跳转"。两者的配合有以下关键时序约束：

（1）BTB必须先于方向预测器完成——只有知道了取指块中哪些指令是分支，才能有意义地进行方向预测。但在实际实现中，BTB和方向预测器可以并行访问，因为方向预测器只需要PC索引（不需要等待BTB确认），而BTB的结果只是用来确定方向预测是否需要被使用。

（2）BTB未命中时的处理——如果BTB中没有当前PC对应的分支记录，即使方向预测器预测taken，处理器也无法知道跳转目标。此时有两种选择：（a）假设当前取指块中没有分支，按顺序继续取指；（b）使用方向预测器的结果标记当前取指块为"可能有分支"，等待译码阶段确认。方案（a）更简单，但可能错过BTB冷启动期间的分支。

（3）BTB命中但方向预测为not-taken时——BTB确认了分支的存在和目标，但方向预测器预测不跳转。此时处理器按顺序取指，分支指令仍然进入流水线正常执行。如果后来发现分支实际为taken（方向预测错误），则触发误预测恢复。

分支预测的多阶段流水线。BP1阶段进行BTB查找和快速方向预测；BP2阶段进行精确方向预测并可能覆盖BP1的结果（产生1周期修正泡沫）。

预测解耦（Decoupled Prediction）

一种更先进的设计方案是将分支预测器与取指管线解耦——分支预测器独立运行，提前产生多个周期的取指地址序列，存入一个取指目标队列（Fetch Target Queue, FTQ）。取指管线从FTQ中读取地址进行I-Cache访问。

解耦的优势是：

• 分支预测器可以超前运行（run-ahead），在取指管线因I-Cache miss而停顿时继续产生预测，积累多个取指请求；

• 分支预测器的时序约束放松——即使预测需要2$\sim$3个周期，只要FTQ不为空，取指管线就不会因等待预测而停顿；

• FTQ可以作为预测信息的缓冲区，减少I-Cache miss期间预测状态丢失的风险。

FTQ的典型深度为16$\sim$32项。每项记录一个取指块的起始地址、有效指令掩码、是否包含分支以及分支的预测方向。FTQ在现代处理器中已是标准设计——Intel从Nehalem（2008年）开始、ARM从Cortex-A76开始都采用了FTQ解耦架构。

PTAB：预测结果的保存

在超标量处理器中，分支指令从被预测到最终执行确认（或退休），可能经过20$\sim$50个流水线周期。在此期间，处理器需要保存每条分支的预测信息，以便在分支执行完毕后与实际结果进行比较。这个保存预测信息的结构称为PTAB（Prediction Target Address Buffer），或更一般地称为分支预测队列（Branch Prediction Queue）。

PTAB的每项结构

PTAB的每一项对应一条正在飞行中（in-flight）的分支指令，记录了该分支在预测阶段的全部信息。典型的PTAB表项包含以下字段：

字段	含义	位宽（典型值）
valid	该项是否有效	1
pc	分支指令的PC	39$\sim$48
pred_taken	预测方向（T/NT）	1
pred_target	预测的目标地址	39$\sim$48
ghr_ckpt	GHR的checkpoint	12$\sim$20
pht_index	预测时使用的PHT索引	10$\sim$14
pht_counter	预测时读出的计数器值	2$\sim$3
meta_counter	元预测器计数器值（竞争预测器）	2
pred_source	预测来自哪个子预测器	2$\sim$3
rob_id	对应的ROB编号	6$\sim$8
branch_mask	分支掩码位（用于错误路径清除）	1

每项的总宽度约为120$\sim$160位。对于一个支持32条同时飞行分支的处理器，PTAB的总存储约为$32 \times 150 = 4800$位$\approx 0.6$ KB。

PTAB的工作流程

PTAB的操作贯穿分支指令的整个生命周期：

（1）分配阶段（预测/重命名时）。当前端遇到一条分支指令时，在PTAB中分配一项。将预测方向、预测目标地址、GHR checkpoint、PHT索引和计数器值等信息写入该项。PTAB的分配使用一个FIFO指针管理——分配指针（allocate pointer）指向下一个可分配的空闲项，退休指针（retire pointer）指向最老的未退休项。

（2）比较阶段（分支执行完毕时）。当分支在执行单元中计算出实际方向和实际目标地址后，将实际结果与PTAB中保存的预测结果进行比较：

• 如果方向和目标地址都匹配——预测正确，分支可以正常退休；

• 如果方向不匹配或目标地址不匹配——发生误预测，触发流水线清空和恢复。

（3）恢复阶段（误预测时）。PTAB中保存的GHR checkpoint用于恢复GHR到正确状态。保存的PHT索引和旧计数器值用于精确地更新PHT——注意，由于误预测恢复需要使用预测时的索引（而非当前GHR计算出的索引，因为GHR可能已被后续分支修改），PTAB中保存索引信息至关重要。

（4）更新阶段（退休时）。分支退休时，使用PTAB中保存的PHT索引和实际结果更新预测表。然后释放PTAB项。

module ptab #(
  parameter DEPTH = 32,
  parameter PC_WIDTH = 40,
  parameter GHR_WIDTH = 16,
  parameter PHT_IDX_WIDTH = 12
)(
  input  logic                     clk, rst_n,
  // 分配接口（前端）
  input  logic                     alloc_valid,
  input  logic [PC_WIDTH-1:0]      alloc_pc,
  input  logic                     alloc_pred_taken,
  input  logic [PC_WIDTH-1:0]      alloc_pred_target,
  input  logic [GHR_WIDTH-1:0]     alloc_ghr_ckpt,
  input  logic [PHT_IDX_WIDTH-1:0] alloc_pht_index,
  input  logic [1:0]               alloc_pht_counter,
  output logic [$clog2(DEPTH)-1:0] alloc_id,
  output logic                     alloc_ready,
  // 执行结果接口（后端）
  input  logic                     exec_valid,
  input  logic [$clog2(DEPTH)-1:0] exec_id,
  input  logic                     exec_actual_taken,
  input  logic [PC_WIDTH-1:0]      exec_actual_target,
  output logic                     exec_mispredict,
  output logic [GHR_WIDTH-1:0]     exec_ghr_restore,
  output logic [PHT_IDX_WIDTH-1:0] exec_pht_index,
  // 退休接口
  input  logic                     retire_valid
);

  // PTAB 存储
  typedef struct packed {
    logic                     valid;
    logic [PC_WIDTH-1:0]      pc;
    logic                     pred_taken;
    logic [PC_WIDTH-1:0]      pred_target;
    logic [GHR_WIDTH-1:0]     ghr_ckpt;
    logic [PHT_IDX_WIDTH-1:0] pht_index;
    logic [1:0]               pht_counter;
  } ptab_entry_t;

  ptab_entry_t entries [DEPTH];
  logic [$clog2(DEPTH)-1:0] alloc_ptr, retire_ptr;

  assign alloc_id = alloc_ptr;
  assign alloc_ready = (entries[alloc_ptr].valid == 1'b0);

  // 分配
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      alloc_ptr <= '0;
      for (int i = 0; i < DEPTH; i++)
        entries[i].valid <= 1'b0;
    end else if (alloc_valid && alloc_ready) begin
      entries[alloc_ptr].valid        <= 1'b1;
      entries[alloc_ptr].pc           <= alloc_pc;
      entries[alloc_ptr].pred_taken   <= alloc_pred_taken;
      entries[alloc_ptr].pred_target  <= alloc_pred_target;
      entries[alloc_ptr].ghr_ckpt     <= alloc_ghr_ckpt;
      entries[alloc_ptr].pht_index    <= alloc_pht_index;
      entries[alloc_ptr].pht_counter  <= alloc_pht_counter;
      alloc_ptr <= alloc_ptr + 1;
    end
  end

  // 执行结果比较
  assign exec_mispredict = exec_valid && (
    entries[exec_id].pred_taken  != exec_actual_taken ||
    (exec_actual_taken &&
     entries[exec_id].pred_target != exec_actual_target)
  );
  assign exec_ghr_restore = entries[exec_id].ghr_ckpt;
  assign exec_pht_index   = entries[exec_id].pht_index;

  // 退休释放
  always_ff @(posedge clk) begin
    if (retire_valid) begin
      entries[retire_ptr].valid <= 1'b0;
      retire_ptr <= retire_ptr + 1;
    end
  end
endmodule

PTAB的容量需求

PTAB的深度取决于处理器中同时飞行的分支指令数量上限。这个上限由两个因素决定：

（1）ROB的深度。ROB中最多有多少条指令，就最多有多少条分支。对于一个256项的ROB，假设分支占比20%，平均约有50条飞行中的分支。

（2）GHR checkpoint的成本。每条飞行中的分支都需要保存一份GHR checkpoint。如果GHR为16位，每个checkpoint只需16位存储；但如果GHR很长（如TAGE预测器使用的1000+位全局历史），保存完整checkpoint的代价不可接受。此时通常使用增量恢复（incremental recovery）——只保存GHR被修改的差异信息。

在实际的高性能处理器中，PTAB的深度通常为16$\sim$64项。Intel的Sandy Bridge微架构使用48项的分支预测队列；ARM的Cortex-A77使用64项。PTAB的深度是处理器能够容忍的最大推测深度的一个关键限制因素——当PTAB满时，前端必须停顿，等待最老的分支退休释放PTAB项。

硬件描述 4 — PTAB与ROB的关系

PTAB可以实现为ROB的一部分（将预测信息嵌入ROB的每一项中），也可以实现为独立的结构。两种方案各有利弊：

嵌入ROB：不需要额外的分配/释放逻辑，PTAB项的生命周期与ROB项完全一致。但ROB的每一项都需要加宽以包含预测信息（约80$\sim$100额外位），即使该ROB项不是分支指令也是如此，浪费了大量存储。对于一个256项的ROB，增加的存储为$256 \times 100 = 25600$位$\approx 3.1$ KB。

独立PTAB：只有分支指令才分配PTAB项，存储效率高。但需要维护PTAB与ROB之间的映射关系（通过ROB编号），且需要独立的分配/释放机制。存储为$48 \times 150 = 7200$位$\approx 0.9$ KB（假设48项PTAB），远小于嵌入方案。

大多数现代高性能处理器采用独立PTAB方案。

分支掩码与错误路径指令的清除

当检测到分支误预测时，处理器需要清除该分支之后在错误路径上取到的所有指令。在超标量处理器中，这些错误路径指令可能分布在流水线的各个阶段——从取指缓冲区、译码队列到发射队列、ROB中都可能存在。如何快速、精确地识别和清除这些指令，是超标量处理器设计中的关键问题。

基于ROB编号的清除

最直接的方法是利用ROB的顺序编号。每条指令在进入ROB时获得一个唯一的顺序编号（ROB ID），编号按程序顺序递增。当分支$B$发生误预测时，$B$的ROB ID为$\text{id}_B$，所有ROB ID大于$\text{id}_B$的指令（即在$B$之后进入ROB的指令）都是错误路径上的指令，需要被清除。

ROB编号的比较需要处理回绕（wrap-around）的情况。在环形ROB中，编号从0增到$N-1$后回绕到0。比较两个编号的先后关系需要同时考虑分配指针和回绕：

// 判断 id_a 是否在 id_b 之后（更年轻）
// head: ROB 的退休指针（最老的指令）
function automatic logic is_younger(
  input logic [$clog2(ROB_DEPTH)-1:0] id_a,
  input logic [$clog2(ROB_DEPTH)-1:0] id_b,
  input logic [$clog2(ROB_DEPTH)-1:0] head
);
  // 将编号映射为相对于 head 的偏移
  logic [$clog2(ROB_DEPTH)-1:0] offset_a, offset_b;
  offset_a = id_a - head;
  offset_b = id_b - head;
  return (offset_a > offset_b);
endfunction

基于ROB编号的清除可以在1$\sim$2个周期内完成——只需将ROB的分配指针重置到$\text{id}_B + 1$，并将所有编号大于$\text{id}_B$的项标记为无效。但这种方法在实际实现中的挑战在于：清除操作不仅需要应用于ROB，还需要同时清除发射队列（Issue Queue）、加载/存储队列（LSQ）、物理寄存器映射等多个结构中的相关项。在这些结构中，按ROB编号范围清除需要对每一项进行并行比较，增加了逻辑面积和时序压力。

分支掩码机制

分支掩码（Branch Mask）是一种更高效的错误路径清除机制，在MIPS R10000、Alpha 21264等经典超标量处理器中被广泛采用。

分支掩码机制的核心思想是：为每条飞行中的（尚未执行确认的）分支指令分配一个唯一的掩码位（mask bit）。处理器维护一个$K$位的分支掩码向量（如$K = 16$或32），每个位对应一条飞行中的分支。当一条新分支被预测时，从掩码向量中分配一个空闲位。

关键在于：每条指令（不仅是分支指令）在进入流水线时，都会被标记上当前所有尚未确认的分支的掩码位的集合。具体而言，如果指令$I$是在分支$B_1$、$B_2$、$B_3$的推测路径上被取到的（即$B_1$、$B_2$、$B_3$尚未执行确认），则$I$的分支依赖掩码为$\{B_1, B_2, B_3\}$对应的掩码位的OR。

假设处理器有4位分支掩码，当前3条飞行中的分支分别占用位0、1、2。考虑以下指令序列：

指令	分支掩码	含义
ADD r1, r2, r3	0b0001	依赖于分支$B_0$
$B_0$: BEQ r4, r5, target0	0b0001	分配掩码位0
SUB r6, r7, r8	0b0011	依赖于$B_0$和$B_1$
$B_1$: BNE r9, r10, target1	0b0011	分配掩码位1
MUL r11, r12, r13	0b0111	依赖于$B_0$、$B_1$、$B_2$
$B_2$: BLT r14, r15, target2	0b0111	分配掩码位2
LW r16, 0(r17)	0b0111	依赖于$B_0$、$B_1$、$B_2$

当$B_1$执行确认且预测正确时，释放掩码位1，$B_1$之后的指令的分支掩码中位1被清除（但位0和位2保留，因为$B_0$和$B_2$尚未确认）。

当$B_1$执行确认但预测错误时，处理器广播掩码位1。所有分支掩码中包含位1的指令都是$B_1$之后的指令（即潜在的错误路径指令），需要被清除。具体而言，SUB、$B_1$本身、MUL、$B_2$、LW的分支掩码都包含位1，它们全部被清除。

分支掩码的清除操作极其高效——只需将误预测分支的掩码位广播到所有流水线结构（ROB、发射队列、LSQ等），每一项通过一个简单的AND操作检查自己的分支掩码是否包含该位：

// 对发射队列中的每一项进行清除检查
// squash_mask: 需要清除的分支掩码位（one-hot）
// entry_dep_mask: 该项的分支依赖掩码
// 如果依赖掩码与清除掩码有交集，则该项需要被清除
wire needs_squash = |(entry_dep_mask & squash_mask);

// 广播清除：对所有项并行执行
genvar i;
generate
  for (i = 0; i < IQ_DEPTH; i++) begin : gen_squash
    wire squash_this = |(iq_entries[i].branch_dep_mask &
                         squash_mask);
    always_ff @(posedge clk) begin
      if (squash_this)
        iq_entries[i].valid <= 1'b0;
    end
  end
endgenerate

分支掩码机制的清除延迟仅为1个周期（广播+AND+清除），且不需要按ROB编号排序比较。这使得它在时序上远优于基于ROB编号范围的清除方案。

分支掩码的位数限制

分支掩码的位数$K$决定了处理器最多能同时容忍多少条未确认的分支。当所有$K$位都被占用时，如果前端再遇到新的分支指令，必须停顿等待某条飞行中的分支执行完毕并释放掩码位。

$K$的典型值为8$\sim$32。在SPEC CPU基准测试中，同时飞行的分支数量取决于ROB深度和分支密度。对于一个224项ROB的处理器，如果分支占比20%，最坏情况下可能有约45条飞行中的分支。但通常分支的执行延迟远小于ROB的总延迟，大部分分支很快就能确认并释放掩码位。实测表明，$K = 16$对于大多数工作负载已经足够，$K = 32$在极端情况下仍有少量停顿。

设计权衡 4 — 分支掩码位数K的选择

$K$越大，因掩码耗尽导致的停顿越少，但硬件代价也越高：

（1）每条指令的额外存储。流水线中的每条指令（不仅是分支）都需要携带一个$K$位的分支依赖掩码。对于$K = 16$，每条指令增加16位存储；$K = 32$则增加32位。在ROB、发射队列、LSQ等所有流水线缓冲中，这些额外位的总面积可能相当可观。

（2）广播逻辑的扇出。清除操作需要将$K$位的掩码广播到所有流水线项。$K$越大，广播线的扇出越高，可能影响时序。

（3）分配逻辑。需要一个$K$位的空闲列表和优先编码器来管理掩码位的分配和释放。

实测在SPEC CPU 2017 INT上的停顿频率：

掩码位数$K$	因掩码耗尽的停顿周期占比
8	3.2%
12	0.8%
16	0.1%
24	$<$0.01%
32	0%

$K = 16$是一个优化的甜点——停顿几乎可以忽略，而硬件开销相对可控。

分支掩码与Tag List

在某些处理器设计中（如参考书中描述的方案），使用Tag List（标记列表）替代或补充分支掩码。Tag List是PTAB中每个分支对应的一个标记值，它被附加到该分支之后所有指令上。当分支误预测时，广播该标记值，所有携带该标记的指令被清除。

Tag List与分支掩码的区别在于：

• 分支掩码是集合——每条指令记录它依赖的所有未确认分支的集合，可以精确地清除只依赖于特定分支的指令；

• Tag List是编号值——每条指令只记录"最近的一条分支"的编号，清除时只能清除编号匹配的指令。

分支掩码方案在语义上更精确（可以处理嵌套分支的部分清除），而Tag List方案的硬件开销更低（每条指令只需$\log_2 K$位而非$K$位）。在实际处理器中，两种方案有时会结合使用——分支掩码用于精确的选择性清除，Tag List用于快速的批量清除。

设计提示

分支掩码和Tag List机制不仅用于分支误预测的恢复，还广泛应用于处理器中的其他推测执行场景：（1）内存消歧——当一条加载指令被推测性地提前执行（绕过了一条地址未知的存储指令），如果后来发现存储地址确实与加载地址冲突，需要清除加载及其之后的所有指令；（2）异常处理——当一条指令产生异常时，需要清除该指令之后的所有推测指令。分支掩码/Tag List提供了统一的清除机制来处理所有这些场景。

误预测恢复的实现

分支误预测恢复是超标量处理器中最复杂的操作之一，涉及前端和后端的多个子系统的协同。本节详细描述恢复过程的各个步骤。

恢复的触发

当分支指令在执行单元中计算出条件结果并与预测方向比较后，如果发现不匹配，执行单元生成一个误预测信号（mispredict signal），包含以下信息：

• 误预测分支的ROB编号或PTAB编号

• 正确的分支方向（taken/not-taken）

• 正确的目标地址（对于taken分支）

• 分支掩码位编号（用于清除错误路径指令）

如果同一周期有多条分支同时报告误预测（在多执行端口的处理器中可能发生），处理器需要选择程序顺序上最早的那条进行恢复。因为更早的分支误预测意味着更晚的分支本身就在错误路径上，无需处理。

恢复步骤

误预测恢复的具体步骤如下：

步骤1：流水线清空（1个周期）。广播误预测分支的分支掩码位，清除所有流水线结构（取指缓冲、译码队列、发射队列、ROB、LSQ）中依赖于该分支的项。同时冻结前端，停止取指。

步骤2：前端重定向（1$\sim$2个周期）。将PC重定向到正确的地址：

• 如果分支应为taken但被预测为not-taken：正确地址 = 分支的目标地址

• 如果分支应为not-taken但被预测为taken：正确地址 = 分支PC + 4（分支的下一条顺序指令）

步骤3：GHR恢复（1个周期）。从PTAB中取出该分支对应的GHR checkpoint，恢复GHR到预测时的状态，然后将正确的分支方向移入GHR。

步骤4：重命名映射表恢复（1$\sim$4个周期）。恢复寄存器重命名映射表（RAT）到该分支预测时的状态。这是恢复过程中最耗时的步骤。常见的恢复方案包括：

• Checkpoint恢复：从预先保存的RAT快照直接恢复（1周期），但需要大量的checkpoint存储；

• 逐步回退（Walk-back）：从ROB尾部逐条撤销重命名操作，恢复到误预测点（$N$个周期，$N$为需要撤销的指令数）；

• BRAT（Branch Register Alias Table）：为每条飞行中的分支维护一份增量RAT，记录该分支之后的重命名修改（恢复时间与修改数量成正比）。

步骤5：重新取指（正常流水线延迟）。前端从正确地址重新开始取指，新指令进入流水线。

从误预测检测到新的正确路径指令到达执行阶段的总延迟称为误预测惩罚（Misprediction Penalty），通常为15$\sim$25个周期，其中：

• 清空+重定向+GHR恢复：2$\sim$3个周期

• RAT恢复：1$\sim$4个周期（取决于恢复方案）

• 重新填充流水线（从取指到执行）：10$\sim$20个周期

性能分析 9 — 误预测恢复延迟的分解

以一个典型的6-wide乱序处理器（类似ARM Cortex-A77）为例：

恢复步骤	延迟（周期）	可否重叠
流水线清空	1	—
前端重定向	1	与清空重叠
GHR恢复	1	与重定向重叠
RAT checkpoint恢复	1	与重定向重叠
I-Cache访问	2$\sim$4	—
预解码/译码	2$\sim$3	—
重命名	1$\sim$2	—
分发/发射	1$\sim$2	—
执行	1+	—
总误预测惩罚	11$\sim$14

注意，清空/重定向/GHR恢复/RAT恢复这几个步骤可以在同一周期内并行完成（或至少重叠执行），因此恢复过程的关键路径主要由重新填充流水线的延迟决定。这也是为什么流水线越深，分支误预测的惩罚越大——流水线从取指到执行的级数直接决定了惩罚的下限。

间接分支预测

前面讨论的分支方向预测主要解决条件分支的方向（taken/not-taken）预测问题。但还有一类重要的分支指令——间接分支（Indirect Branch），其目标地址不是指令中编码的固定值，而是来自寄存器的运行时值。在RISC-V中，**JALR**指令（JALR rd, rs1, offset）就是典型的间接分支，其目标地址为rs1 + offset。在x86中，JMP [rax]、CALL [rbx]、RET等都是间接分支。

间接分支的目标地址不固定，这使得简单的BTB（只记录最近一次的目标地址）对间接分支的预测精度很低。间接分支在以下场景中大量出现：

• 虚函数调用（C++/Java）：obj->method()编译为通过虚表的间接调用，目标地址取决于对象的动态类型；

• switch语句：编译器通常将switch编译为跳转表（Jump Table），通过间接跳转实现；

• 函数指针：回调函数、动态链接等机制使用函数指针；

• 解释器分派（Interpreter Dispatch）：如Python、JavaScript解释器中的opcode分派循环。

在面向对象程序（C++、Java）和脚本语言解释器中，间接分支占所有分支的5%$\sim$15%，但由于其高误预测率，对总体MPKI的贡献可达30%$\sim$50%。

返回地址栈

函数返回是间接分支中最常见也是最容易预测的一种。函数调用和返回具有严格的LIFO（后进先出）关系——最后一个被调用的函数最先返回。因此，使用一个硬件栈即可精确预测返回地址。

返回地址栈（Return Address Stack，RAS）是一个小型的LIFO硬件栈（通常16$\sim$32项），专门用于预测函数返回指令的目标地址：

• 当检测到一条调用指令（如**JAL、JALR**且$\text{rd} = \text{ra}$）时，将下一条指令的地址（返回地址 = PC + 4）压入RAS；

• 当检测到一条返回指令（如**JALR且$\text{rs1} = \text{ra}$，$\text{rd} = \text{x0}$）时，从RAS弹出**栈顶作为预测的目标地址。

RAS的预测精度极高——在大多数程序中可达95%$\sim$99%。误预测主要发生在以下情况：

（1）栈溢出。当调用深度超过RAS的容量时，最早的返回地址被覆盖。在递归深度为16的程序中，16项的RAS会发生溢出；但在实际程序中，调用深度很少超过16$\sim$32层（除非使用深递归），因此RAS溢出通常不是主要问题。

（2）推测性压栈/弹栈。在推测路径上的调用/返回操作会修改RAS状态。如果推测被证明错误，RAS的状态已被破坏。恢复RAS的方法与GHR恢复类似——使用checkpoint在每次推测性弹栈前保存栈顶指针和内容。

（3）非标准的调用/返回模式。某些代码（如setjmp/longjmp、异常处理、协程切换）不遵循标准的call/return配对，导致RAS中的内容与实际返回地址不匹配。

module ras #(
  parameter DEPTH = 16,
  parameter ADDR_WIDTH = 40
)(
  input  logic                  clk, rst_n,
  input  logic                  push_valid,    // 调用指令
  input  logic [ADDR_WIDTH-1:0] push_addr,     // 返回地址
  input  logic                  pop_valid,     // 返回指令
  output logic [ADDR_WIDTH-1:0] pop_addr,      // 预测目标
  output logic                  pop_valid_out, // RAS 非空
  // Checkpoint 接口
  input  logic                  save_ckpt,
  output logic [$clog2(DEPTH)-1:0] ckpt_tos,   // 栈顶指针
  input  logic                  restore_ckpt,
  input  logic [$clog2(DEPTH)-1:0] restore_tos
);

  logic [ADDR_WIDTH-1:0] stack [DEPTH];
  logic [$clog2(DEPTH)-1:0] tos; // Top Of Stack
  logic [$clog2(DEPTH):0] count; // 有效项数

  assign pop_addr = stack[tos];
  assign pop_valid_out = (count > 0);
  assign ckpt_tos = tos;

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      tos <= '0;
      count <= '0;
    end else if (restore_ckpt) begin
      tos <= restore_tos;
      // count 需要从 checkpoint 恢复（简化省略）
    end else begin
      if (push_valid) begin
        tos <= tos + 1;
        stack[tos + 1] <= push_addr;
        if (count < DEPTH) count <= count + 1;
      end else if (pop_valid && count > 0) begin
        tos <= tos - 1;
        count <= count - 1;
      end
    end
  end
endmodule

RAS的推测性操作与恢复

在超标量处理器中，RAS面临一个与GHR类似的问题：推测路径上的调用/返回指令会修改RAS状态。当推测被证明错误时，RAS需要恢复到误预测前的状态。

考虑以下场景：分支$B$被预测为taken（实际为not-taken），在错误路径上执行了一个CALL指令，将错误的返回地址压入RAS。随后的RET指令从RAS弹出的地址是错误的。更糟糕的是，即使$B$的误预测被检测到并恢复，RAS中已被压入的错误地址如果不被清除，将在后续的正确路径上导致返回地址预测错误。

RAS恢复的常见方案：

方案一：栈顶指针Checkpoint。在每条分支指令预测时保存RAS的栈顶指针（TOS）。误预测恢复时，将TOS恢复到保存的值。这种方案简单且快速（1周期恢复），但不完全正确——如果错误路径上的CALL覆盖了栈中的某些项，仅恢复TOS不能恢复被覆盖的数据。

方案二：完整Checkpoint。在每条调用/返回指令时保存整个RAS的内容。这保证了完全正确的恢复，但存储开销极大（$16 \times 40 \times 32 = 20480$位$\approx 2.5$ KB，假设16项RAS、40位地址、32个checkpoint）。

方案三：循环覆盖检测。使用方案一的TOS checkpoint，但在RAS的每一项增加一个"推测计数器"来追踪该项是否被推测路径修改过。恢复时，不仅恢复TOS，还检查并修复被推测修改的项。这是存储效率和正确性之间的折中。

在实际处理器中，方案一因其简单性而最为常用。RAS的深度通常为16$\sim$32项，且正常程序中调用深度很少在短时间内超过RAS深度，因此TOS checkpoint在大多数情况下足够准确。

性能分析 10 — RAS预测精度与深度的关系

在SPEC CPU 2017 INT基准测试中，RAS深度对返回地址预测精度的影响：

RAS深度	返回预测精度	因RAS溢出的误预测/KRET
4	89.2%	108
8	95.8%	42
16	98.7%	13
32	99.5%	5
64	99.8%	2

其中KRET表示每千条返回指令。16项的RAS已经达到98.7%的精度，32项接近完美。大多数商用处理器采用16$\sim$32项的RAS，存储开销仅$32 \times 40 = 1280$位$= 160$字节。

间接跳转目标缓存

对于非返回的间接分支（虚函数调用、跳转表等），RAS不适用。标准BTB只记录最近一次的目标地址，如果同一条间接分支在不同执行实例中跳转到不同目标，BTB只能记住最后一次的目标。

BTB对间接分支的局限

考虑一个虚函数调用的场景：

for (auto& shape : shapes) {
    shape->draw();  // 间接调用，目标取决于 shape 的类型
}

如果shapes数组中交替包含Circle和Rectangle对象，则draw()的目标地址交替为Circle::draw和Rectangle::draw。标准BTB只记住最后一次的目标，每次目标变化时都会误预测。对于$N$种类型均匀分布的情况，BTB的命中率仅为$1/N$——当$N > 2$时，误预测率超过50%。

ITTAGE：间接目标TAGE预测器

ITTAGE（Indirect Target TAGE）是将TAGE预测器的核心思想——几何级数增长的多长度历史+标签匹配——应用于间接分支目标预测的方案，由Seznec于2011年提出。

ITTAGE的结构与TAGE类似，由一个基础表和多个标记表组成。关键区别在于：

• TAGE的每项存储一个2$\sim$3位的方向预测计数器；

• ITTAGE的每项存储一个目标地址（或目标地址的低位/哈希值），通常需要20$\sim$40位。

ITTAGE的每个标记表项包含：

字段	含义	位宽
tag	部分标签（PC+历史的哈希）	8$\sim$12
target	预测的目标地址（低位）	20$\sim$32
useful	有用位	1$\sim$2

预测流程与TAGE相同：用PC和不同长度的折叠历史索引各个表，进行标签匹配，选择匹配的最长历史表的目标地址作为预测结果。

存储开销分析

ITTAGE的存储开销远大于方向TAGE，因为每项需要存储完整（或部分）的目标地址。以一个4表ITTAGE为例：

• 4张标记表，每张256项，每项$(12 + 24 + 2) = 38$位

• 总存储 $= 4 \times 256 \times 38 = 38912$位$\approx 4.7$ KB

• 加上基础表256项，每项24位$= 6144$位

• 总计约$5.5$ KB

相比方向TAGE的$\sim$10 KB可以容纳数千项，ITTAGE在相同面积下只能容纳数百项。因此，ITTAGE通常只用于高频出现的间接分支——大部分低频间接分支仍然由标准BTB处理。

虚函数密集程序中的效果

在C++虚函数密集的程序中，ITTAGE的效果极为显著：

基准测试	间接分支占比	BTB精度	ITTAGE精度
xalancbmk	12%	52%	89%
omnetpp	8%	61%	91%
perlbench	9%	55%	85%
gcc	6%	68%	93%
平均	8.8%	59%	89.5%

ITTAGE将间接分支的预测精度从平均59%提升到89.5%，改善幅度达30个百分点。考虑到间接分支的误预测惩罚通常比条件分支更高（因为不仅方向错误，而且需要完全替换前端的取指流），ITTAGE对整体IPC的贡献非常显著。

switch-case的跳转表预测

编译器通常将大型switch语句编译为跳转表（Jump Table）。跳转表中的间接分支具有一个特殊属性：虽然目标地址不固定，但可能的目标集合是有限的（等于case的数量），且选择哪个目标取决于switch的输入值。

switch (opcode) {
    case OP_ADD:  goto handler_add;   // target 0
    case OP_SUB:  goto handler_sub;   // target 1
    case OP_MUL:  goto handler_mul;   // target 2
    case OP_DIV:  goto handler_div;   // target 3
    // ... 更多 case
}

如果opcode的分布具有时间局部性或周期性（例如，解释器中某些opcode序列频繁出现），ITTAGE可以利用全局历史来捕捉这种模式，实现高精度的目标预测。在解释器workload中（如Python解释器执行紧密循环），ITTAGE可以将opcode分派的间接分支预测精度提升到80%$\sim$90%。

案例研究 2 — 解释器中的间接分支

考虑一个简单的字节码解释器的主循环：

while (1) {
    uint8_t opcode = *pc++;
    switch (opcode) {  // 间接分支
        case LOAD:  ... break;
        case STORE: ... break;
        case ADD:   ... break;
        case SUB:   ... break;
        case JMP:   ... break;
    }
}

假设执行的字节码序列为LOAD, LOAD, ADD, STORE, LOAD, LOAD, ADD, STORE, ...，呈现周期为4的重复模式。

标准BTB：只记住最后一个目标。序列中连续相同的opcode（如两个LOAD）会被正确预测，但每次opcode变化时都会误预测。4次迭代中至少2次误预测，精度$\leq 50\%$。

ITTAGE（使用4位历史）：ITTAGE可以学习到"在LOAD, ADD, STORE之后的下一个opcode是LOAD"等模式。一旦全部4种历史模式都被学习，预测精度接近100%。

在实际的SPECjvm2008和Python基准测试中，ITTAGE将解释器分派的间接分支MPKI从15$\sim$20降低到3$\sim$5，带来显著的IPC提升。

循环预测器的深入设计

在14.3.3 节节中，我们已经介绍了循环预测器的基本原理。本节深入讨论循环预测器的硬件实现细节，包括表项的精确位宽、CAM结构的设计，以及与主预测器的协同机制。

循环预测器的表项结构

一个完整的循环预测器表项需要存储以下信息：

字段	含义	位宽	说明
valid	有效位	1	该项是否有效
tag	部分PC标签	12$\sim$16	用于确认匹配
limit	学习到的循环次数	14	最多支持$2^{14}=16384$次迭代
count	当前迭代计数	14	从0递增
conf	置信度	2	00=未学习，11=已确认
age	老化计数器	3	用于替换策略
dir	循环方向	1	0=循环结束时NT, 1=反向

每项总宽度 $= 1 + 14 + 14 + 14 + 2 + 3 + 1 = 49$位。对于一个32项的循环预测器表，总存储为$32 \times 49 = 1568$位$\approx 196$字节——这是非常小的存储开销。

CAM结构的硬件实现

循环预测器使用CAM（Content-Addressable Memory）结构进行查找——输入分支PC的标签，并行比较所有表项的tag字段，找到匹配的项。CAM结构的硬件开销主要在于并行比较逻辑：

module loop_predictor #(
  parameter ENTRIES = 32,
  parameter TAG_WIDTH = 14,
  parameter COUNT_WIDTH = 14
)(
  input  logic                   clk, rst_n,
  input  logic [TAG_WIDTH-1:0]   lookup_tag,    // PC 的部分位
  output logic                   loop_pred_valid,
  output logic                   loop_pred_taken,
  // 更新接口
  input  logic                   update_valid,
  input  logic                   update_taken,   // 实际方向
  input  logic [TAG_WIDTH-1:0]   update_tag
);

  typedef struct packed {
    logic                    valid;
    logic [TAG_WIDTH-1:0]    tag;
    logic [COUNT_WIDTH-1:0]  limit;
    logic [COUNT_WIDTH-1:0]  count;
    logic [1:0]              conf;     // 置信度
    logic [2:0]              age;
  } loop_entry_t;

  loop_entry_t entries [ENTRIES];

  // 并行 CAM 查找
  logic [ENTRIES-1:0] match;
  logic [$clog2(ENTRIES)-1:0] match_idx;
  logic match_found;

  genvar i;
  generate
    for (i = 0; i < ENTRIES; i++) begin : gen_match
      assign match[i] = entries[i].valid &&
                         (entries[i].tag == lookup_tag);
    end
  endgenerate

  // 优先编码器（通常最多一个匹配）
  always_comb begin
    match_found = 1'b0;
    match_idx = '0;
    for (int j = 0; j < ENTRIES; j++) begin
      if (match[j] && !match_found) begin
        match_found = 1'b1;
        match_idx = j[$clog2(ENTRIES)-1:0];
      end
    end
  end

  // 预测逻辑
  assign loop_pred_valid = match_found &&
                           (entries[match_idx].conf == 2'b11);
  assign loop_pred_taken =
    (entries[match_idx].count < entries[match_idx].limit);
endmodule

32项的CAM结构需要32个$14$位的并行比较器，每个比较器约需要$14 \times 4 = 56$个晶体管（使用XOR+NOR树），总计约1800个晶体管——这在现代工艺下的面积几乎可以忽略。

循环预测器的学习流程

循环预测器的学习需要观察至少两个完整的循环周期才能确认循环的迭代次数。详细的学习流程如下：

首次检测

当一条分支连续taken若干次后第一次出现not-taken时，循环预测器怀疑这可能是一个循环退出。它在CAM表中分配一项（如果该分支的PC标签尚未存在），记录当前的count值为candidate_limit，将conf设为01（部分确认）。

确认阶段

在随后的执行中，循环预测器继续计数。如果在下一次not-taken时，count恰好等于之前记录的candidate_limit，则将conf提升为11（完全确认）。如果count不等于candidate_limit，说明循环的迭代次数不固定，将conf降为00（失败）或更新candidate_limit为新值。

预测阶段

只有当conf $=$ 11时，循环预测器才输出有效预测。预测逻辑极其简单： $$\text{prediction} = \begin{cases} \text{taken} & \text{if } \texttt{count} < \texttt{limit} \\ \text{not-taken} & \text{if } \texttt{count} = \texttt{limit} \end{cases}$$

去确认

如果在conf $=$ 11的状态下，实际的循环迭代次数与limit不符（例如，循环提前退出或迭代次数增加），循环预测器将conf降为01或00，并重新进入学习阶段。

考虑一个循环for (i = 0; i < 5; i++)，其回跳分支的行为序列为$\{T, T, T, T, \mathrm{NT}, T, T, T, T, \mathrm{NT}, \ldots\}$。循环预测器的状态变化如下：

步骤	实际	count	limit	conf	预测	说明
1	T	0	—	00	(无)	首次出现，开始计数
2	T	1	—	00	(无)	计数中
3	T	2	—	00	(无)
4	T	3	—	00	(无)
5	NT	4	4	01	(无)	首次NT，记录limit=4
6	T	0	4	01	(无)	新一轮，count重置
7	T	1	4	01	(无)
8	T	2	4	01	(无)
9	T	3	4	01	(无)
10	NT	4	4	11	(无)	count=limit，确认！
11	T	0	4	11	T	开始输出预测
12	T	1	4	11	T
13	T	2	4	11	T
14	T	3	4	11	T
15	NT	4	4	11	NT	精确预测退出！

从第11步开始，循环预测器实现了100%的预测精度，包括第15步的循环退出——这是两位饱和计数器无法正确预测的关键时刻。

循环预测器与TAGE的协同

在现代处理器中，循环预测器通常作为TAGE预测器的辅助组件。两者的协同策略如下：

1. TAGE和循环预测器并行对同一条分支进行预测；

2. 如果循环预测器有有效预测（conf $=$ 11且表项匹配），则其预测覆盖TAGE的预测；

3. 如果循环预测器没有有效预测（无匹配或conf不足），则使用TAGE的预测。

循环预测器覆盖TAGE的理由是：对于固定迭代循环，循环预测器的精度严格优于TAGE。TAGE对循环退出的预测依赖于全局历史中的模式匹配，但如果循环迭代次数较大（如100次），TAGE需要极长的历史（至少100位）才能精确预测退出时机——这对TAGE的表容量和训练样本数都是巨大的压力。而循环预测器只需一个14位的计数器即可精确计数100次迭代。

需要注意的一个微妙问题是：当循环预测器覆盖TAGE的预测后，如果循环预测器预测错误（例如循环迭代次数突然变化），而TAGE预测正确，这种覆盖反而降低了精度。为了处理这种情况，某些实现引入了一个覆盖置信度（override confidence）计数器：只有当循环预测器连续多次覆盖TAGE都成功时，才允许覆盖；一旦覆盖失败，降低覆盖优先级。

TAGE预测器的核心实现

TAGE（TAgged GEometric history length）预测器是目前已知精度最高的基于表结构的分支方向预测器，由André Seznec于2006年提出。TAGE将本章讨论的多种基本技术——全局历史、标签匹配、多长度历史——融合为一个统一的框架，实现了显著超越GShare和竞争预测器的精度。由于TAGE在第 15.0 章中将作为高级预测方法的核心内容详细展开，本节仅从硬件实现的角度介绍其关键组件的结构和工作流程，作为基本方法到高级方法的过渡。

TAGE的整体结构

TAGE预测器由以下组件组成：

1. 基础预测器$T_0$：一个不使用全局历史的简单BHT，使用PC直接索引，每项2位饱和计数器。

2. $M$张标记表$T_1, T_2, \ldots, T_M$：每张表使用不同长度的全局历史进行索引。历史长度按几何级数递增：$L_1 < L_2 < \cdots < L_M$。

3. 一个全局历史寄存器GHR，长度至少为$L_M$位。

标记表的表项结构

每张标记表的每一项（entry）包含3个字段：

预测计数器（ctr，3位）

3位的饱和计数器，取值范围$[-4, +3]$（有符号表示）或$[0, 7]$（无符号表示）。MSB为预测方向（1=taken，0=not-taken），低2位表示置信度。相比基础BHT的2位计数器，3位计数器提供了更强的滞后性——需要连续4次相反方向才能翻转预测，适合在标记表中对抗别名干扰。

3位有符号计数器的预测规则： $$\text{prediction} = \begin{cases} \text{taken} & \text{if } \texttt{ctr} \geq 0 \\ \text{not-taken} & \text{if } \texttt{ctr} < 0 \end{cases}$$

置信度信息（$|\texttt{ctr}|$的大小）也被传递给统计校正器（SC）作为辅助特征。

部分标签（tag，8$\sim$12位）

由PC和折叠后的全局历史计算得到的部分标签，用于验证表项是否确实属于当前的分支+历史组合。部分标签的计算通常使用不同于索引的哈希函数，以降低索引相同但标签碰巧也相同的"双重别名"概率。

标签宽度的选择需要平衡存储开销和别名概率。对于一张1024项的标记表，使用10位标签时，"虚假匹配"（标签碰巧匹配但实际不是同一分支/历史对）的概率为$1/2^{10} \approx 0.1\%$。考虑到$M$张表中同时发生虚假匹配的概率更低，10位标签在实践中已经足够。

有用位（useful，2位）

2位的有用计数器（useful counter），用于替换策略。当一个表项的预测结果与较短历史表的预测不同且正确时，有用位递增（说明该表项提供了不可替代的预测能力）。有用位为0的表项被认为是"无用"的，可以被新分配的表项替换。

有用位还需要定期衰减（aging），以防止旧表项永远不被替换。衰减机制通常使用一个全局计数器：每当一定数量的分支被提交后（如每256K条分支），将所有表中所有表项的有用位整体减1（但不低于0）。

折叠历史哈希的实现

TAGE预测器面临一个技术挑战：标记表$T_i$使用长度为$L(i)$的全局历史作为索引和标签的输入，但$L(i)$可能非常大（如$L_{11} = 1129$位），而索引只需要10$\sim$12位，标签只需要8$\sim$12位。如何将$L(i)$位的历史压缩为10$\sim$12位的索引/标签？

答案是折叠哈希（Fold Hash）：将$L(i)$位的历史按索引宽度$k$位进行分组，然后将所有组进行XOR。具体而言，设索引宽度为$k$位，历史长度为$L$位：

$$H_{\text{fold}}[k\!-\!1:0] = h[k\!-\!1:0] \oplus h[2k\!-\!1:k] \oplus h[3k\!-\!1:2k] \oplus \cdots \oplus h[L\!-\!1:({\lfloor L/k \rfloor})\cdot k]$$

其中$h[L-1:0]$是$L$位的全局历史。例如，将130位历史折叠为10位索引： $$H_{\text{fold}} = h[9:0] \oplus h[19:10] \oplus h[29:20] \oplus \cdots \oplus h[129:120]$$ 共需要13次XOR（$\lceil 130/10 \rceil = 13$组）。

CSR的增量更新

直接计算折叠哈希需要对整个$L$位历史进行XOR，这在$L$很大时（如1000+位）是不可行的——不仅组合逻辑深度大，而且需要读取整个GHR。

解决方案是使用循环移位寄存器（Circular Shift Register，CSR）进行增量更新。CSR是一个$k$位的寄存器，每当GHR移入一个新位时，CSR通过以下操作更新：

$$\text{CSR}_{\text{new}} = (\text{CSR}_{\text{old}} \ll 1) \oplus h_{\text{new}} \oplus h_{\text{old}}$$

其中$h_{\text{new}}$是新移入GHR的位（最低位），$h_{\text{old}}$是被移出的位（GHR的第$L$位），$\ll 1$表示循环左移1位。

这个增量更新的正确性可以直观理解：每次GHR移位时，折叠哈希的每一组都"移动"了一位。新进入的位影响第0组，被移出的位影响最后一组。循环左移对应于组内位置的移动，XOR $h_{\text{new}}$和$h_{\text{old}}$分别处理新进入和被移出的位的影响。

module csr_fold #(
  parameter CSR_WIDTH = 10,   // 折叠后的宽度（索引/标签宽度）
  parameter HIST_LEN  = 130   // 对应的历史长度
)(
  input  logic                  clk, rst_n,
  input  logic                  shift_valid,
  input  logic                  h_new,    // 新移入 GHR 的位
  input  logic                  h_old,    // 从 GHR 移出的位 (GHR[HIST_LEN-1])
  output logic [CSR_WIDTH-1:0]  csr_out,
  // 恢复接口
  input  logic                  restore_valid,
  input  logic [CSR_WIDTH-1:0]  restore_value
);

  logic [CSR_WIDTH-1:0] csr;
  assign csr_out = csr;

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      csr <= '0;
    end else if (restore_valid) begin
      csr <= restore_value;
    end else if (shift_valid) begin
      // 循环左移 1 位
      logic [CSR_WIDTH-1:0] shifted;
      shifted = {csr[CSR_WIDTH-2:0], csr[CSR_WIDTH-1]};
      // XOR 新位（影响第 0 位）和旧位（影响第 HIST_LEN mod CSR_WIDTH 位）
      shifted[0] = shifted[0] ^ h_new;
      shifted[HIST_LEN % CSR_WIDTH] =
        shifted[HIST_LEN % CSR_WIDTH] ^ h_old;
      csr <= shifted;
    end
  end
endmodule

CSR增量更新的关键优势：

• 时间复杂度：每次GHR更新只需$O(1)$的操作（1次循环移位 + 2次XOR），不依赖于历史长度$L$。

• 空间复杂度：每张标记表只需要2个CSR（一个用于索引哈希，一个用于标签哈希），每个CSR仅$k$位。$M$张表共需$2M$个CSR。

• 与GHR的checkpoint配合：误预测恢复时，不仅需要恢复GHR，还需要恢复所有CSR。因此，PTAB中需要为每条飞行中的分支保存所有CSR的值。对于$M = 12$张表、每张表2个CSR、每个CSR约10$\sim$12位的配置，每条分支需要保存$24 \times 11 = 264$位的CSR状态。

TAGE的预测流程

TAGE的预测在一个周期内完成以下操作（可能需要2个周期在高频设计中）：

步骤1：使用PC的低位直接索引基础预测器$T_0$，读出2位计数器，得到基础预测$p_0$。

步骤2：对于每张标记表$T_i$（$i = 1, 2, \ldots, M$），使用$\text{PC} \oplus \text{CSR}_i^{\text{index}}$计算索引，读出表项。同时使用$\text{PC} \oplus \text{CSR}_i^{\text{tag}}$计算标签，与读出的表项中的标签字段进行比较。

步骤3：确定匹配的表。如果$T_i$的标签匹配，记$T_i$为候选提供者。

步骤4：在所有匹配的表中，选择历史最长的那张表$T_j$（$j = \max\{i : T_i \text{ 匹配}\}$），称为最终提供者（provider）。$T_j$的计数器值给出最终预测$p_j$。

步骤5：如果没有任何标记表匹配，使用基础预测$p_0$作为最终预测。

这个流程可以用以下伪代码精确描述：

prediction $\gets$ $T_0$[PC].ctr[MSB] provider_id $\gets$ 0 alt_prediction $\gets$ prediction alt_provider $\gets$ 0 (prediction, provider_id, alt_prediction, alt_provider)

注意，算法中还记录了备选预测（alternate prediction）$p_{\text{alt}}$和备选提供者——这是匹配的次长历史表的预测。备选预测在更新策略中起重要作用：当最终提供者的计数器值处于"弱"状态（如$\texttt{ctr} = 0$或$-1$）时，备选预测的正确与否决定了是否需要调整提供者的选择。

考虑一个3表TAGE预测器（$M = 3$，历史长度$L_1 = 5$，$L_2 = 15$，$L_3 = 44$），对分支PC = 0x4028进行预测：

步骤1：基础预测器$T_0$[PC低12位] = $T_0$[0x028]，读出计数器值0b10（WT），基础预测 = Taken。

步骤2：计算各标记表的索引和标签：

• $T_1$：index = PC $\oplus$ CSR$_1^{\text{idx}}$ = 0x028 $\oplus$ 0x1A3 = 0x18B，tag = PC $\oplus$ CSR$_1^{\text{tag}}$ = 0xF5

• $T_2$：index = PC $\oplus$ CSR$_2^{\text{idx}}$ = 0x028 $\oplus$ 0x07C = 0x054，tag = PC $\oplus$ CSR$_2^{\text{tag}}$ = 0x2B

• $T_3$：index = PC $\oplus$ CSR$_3^{\text{idx}}$ = 0x028 $\oplus$ 0x341 = 0x369，tag = PC $\oplus$ CSR$_3^{\text{tag}}$ = 0x87

步骤3：标签匹配检查：

• $T_1$[0x18B].tag = 0xF5 $\Rightarrow$ 匹配！ctr = +2（预测Taken）

• $T_2$[0x054].tag = 0x9D $\neq$ 0x2B $\Rightarrow$ 不匹配

• $T_3$[0x369].tag = 0x87 $\Rightarrow$ 匹配！ctr = -1（预测Not-Taken）

步骤4：$T_1$和$T_3$都匹配，$T_3$使用更长的历史（$L_3 = 44 > L_1 = 5$），因此$T_3$为最终提供者。

最终预测：Not-Taken（来自$T_3$，ctr $= -1$）。

备选预测：Taken（来自$T_1$，ctr $= +2$）。

注意：$T_3$的计数器值$\texttt{ctr} = -1$处于弱预测状态——如果这次预测错误，TAGE会考虑备选预测是否更准确，并可能调整$T_3$的表项。

TAGE的更新策略

TAGE的更新策略是其高精度的关键，比简单的饱和计数器更新复杂得多。

预测正确时

如果最终提供者$T_j$的预测正确：

• 更新$T_j$中匹配表项的预测计数器：如果实际为taken，ctr $\gets$ $\min(\texttt{ctr}+1, +3)$；如果实际为not-taken，ctr $\gets$ $\max(\texttt{ctr}-1, -4)$。

• 如果提供者的预测与备选预测不同，说明提供者提供了独特的价值，增加其有用位：useful $\gets$ $\min(\texttt{useful}+1, 3)$。

• 不分配新表项（预测已经正确，不需要额外信息）。

预测错误时

如果最终提供者$T_j$的预测错误：

• 仍然更新$T_j$的预测计数器（朝正确方向调整）。

• 在$T_j$之后的表（$T_{j+1}, T_{j+2}, \ldots, T_M$，即使用更长历史的表）中尝试分配一个新表项。分配的逻辑是：更长的历史可能包含了$T_j$未能捕捉到的模式信息，在更长历史的表中建立新条目有助于在未来正确预测。

• 分配目标的选择：优先选择有用位$= 0$的表项（因为有用位为0表示该项没有提供独特价值，可以安全替换）。如果所有候选表中都没有有用位为0的项，则不分配新表项，但将所有候选表中的有用位全部减1。这个"渐进式衰减"机制确保长期未被使用的表项最终会被替换。

// 预测错误时的分配逻辑
// provider_id: 最终提供者编号
// M: 标记表总数
task automatic tage_alloc_on_mispredict(
  input int provider_id,
  input logic actual_taken,
  input logic [TAG_WIDTH-1:0] computed_tags [M],
  input logic [IDX_WIDTH-1:0] computed_indices [M]
);
  logic allocated;
  allocated = 1'b0;

  // 在 provider 之后的表中寻找 useful=0 的项
  for (int i = provider_id + 1; i <= M; i++) begin
    if (!allocated &&
        tables[i][computed_indices[i]].useful == 2'b00) begin
      // 分配新表项
      tables[i][computed_indices[i]].tag <= computed_tags[i];
      tables[i][computed_indices[i]].ctr <=
        actual_taken ? 3'b000 : 3'b111; // 弱方向初始化
      tables[i][computed_indices[i]].useful <= 2'b00;
      allocated = 1'b1;
    end
  end

  // 如果未能分配，衰减所有候选表的 useful 位
  if (!allocated) begin
    for (int i = provider_id + 1; i <= M; i++) begin
      if (tables[i][computed_indices[i]].useful > 2'b00)
        tables[i][computed_indices[i]].useful <=
          tables[i][computed_indices[i]].useful - 1;
    end
  end
endtask

有用位的全局衰减

除了分配失败时的局部衰减外，TAGE还实施全局衰减（global aging）：每当一个全局计数器（通常计数分支退休的数量）达到阈值时（如每256K条分支），将所有标记表中所有表项的有用位右移1位（即除以2，向下取整）。这确保了：

• 长期未被"证明有用"的表项的有用位逐渐降为0，使其可被替换；

• 频繁被证明有用的表项能保持较高的有用位，不被轻易替换；

• 当程序的行为模式发生根本性变化时（如进入新的程序阶段），旧的表项会在若干个衰减周期后被新模式的表项替换。

TAGE的存储预算分析

以一个典型的5表TAGE配置（$M = 5$）为例：

基础预测器$T_0$：

• $4096$项，每项2位

• 存储 $= 4096 \times 2 = 8192$位 $= 1$ KB

标记表$T_1 \sim T_5$，历史长度$L \in \{5, 15, 44, 130, 383\}$：

• 每张表1024项

• 每项：3位计数器 $+$ 10位标签 $+$ 2位有用位 $= 15$位

• 每张表存储 $= 1024 \times 15 = 15360$位

• 5张表总计 $= 5 \times 15360 = 76800$位 $= 9.375$ KB

辅助结构：

• GHR：383位（最长历史长度）

• CSR：$5 \times 2 \times 11 = 110$位（每张表2个CSR，每个约11位）

• 全局衰减计数器：18位

• 合计：约511位 $\approx 64$字节

总存储： $$1\text{\,KB} + 9.375\text{\,KB} + 0.064\text{\,KB} \approx 10.4\text{\,KB}$$

这个存储预算与Alpha 21264的竞争预测器（3.6 KB）相比增加了约3倍，但预测精度从95%$\sim$96%提升到97%$\sim$98%（MPKI从5.5降低到3.0$\sim$3.5），性价比极高。

表数$M$	每表项数	最长历史	总存储	MPKI	精度
3	512	44	3.8 KB	5.1	94.8%
5	1024	383	10.4 KB	3.3	97.0%
8	1024	1129	16.0 KB	2.8	97.5%
12	2048	2048	46.0 KB	2.3	98.0%

不同TAGE配置的存储与精度

表表 14.10展示了TAGE预测器的可扩展性：随着存储预算的增加，MPKI持续降低，但收益递减。从3表到12表，存储增加了12倍（3.8 KB $\to$ 46 KB），但MPKI仅降低了2.8点（5.1 $\to$ 2.3）。在实际的处理器设计中，存储预算通常限制在8$\sim$32 KB，对应5$\sim$8表的TAGE配置。

统计校正器预测器

即使是精心调优的TAGE预测器，仍然存在一些系统性的预测偏差。统计校正器（Statistical Corrector，SC）的设计目标是检测并修正TAGE的这些系统性偏差，通过对TAGE的预测结果进行"二次校正"来进一步降低MPKI。

TAGE的系统性偏差

为什么TAGE会有系统性偏差？主要有以下原因：

（1）标签别名。TAGE使用部分标签（8$\sim$12位），存在虚假匹配的可能。某些分支可能持续被错误的表项"干扰"，导致系统性的预测偏差。

（2）历史长度盲区。TAGE的几何级数历史长度之间存在间隔。如果某条分支恰好需要的历史长度处于两张表之间的间隔中（如需要100位历史，但最近的表只有76位和130位），则可能无法精确匹配最优历史。

（3）线性分类的局限。TAGE本质上是一个查表式的最近邻分类器——在固定的历史上下文中，通过饱和计数器学习分支的条件概率。但某些分支的行为可能取决于多个不相邻的历史位的非线性组合，TAGE难以直接捕捉这种模式。

SC的工作原理

SC的核心思想是训练一组辅助预测器来预测"TAGE是否会在这条分支上犯错"。具体来说，SC接收多个输入特征（features），计算一个加权和，如果加权和与TAGE的预测方向相反且幅度足够大（超过某个阈值），则翻转TAGE的预测。

SC的输入特征

SC通常使用以下特征作为输入：

• TAGE的预测计数器值：计数器值越接近0（弱预测），TAGE犯错的概率越高；

• TAGE提供者的编号：来自短历史表的预测可能不如长历史表可靠；

• TAGE备选预测与最终预测是否一致：如果备选预测与最终预测不同，说明存在分歧，预测可能不可靠；

• 局部历史：每条分支自身最近几次的执行结果；

• 全局历史的不同子集：例如最近4位、最近8位、最近16位的全局历史。

加权和计算

SC使用多个小型的查找表，每个表由一个特征索引，输出一个有符号的权重值（通常5$\sim$7位）。所有权重值相加得到总和$S$：

$$S = \sum_{j=1}^{N_{\text{sc}}} w_j$$

其中$w_j$是第$j$个SC子表的输出权重。

校正决策

设TAGE的预测方向为$d_{\text{TAGE}}$（$+1$表示taken，$-1$表示not-taken），则SC的最终决策为：

$$d_{\text{final}} = \begin{cases} -d_{\text{TAGE}} & \text{if } d_{\text{TAGE}} \cdot S < -\theta \\ d_{\text{TAGE}} & \text{otherwise} \end{cases}$$

其中$\theta > 0$是一个动态调整的阈值。SC只在$|S|$足够大且方向与TAGE相反时才翻转预测。阈值$\theta$的存在确保SC只在"有足够信心"时才进行校正，避免过度校正反而降低精度。

SC的存储开销与收益

SC通常由4$\sim$8个小型查找表组成，每个表256$\sim$1024项，每项6位有符号权重。以6个表、每表512项、每项6位为例：

$$\text{SC存储} = 6 \times 512 \times 6 = 18432\text{位} \approx 2.25\text{\,KB}$$

SC的MPKI改善幅度通常为0.3$\sim$0.8个MPKI点。对于一个TAGE基线MPKI为3.3的配置，SC可以将其降低到2.5$\sim$3.0。这看似幅度不大，但在高精度区域，每0.1个MPKI点的改善都对应约0.5%$\sim$1%的IPC提升。SC的2.25 KB存储换取约10%$\sim$20%的MPKI降低，性价比非常高。

性能分析 11 — SC对TAGE的改善效果

以SPEC CPU 2017 INT基准测试为例，使用5表TAGE（10.4 KB）作为基线：

基准测试	TAGE MPKI	TAGE+SC MPKI
gcc	4.8	4.1
mcf	7.2	6.8
xalancbmk	3.1	2.5
deepsjeng	2.4	2.0
leela	3.6	3.0
exchange2	0.8	0.7
平均	3.65	3.18

SC的平均MPKI改善为0.47点（约13%），额外存储仅2.25 KB。注意SC对不同基准测试的改善幅度不同——在xalancbmk和leela等存在较多TAGE系统性偏差的程序上效果显著，而在exchange2等TAGE已经非常精确的程序上几乎没有改善空间。

设计提示

统计校正器的设计哲学是一个普遍的工程原则：先建立一个强大的基础系统，然后用一个轻量级的辅助系统修正基础系统的残余误差。这种"级联校正"的思想在许多领域都有应用——例如，通信系统中的纠错编码（基础编码+辅助编码），机器学习中的boosting（基础模型+残差模型）。在分支预测中，TAGE是强大的基础预测器，SC是轻量级的残差校正器，两者的组合效果远超任一单独使用。

分支预测结果的精确恢复

本节深入讨论在超标量处理器中，如何精确地恢复分支预测相关的所有状态——包括GHR、CSR（对于TAGE预测器）、RAS，以及预测表中可能被推测性更新的内容。

需要恢复的状态清单

当检测到分支误预测时，需要恢复到误预测点的正确状态。涉及的分支预测状态包括：

状态	位宽	恢复方式	恢复延迟
GHR	12$\sim$1000+	Checkpoint	1周期
CSR（TAGE的折叠寄存器）	$2M \times k$	Checkpoint	1周期
RAS栈顶指针	$\log_2(\text{RAS深度})$	Checkpoint	1周期
PHT/BHT计数器	—	不恢复/延迟更新	—
PTAB分配指针	$\log_2(\text{PTAB深度})$	从ROB ID推导	1周期
分支掩码空闲列表	$K$位	广播释放	1周期

Checkpoint策略的存储开销

使用Checkpoint策略意味着每条飞行中的分支都需要保存一份预测状态的快照。Checkpoint的总存储开销为：

$$\text{Checkpoint总存储} = N_{\text{branch}} \times (\text{GHR位数} + \text{CSR总位数} + \text{RAS指针位数} + \cdots)$$

以一个5表TAGE（最长历史383位）、32条飞行中分支为例：

• GHR checkpoint：$32 \times 383 = 12256$位（完整GHR快照）

• CSR checkpoint：$32 \times (5 \times 2 \times 11) = 32 \times 110 = 3520$位

• RAS指针：$32 \times 4 = 128$位

• 总计：$12256 + 3520 + 128 = 15904$位$\approx 1.9$ KB

如果使用更长的全局历史（如TAGE-SC-L的2048位），GHR checkpoint的开销将暴涨至$32 \times 2048 = 65536$位$= 8$ KB——这可能超过TAGE预测表本身的大小。

压缩GHR Checkpoint

为了解决长GHR的checkpoint开销问题，有几种压缩方案：

方案一：只checkpoint CSR，不checkpoint GHR。CSR本身就是GHR的压缩表示。但CSR恢复后无法重建完整的GHR——这意味着恢复后的GHR与真实状态不完全一致，可能导致后续预测索引的轻微偏差。实验表明，这种"近似恢复"的精度损失通常很小（$<$0.1 MPKI），因为CSR已经保留了GHR中对索引/标签计算最重要的信息。

方案二：分段checkpoint。将GHR分成若干段（如每64位一段），只在分支发生时checkpoint当前正在被修改的段。由于每次GHR移位只修改最新的1位，大部分段在连续的几十条分支之间保持不变，可以通过"增量checkpoint"减少存储开销。

方案三：Copy-on-Write。使用一个大的GHR缓冲区和多个指针。每条飞行中的分支只保存一个指向GHR缓冲区中某个位置的指针，而非整个GHR的副本。GHR缓冲区使用环形结构，新位不断追加，旧位在所有引用该位置的分支都退休后才被释放。

在实际处理器中，方案一（只checkpoint CSR）因其简单性和近似恢复的可接受性而被广泛采用。方案三在学术研究中有较多讨论，但硬件实现复杂度较高。

非推测更新PHT的恢复简化

如果PHT采用非推测更新策略（仅在分支退休时更新），则PHT本身不需要任何恢复操作——因为PHT的状态永远只反映已确认的（正确路径上的）分支信息。这大幅简化了恢复逻辑。

非推测更新PHT的代价是更新延迟：从分支预测到退休可能需要30$\sim$50个周期。如14.6.2 节节所分析的，这个延迟会降低GHR的有效历史深度。但对于TAGE预测器而言，由于其标记表使用标签匹配（而非像GShare那样依赖精确的索引），PHT的更新延迟对TAGE的影响相对较小——TAGE的标签匹配机制本身就能容忍一定程度的索引偏差。

硬件描述 5 — 误预测恢复的完整时序

以下是一个典型的超标量处理器中分支误预测恢复的完整时序（以ARM Cortex-A77级别的设计为参考）：

周期	操作	详情
$T+0$	执行单元检测误预测	分支ALU计算条件，比较预测与实际结果
$T+1$	广播清除信号	分支掩码广播到ROB/IQ/LSQ/PTAB
	读取PTAB	获取GHR checkpoint、正确目标地址
$T+2$	GHR/CSR恢复	从checkpoint恢复GHR和所有CSR
	前端PC重定向	将取指PC设为正确目标地址
	清除完成	所有错误路径指令标记为无效
$T+3$	I-Cache访问开始	从正确地址取指（可能需要2$\sim$4周期）
$T+5\sim7$	预解码/译码	新指令进入译码阶段
$T+7\sim9$	重命名/分发	新指令获得物理寄存器
$T+9\sim11$	发射/执行	新指令开始执行
总恢复延迟：$T+11 \sim T+14$（即11$\sim$14个周期的"气泡"）

在这11$\sim$14个周期中，处理器仍然可以执行误预测分支之前的正确路径指令（它们仍在ROB中等待退休），但不会有新的指令进入执行阶段。这些"气泡"周期直接转化为IPC的损失。

分支预测子系统的整体设计权衡

本章讨论了大量的分支预测方法和实现细节，本节将这些内容整合为一个连贯的设计空间分析，讨论处理器架构师在设计分支预测子系统时面临的关键权衡。

存储预算的分配

一个典型的高性能处理器为分支预测子系统分配的总存储预算约为20$\sim$60 KB。这个预算需要在以下组件之间分配：

组件	典型预算	占比
BTB（分支目标缓冲）	8$\sim$16 KB	30%$\sim$40%
方向预测器（TAGE）	8$\sim$24 KB	30%$\sim$50%
统计校正器（SC）	2$\sim$4 KB	5%$\sim$10%
循环预测器	0.2$\sim$0.5 KB	$<$2%
间接分支预测器（ITTAGE）	2$\sim$6 KB	5%$\sim$15%
RAS	0.1$\sim$0.2 KB	$<$1%
Checkpoint/PTAB	1$\sim$4 KB	5%$\sim$10%
总计	20$\sim$50 KB	100%

BTB通常占据最大的预算份额，因为BTB的每一项需要存储完整的目标地址（40$\sim$48位），而方向预测器的每一项只需几位。BTB的容量直接决定了处理器能够"记住"多少分支的位置和目标——BTB未命中意味着处理器甚至不知道取指块中有分支，方向预测和目标预测都无法进行。

精度与功耗的权衡

分支预测器在每个取指周期都会被访问，是处理器中最频繁使用的结构之一。更大、更复杂的预测器虽然精度更高，但也消耗更多的动态功耗（每次访问的能量）和静态功耗（漏电流）。

在移动处理器（如ARM Cortex-A7xx系列的大核）中，分支预测器的功耗可占前端总功耗的15%$\sim$25%。为了在精度和功耗之间取得平衡，现代处理器通常采用分层预测（Tiered Prediction）架构：

• L0预测器（Micro-BTB/nanoBTB）：极小（16$\sim$64项），用于预测最热的分支。访问延迟0$\sim$1周期，功耗极低。覆盖约50%$\sim$70%的分支（利用局部性）。

• L1预测器（主预测器/TAGE）：中等大小（数千项），覆盖绝大多数分支。访问延迟1$\sim$2周期。只有当L0未命中时才激活L1——这种"按需激活"策略可以节省30%$\sim$50%的预测器功耗。

• L2预测器（辅助/SC）：只有当L1预测的置信度较低时才激活。由于大部分分支L1的预测置信度很高（约90%的分支计数器处于强状态），L2的激活率很低，功耗几乎可以忽略。

设计权衡 5 — 分支预测精度与IPC的非线性关系

分支预测精度对IPC的影响是高度非线性的。在低精度区域（如80%$\sim$90%），精度每提高1%，IPC提升约1%$\sim$2%。但在高精度区域（如97%$\sim$99%），精度每提高0.1%，IPC提升也可以达到0.5%$\sim$1%——这是因为高精度区域的每一次误预测惩罚（15$\sim$25个周期）在IPC中所占的比例更大。

用一个简化的分析模型来说明这种非线性关系。设分支占比$f_b = 0.20$，误预测惩罚$P = 20$周期，基础$\mathrm{CPI}_0 = 1.2$（不考虑分支惩罚），则： $$\mathrm{CPI}= \mathrm{CPI}_0 + f_b \cdot (1 - A) \cdot P = 1.2 + 0.20 \cdot (1-A) \cdot 20 = 1.2 + 4(1-A)$$ $$\mathrm{IPC}= 1/\mathrm{CPI}= 1 / (1.2 + 4(1-A))$$

精度$A$	CPI	IPC
90%	1.60	0.625
95%	1.40	0.714
97%	1.32	0.758
98%	1.28	0.781
99%	1.24	0.806
99.5%	1.22	0.820

从90%到95%（提高5%），IPC提升14.2%；从95%到99%（提高4%），IPC提升12.9%；从99%到99.5%（提高0.5%），IPC仍提升1.7%。这说明即使在99%以上的精度区域，继续投入存储预算提升预测精度仍然是值得的。

面积与时序的约束

分支预测器的面积不仅包括存储SRAM的面积，还包括大量的组合逻辑（哈希计算、标签比较、优先编码器等）和控制逻辑（更新状态机、分配逻辑等）。

以一个5表TAGE预测器为例，各部分的面积贡献（以等效NAND2门计）：

• 存储SRAM（基础表+5张标记表）：约40K$\sim$60K门

• 5组索引哈希/标签哈希电路：约5K$\sim$8K门

• 5组标签比较器（每组10位$\times$1024项）：约3K$\sim$5K门

• 优先编码器和MUX选择：约1K$\sim$2K门

• 更新和分配逻辑：约3K$\sim$5K门

• CSR增量更新电路（10个CSR）：约1K门

• 总计：约55K$\sim$80K门

在7 nm工艺下，这对应约$0.01\sim0.015$ mm$^2$的面积——相对于整个处理器核心（约$5\sim10$ mm$^2$）而言非常小。但分支预测器的时序约束可能比面积约束更为严格：预测结果必须在1$\sim$2个周期内产生，任何关键路径上的延迟增加都会直接降低处理器的主频或增加预测泡沫。

本章介绍的各种分支方向预测方法——从静态预测到两位饱和计数器、局部历史、全局历史、竞争预测器，以及超标量处理器中的分支预测实现细节——构成了分支预测技术的完整基础。回顾这些方法的发展脉络，可以看到一条清晰的主线：通过不断增加预测器利用的上下文信息量来提高预测精度。

• 静态预测不使用任何运行时信息，精度30%$\sim$75%；

• BHT利用每条分支自身的历史偏向，精度80%$\sim$90%；

• 局部历史利用每条分支最近若干次的执行模式，精度90%$\sim$95%；

• 全局历史利用最近所有分支的执行序列（分支间相关性），精度91%$\sim$94%；

• 竞争预测器动态组合多种信息源，精度95%$\sim$97%；

• TAGE通过多长度历史和标签匹配，精度97%$\sim$98%；

• TAGE+SC+Loop进一步校正TAGE的残余误差，精度$>$98%。

同时，超标量处理器中分支预测的实现远比算法本身复杂——取指组中多分支的并行预测、PTAB对预测状态的保存、分支掩码/Tag List对错误路径指令的高效清除、GHR/CSR的checkpoint与恢复——这些工程细节决定了分支预测器能否在实际的高频处理器中可靠地工作。

每一步提升都伴随着存储开销和硬件复杂度的增长，但预测精度的收益通常远超成本——在现代深流水线超标量处理器中，预测精度每提高1%可以带来数个百分点的IPC提升。

这些方法各有优缺点和适用场景，表表 14.11对它们进行了总结比较。在下一章中，我们将深入讨论TAGE-SC-L组合预测器的完整实现、感知机预测器的非线性方法，以及它们在CBP竞赛和商用处理器中的应用。

本章建立了分支方向预测的完整基础——从静态预测到全局历史再到竞争预测器。这些方法在20世纪90年代到2000年代初期是处理器设计的主流。下一章（第 15.0 章）将讨论从2006年至今发展起来的高级预测方法：TAGE通过几何级数历史长度实现了多尺度的“投机精度”优化；感知机预测器用线性分类器的计算换取存储效率；TAGE-SC-L组合架构代表了当前方向预测的技术顶峰。

回调线索。本章讨论的取指组中多分支识别和并行预测机制（14.7.1 节）将在第 17.0 章的超标量预测系统集成中以FTB+FTQ的形式得到完整展开。多分支识别中依赖的预解码标记技术将在第 22.0 章中从I-Cache填充流水线的角度给出硬件实现。分支密度与取指宽度的交互分析（14.7.2 节）直接延续了第 2.0 章中对取指带宽选择的宏观讨论——在有限的芯片面积下，取指宽度的最终决定因素不是I-Cache端口数或译码器宽度，而是分支截断效应施加的有效带宽上限。