分支方向预测：高级方法

2006年，André Seznec发表了TAGE（TAgged GEometric history length）预测器——这是分支预测领域自1990年代两级预测器以来最重要的架构创新。TAGE的核心洞察简洁而深刻：不同的分支需要不同长度的历史来预测。通过维护多张以几何级数增长的历史长度索引的预测表，TAGE可以自动为每条分支找到最佳的历史深度——无需任何先验知识或静态配置。

从本书的统一视角来看，TAGE的几何级数历史长度是对“投机精度”的多尺度优化——在历史长度的对数空间中均匀采样，用最少的表覆盖最大的历史范围。感知机预测器则从另一个方向逼近同一目标：用线性分类器的加权和替代查表，以计算换取存储效率。两种方法代表了“查表” vs “计算”这一处理器设计中反复出现的根本权衡（类似于第 29.0 章中讨论的仲裁器设计中加法器链 vs 查找表的权衡）。感知机的点积计算（加法链）与第 14.0 章中讨论的基础预测器以及第 17.0 章中的系统集成构成了完整的分支预测技术栈。

读完本章，你将理解TAGE、统计校正器、循环预测器和感知机预测器的核心算法与硬件实现，掌握TAGE-SC-L组合预测器的设计原理，并能评估不同预测方案在存储预算、延迟和精度之间的权衡。

回到本书的统一视角——处理器设计的本质是在有限的晶体管预算和功耗约束下，通过投机和并行的层层叠加来逼近指令吞吐率的理论上限——本章的核心问题是：如何在有限的存储预算下最大化投机的准确率？TAGE的几何级数历史长度方案是对“投机所需信息量”的最优分配：大多数分支只需要短历史即可投机正确，少数困难分支需要几百上千位的历史。几何级数在对数空间中均匀采样，以最少的表同时覆盖短程和长程相关性——这本质上是一个信息论问题的工程最优解。感知机预测器则从另一个维度优化投机效率：将$2^n$项的查表指数存储替换为$O(n)$的线性计算，在存储效率上实现了指数级提升，代价是丧失了对非线性模式的捕获能力。两者的对比揭示了一个深刻的设计二元性：“查表 vs 计算”——这一权衡在第 29.0 章的加法器链 vs 查找表选择中、在第 14.0 章的BHT vs GShare的存储分配中反复出现。

在第 14.0 章中，我们讨论了分支方向预测的基本方法：从简单的两位饱和计数器，到基于局部历史和全局历史的两级预测器，再到竞争预测器。这些方法在1990年代到2000年代初期是处理器设计的主流，GShare预测器在Alpha 21264中，竞争预测器在Intel Pentium Pro/P6系列中得到了广泛应用。然而，随着超标量处理器的流水线越来越深、乱序窗口越来越大，分支预测精度的每一个百分点提升都对IPC产生显著影响。在典型的6-wide超标量处理器中，分支预测精度从97%提升到98%（即MPKI从6降低到4），可以带来约5%$\sim$8%的IPC提升。

本章将讨论从2000年代中期至今发展起来的高级分支方向预测方法，这些方法构成了现代高性能处理器分支预测器的核心。TAGE（TAgged GEometric history length）预测器通过使用几何级数增长的多个历史长度来捕获不同深度的分支相关性，是目前已知最精确的基于表的预测器架构。统计校正器（Statistical Corrector, SC）通过对TAGE的预测结果进行二次校正，进一步降低了难以预测的分支的错误率。循环预测器（Loop Predictor）专门针对固定迭代次数的循环分支，能够精确预测循环的退出时机。感知机（Perceptron）预测器则从机器学习的角度出发，使用线性分类器替代传统的查表机制，在存储效率上具有独特的优势。最终，TAGE-SC-L架构将上述组件有机地融合在一起，在国际分支预测竞赛（Championship Branch Prediction, CBP）中取得了迄今为止最高的预测精度。

TAGE预测器

TAGE预测器（TAgged GEometric history length predictor）由André Seznec在2006年提出，其核心思想是同时使用多个不同长度的全局历史来索引多张预测表，并通过标签匹配来选择最相关的历史长度进行预测。TAGE是对PPM（Prediction by Partial Matching）压缩算法在分支预测领域的直接应用——正如PPM通过尝试不同阶的马尔可夫模型来找到最佳的上下文匹配，TAGE通过尝试不同长度的分支历史来找到最佳的历史匹配。

Tagged Geometric History的原理

传统的全局历史预测器（如GShare）使用单一长度的全局历史寄存器。历史长度的选择面临一个根本性的矛盾：

• 短历史（如8$\sim$16位）能够快速训练，但无法捕获分支之间的长程相关性。例如，一个依赖于16层嵌套条件的分支，在8位历史下完全不可预测。

• 长历史（如128$\sim$1024位）能够捕获深层相关性，但训练所需的样本数呈指数增长——一个$n$位历史对应$2^n$种可能的历史模式，在有限的预测表容量下，长历史的表项大部分处于未训练状态，导致冷启动（cold start）问题严重。

TAGE的关键洞察是：不同的分支需要不同长度的历史。某些分支（如简单的if-else）只需要最近几个分支的历史就能精确预测；另一些分支（如嵌套循环的外层循环退出条件）可能需要数百个分支的历史。TAGE通过维护多张预测表，每张表使用不同长度的历史进行索引，从而同时覆盖短程和长程相关性。

几何级数历史长度

TAGE预测器使用$M$张标记表（tagged table）$T_1, T_2, \ldots, T_M$和一张基础预测表（base predictor）$T_0$。基础预测表$T_0$是一个不使用全局历史的简单两位饱和计数器表，使用分支PC直接索引。标记表$T_i$使用长度为$L(i)$的全局历史进行索引，其中历史长度按几何级数递增：

$$L(i) = \alpha^{i-1} \cdot L_{\min}, \quad i = 1, 2, \ldots, M$$

其中$L_{\min}$是最短的历史长度，$\alpha > 1$是公比。取整后，典型的配置为：

$$L(i) \in \{5, 9, 15, 25, 44, 76, 130, 223, 383, 657, 1129\}$$

上例中$M = 11$，$L_{\min} = 5$，$\alpha \approx 1.72$，最长历史达到1129位。几何级数的选择是至关重要的——相比算术级数（如5, 10, 15, 20, ...），几何级数能够用更少的表覆盖更大的历史范围。具体而言，$M$张表可以覆盖从$L_{\min}$到$L_{\min} \cdot \alpha^{M-1}$的历史范围。例如，$M = 12$张表可以覆盖从5到约2000位的历史长度，而算术级数需要400张表才能达到同样的覆盖范围。

为何几何级数最优

Seznec在分析中证明，在给定的总存储预算下，几何级数历史长度的配置能够最小化预测器的平均MPKI。直觉上，分支的历史深度需求近似服从对数分布——需要很长历史的分支相对较少，但这些分支对整体MPKI的贡献不可忽视。几何级数恰好与这种分布匹配：在短历史端密集分布（因为大多数分支只需要短历史），在长历史端稀疏分布（只覆盖少数需要长历史的分支），同时保证相邻两张表的历史长度之比不超过$\alpha$，避免出现历史长度的“盲区”。

更严格地说，考虑一个程序中所有条件分支的集合$\mathcal{B}$。对于分支$b \in \mathcal{B}$，定义其最优历史深度$d^*(b)$为使其MPKI最小的历史长度。如果TAGE使用的历史长度集合$\{L_1, L_2, \ldots, L_M\}$中不包含$d^*(b)$，则分支$b$只能使用最接近的可用历史长度，产生次优预测。定义历史长度失配损失为：

$$\Delta_{\text{mismatch}} = \sum_{b \in \mathcal{B}} f(b) \cdot g\!\left(\frac{\min_{i} |L_i - d^*(b)|}{d^*(b)}\right)$$

其中$f(b)$为分支$b$的执行频率，$g(\cdot)$为失配程度到MPKI贡献的映射函数。几何级数使得$|L_i - L_{i-1}|/L_i \approx 1 - 1/\alpha$对所有$i$保持常数，从而在对数空间中均匀覆盖所有可能的最优历史深度，最小化$\Delta_{\text{mismatch}}$。

Seznec的实验表明，对于CBP基准测试集，$\alpha$的最优值在1.5到2.0之间。$\alpha$过小（如1.2）会导致表数$M$过多，每张表被迫太小（因为总存储预算固定），增加了别名冲突；$\alpha$过大（如3.0）会在相邻表之间留下太大的历史长度间隙，导致某些分支的历史需求无法被精确匹配。$\alpha \approx 1.72$是64 KB预算下12张表配置的经验最优值。

TAGE与PPM的理论联系

TAGE的设计灵感直接来自数据压缩领域的PPM（Prediction by Partial Matching）算法。PPM是一种自适应的统计压缩方法，其核心思想是尝试不同阶（order）的马尔可夫模型来预测下一个符号。对于一个待压缩的符号序列，PPM首先尝试用最长的上下文（最高阶模型）来预测，如果最高阶模型没有可用的预测（即该上下文从未出现过），则回退到次高阶模型，依次类推，直到找到一个有可用预测的模型或到达零阶模型（简单的符号频率统计）。

将PPM映射到分支预测：

• PPM中的“符号”对应分支的方向（taken或not-taken）。

• PPM中的“上下文”对应分支历史（GHR中最近的分支方向序列）。

• PPM中的“不同阶模型”对应TAGE中使用不同历史长度的标记表。

• PPM中的“最长匹配优先”策略直接对应TAGE的选择规则。

PPM的理论分析表明，“最长匹配优先”策略在稳态下是渐近最优的——它能够自动适应不同的信源统计特性，无需事先知道信源的参数。TAGE继承了这一特性：它不需要预先知道每条分支的“最优历史深度”，而是在运行时通过标签匹配自动找到最佳的历史长度。这种自适应性是TAGE相对于固定历史长度预测器（如GShare）的根本优势。

分支历史深度需求的分布与几何级数覆盖（示意）

多表组织与几何级数历史长度

TAGE预测器的完整结构如图图 15.2所示。预测时，分支PC和全局历史通过哈希函数同时索引所有$M+1$张表，基础表$T_0$总是能够提供一个预测，而标记表$T_1, \ldots, T_M$只在标签匹配时才提供有效预测。最终的预测结果来自标签匹配的、历史最长的那张表——这体现了“最长匹配优先”（longest match first）的PPM原则。

TAGE预测器的整体结构

典型配置

表表 15.1列出了几种不同存储预算下的TAGE典型配置。在CBP-4竞赛的标准预算（64 KB）下，TAGE通常使用12张标记表加1张基础表，各表的大小从512项到4096项不等。

预算	表数 $M$	$L_{\min}$	$L_{\max}$	单表项数	MPKI
8 KB	5	5	130	512	$\sim$5.8
16 KB	7	5	240	1024	$\sim$4.9
32 KB	10	5	640	1024$\sim$2048	$\sim$4.2
64 KB	12	5	1129	1024$\sim$4096	$\sim$3.6
128 KB	12	5	2048	2048$\sim$8192	$\sim$3.2

不同存储预算下的TAGE典型配置

索引哈希函数

每张标记表$T_i$的索引由分支PC和长度为$L(i)$的全局历史通过哈希函数计算得到。由于全局历史$L(i)$可能长达数百甚至数千位，直接用作索引是不可行的，需要通过折叠异或（folded XOR）将历史压缩到索引宽度。设表$T_i$有$2^{k_i}$个表项，则索引计算为：

$$\text{index}_i = \text{PC}[k_i{-}1:0] \oplus \text{CSR}_i^{(1)} \oplus \text{CSR}_i^{(2)}$$

其中$\text{CSR}_i^{(1)}$和$\text{CSR}_i^{(2)}$分别是长度为$L(i)$的全局历史经过折叠异或压缩到$k_i$位和$(k_i{-}1)$位后的结果。折叠异或的具体操作是将长度为$L(i)$的历史向量按每$k_i$位一段进行分割，然后将所有段逐位异或：

$$\text{CSR}_i^{(1)} = \bigoplus_{j=0}^{\lceil L(i)/k_i \rceil - 1} \text{GHR}\bigl[(j{+}1)k_i{-}1 : jk_i\bigr]$$

使用两个不同宽度的CSR（Circular Shift Register）来计算索引和标签，可以降低不同表之间的别名冲突概率。不同宽度的CSR产生的哈希值具有不同的周期性，从而使得两个不相关的分支同时在索引和标签上发生碰撞的概率降至$2^{-(k_i + t_i)}$。

CSR的更新是增量式的：每次全局历史移入一个新的分支结果时，CSR只需一次移位和两次异或操作即可更新，无需重新计算整个哈希——这一特性对于高频率实现至关重要。

多哈希函数的抗别名设计

TAGE使用多组不同的哈希函数来分别计算索引和标签，这一设计的目的是最大化地降低构造性别名（constructive aliasing）的概率。所谓构造性别名，是指两条不相关的分支同时在同一张表的同一个表项中发生索引碰撞和标签碰撞——此时预测器无法区分这两条分支，会用一条分支训练出的结果来预测另一条分支。

设表$T_i$的索引宽度为$k_i$位，标签宽度为$t_i$位。如果索引和标签使用独立的哈希函数，则两条不相关分支发生构造性别名的概率为：

$$P_{\text{alias}} = 2^{-(k_i + t_i)}$$

对于$k_i = 11$（2048项表）和$t_i = 12$，$P_{\text{alias}} = 2^{-23} \approx 1.2 \times 10^{-7}$，即约每800万次查询才会发生一次构造性别名。

然而，如果索引和标签使用相同或高度相关的哈希函数，则两者碰撞的事件不再独立，实际别名概率会远高于上述理论值。TAGE通过使用不同宽度的CSR来确保索引哈希和标签哈希的独立性：索引使用宽度为$k_i$的CSR，标签使用宽度为$t_i$和$t_i - 1$的两个CSR，三者的周期性（由CSR宽度决定）互不相同，从而保证了哈希值之间的近似独立性。

CSR的增量更新

CSR可以看作一个$k$位的循环移位寄存器，维护历史的折叠异或值。当全局历史的最新位$h_{\text{new}}$被移入、最旧的相关位$h_{\text{old}}$被移出时，CSR的更新公式为：

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

其中$\ll$表示循环左移。整个更新操作只涉及一次移位和两次异或，硬件代价为$O(k)$个门，与历史长度$L$无关。这使得即使最长历史达到数千位，CSR的更新也能在一个时钟周期内完成。

标签匹配与有效位

TAGE的标记表之所以称为“标记”表，是因为每个表项除了预测计数器外，还包含一个标签（tag）字段。标签用于验证当前索引命中的表项确实对应于当前分支的历史模式，而不是一个别名冲突（aliasing collision）。

标签的计算

标签同样由分支PC和全局历史通过哈希函数计算得到，但使用与索引不同的哈希函数以降低同时命中但标签不匹配的概率：

$$\text{tag}_i = \text{PC}[t_i{-}1:0] \oplus \text{CSR}_i^{(\text{tag1})} \oplus (\text{CSR}_i^{(\text{tag2})} \ll 1)$$

其中$t_i$为标签宽度，$\text{CSR}_i^{(\text{tag1})}$和$\text{CSR}_i^{(\text{tag2})}$分别是全局历史折叠到$t_i$位和$(t_i{-}1)$位的结果。

部分标签匹配

TAGE使用部分标签（partial tag），而非完整的PC+历史拼接作为标签。典型的标签宽度为8$\sim$15位——远小于完整的PC+历史位数。这意味着标签匹配存在伪命中（false positive）的概率。对于$t$位宽的标签，伪命中概率为$2^{-t}$。以12位标签为例，伪命中概率约为$1/4096 \approx 0.024\%$，在实际应用中，这一概率足够低，不会显著影响预测精度。

使用部分标签而非完整标签的原因是存储效率。设表项数量为$N_{\text{entries}}$，完整标签需要$\log_2(\text{PC空间} \times 2^{L(i)})$位，对于64位地址和1000位历史，标签将超过1000位——这是不可接受的。而12位的部分标签在$N_{\text{entries}} = 1024$项的表中仅占用12 KB的存储，是一个合理的开销。

表项结构

每个标记表$T_i$的表项包含三个字段：

字段	位宽	说明
tag	8$\sim$15位	部分标签，用于验证匹配
ctr	3位	预测计数器（有符号饱和计数器，范围$[-4, 3]$）
u	1$\sim$2位	useful计数器，标记该表项是否“有用”

基础表$T_0$的表项只包含一个2位或3位的无符号饱和计数器，不需要标签和useful位。

预测计数器与弱预测的处理

标记表中使用3位有符号饱和计数器，这一位宽选择经过了仔细的权衡分析。表表 15.2总结了不同计数器宽度对预测精度的影响。

计数器宽度	范围	每项节省（位）	MPKI变化
2位	$[-2, 1]$	$+1$（可增加表项数）	$+0.08$（噪声敏感）
3位	$[-4, 3]$	基准	基准
4位	$[-8, 7]$	$-1$（减少表项数）	$+0.03$（存储浪费）
5位	$[-16, 15]$	$-2$（减少表项数）	$+0.10$（存储严重浪费）

不同计数器宽度对TAGE预测精度的影响（64 KB预算）

2位计数器对噪声过于敏感——仅一次偶然的方向翻转就会使计数器跨越决策边界，导致后续预测错误。4位及更宽的计数器虽然抗噪声能力更强，但每项增加的1$\sim$2位存储会减少可用的表项数，在总存储预算固定的约束下反而降低了整体精度。3位是在抗噪声性和存储效率之间的最佳平衡点。

弱预测与替代预测的使用

TAGE中一个精巧的优化是对弱预测（weak prediction）的特殊处理。当提供者表$T_i$的计数器值恰好为0或$-1$时（即刚好在决策边界上），预测的置信度很低。Seznec在后续的TAGE改进中引入了USE_ALT_ON_NA（Use Alternate prediction on Newly Allocated entries）机制：

当提供者表的表项是新分配的（计数器值为弱状态，即$|\text{ctr}| \leq 1$），且备选预测（altpred）来自使用更短历史的表时，TAGE有一定概率使用备选预测而非提供者的预测。这一机制的直觉是：新分配的表项可能还没有积累足够的训练数据，其预测不够可靠，此时使用已经被充分训练的较短历史表的预测可能更准确。

USE_ALT_ON_NA通过一个4位的饱和计数器来控制：当使用备选预测比使用提供者预测更准确时，计数器递增（倾向于使用备选预测）；反之递减。这个自适应机制使得TAGE能够根据工作负载的统计特性自动调整弱预测的处理策略。

预测计数器

标记表中使用3位有符号饱和计数器（范围$[-4, 3]$），预测方向由计数器值的符号决定：$\text{ctr} \geq 0$时预测taken，$\text{ctr} < 0$时预测not-taken。3位计数器相比2位计数器提供了更强的噪声抵抗能力——一次偶然的预测错误不会立即翻转预测方向，需要连续多次反方向结果才能改变预测。

useful计数器

useful计数器（简记为$u$位）是TAGE设计中的一个精巧机制，用于区分“有用的”表项和“无用的”表项。一个表项是“有用的”，当且仅当它提供了与备选预测不同的预测结果，且其预测被证明是正确的。具体而言：

• 当表$T_i$提供了最终预测（即$T_i$是匹配的最长历史表），且$T_i$的预测与备选预测（altpred，即$T_i$被移除后的预测结果）不同，且$T_i$的预测是正确的：useful计数器递增（表明$T_i$确实提供了有价值的信息）。

• 当$T_i$提供了最终预测，且$T_i$的预测与备选预测不同，但$T_i$的预测是错误的：useful计数器递减（$T_i$不仅没帮忙，还帮了倒忙）。

• 当$T_i$的预测与备选预测相同：useful计数器不变（无法判断$T_i$是否有用）。

useful计数器在表项分配策略中扮演关键角色——当需要分配新表项时，只有$u = 0$的表项（即被标记为“无用”的）才会被替换。

表项的分配策略

TAGE的表项分配策略决定了预测错误后如何在标记表中创建新的表项。这一策略对预测精度的影响与预测机制本身同样重要。

分配时机

表项分配发生在预测错误时。当提供最终预测的表$T_i$（或基础表$T_0$）发生预测错误后，TAGE尝试在比$T_i$使用更长历史的表$T_{i+1}, T_{i+2}, \ldots, T_M$中分配一个新表项——因为更长的历史可能包含了区分当前分支方向的信息，而这些信息在较短的历史中丢失了。

分配目标的选择

在表$T_{i+1}, T_{i+2}, \ldots, T_M$中，TAGE寻找一个$u = 0$的表项进行替换。搜索从$T_{i+1}$开始，逐表向更长历史的方向进行。在原始TAGE设计中，采用以下启发式：

1. 在$T_{i+1}$到$T_M$中，找到所有$u = 0$的候选表项。

2. 如果存在多个候选，以一定的概率分配到较短历史的表中。具体而言，$T_{i+k}$被选中的概率大约为$T_{i+k+1}$的两倍。这一偏向的理由是：较短历史的表项更容易被训练充分，能够更快地提供正确预测。

3. 如果没有找到$u = 0$的候选表项，则不进行分配，但将所有候选表的useful计数器递减（aging机制），为未来的分配创造机会。

aging机制

Aging（老化）是TAGE中防止useful计数器饱和并阻止新表项分配的关键机制。有两种主要的aging策略：

（1）周期性全局重置。每隔固定的周期数（如$2^{18} \approx 256\text{K}$个分支），将所有标记表的所有useful计数器重置为0。这种方式简单暴力，但可能导致在重置点附近出现短暂的精度下降，因为所有表项都变得“可替换”。

（2）渐进式aging。当分配失败（找不到$u = 0$的表项）时，将搜索范围内所有表项的useful计数器递减1。这种方式更加平滑——只有当分配压力增大时才触发aging，且只影响竞争资源的表项。Seznec在后续工作中推荐的方案是：每次分配失败时，将$T_{i+1}$到$T_M$中所有被索引到的表项的$u$值减1。

在TAGE-SC-L的最新实现中，aging策略进一步演化为双计数器aging。每张标记表维护一个全局的aging计数器$A_i$（通常为8位）。$A_i$在每次该表发生分配失败时递增，在每次该表的表项提供了正确预测时递减。当$A_i$超过阈值$A_{\text{th}}$时，该表的所有useful计数器被全局重置为0，同时$A_i$被重置。

这种双计数器机制的优势在于自适应性：对于分配压力大的表（频繁的分配失败表明该表的容量不足或别名严重），$A_i$增长快，aging更频繁，表项被更积极地替换；对于分配压力小的表（大多数预测正确，很少需要分配新表项），$A_i$保持较低值，aging不频繁，有用的表项被更好地保护。

分配概率控制

TAGE的分配策略中一个微妙但重要的参数是分配概率（allocation probability）。并非每次预测错误都应该触发新表项的分配——过于激进的分配会导致表项被频繁替换，已有表项来不及充分训练就被新分配的表项覆盖。

Seznec引入了一个分配概率控制参数$P_{\text{alloc}}$：每次预测错误时，以概率$P_{\text{alloc}}$进行新表项分配。$P_{\text{alloc}}$通常被设置为一个随表编号增加而递减的值——短历史表的分配概率较高（因为短历史表项训练快，即使被替换也能快速恢复），长历史表的分配概率较低（因为长历史表项训练慢，应尽量保护已有的训练成果）。

一种简单的实现方式是使用一个计数器来控制分配频率：每次预测错误时计数器递减，只有当计数器归零时才实际执行分配。计数器的初始值可以根据目标分配概率来设置（例如，$P_{\text{alloc}} = 1/2$对应初始值2）。

新分配表项的初始化

新分配的表项按照以下方式初始化：

• tag：设置为当前分支PC和全局历史的哈希值。

• ctr：设置为弱正确方向——即如果实际方向是taken，则ctr初始化为0（弱taken）；如果实际方向是not-taken，则ctr初始化为$-1$（弱not-taken）。弱初始化使得新表项在后续预测中能够快速被验证或修正。

• u：初始化为0。

弱初始化的选择有深层的理由。如果新表项的计数器被初始化为强方向（如ctr = 3，强taken），则一次偶然的错误分配（由于别名或噪声）会导致该表项在后续的多次预测中持续给出错误预测——需要连续4次反方向结果才能纠正。弱初始化确保了一次反方向结果就足以翻转预测，使得错误分配的表项能被快速修正。

在另一方面，新分配表项的弱初始化也意味着它容易被噪声翻转。USE_ALT_ON_NA机制（见15.1.3 节中弱预测的讨论）正是为了缓解这一问题——当新分配的表项给出弱预测时，TAGE倾向于使用训练更充分的备选预测，避免被未经充分验证的新表项误导。

硬件描述 1 — TAGE预测器的预测与更新流程

TAGE预测器的完整预测和更新流程可以总结为以下伪代码。

算法 15.1：TAGE预测流程

输入: 分支PC, 全局历史 GHR
输出: 预测方向 pred

provider ← T_0                                       # 默认提供者为基础表
altpred  ← (T_0.lookup(PC).ctr ≥ 0)
pred     ← altpred

for i ← 1 to M do
    idx ← hash_index(i, PC, GHR)
    tag ← hash_tag(i, PC, GHR)
    if T_i[idx].tag = tag then
        altpred  ← pred                              # 保存上一匹配表的预测作为备选
        pred     ← (T_i[idx].ctr ≥ 0)
        provider ← T_i
    end if
end for

return pred

算法 15.2：TAGE更新流程

输入: 分支PC, GHR, 实际方向 actual,
      预测方向 pred, provider, altpred

# --- 更新提供者的计数器 ---
if actual = taken then
    provider.ctr ← min(provider.ctr + 1,  3)
else
    provider.ctr ← max(provider.ctr - 1, -4)
end if

# --- 更新 useful 位（仅当 pred 与 altpred 不一致时） ---
if pred ≠ altpred then
    if pred = actual then
        provider.u ← min(provider.u + 1, u_max)
    else
        provider.u ← max(provider.u - 1, 0)
    end if
end if

# --- 预测错误时分配新表项 ---
if pred ≠ actual then
    allocated ← false
    for j ← provider_idx + 1 to M do
        if T_j[hash_index(j, PC, GHR)].u = 0 then
            在 T_j 中分配新表项（tag 置为 hash_tag(j,PC,GHR)，
                                ctr 初始化为弱状态，u ← 0）
            allocated ← true
            break
        end if
    end for
    if not allocated then
        对所有候选表项执行 aging: u ← u - 1           # 全局降权以便后续分配
    end if
end if

TAGE的存储预算分析

TAGE预测器的存储预算分析对于硬件实现至关重要。每个标记表项消耗的存储为：

$$b_{\text{entry}} = t + w_{\text{ctr}} + w_u$$

其中$t$为标签宽度，$w_{\text{ctr}}$为计数器宽度（通常3位），$w_u$为useful位宽度（通常1$\sim$2位）。典型的表项大小为$12 + 3 + 1 = 16$位或$10 + 3 + 2 = 15$位。基础表每项仅需2$\sim$3位（一个饱和计数器）。

在给定总存储预算$B_{\text{total}}$的情况下，TAGE的配置优化问题是：

$$\min \text{MPKI} \quad \text{s.t.} \quad N_0 \cdot w_0 + \sum_{i=1}^{M} N_i \cdot b_{\text{entry},i} \leq B_{\text{total}}$$

其中$N_0$为基础表项数，$N_i$为标记表$T_i$的项数。Seznec通过大量的模拟实验得出了以下经验性结论：

• 增加表数$M$（即增加历史长度的覆盖范围）通常比增加单表大小$N_i$更有效。从8张表增加到12张表的MPKI改善幅度，通常大于将每张表的大小翻倍。

• 各表的大小$N_i$不需要相同。使用中等历史长度的表（如$L = 20\sim100$）通常从更大的表中受益最多，因为在这个范围内竞争的分支最多。

• 标签宽度$t$对精度有显著影响。将标签从8位增加到12位可以降低约5%的MPKI，但进一步增加到16位的改善就很小了。

• 在总预算超过64 KB后，TAGE的精度提升进入了收益递减区域。对于SPEC CPU 2006基准测试集，64 KB TAGE的MPKI约为3.6，128 KB仅改善到3.2——翻倍的存储仅带来了约11%的MPKI改善。

性能分析 1 — TAGE存储效率：64 KB预算下的配置优化

考虑64 KB（即$64 \times 1024 \times 8 = 524288$位）的总存储预算。一个典型的优化配置为：

组件	项数	标签宽度	计数器	useful	位数
$T_0$（基础表）	8192	—	2位	—	16384
$T_1$（$L=5$）	2048	9位	3位	1位	26624
$T_2$（$L=9$）	2048	9位	3位	1位	26624
$T_3$（$L=15$）	2048	10位	3位	1位	28672
$T_4$（$L=25$）	2048	10位	3位	1位	28672
$T_5$（$L=44$）	2048	11位	3位	1位	30720
$T_6$（$L=76$）	2048	11位	3位	1位	30720
$T_7$（$L=130$）	2048	12位	3位	1位	32768
$T_8$（$L=223$）	2048	12位	3位	1位	32768
$T_9$（$L=383$）	1024	13位	3位	1位	18432
$T_{10}$（$L=657$）	1024	14位	3位	1位	19456
$T_{11}$（$L=1129$）	1024	15位	3位	1位	20480
GHR（全局历史寄存器）					1129
CSR（循环移位寄存器）$\times 2 \times 12$					$\sim$600
总计					$\approx$314449

上述配置仅使用了约38 KB的存储，还有约26 KB的余量可以用于统计校正器（SC）和循环预测器（Loop Predictor）等附加组件。注意，历史较长的表使用更宽的标签——这是因为长历史的哈希空间更大，需要更宽的标签来降低伪命中率。

设计提示

TAGE预测器的实现要点：（1）CSR的增量更新是实现高频率TAGE的关键——如果每次预测都需要从GHR重新计算折叠异或，关键路径将长达数十个门延迟，无法在一个时钟周期内完成。（2）所有标记表可以并行查询，因此TAGE的查询延迟与表的数量无关（取决于单表的查询延迟），但面积和功耗与表数成正比。（3）在超标量处理器中，如果每周期需要预测多条分支（如每周期取指4$\sim$8条指令，可能包含多条分支），则需要对GHR进行推测性更新——在分支实际解析之前，就将预测的方向移入GHR，以便后续分支可以使用更新的历史进行预测。推测更新在预测正确时不需要修正，但在预测错误时需要将GHR恢复到正确的状态，这需要维护一个GHR的检查点或恢复栈。

TAGE的关键路径与流水线化

TAGE预测器在高频率处理器中的实现面临严格的时序约束。理解其关键路径对于正确的流水线划分至关重要。

单周期TAGE的时序分析

一次完整的TAGE预测操作包含以下串行步骤：

1. 索引/标签计算：PC与CSR进行异或运算。对于$k$位宽的索引，异或操作需要1层XOR门延迟（约20 ps$\sim$30 ps@ 5nm）。由于每张表的索引和标签计算是独立的，所有表的哈希可以并行进行。

2. SRAM读取：使用索引访问SRAM，读取表项数据。SRAM的读取延迟取决于表的大小：512项的表约80 ps，2048项的表约120 ps，4096项的表约150 ps（含地址解码和灵敏放大器延迟）。

3. 标签比较：将SRAM读出的标签与计算的标签进行逐位比较。12位标签的比较需要1层XOR门加1个12输入AND门，延迟约30 ps$\sim$40 ps。

4. 最长匹配选择：在所有标签匹配的表中选择使用最长历史的那一个。这需要一个$M$输入的优先级编码器。对于$M = 12$，使用树状结构的编码器延迟约40 ps$\sim$60 ps。

5. 预测输出：根据选中表的计数器符号位确定预测方向。这只需要读取一个比特，延迟可以忽略。

将上述延迟相加，一次TAGE预测的总延迟约为：

$$t_{\text{TAGE}} \approx t_{\text{hash}} + t_{\text{SRAM}} + t_{\text{tag\_cmp}} + t_{\text{priority}} \approx 25 + 120 + 35 + 50 = 230\,\text{ps}$$

在5 GHz（周期200 ps）的处理器中，这一延迟超过了单个时钟周期，因此TAGE必须被流水线化为至少2级。

两级TAGE流水线

在典型的两级实现中，TAGE的查询被划分为：

• 第1级（BP0）：索引/标签哈希计算 + SRAM读取启动。这一级的延迟主要由SRAM的地址解码决定，约100 ps$\sim$130 ps。

• 第2级（BP1）：SRAM数据输出 + 标签比较 + 最长匹配选择 + 预测方向输出。这一级的延迟约100 ps$\sim$120 ps。

两级流水线意味着从发起预测到获得结果需要2个周期。对于连续的not-taken分支块，下一个预测的PC可以在不等待当前预测结果的情况下计算（PC + 取指块大小），因此不产生气泡。但对于taken分支，下一个预测的PC取决于当前预测的目标地址——这需要BTB和TAGE的结果同时可用——产生1个周期的预测气泡。

TAGE的多银行组织

为了支持高吞吐率的预测（例如每周期预测多个取指块，或在同一周期内完成预测和更新），TAGE的SRAM可以采用多银行（multi-bank）组织：将每张表的SRAM分为多个银行（bank），不同的操作访问不同的银行，从而避免端口冲突。

一种常见的组织是将预测和更新分配到不同的半周期：在时钟的上升沿触发预测读取，在下降沿触发更新写入。这种半周期分时（half-cycle time-division）策略在单端口SRAM上实现了逻辑上的双端口行为，代价是需要在半个时钟周期内完成SRAM访问——这要求SRAM的物理尺寸足够小（通常每张表不超过2048项）。

另一种方案是为每张表使用物理上的双端口SRAM（一个读端口用于预测，一个写端口用于更新）。双端口SRAM的面积约为单端口SRAM的1.5$\sim$2倍，对于TAGE的12张表来说，总面积增加约50%$\sim$100%。在面积受限的设计中，通常优先选择半周期分时方案。

硬件描述 2 — TAGE预测器的推测更新与恢复

在超标量乱序处理器中，TAGE的全局历史寄存器（GHR）和折叠历史寄存器（CSR）需要支持推测更新和恢复。以下是完整的推测管理流程：

推测更新：当一条分支指令在取指阶段被预测时（尚未实际执行），其预测方向被立即移入GHR，同时所有CSR通过增量更新公式（式 (15.7)）进行更新。这使得紧随其后的分支可以使用包含该预测方向的最新历史进行查询。

检查点保存：在每条分支指令被预测时，保存当前GHR的一个检查点。对于一个128位的GHR，每个检查点需要128位存储。如果飞行中最多有64条分支，检查点总存储为$64 \times 128 = 8192$位$\approx$1 KB。此外，每张TAGE表的两个CSR也需要保存检查点。对于12张表、每个CSR约12位，CSR检查点需要$64 \times 12 \times 2 \times 12 = 18432$位$\approx$2.25 KB。总的检查点存储约3.25 KB。

恢复：当一条分支在执行阶段被解析为预测错误时：

1. 从该分支的检查点恢复GHR。

2. 将正确的分支方向（而非预测方向）移入恢复后的GHR。

3. 从恢复后的GHR重新计算所有CSR——这可以使用增量更新逐步完成，但需要多个周期（每个CSR需要一个周期的更新操作），或者使用检查点直接恢复CSR。

4. 丢弃该分支之后所有指令的预测结果，从正确地址重新开始预测。

一种实用的优化是只保存CSR的检查点而不保存完整GHR的检查点，因为TAGE的索引和标签计算只依赖CSR而非完整GHR。恢复时直接用CSR检查点恢复每张表的索引/标签哈希状态，无需重建GHR。这将检查点存储从3.25 KB降低到约2.25 KB。但这种优化要求GHR的恢复通过其他机制（如ROB中存储的分支方向记录）来完成，增加了恢复逻辑的复杂性。

统计校正器

TAGE预测器虽然精度很高，但在某些特定的分支模式下仍然会出现系统性的预测错误。统计校正器（Statistical Corrector, SC）的目标就是识别这些模式并对TAGE的预测进行二次校正。

SC的基本原理

SC的核心观察是：TAGE的错误预测并非完全随机的，而是存在统计规律性。例如，某些分支的实际方向与TAGE预测方向之间存在系统性偏差——TAGE可能对这些分支持续地预测taken，但实际上它们有60%的概率是not-taken。SC通过学习“TAGE在什么条件下会犯错”来校正这些偏差。

SC的工作原理

SC本质上是一个对TAGE预测结果的预测器——它预测的不是分支方向本身，而是“TAGE的预测是否正确”。SC使用多个小型的计数器表来捕获TAGE预测错误的相关信息，每个表使用不同的特征进行索引：

• 分支PC的哈希值

• 全局历史的短前缀（如最近4$\sim$16位）

• 分支PC与全局历史的组合

• TAGE的内部置信度信息（如提供者的计数器值接近阈值）

SC中的每个表存储有符号计数器，其输出被加权求和后与一个阈值进行比较。当加权和超过阈值时，SC认为TAGE的预测可能是错误的，并翻转TAGE的预测方向。

数学表达

设SC包含$K$个计数器表$S_1, S_2, \ldots, S_K$，每个表使用不同的特征$f_k$进行索引。对于给定的分支，SC的加权和为：

$$\sigma = \sum_{k=1}^{K} S_k\bigl[\text{hash}_k(\text{PC}, \text{GHR})\bigr]$$

其中$S_k[\cdot]$为表$S_k$中对应项的有符号计数器值。SC的校正决策为：

$$\text{pred}_{\text{final}} = \begin{cases} \text{pred}_{\text{TAGE}} & \text{if } |\sigma| < \theta \\ \overline{\text{pred}_{\text{TAGE}}} & \text{if } |\sigma| \geq \theta \text{ 且 } \text{sign}(\sigma) \neq \text{pred}_{\text{TAGE}} \end{cases}$$

其中$\theta$为校正阈值。当$|\sigma|$较小时，SC对自己的判断没有足够的置信度，不会修改TAGE的预测；只有当$|\sigma|$足够大时，SC才会翻转TAGE的预测。阈值$\theta$的选择需要平衡两个因素：$\theta$过小会导致SC过于激进，频繁地翻转TAGE的正确预测；$\theta$过大会使SC过于保守，错过真正需要校正的情况。

SC的训练

SC的计数器更新规则如下：

• 当SC的校正是正确的（即TAGE预测错误且SC翻转后正确），或者SC未校正且TAGE预测正确：所有被索引的计数器向实际方向更新（taken方向递增，not-taken方向递减）。

• 当SC的校正是错误的（即TAGE预测正确但SC翻转后变错误）：所有被索引的计数器向实际方向更新，且阈值$\theta$适当增大（使SC变得更保守）。

• 阈值$\theta$通过一个自适应机制进行动态调整：当SC的校正导致预测变好时$\theta$减小，当SC的校正导致预测变差时$\theta$增大。

SC的更新具有一个重要的特性：所有被索引的表项都会被更新，而不仅仅是“命中”的表项。这与TAGE的更新策略不同——TAGE只更新提供最终预测的那张表的表项。SC的“全部更新”策略来源于感知机的训练规则：在感知机学习中，所有参与加权和计算的权重都需要被更新，以确保梯度信息被正确传播到每个特征。

SC的训练还需要处理计数器饱和问题。6位有符号计数器的范围为$[-32, 31]$。当一个计数器已经饱和在最大值31时，继续向同一方向更新不会改变其值。饱和的计数器在加权和中贡献一个固定的值，降低了SC的适应性。为此，SC通常配合一个周期性衰减（periodic decay）机制：每隔一定数量的分支执行（如$2^{16}$次），将所有SC计数器的绝对值减1。这使得长期不被更新的饱和计数器逐渐衰减到0，释放出动态范围用于新的学习。

SC的多层扩展

在Seznec的后续工作中，SC被扩展为多层SC（SC with multiple layers）。第一层SC校正TAGE的预测，第二层SC校正第一层SC的校正结果。多层SC可以捕获更复杂的TAGE错误模式，但每增加一层都会在关键路径上增加延迟，且边际收益递减。

在实践中，两层SC（即一个主SC加一个二级SC）在64 KB预算下可以将MPKI额外降低约3%$\sim$5%。三层以上的SC在现有的预算和工作负载下没有显著收益。两层SC的总存储约为8$\sim$12 KB（主SC约6 KB + 二级SC约3 KB + 阈值表约1 KB），占总预算的15%$\sim$20%。

统计校正器（SC）的工作流程

SC的存储结构

SC通常包含4$\sim$6个小型计数器表，每个表使用不同的索引函数。各表的大小通常为256$\sim$2048项，每项为6位有符号饱和计数器（范围$[-32, 31]$）。6位宽度的选择是基于以下分析：SC需要足够的动态范围来积累统计信息，但计数器太宽会浪费存储。6位计数器可以在$2^5 = 32$次连续同向更新后饱和，这在大多数工作负载下足以区分“TAGE系统性地预测错误”和“偶尔的随机错误”。

一个典型的SC配置如下：

表	索引特征	项数	计数器宽度
$S_1$	PC[10:0]	2048	6位
$S_2$	PC $\oplus$ GHR[3:0]	1024	6位
$S_3$	PC $\oplus$ GHR[7:0]	1024	6位
$S_4$	PC $\oplus$ GHR[15:0]	512	6位
$S_5$	PC $\oplus$ GHR[31:0]	512	6位
$S_6$	TAGE provider $\oplus$ PC	512	6位
SC总存储			33792位 $\approx$ 4.1 KB

SC的总存储开销仅为4$\sim$8 KB，远小于TAGE的存储。但SC对整体MPKI的改善比例（10%$\sim$15%）相对于其存储占比（约10%$\sim$15%的总预算）是合理的。

SC的动态阈值调整

SC的校正阈值$\theta$不是一个固定值，而是通过自适应机制进行动态调整。动态阈值的核心思想是：如果SC的校正经常是正确的（即TAGE经常在某些模式下犯错），则$\theta$应该降低，使SC更积极地进行校正；如果SC的校正经常是错误的（即SC“帮倒忙”的概率较高），则$\theta$应该增大，使SC更保守。

动态阈值通过以下机制实现：

1. 维护一个阈值调整计数器$\tau$（通常为7位有符号饱和计数器）。

2. 当SC的校正导致预测变好（TAGE预测错误但SC校正后正确）时，$\tau$递减（趋向于降低阈值）。

3. 当SC的校正导致预测变差（TAGE预测正确但SC校正后错误）时，$\tau$递增（趋向于提高阈值）。

4. 当$\tau$达到上界或下界时，$\theta$相应地增加或减少1，并将$\tau$重置为中间值。

动态阈值调整的粒度可以是全局的（所有分支共享一个$\theta$）或局部的（不同的分支PC对应不同的$\theta$）。Seznec在TAGE-SC-L的实现中使用了一个小型的阈值表（每项包含一个$\theta$值和一个$\tau$计数器），按分支PC的低位索引，使得不同的代码区域可以有不同的校正激进度。

SC与TAGE的时序串联问题

SC的一个关键实现挑战是它在关键路径上串联在TAGE之后。SC需要两个来自TAGE的信息才能做出校正决策：（1）TAGE的预测方向（决定$\sigma$的符号是否与TAGE一致）；（2）TAGE提供者的计数器绝对值（用于置信度判断，决定是否允许校正）。这意味着SC的决策必须等待TAGE的完整查询结果。

如果TAGE的查询需要1个流水线阶段，SC的查询和决策需要另外0.5$\sim$1个阶段，则整个TAGE-SC的延迟为1.5$\sim$2个阶段。在实际的2级流水线实现中，一种策略是让SC的表查询与TAGE的表查询并行进行（都在BP0阶段），但SC的最终决策在BP1阶段完成——BP1阶段同时进行TAGE的标签匹配/选择和SC的加权和计算/阈值比较。

这种并行策略要求SC的索引计算不依赖TAGE的结果（只依赖PC和GHR），但SC的最终决策仍然需要TAGE的输出。关键路径变为：BP0结束时SRAM数据可用$\to$BP1中TAGE标签比较和SC加权和并行进行$\to$BP1末尾SC获取TAGE置信度$\to$SC做出校正决策。这条路径中的串行部分（TAGE置信度$\to$SC决策）只涉及一个简单的比较和一个2:1多路选择器，延迟约30 ps$\sim$50 ps，通常可以在BP1阶段的时间预算内完成。

TAGE-SC组合

TAGE和SC的组合需要仔细的工程设计，以确保SC的校正真正提升而非降低预测精度。

置信度估计

SC校正的一个关键前提是：只有当TAGE的预测置信度较低时，SC的校正才更可能是正确的。TAGE预测的置信度可以从提供者的计数器值推断——当计数器值接近0（即接近taken/not-taken的决策边界）时，TAGE的置信度较低，此时SC校正的价值最高。

在TAGE-SC组合中，SC的校正受到以下条件的调节：

$$\text{校正生效} \iff |\sigma| \geq \theta \quad \text{且} \quad |\text{ctr}_{\text{provider}}| \leq c_{\text{weak}}$$

其中$c_{\text{weak}}$是一个阈值（通常为1或2），当TAGE提供者的计数器绝对值较大时（强置信度），SC的校正被抑制。这一保护机制有效防止了SC错误地翻转TAGE的高置信度预测。

存储预算分配

在给定的总存储预算下，TAGE和SC之间的预算分配是一个重要的设计决策。经验表明，将总预算的约70%$\sim$80%分配给TAGE、20%$\sim$30%分配给SC能够达到最佳的整体MPKI。例如，在64 KB总预算下，约45$\sim$50 KB用于TAGE，15$\sim$20 KB用于SC。

预算分配的优化可以通过边际分析来指导：计算将最后1 KB的存储分配给TAGE或SC中哪一个能带来更大的MPKI改善。随着TAGE存储的增加，TAGE的MPKI改善速率逐渐递减（由于收益递减效应）；而SC的MPKI改善在一定范围内近似线性（更多的表项意味着更低的别名，更准确的校正）。当两者的边际MPKI改善率相等时，达到最优分配点。

以下是不同TAGE/SC比例在64 KB总预算下的MPKI数据：

TAGE:SC比例	TAGE存储	SC存储	MPKI	备注
100:0	64 KB	0 KB	3.58	无SC
90:10	57 KB	7 KB	3.21	SC不足
80:20	51 KB	13 KB	3.05	接近最优
75:25	48 KB	16 KB	2.98	最优附近
70:30	45 KB	19 KB	3.01	TAGE不足
60:40	38 KB	26 KB	3.12	TAGE严重不足

可以看到，TAGE:SC = 75:25附近是最优分配比例。偏离这个比例（无论向哪个方向），MPKI都会增加。

TAGE-SC的MPKI改善

SC对TAGE的MPKI改善因工作负载而异，平均约10%$\sim$15%。表表 15.3给出了在CBP-5基准测试集上的典型数据。

工作负载类型	TAGE MPKI	TAGE-SC MPKI	改善
整数计算	4.12	3.51	14.8%
浮点计算	1.85	1.68	9.2%
服务器工作负载	5.73	5.01	12.6%
多媒体	2.41	2.19	9.1%
平均	3.53	3.10	12.2%

SC对TAGE预测精度的改善（64 KB预算）

设计提示

SC的实现需要注意时序问题。SC的校正决策依赖于TAGE的预测结果（需要知道提供者和计数器值），因此SC的关键路径串联在TAGE之后。在高频率实现中，可以将TAGE查询和SC查询安排在两个流水线阶段中：第一阶段完成TAGE查询并输出预测结果供取指使用，第二阶段完成SC校正。如果SC决定翻转，则通过一个1周期延迟的校正信号来取消已取出的指令。这种“先预测后校正”的设计在TAGE预测正确率很高（约96%$\sim$98%）的前提下是合理的——SC的校正只影响少量预测，且校正的延迟通过取消已取出的1$\sim$2条错误指令来弥补。

循环预测器

在程序中，循环是最常见的控制流结构之一。许多循环的迭代次数是固定的或在运行时可预测的。循环预测器（Loop Predictor）专门针对这类分支进行优化。

循环计数检测

循环分支的行为特征

一个迭代$N$次的for循环在其条件分支上产生的行为模式是：连续$N-1$次taken（继续循环），然后一次not-taken（退出循环），如此周期性地重复。对于TAGE等基于历史的预测器，预测循环退出的那一次not-taken是困难的——因为在连续$N-1$次taken之后，历史中充满了taken的记录，预测器倾向于预测taken，从而在循环退出时发生一次错误预测。如果$N$很大（如$N = 100$），TAGE需要至少$N$位的历史才能区分“第$N-1$次迭代”和“第$N$次迭代”，这对历史长度和表容量的需求是巨大的。

循环预测器通过直接计数循环的迭代次数来解决这一问题。其基本策略是：

1. 检测一个分支是否表现出固定迭代次数的循环行为。

2. 如果是，记录该分支的迭代次数$N$。

3. 在后续的执行中，通过计数来精确预测循环的退出时机。

循环检测机制

循环预测器为每个被监控的循环分支维护一个表项，包含以下字段：

字段	位宽	说明
tag	12$\sim$16位	分支PC的部分标签
count	10$\sim$14位	当前迭代计数
limit	10$\sim$14位	已确认的循环迭代次数
spec_count	10$\sim$14位	推测性迭代计数（用于推测更新）
conf	2$\sim$3位	置信度计数器（循环次数是否稳定）
age	3位	老化计数器
dir	1位	循环方向（大多数迭代是taken还是not-taken）

循环检测的状态机如图图 15.4所示。

循环预测器的状态机

学习阶段

当一个分支首次被识别为可能的循环分支时（例如，一个向后跳转的条件分支），循环预测器进入学习阶段。在学习阶段，预测器不提供预测，而是静默地观察分支的行为，记录连续taken的次数。当分支第一次变为not-taken时，当前的taken计数被记录为候选迭代次数$N_{\text{cand}}$。

确认阶段

在下一个循环周期中，如果分支再次在恰好$N_{\text{cand}}$次taken后变为not-taken，候选迭代次数被确认——即$\text{limit} \gets N_{\text{cand}}$，置信度计数器递增。如果迭代次数不匹配（如第二次循环只执行了$N_{\text{cand}} - 3$次就退出），则候选被拒绝，表项被重置。通常需要连续2$\sim$3次匹配才会将置信度提升到预测阈值。

预测阶段

一旦置信度达到预测阈值，循环预测器在后续的执行中通过简单的计数来预测：当spec_count $<$ limit时预测taken（继续循环），当spec_count $=$ limit时预测not-taken（退出循环）。每次分支被解析后，如果实际方向为taken则count递增，如果为not-taken则count被重置为0（新的循环开始）。

循环迭代次数变化的处理

在某些程序中，循环的迭代次数并非严格固定，而是在一定范围内变化。例如，处理变长数据包的循环，其迭代次数取决于数据包长度。对于这类“不稳定”的循环，循环预测器的置信度会反复下降，最终放弃预测，让TAGE来处理。循环预测器只对稳定的固定迭代次数循环有效，这正是其设计初衷。

性能分析 2 — 循环预测器的价值量化

在典型的整数基准测试（如SPEC CPU 2017 intrate）中，固定迭代次数的循环分支约占所有条件分支的5%$\sim$10%。这些分支在TAGE预测器下的平均MPKI贡献为0.3$\sim$0.5——即每1000条指令中有0.3$\sim$0.5次错误预测来自循环退出预测错误。循环预测器可以将这部分MPKI几乎完全消除（降低到$< 0.05$），但对整体MPKI的改善相对有限（约5%$\sim$8%的TAGE MPKI被消除）。

然而，循环预测错误的代价往往高于普通分支预测错误，因为循环退出通常发生在长时间连续执行的循环之后——此时流水线可能已经基于循环继续的假设推测执行了大量指令，错误预测导致的flush开销更大。因此，循环预测器的实际IPC改善可能高于其MPKI改善的比例。

循环预测器的推测管理

在超标量处理器中，循环分支的多个迭代可能在未解析状态下连续被预测。循环预测器的推测管理是保证其高精度的关键。

推测计数器的管理

循环预测器的spec_count字段在每次预测时被推测性更新：预测taken时递增，预测not-taken时重置为0。但如果之前的分支预测错误导致流水线被刷新，spec_count中可能包含了错误路径上的推测更新，需要恢复到正确状态。

恢复策略有两种：

检查点恢复。在每条条件分支指令被预测时，保存当前的spec_count值作为检查点。当该分支被解析为预测错误时，将spec_count恢复到检查点值。对于一个64项的循环预测器和64条飞行中的分支，检查点存储为$64 \times 14 = 896$位$\approx$112字节——开销可以接受。

架构计数器恢复。维护一个非推测性的count字段（只在分支退休时更新），当发生推测恢复时，将spec_count重置为count的值。这种方案更简单，但恢复后的spec_count可能不精确——count反映的是已退休分支的状态，而spec_count应该反映已预测但未退休的分支的状态。两者之间的差距等于飞行中的分支数量中属于当前循环的那些迭代数。在实践中，由于循环预测器本身的精度很高（>97%），这种不精确性对整体MPKI的影响很小。

推测退出预测

循环预测器最关键的预测时刻是循环退出——预测not-taken。这个预测如果错误（即循环实际继续而非退出），会导致流水线flush。推测管理需要确保退出预测的可靠性。

一种保护机制是：当spec_count等于limit时，在预测not-taken之前额外检查当前的TAGE预测。如果TAGE也预测not-taken，则循环预测器的退出预测得到了双重确认，置信度更高；如果TAGE预测taken（与循环预测器矛盾），则可能意味着循环的迭代次数发生了变化——此时应该使用TAGE的预测而非循环预测器的。这种“交叉验证”机制可以将循环退出预测的错误率降低约30%$\sim$50%。

与TAGE的配合

循环预测器与TAGE之间的优先级关系需要仔细设计。基本原则是：

循环预测器的优先级

当循环预测器的置信度高时（即conf字段达到预测阈值），循环预测器的预测结果覆盖TAGE的预测。这是因为对于固定迭代次数的循环，循环预测器的计数机制在理论上可以达到100%的精度，而TAGE的精度受限于历史长度和表容量。

然而，当循环预测器的预测与TAGE的预测一致时，直接使用（任一方的）预测结果即可。关键场景是两者预测不一致的情况——此时循环预测器优先。

循环预测器与TAGE的更新交互

当循环预测器提供了最终预测（覆盖了TAGE）时，TAGE的更新策略需要相应调整：

• 如果循环预测器的预测是正确的，TAGE不需要进行表项分配（因为最终预测已经正确，即使TAGE预测错误也不需要“修复”TAGE）。但TAGE的计数器仍然按照实际方向更新，以保持训练的连续性。

• 如果循环预测器的预测是错误的（即循环的迭代次数发生了变化），TAGE按照正常的更新策略进行更新和分配。同时，循环预测器的表项被重置或降低置信度。

推测性更新

在超标量处理器中，循环分支的多个迭代可能在多个周期中被连续预测（在实际解析之前），因此循环预测器需要支持推测性更新。spec_count字段用于维护推测性的迭代计数——每次预测taken时spec_count递增，预测not-taken时spec_count被重置。当分支实际解析后，如果预测正确则commit更新到count字段；如果预测错误则spec_count被恢复。

循环预测器的存储开销

循环预测器的存储开销相对较小。每个循环表项需要约50$\sim$60位（12位tag + 14位count + 14位limit + 14位spec_count + 3位conf + 3位age + 1位dir）。一个64项的循环预测器仅需约$64 \times 56 = 3584$位$\approx 0.44$ KB的存储——不到TAGE存储的1%。即使增加到128项，存储也不到1 KB，因此循环预测器在存储效率方面非常出色。

循环预测器的表容量（项数）决定了它能够同时跟踪多少个不同的循环分支。在典型的程序执行中，同时“活跃”的固定迭代循环数量通常不超过8$\sim$16个（考虑到嵌套循环和函数调用中的多个循环），因此64项的循环预测器在大多数工作负载下绑定充足。当循环预测器的容量不足时，老化（age）机制会自动驱逐最不活跃的循环表项，为新的循环分支腾出空间。

嵌套循环的处理

嵌套循环对循环预测器提出了特殊的挑战。考虑一个经典的双重循环：

for (int i = 0; i < M; i++) {      // 外循环：M次
    for (int j = 0; j < N; j++) {   // 内循环：N次
        // 循环体
    }
}

内循环的分支行为是：连续$N-1$次taken，然后1次not-taken，周期为$N$。循环预测器可以轻松学习这一模式（$\text{limit} = N-1$）。外循环的分支行为更为复杂：它在每次内循环完成后执行一次，连续$M-1$次taken，然后1次not-taken。但外循环的相邻两次执行之间间隔了$N$次内循环分支的执行——在这$N$次间隔中，全局历史寄存器被内循环的方向记录所“污染”。

对于循环预测器来说，外循环的处理相对简单——循环预测器使用的是本地计数器（per-branch counter），不受全局历史的影响。每次外循环分支执行时，循环预测器的spec_count递增，直到等于limit时预测not-taken。因此，循环预测器天然地能够处理嵌套循环中的外循环。

然而，在超标量处理器中，内循环的最后一次迭代（not-taken）和外循环的下一次迭代（taken）可能在非常近的时间点被预测。如果两者的预测间隔不到外循环分支的实际执行延迟（即内循环尾部的not-taken尚未被解析），循环预测器对外循环的spec_count更新可能基于推测路径——这需要与推测恢复机制配合。

循环预测器与变迭代次数循环

实际程序中的很多循环并非固定迭代次数。例如，遍历链表的循环的迭代次数取决于链表长度，每次调用可能不同。对于这类变迭代次数循环，循环预测器的置信度会反复被破坏。

一种改进方案是多限值循环预测器（Multi-limit Loop Predictor）：为同一条循环分支记录最近$K$个不同的limit值（如$K = 2\sim 4$），在预测时尝试匹配当前计数是否等于某个已记录的limit。当计数等于任一已记录的limit时，预测not-taken；否则预测taken。这种方案可以处理迭代次数在少数几个值之间交替变化的循环（如处理不同长度的数据包），但对于迭代次数完全随机的循环仍然无效。

多限值循环预测器的存储开销为每项增加$K \times w_{\text{limit}}$位（$w_{\text{limit}}$为limit字段宽度），对于$K = 2$和$w_{\text{limit}} = 14$，每项增加28位。在64项的循环预测表中，这增加约224字节的存储——仍然是可接受的。

感知机预测器

感知机预测器（Perceptron Predictor）由Daniel Jiménez和Calvin Lin在2001年提出，是将机器学习方法应用于分支预测的开创性工作。与基于查表的传统预测器不同，感知机预测器使用线性分类器来学习分支方向与历史模式之间的关系。

感知机算法在分支预测中的应用

经典感知机模型

感知机是最简单的人工神经网络模型，由Frank Rosenblatt在1957年提出。一个感知机接受$n$个输入$x_1, x_2, \ldots, x_n$，每个输入对应一个权重$w_1, w_2, \ldots, w_n$，以及一个偏置$w_0$。感知机的输出为：

$$y = \text{sign}\Bigl(w_0 + \sum_{i=1}^{n} w_i \cdot x_i\Bigr)$$

在分支预测中，输入$x_i$取值$+1$（对应分支历史中的taken）或$-1$（对应not-taken），偏置$w_0$对应分支本身的倾向性（bias），输出$y > 0$预测taken，$y \leq 0$预测not-taken。

感知机分支预测器的结构

对于每个分支（由PC索引），维护一个权重向量$\mathbf{w} = (w_0, w_1, \ldots, w_n)$，其中$n$为全局历史长度。权重向量存储在一个以分支PC为索引的表中。预测过程为：

1. 用分支PC索引权重表，获取对应的权重向量$\mathbf{w}$。

2. 将全局历史$\mathbf{h} = (h_1, h_2, \ldots, h_n)$（其中$h_i \in \{+1, -1\}$）与权重向量做点积：

$$y = w_0 + \sum_{i=1}^{n} w_i \cdot h_i$$

3. 如果$y \geq 0$则预测taken，否则预测not-taken。

权重的训练

感知机使用在线学习算法进行训练。当分支被解析后，按照以下规则更新权重：

$$\text{if } (\text{sign}(y) \neq t) \text{ or } (|y| \leq \theta): \quad w_i \gets w_i + t \cdot x_i, \quad \forall i \in \{0, 1, \ldots, n\}$$

其中$t \in \{+1, -1\}$为实际分支方向，$x_0 = 1$为偏置输入，$\theta$为训练阈值。训练条件有两种情况触发更新：

• 预测错误（$\text{sign}(y) \neq t$）：必须更新权重以修正错误。

• 预测正确但置信度低（$|y| \leq \theta$）：虽然预测正确，但权重还没有“学到足够”，继续强化。

训练阈值$\theta$控制了学习的速度和稳定性。Jiménez给出的最优阈值公式为：

$$\theta = \lfloor 1.93 \cdot n + 14 \rfloor$$

其中$n$为历史长度。这一公式的推导基于感知机收敛定理的分析。

感知机训练算法的完整分析

为了更深入地理解感知机预测器的行为，本小节将从收敛性、训练开销和实际程序中的线性可分性三个角度进行系统分析。

感知机收敛定理在分支预测中的应用。经典的感知机收敛定理（Novikoff, 1962）指出：如果训练数据是线性可分的（即存在一个权重向量$\mathbf{w}^*$使得$t \cdot (\mathbf{w}^* \cdot \mathbf{x}) > 0$对所有训练样本成立），那么感知机学习算法在有限步内收敛到一个正确分类所有样本的权重向量。收敛所需的更新步数上界为：

$$k \leq \frac{R^2 \|\mathbf{w}^*\|^2}{\gamma^2}$$

其中$R = \max \|\mathbf{x}\|$为输入向量的最大范数，$\gamma = \min_i \frac{t_i \cdot (\mathbf{w}^* \cdot \mathbf{x}_i)}{\|\mathbf{w}^*\|}$为最优分类器的间隔（margin）。

将此定理应用到分支预测中：$\mathbf{x} = (1, h_1, h_2, \ldots, h_n)$其中$h_i \in \{+1, -1\}$，因此$R = \sqrt{n+1}$。如果一条分支是线性可分的且最优间隔为$\gamma$，则感知机最多需要$(n+1)/\gamma^2$次训练更新即可收敛。对于$n = 64$和典型的$\gamma \approx 1$，收敛需要约65次更新——以6-wide处理器每周期retire 1$\sim$2条分支计算，约需30$\sim$65个周期。这比TAGE的饱和计数器（2$\sim$3次更新即可收敛）慢约20$\times$。

实际程序中分支的线性可分比例。Jiménez在其研究中通过穷举搜索估算了SPEC CPU基准中分支的线性可分比例：

工作负载类别	线性可分比例	XOR类分支比例
SPEC INT	78%$\sim$85%	3%$\sim$8%
SPEC FP	85%$\sim$92%	1%$\sim$4%
Server	75%$\sim$82%	5%$\sim$10%

这意味着约80%$\sim$85%的分支可以被感知机准确预测（假设训练充分），剩余15%$\sim$20%包含非线性相关性——其中3%$\sim$10%是XOR类型的纯非线性模式，其余是更复杂的高阶交互。TAGE通过多表结构间接处理这些非线性模式，因此在总体MPKI上通常略优于经典感知机。

训练开销的硬件量化。在6-wide处理器中，分支指令约占提交指令的15%$\sim$20%，即每周期约retire 0.9$\sim$1.2条分支。每条分支retire时需要执行以下训练操作：

1. 判断训练条件：比较$|y|$与$\theta$（一次8位比较），以及检查预测是否正确（一次1位比较）。这两个比较可以在1个gate延迟内完成。

2. 如果需要更新：对$n+1$个权重执行$w_i \gets w_i + t \cdot h_i$。由于$t, h_i \in \{+1, -1\}$，$t \cdot h_i$等于$+1$或$-1$，因此更新操作简化为$w_i \gets w_i + 1$或$w_i \gets w_i - 1$——即每个权重的更新只需一个8位增量器/减量器。

3. $n+1$个增量器可以完全并行执行（权重之间没有数据依赖），总的训练延迟为一次8位加法的延迟——约2$\sim$3个gate延迟。

4. 训练的写回带宽需求为$(n+1) \times 8$位。对于$n = 64$，每次训练需要写回520位。如果权重表使用单端口SRAM，每周期只能写一项（$\sim$520位），写带宽匹配训练需求。

设计权衡 1 — 感知机延迟（加法链） vs. TAGE延迟（SRAM读+比较）

感知机和TAGE在预测延迟的特征上有本质区别，这一区别直接影响了它们在流水线中的集成方式。

TAGE的延迟构成：（1）索引哈希计算（XOR，$\sim$2个gate延迟）$\to$（2）SRAM读取（$\sim$3$\sim$4个gate延迟）$\to$（3）标签比较（12位XNOR+AND，$\sim$2个gate延迟）$\to$（4）优先级选择（最长匹配编码器，$\sim$2个gate延迟）。总计$\sim$9$\sim$10个gate延迟。所有表的读取并行进行，因此表的数量不影响延迟。

感知机的延迟构成：（1）权重表SRAM读取（$\sim$3$\sim$4个gate延迟）$\to$（2）条件取反（$h_i = -1$时取反，$\sim$1个gate延迟）$\to$（3）加法器树（$\lceil\log_2(n+1)\rceil$级，每级$\sim$2$\sim$3个gate延迟）。对于$n = 64$：$4 + 1 + 7 \times 2.5 \approx 22.5$个gate延迟。

感知机的延迟约为TAGE的2$\sim$2.5$\times$。在时钟频率为4 GHz的处理器中（每周期约250 ps），TAGE可以在一个周期内完成预测（约100 ps的延迟），而感知机需要两个周期。这意味着感知机预测器如果用于主预测，需要额外1个周期的“预测气泡”——这与第 14.0 章中讨论的BHT预测延迟分析类似，每个额外周期的气泡约降低3%$\sim$5%的IPC。

AMD Zen系列的解决方案是使用两级预测流水线：第一级使用一个小型快速预测器（可能是简单的BHT或小型TAGE），第二级使用感知机主预测器。当两级结果不一致时，以第二级为准（覆盖第一级）。这样感知机的额外延迟只在覆盖发生时才产生气泡，平均影响可控。

性能分析 3 — 感知机 vs. TAGE在相同存储预算下的MPKI对比

以64 KB存储预算为例，对比感知机和TAGE在CBP-5竞赛trace上的MPKI表现。

步骤1：配置。TAGE：12张表 + 基础表 + 循环预测器。历史长度$\{5, 9, 15, 25, 44, 76, 130, 223, 383, 657, 1129, 1938\}$。每张表$\sim$4K项。总存储$\sim$64 KB。Hashed Perceptron：$K = 8$个权重表，每表$\sim$8K项，历史长度$n = 62$，8位权重。总存储$\sim$64 KB。

步骤2：整体MPKI。TAGE：加权MPKI $\approx$ 3.42。Hashed Perceptron：加权MPKI $\approx$ 3.58。TAGE优势约4.5%。

步骤3：分工作负载分析。在短循环密集的工作负载上，TAGE凭借循环预测器（精确计数loop退出）显著优于感知机（MPKI差距可达15%$\sim$20%）。在深度嵌套条件分支上，感知机凭借长历史+多特征的综合能力略优于TAGE（MPKI差距约5%$\sim$8%）。在解释器/虚拟机类工作负载上，TAGE凭借长历史表的覆盖能力优于感知机（MPKI差距约10%）。

步骤4：延迟影响。上述MPKI比较未考虑预测延迟。如果将感知机的额外1周期气泡折算为等效MPKI，需要增加约0.1$\sim$0.2 MPKI的“延迟惩罚”，进一步拉大与TAGE的差距。

步骤5：结论。在相同存储预算下，TAGE在总体MPKI上以约5%$\sim$10%的优势领先于Hashed Perceptron。感知机的核心劣势在于线性不可分问题和训练速度，优势在于存储效率和长历史能力。两种方法的精度差距随着存储预算的增大而缩小——在256 KB预算下，Multiperspective Perceptron与TAGE-SC-L的MPKI差距不到3%。

感知机 vs. 查表预测器：存储效率

感知机预测器相对于传统查表预测器的核心优势在于存储效率。考虑使用$n$位全局历史的预测器：

• GShare（查表）：预测表有$2^n$个表项，每项2位。总存储为$2^{n+1}$位。当$n = 64$时，存储需求为$2^{65}$位——完全不可行。实际中GShare的历史长度受限于$n \leq 20$左右。

• 感知机（线性模型）：每个分支的权重向量有$n+1$个权重，每个权重为$\lceil \log_2(2\theta + 1) \rceil$位（通常8位）。若权重表有$N$项，总存储为$N \times (n+1) \times 8$位。当$n = 64$、$N = 1024$时，总存储为$1024 \times 65 \times 8 = 532480$位$\approx 65$ KB。

感知机预测器可以使用任意长的历史而不会导致存储需求指数爆炸——这是因为感知机假设分支方向是历史位的线性函数，而查表方法不做任何假设（因此需要枚举所有可能的历史模式）。当然，线性假设也带来了局限性——感知机无法学习非线性可分的模式，如XOR关系（一个分支的方向是两个历史位的异或）。

关键路径分析

感知机预测器的一个实现挑战是点积计算的延迟。$n$个乘累加操作（$w_i \times h_i$的求和）在串行实现下需要$O(n)$个加法器延迟。对于$n = 64$，即使使用加法器树将延迟降低到$O(\log n)$，仍然需要6级加法器——每个加法器约2$\sim$3个gate延迟，总延迟约12$\sim$18个gate延迟。这比TAGE的查表+标签比较的延迟（约6$\sim$8个gate延迟）要长得多。

感知机预测器的点积计算（加法器树实现）

感知机的局限性：线性不可分问题

感知机的根本局限在于它只能学习线性可分的函数。在分支预测的语境中，这意味着感知机假设分支方向$t$可以表示为历史位$h_i$的线性组合加上偏置：$t = \text{sign}(\sum w_i h_i + w_0)$。然而，某些分支的方向取决于历史位之间的非线性关系。最典型的例子是XOR关系：

$$t = h_1 \oplus h_2 = \begin{cases} +1 & \text{if } h_1 \neq h_2 \\ -1 & \text{if } h_1 = h_2 \end{cases}$$

这一函数无法用任何权重$w_0, w_1, w_2$的线性组合来表示——这正是Minsky和Papert在1969年证明的感知机不可学习XOR问题。

在实际程序中，XOR类型的非线性关系确实存在。例如，一个分支的方向可能取决于“之前两条分支是否都是taken或者都是not-taken”——这正是一个XOR关系。TAGE通过其多表结构间接地处理这类非线性关系（不同的历史长度提供了不同的“视角”），而感知机则完全无能为力。

为了缓解线性不可分问题，后续的研究提出了几种扩展：

• 路径感知机（Path-based Perceptron）：使用分支路径信息（不仅是方向，还包括分支PC的部分地址）来丰富特征空间，间接引入非线性。

• 多路感知机（Multiperspective Perceptron）：使用多种不同的特征（局部历史、全局历史、路径历史、分支地址的各种组合）来增加模型的表达能力。Multiperspective Perceptron在CBP-5竞赛中取得了接近TAGE-SC-L的精度。

• 乘积项（Product Terms）：将某些历史位的乘积$h_i \cdot h_j$作为额外特征，直接建模二阶交互。代价是特征数量从$n$增加到$n + \binom{n}{2}$，存储和计算开销显著增加。

Multiperspective Perceptron的架构

Multiperspective Perceptron（多视角感知机）由Jiménez在2016年CBP-5竞赛中提出，其核心改进是将经典感知机的单一全局历史特征扩展为多种不同类型的特征（perspectives），每种特征从不同角度描述当前分支的执行上下文。

典型的特征类型包括：

1. 全局方向历史（Global History）：最近$n$条分支的方向序列，即经典感知机使用的特征。

2. 局部方向历史（Local History）：当前分支PC在最近$k$次执行中的方向序列。局部历史能够捕获单条分支的周期性行为（如循环分支的taken/not-taken模式）。

3. 路径历史（Path History）：最近$m$条分支指令的PC地址（而非方向）的序列。路径历史记录了“程序走过的路径”，能够区分同一条分支在不同调用路径下的行为差异。

4. 地址组合特征（Address-based Features）：当前分支PC与全局历史或路径历史的各种哈希组合。例如，PC的低8位与GHR的低16位异或后的哈希值。

5. ACYCLIC特征：记录当前分支在最近几次执行中的方向变化模式。如果一条分支在最近3次执行中分别是T、T、NT，则ACYCLIC特征编码为“110”。

6. 回退预测特征（Recency Features）：记录最近几条被预测为taken的分支的PC地址，用于捕获“哪些分支最近被执行过”的信息。

Multiperspective Perceptron为每种特征维护独立的权重表，最终预测是所有特征的加权和：

$$y = w_0[\text{PC}] + \sum_{p=1}^{P} W_p\bigl[\text{hash}_p(\text{PC}, \text{feature}_p)\bigr]$$

其中$P$为特征类型数量（通常$P = 8\sim 15$），$\text{feature}_p$为第$p$种特征，$W_p$为对应的权重表。

Multiperspective Perceptron在CBP-5竞赛中（64 KB预算类别）的MPKI约为3.05，仅略高于TAGE-SC-L的2.98，但其架构比TAGE-SC-L更为统一——所有特征都通过相同的加权和机制贡献预测，不需要TAGE的标签匹配和最长匹配选择逻辑，也不需要SC的串联校正。这种统一性使得Multiperspective Perceptron在某些实现场景中（特别是需要定制化特征组合时）比TAGE-SC-L更灵活。

感知机预测器的训练速度问题

感知机预测器的一个实际问题是训练速度较慢。GShare或TAGE使用饱和计数器，一次预测错误后计数器立即向正确方向调整，通常经过2$\sim$3次训练就能收敛到正确预测。感知机的权重更新则遵循梯度下降的原则，每次更新只改变权重$\pm 1$，对于一个需要$|w_i| = 20$的权重，需要约20次训练才能从初始值0收敛到目标值。

在程序上下文频繁切换的场景中（如操作系统内核、虚拟机管理程序），感知机的慢训练速度意味着预测器需要更长的时间才能适应新的分支模式，导致冷启动阶段的MPKI较高。相比之下，TAGE的饱和计数器只需2$\sim$3次训练即可锁定预测方向，在上下文切换频繁的场景中具有明显优势。

一种缓解慢训练的方法是使用加速训练机制：当预测严重错误（$|y|$很小但方向相反）时，将权重更新步长从1增加到2或4。但这种加速可能导致权重振荡，需要与训练阈值$\theta$的设置仔细配合。

感知机预测延迟的优化技术

感知机预测的点积计算延迟是其硬件实现的核心瓶颈。除了加法器树之外，还有以下优化技术：

部分和缓存（Partial Sum Caching）。观察到相邻两次预测之间，GHR只变化了1位（最新的分支方向被移入，最旧的被移出）。因此，新的点积可以从旧的点积增量计算：

$$y_{\text{new}} = y_{\text{old}} - w_n \cdot h_n^{\text{old}} + w_0^{\text{new}} \cdot 1 + (\text{权重移位调整})$$

但由于权重向量也发生了变化（不同的分支PC对应不同的权重），增量计算只在同一条分支连续多次执行时有效（如循环体中的分支），对于一般场景的适用性有限。

ahead pipelining。将点积计算分为多个流水线级：第1级完成前$n/2$个乘累加，第2级完成后$n/2$个乘累加并与第1级结果相加。这将关键路径减半，但引入了1个周期的额外预测延迟。

近似计算。在点积计算中使用截断加法（忽略低位进位）来加速。研究表明，截断加法在不超过8位权重的情况下造成的预测精度损失不到0.5%的MPKI，但可以将加法器延迟降低20%$\sim$30%。

Hashed Perceptron

经典感知机预测器为每个分支PC维护独立的权重向量，当权重表的项数有限时，不同PC之间存在别名冲突。Hashed Perceptron（哈希感知机）由Jiménez在2005年提出，通过改变权重存储的组织方式来缓解这一问题，同时降低存储开销。

基本思想

Hashed Perceptron不再为每个分支维护完整的权重向量，而是将全局历史分为多个子段，每个子段使用独立的权重表。具体而言，将$n$位全局历史分为$K$个子段，每个子段的长度为$n/K$位。权重$w_i$不再由PC单独索引，而是由PC与第$i$个历史位的组合哈希来索引一个共享的权重表。

更精确地说，Hashed Perceptron使用$K$个权重表$W_1, W_2, \ldots, W_K$，其中$W_k$由分支PC与全局历史的第$k$个子段的哈希来索引：

$$y = W_0[\text{PC}] + \sum_{k=1}^{K} W_k\bigl[\text{hash}(\text{PC}, \text{GHR}_{k})\bigr]$$

其中$\text{GHR}_k$表示全局历史的第$k$个子段。

存储效率提升

Hashed Perceptron的关键优势是不同分支可以共享权重表。经典感知机中，$N$个分支需要$N \times (n+1)$个权重；Hashed Perceptron中，每个权重表有$T$个表项（独立于分支数和历史长度），$K$个表总共需要$K \times T$个权重。当$K \times T \ll N \times (n+1)$时，存储效率显著提升。

与TAGE的关系

有趣的是，Hashed Perceptron与TAGE在结构上有相似之处：两者都使用多个表、每个表使用不同的特征进行索引、最终输出是多个表的“投票”结果。主要区别在于：

• TAGE使用“最长匹配优先”的选择策略，只有一个表提供预测；Hashed Perceptron使用所有表的加权和。

• TAGE的表项包含标签和饱和计数器；Hashed Perceptron的表项只包含有符号权重（无标签）。

• TAGE对标签不匹配的表项不使用；Hashed Perceptron的每个表总是贡献一个权重（即使存在别名）。

这种结构上的相似性揭示了一个更深层的统一视角：TAGE和Hashed Perceptron可以被看作同一个预测框架的两种极端实现。在这个框架中，多个使用不同特征索引的表并行查询，最终预测是各表输出的某种组合。TAGE使用“赢者通吃”的组合方式（只选一个表），Hashed Perceptron使用“民主投票”的组合方式（所有表加权求和）。两者的中间地带可能存在更好的组合策略——例如，使用前$K$个最长匹配表的加权和（而非仅用最长匹配），或者根据各表的匹配质量（标签匹配位数）来动态调整权重。

Hashed Perceptron的训练算法

Hashed Perceptron的训练遵循与经典感知机相同的在线学习规则，但由于多条分支共享权重表，别名冲突会干扰训练过程。当两条行为不同的分支映射到同一个权重表项时，它们的训练更新会相互冲突——一条分支将权重向$+$方向更新，另一条可能将同一个权重向$-$方向更新，导致权重在0附近振荡。

缓解别名干扰训练的一种方法是条件训练：只有当预测错误或置信度低时才更新权重（即式 (15.17)中的训练条件）。对于高置信度的正确预测，跳过权重更新，减少了不必要的更新操作，从而降低了别名冲突的频率。训练阈值$\theta$的设置控制了“高置信度”的判定标准——$\theta$越大，越多的正确预测会触发权重更新以加速收敛，但也增加了别名干扰的可能。

感知机的硬件实现架构

将感知机算法转化为高效的硬件实现需要解决几个关键的微架构问题。

权重表的组织

在经典感知机中，每条分支需要一个$(n+1)$元素的权重向量。如果权重表有$N$项、历史长度为$n$、每个权重为$w$位，则权重表的总存储为$N \times (n+1) \times w$位。对于$N = 1024$、$n = 64$、$w = 8$的典型配置，总存储为$1024 \times 65 \times 8 = 532480$位$\approx 65$ KB。

这个存储需要在每次预测时被完整读取——一次预测需要读出整个权重向量（65个8位权重）。如果使用常规SRAM，这意味着需要一个65$\times$8 = 520位宽的读端口，或者将权重向量分散在多个bank中并行读取。

一种实用的组织方式是将权重表按行存储：每行对应一条分支的完整权重向量，行宽为$(n+1) \times w$位。SRAM按行读取，一次读出整个权重向量。但这要求SRAM的位线宽度非常大——520位的位线在物理实现上可能导致显著的读取延迟和功耗。

乘法的简化

感知机的“乘法”$w_i \times h_i$中，$h_i \in \{+1, -1\}$只有两个值，因此乘法可以简化为条件取反：如果$h_i = +1$，结果为$w_i$；如果$h_i = -1$，结果为$-w_i$（即$\overline{w_i} + 1$的补码表示）。对于8位权重，条件取反只需要8个XOR门和1个条件加1操作，远比通用乘法器简单。

进一步的优化是使用2的补码表示的性质：$-w_i = \overline{w_i} + 1$中的“+1”可以被推迟到加法器树中处理（作为进位输入），从而将每个乘法单元的延迟减少到仅一层XOR门。

加法器树的面积优化

$n = 64$个8位有符号数的求和需要一个加法器树。直接使用二叉加法器树需要63个加法器，每级加法器的宽度逐级增加（第1级为8位，第2级为9位，...，第6级为14位）。总的加法器面积约为$63 \times 11 \times C_{\text{FA}}$（其中11是加法器的平均位宽，$C_{\text{FA}}$是一个全加器的面积）。

使用Wallace tree或Dadda tree等压缩树结构可以减少加法器树的级数（从$\log_2 64 = 6$级减少到约4级），但每级的逻辑复杂度增加。在面积和延迟之间的最优权衡取决于目标工作频率和工艺节点的特性。

在5 nm工艺下，一个64输入$\times$8位的加法器树的面积约为0.005 mm$^2$，延迟约为150 ps$\sim$200 ps。对于$N = 1024$条分支的权重表加上加法器树，感知机预测器的总面积约为0.02$\sim$0.03 mm$^2$，与同等存储预算的TAGE相当。

设计提示

感知机加法器树与第 29.0 章的联系。感知机预测器的核心延迟瓶颈——64输入的加法器树——本质上是第 29.0 章中讨论的多输入加法器问题的一个具体实例。第 29.0 章将详细介绍Wallace tree、Dadda tree以及4:2压缩器等技术，这些技术可以直接用于优化感知机的点积计算。一个有趣的设计决策是：感知机的加法器树与ALU中的乘法器共享了相同的微架构结构（都是多输入部分积的规约问题），甚至可以在物理实现上共享硬件——但时序路径上感知机在前端，乘法器在后端，两者的时序约束截然不同。这再次印证了“查表 vs 计算”的权衡在处理器不同子系统中的普遍性。

AMD Zen系列中的感知机预测器

AMD从Zen微架构（2017年）开始在其高性能处理器中采用感知机预测器，这是感知机分支预测在商业处理器中最著名的应用。

案例研究 1 — AMD Zen系列的分支预测器演进

AMD Zen系列的分支预测器设计经历了显著的演进：

Zen/Zen+（2017$\sim$2018）

Zen的分支预测器采用了以感知机为核心的架构，使用了哈希感知机（Hashed Perceptron）作为主预测器。根据AMD的公开文献和微架构分析，Zen的预测器包含：

• 一个Hashed Perceptron方向预测器

• 一个BTB（Branch Target Buffer）用于目标地址预测

• 一个间接跳转预测器

• 一个返回地址栈（RAS）

Zen的分支预测流水线为2级：第一级使用一个小型的L1 BTB提供快速预测（0周期气泡），第二级使用感知机预测器提供高精度预测（1周期气泡）。当两级预测结果不一致时，采用更高精度的第二级结果。

Zen 2（2019）

Zen 2在分支预测方面的主要改进包括增大了预测器的存储预算，以及改进了BTB的组织（L1 BTB从256项增加到512项，L2 BTB从4K项增加到7K项）。感知机预测器的核心架构变化不大，但表容量有所增加。

Zen 3（2020）

Zen 3对分支预测器进行了较大的架构升级。根据微基准测试的分析，Zen 3的预测精度有了显著提升，尤其是在嵌套条件和间接跳转方面。推测Zen 3可能在感知机预测器的基础上增加了类似TAGE的组件或统计校正机制。

Zen 4/Zen 5（2022$\sim$2024）

Zen 4进一步增大了BTB容量（L2 BTB增加到8K$\sim$12K项），并且改进了分支预测器的训练速度。微架构分析表明，Zen 4的方向预测MPKI在SPEC CPU 2017上约为2.5$\sim$4.0，与Intel的Golden Cove大致相当。

Zen 5（2024年）是AMD在分支预测方面最大的一次架构跳跃。根据公开的微架构分析，Zen 5的分支预测器进行了全面重设计，主要改进包括：

• 双管道预测。Zen 5的前端被扩展为2个独立的取指管道，每个管道每周期可以独立预测和取指。这意味着在理想情况下，Zen 5每周期可以处理两个取指块，将前端的峰值指令供给速率翻倍。这种双管道设计要求分支预测器也能每周期产生两个预测结果——需要预测表提供双倍的读带宽或使用双端口SRAM。

• 更大的方向预测器。Zen 5的方向预测器存储预算据推测增加了约50%（从约48 KB增加到约72 KB），使得预测精度在大代码足迹工作负载上有显著提升。

• 改进的间接分支预测。Zen 5增大了间接分支预测器的容量和历史长度覆盖范围，对虚函数密集的C++和Java工作负载带来了明显的性能改善。

为什么AMD选择感知机

AMD选择感知机而非TAGE的原因可能包括：（1）感知机在功耗效率上具有优势——其权重表不需要标签字段，在相同存储预算下可以容纳更多的有效预测信息。（2）AMD在感知机预测器方面拥有长期的研究积累（Jiménez曾在AMD的研究中心工作）。（3）Hashed Perceptron的多表结构与TAGE相似，但加权和机制比TAGE的“最长匹配”机制更加“民主”，在某些工作负载上可能更稳健。

设计权衡 2 — TAGE与感知机的对比

TAGE和感知机代表了两种不同的分支预测哲学——查表与计算。表表 15.4总结了两者的关键差异。

特性	TAGE	感知机/Hashed Perceptron
预测机制	查表+标签匹配	线性加权和
历史利用	最长匹配优先	所有历史段并行贡献
表项结构	tag + ctr + u	有符号权重
非线性能力	有限（通过多表间接实现）	无（纯线性）
关键路径	表查询+标签比较	点积计算（加法器树）
存储效率	标签开销较大	无标签，密度高
抗别名	标签过滤	无过滤，靠统计平均
训练速度	快（饱和计数器）	较慢（权重收敛需更多样本）
实现复杂度	中等	加法器树面积大

TAGE-SC-L：CBP竞赛冠军架构

TAGE-SC-L（TAGE + Statistical Corrector + Loop predictor）是由Seznec提出的完整分支预测器架构，在CBP-4（2014年）和CBP-5（2016年）竞赛中均获得冠军。它将前述的TAGE、统计校正器和循环预测器有机地组合在一起，代表了基于表的分支预测器的最高水平。

完整结构

TAGE-SC-L的完整结构如图图 15.6所示。

TAGE-SC-L的完整架构

各组件的协同

TAGE-SC-L的预测流程按照以下步骤进行：

步骤1：并行查询

分支PC和全局历史同时被送入三个组件：TAGE预测器、统计校正器和循环预测器。三者的查询是并行的，但SC的校正决策需要等待TAGE的预测结果。

步骤2：TAGE预测

TAGE按照算法 15.1中的流程进行预测，输出以下信息：

• pred_TAGE：TAGE的预测方向

• provider：提供预测的表编号和表项

• altpred：备选预测方向

• confidence：置信度（由提供者计数器的绝对值衡量）

步骤3：SC校正

SC接收TAGE的预测结果和置信度信息，计算加权和$\sigma$，并根据式 (15.13)和式 (15.14)决定是否翻转TAGE的预测。SC的校正只在TAGE置信度较低时生效。

步骤4：Loop覆盖

循环预测器独立地判断当前分支是否为已确认的循环分支。如果是，且循环预测器的置信度高（conf达到阈值），则循环预测器的预测覆盖TAGE和SC的结果。

步骤5：最终预测输出

最终预测的优先级为：

$$\text{pred}_{\text{final}} = \begin{cases} \text{pred}_{\text{Loop}} & \text{if Loop置信度高} \\ \text{pred}_{\text{SC}} & \text{if SC校正生效} \\ \text{pred}_{\text{TAGE}} & \text{otherwise} \end{cases}$$

更新流程

预测的更新在分支被实际解析后进行，顺序如下：

1. Loop更新：如果当前分支被循环预测器跟踪，更新其count/spec_count字段。如果循环预测器预测错误（迭代次数变化），重置循环表项。

2. TAGE更新：按照算法 15.2更新TAGE的计数器、useful位，并在预测错误时尝试分配新表项。

3. SC更新：更新SC的计数器表。如果SC的校正导致了错误预测，调整校正阈值$\theta$。

4. GHR更新：将实际分支方向移入全局历史寄存器，并更新所有CSR。

硬件描述 3 — TAGE-SC-L的流水线时序

在实际硬件实现中，TAGE-SC-L的查询通常需要2$\sim$3个流水线阶段：

阶段	操作
F0（取指第1阶段）	PC送入TAGE/SC/Loop的索引计算；SRAM读取开始
F1（取指第2阶段）	SRAM读取完成；标签比较和最长匹配选择；TAGE输出初步预测；SC加权和计算
F2（取指第3阶段）	SC校正决策完成；Loop覆盖判断；最终预测方向确定

在F1阶段结束时，TAGE的预测已经可用，取指单元可以基于TAGE的预测开始取指。如果在F2阶段SC或Loop修改了预测方向，则需要1个周期的气泡来重新取指。由于SC/Loop只在少数情况下（$<5\%$的分支）修改TAGE的预测，这一额外的气泡的IPC影响很小。

另一种实现策略是将整个TAGE-SC-L的查询压缩到2个流水线阶段中完成，代价是每个阶段的逻辑更深，可能限制最高工作频率。在5 GHz级别的处理器中，2阶段实现的时序裕度非常紧张，通常需要定制的SRAM和加法器设计。

存储预算与精度权衡

表表 15.5给出了TAGE-SC-L在不同存储预算下的预测精度，基于CBP-5基准测试集的平均MPKI数据。

预算	GShare	竞争	TAGE	TAGE-SC	TAGE-SC-L
4 KB	8.92	7.85	6.41	5.98	5.82
8 KB	7.53	6.82	5.62	5.12	4.95
16 KB	6.45	5.91	4.73	4.28	4.12
32 KB	5.71	5.22	4.08	3.62	3.48
64 KB	5.28	4.81	3.58	3.12	2.98
128 KB	5.02	4.55	3.22	2.82	2.71

不同存储预算下各预测器架构的MPKI对比（CBP-5基准测试集）

不同存储预算下各预测器架构的MPKI对比

在解读这些数据时需要注意的一个重要方面是MPKI分布的不均匀性。上表中的MPKI是所有基准测试的几何平均值，但不同基准测试之间的MPKI差异可以超过一个数量级。例如，在64 KB TAGE-SC-L配置下，mcf（图论算法，大量数据依赖分支）的MPKI可达8$\sim$12，而povray（光线追踪，规则控制流）的MPKI不到0.5。这种不均匀性意味着：

• 整体MPKI的改善主要来自难以预测的少数基准测试。如果去掉最差的3$\sim$5个基准测试，不同预测器之间的差距会大幅缩小。

• 预测器的设计需要在“帮助最难的分支”和“不损害最容易的分支”之间取得平衡。例如，SC的校正主要帮助TAGE表现较差的分支，但如果SC过于激进，它可能在TAGE已经正确预测的分支上“帮倒忙”。

从表表 15.5和图图 15.7可以观察到以下规律：

1. TAGE相对于传统预测器的优势巨大。在64 KB预算下，TAGE的MPKI（3.58）比GShare（5.28）低32%，比竞争预测器（4.81）低26%。这一优势来自于TAGE的多历史长度覆盖——GShare使用单一历史长度，在任何给定的预算下都无法同时优化短程和长程相关性的预测。

2. SC提供了稳定的增量改善。在所有预算下，SC将TAGE的MPKI降低了约10%$\sim$15%。SC的改善幅度相对稳定，因为SC校正的是TAGE的系统性错误模式，这些模式不随TAGE表容量的增加而消失。

3. Loop预测器的贡献相对较小但一致。TAGE-SC-L相对于TAGE-SC的MPKI改善约3%$\sim$5%。循环预测器的主要价值不在于MPKI的数值改善，而在于消除了循环退出时的必然错误预测——这些错误预测的惩罚通常较大。

4. 收益递减效应显著。从4 KB到64 KB（$16\times$存储），TAGE-SC-L的MPKI从5.82降低到2.98（49%改善）；但从64 KB到128 KB（$2\times$存储），MPKI仅从2.98降低到2.71（9%改善）。这表明在64 KB以上的预算下，仅靠增加存储来提升精度的效率很低，需要算法层面的创新。

性能分析 4 — TAGE-SC-L的精度极限

以CBP-5的64 KB预算类别为参考，TAGE-SC-L的平均MPKI约为2.98。将这一数字转换为预测精度：假设分支指令占所有指令的15%$\sim$20%（典型的整数工作负载），MPKI = 2.98意味着每千条分支指令约有15$\sim$20次预测错误，即方向预测精度约为98.0%$\sim$98.5%。

这一精度已经非常接近理论极限。在分支预测竞赛的基准测试中，存在一部分内禀不可预测（inherently unpredictable）的分支——它们的方向取决于输入数据（如哈希表查找的比较结果、加密算法的条件分支等），任何基于历史的预测器都无法正确预测。这些分支的MPKI贡献约为1.5$\sim$2.0，构成了方向预测精度的硬性下限。

进一步提升预测精度的方向包括：（1）使用更复杂的非线性模型（如深度学习），但硬件实现成本极高；（2）利用程序的语义信息（如值预测），但这超出了传统分支预测的范畴；（3）编译器辅助——通过代码变换减少难以预测的分支（如无分支条件移动、谓词执行等）。

TAGE-SC-L在商业处理器中的影响

虽然没有商业处理器完全公开其分支预测器的详细实现，但从微架构分析和专利文献来看，现代高性能处理器的方向预测器在架构上与TAGE-SC-L有很多相似之处：

• Intel（Golden Cove/Raptor Cove及后续）：Intel的分支预测器被认为使用了类TAGE的多历史长度表组织，加上额外的校正机制。Intel的专利文献中多次出现“几何级数历史长度”和“标记表”的描述。

• AMD（Zen系列）：如前所述，AMD使用Hashed Perceptron作为核心预测器，但也可能融合了TAGE的某些设计元素。

• Apple（A系列/M系列）：Apple的处理器在分支预测精度方面表现出色（微基准测试显示其MPKI在业界最低水平），推测其使用了TAGE-SC-L的变体或类似复杂度的预测器架构。

• ARM（Cortex-X系列）：ARM的高性能核心（如Cortex-X4）也采用了多级分支预测器，其方向预测器的架构细节未公开，但从性能数据推断具有与TAGE相当的预测精度。

TAGE-SC-L与Multiperspective Perceptron的精度对比

在CBP-5竞赛中，TAGE-SC-L和Multiperspective Perceptron是两个最强的参赛方案，它们的精度非常接近但各有优势的工作负载领域。表表 15.6详细对比了两者在不同类型工作负载上的MPKI。

工作负载	TAGE-SC-L	MP Perceptron	胜出方
规则控制流（循环、简单条件）	2.1	2.5	TAGE-SC-L
深度嵌套条件	2.8	2.6	MP Perceptron
数据依赖分支（排序、搜索）	4.5	4.3	MP Perceptron
解释器分发循环	3.2	3.8	TAGE-SC-L
服务器工作负载	4.8	5.1	TAGE-SC-L
科学计算	1.5	1.4	MP Perceptron
加权平均	2.98	3.05	TAGE-SC-L

TAGE-SC-L与Multiperspective Perceptron的详细MPKI对比（64 KB预算）

从表中可以观察到：TAGE-SC-L在规则控制流和解释器场景中占优，这归功于TAGE的长历史覆盖能力和循环预测器的精确计数；Multiperspective Perceptron在深度嵌套条件和数据依赖分支中略占优势，这得益于其多种特征类型的综合利用能力。两者的加权平均MPKI非常接近，差异不到3%。

这一对比结果暗示，未来的分支预测器可能会融合TAGE和感知机两种范式的优点——使用TAGE的标签匹配和最长匹配选择来处理长程相关性，使用感知机的加权和来处理需要综合多种特征的复杂分支模式。

设计权衡 3 — 分支方向预测器的选择：实现复杂度 vs. 精度

在实际处理器设计中，分支方向预测器的选择需要综合考虑精度、面积、功耗、时序和设计复杂度等多个维度。

预测器	精度	面积	功耗	时序	设计复杂度
GShare	中	小	低	快	低
竞争预测器	中高	小	低	快	低
TAGE	高	中	中	中	中高
感知机	高	中	中	慢（点积）	中高
TAGE-SC	很高	中大	中高	慢（串联SC）	高
TAGE-SC-L	最高	大	高	慢	很高

对于中端处理器核心（如ARM Cortex-A7x系列），TAGE的纯版本（不含SC和Loop）通常就是性价比最高的选择：TAGE在约16$\sim$32 KB的预算下提供了远超GShare和竞争预测器的精度，且设计复杂度可控。对于高端处理器核心（如Intel Golden Cove、Apple Everest、AMD Zen 4），TAGE-SC-L或其变体是追求极致IPC时的合理选择——在这类处理器中，分支预测器的面积和功耗仅占整个核心的3%$\sim$5%，但其精度改善可以带来5%$\sim$10%的IPC提升。对于嵌入式或低功耗核心，简单的GShare或竞争预测器仍然是合理的选择。

分支预测与处理器架构的协同设计

分支方向预测器并非孤立存在——它与处理器的其他子系统紧密耦合。几个关键的协同设计考虑包括：

（1）预测器与取指带宽。在宽度为$W$的超标量处理器中，取指单元每周期可能遇到多条分支指令。预测器需要每周期为所有可能的分支提供预测，或者与取指单元配合，在一个周期中只处理一个取指块中的第一条被预测为taken的分支。TAGE-SC-L的多表并行查询在面积和功耗上的开销与取指宽度成正比。

（2）预测延迟与流水线深度。预测延迟（从PC到预测结果的周期数）直接影响每次预测错误的惩罚。在现代处理器中，取指阶段通常有3$\sim$5个流水线级，分支预测器的查询延迟需要在2$\sim$3个周期内完成。TAGE-SC-L的2$\sim$3级流水线化查询正好匹配这一需求。

（3）推测更新与恢复。在乱序执行中，分支的实际解析可能延迟数十个周期。在此期间，预测器需要基于推测的历史进行预测。推测更新的GHR和CSR需要在预测错误时恢复到正确状态。TAGE的CSR恢复需要从检查点重建，这比简单的GHR恢复更复杂——每张表的CSR都需要独立的检查点，$M = 12$张表意味着24个CSR检查点（每张表2个CSR）。

（4）预测器的训练延迟。分支从被预测到实际解析（提交）之间的延迟越长，预测器的训练就越滞后。在深流水线、大窗口的处理器中，一条分支从预测到提交可能需要50$\sim$100个周期，在此期间同一PC的后续分支可能已经被预测了多次，都使用了过时的预测信息。一种缓解策略是在执行阶段（而非提交阶段）就更新预测器——这被称为“推测更新”（speculative update），但需要处理推测错误时的回滚。

训练延迟的量化分析。设一条分支指令从预测到结果可用的延迟为$D$个周期（通常$D = 15\sim 25$），同一条分支的两次执行之间的间隔为$I$条指令（对于紧密循环体中的分支，$I$可能很小，如10$\sim$20条指令；对于函数入口处的分支，$I$可能很大，如数千条指令）。如果$I / \text{IPC} < D$（即分支的执行间隔短于训练延迟），则同一条分支的多次执行会“堆叠”在流水线中——后面的执行使用的仍然是旧的预测器状态，而非最新的训练结果。

在一个IPC为4的处理器中，$D = 20$对应约80条指令的训练延迟。对于执行间隔$I < 80$的分支（如循环体中的分支），同一分支的最多$80/I$次执行会使用相同的过时预测器状态。如果预测器在第一次执行时预测错误并在训练后能够正确预测，那么在训练延迟期间的后续$80/I - 1$次执行也会预测错误——训练延迟放大了单次预测错误的影响。

这一分析表明，在执行阶段而非提交阶段更新预测器（将$D$从约20$\sim$25周期减少到10$\sim$15周期）可以显著降低频繁执行分支的MPKI。但推测更新引入了正确性问题——如果执行阶段的分支解析本身基于错误路径的推测值，更新到预测器中的信息就是错误的。这一问题将在第 17.0 章中进一步深入讨论。

功耗优化

分支方向预测器的功耗在高性能处理器核心中不可忽视。TAGE-SC-L的每次预测需要读取$M + 1$张表的SRAM（TAGE）加上$K$张表（SC）和一张循环表（Loop），总共约15$\sim$20次SRAM读取操作。以64 KB总预算为例，假设每张表的容量约3$\sim$4 KB，每次读取约0.5$\sim$1.0 pJ（在5 nm工艺下），则一次完整的TAGE-SC-L预测的功耗约为8$\sim$20 pJ。在5 GHz的处理器中，每秒约有$1.5 \times 10^9$次分支预测（假设分支频率为每4条指令一次、每周期退休$\sim$6条指令），分支预测器的总功耗约为12$\sim$30 mW——这占整个处理器核心功耗（约5$\sim$10 W）的0.1%$\sim$0.6%。

降低预测器功耗的常见技术包括：

• 分级预测。使用一个小型的、低功耗的L0预测器（如一个小型的bimodal预测器或小型BTB）提供快速预测。只有当L0预测的置信度低时，才激活完整的TAGE-SC-L预测器。由于大多数分支（$>80\%$）可以被简单的预测器正确预测，这种分级策略可以将预测器的平均功耗降低60%$\sim$80%。

• 选择性表激活。在TAGE中，不一定需要同时读取所有$M$张标记表。可以先读取使用较短历史的表，如果在这些表中找到了高置信度的匹配（计数器绝对值大），则跳过使用较长历史的表。这需要将TAGE的查询流水线化为多个阶段，代价是增加了预测延迟。

• SC和Loop的条件激活。SC和Loop只在少数情况下修改TAGE的预测。可以使用一个简单的过滤器（如TAGE置信度检查）来决定是否激活SC——只有当TAGE的置信度低于阈值时才读取SC的表，从而避免大多数情况下的SC功耗。

性能分析 5 — 分支预测器功耗的量化分析

以一个5 GHz、6-wide超标量处理器的TAGE-SC-L实现为例，详细分析其功耗构成：

组件	SRAM读次数/预测	功耗/预测(pJ)	占比
TAGE（12张标记表）	12	9.6	48%
基础表$T_0$	1	0.3	1.5%
SC（6张表）	6	3.0	15%
循环预测器	1	0.4	2%
SC加法器+比较	—	1.2	6%
标签比较器$\times 12$	—	2.4	12%
优先级选择+控制	—	1.6	8%
CSR更新（24个）	—	1.5	7.5%
总计		$\approx$20	100%

假设预测器每周期查询一次（以取指块为粒度），总功耗为$20 \times 10^{-12} \times 5 \times 10^9 = 0.1$ W $= 100$ mW。在一个5$\sim$10 W的处理器核心中占比1%$\sim$2%。使用分级预测（80%的预测由低功耗L0完成，L0功耗约3 pJ/预测）可以将平均功耗降低到$0.8 \times 3 + 0.2 \times 20 = 6.4$ pJ/预测$\approx 32$ mW，节省约68%。

TAGE-SC-L的抗干扰与鲁棒性

TAGE-SC-L的三个组件在某些极端工作负载下可能相互干扰。一种已知的病理情况是：SC反复错误地翻转TAGE的正确预测，导致TAGE的useful计数器无法积累——因为最终预测（SC翻转后）是错误的，TAGE认为自己的表项“没用”，触发替换。

为了防止这种病理行为，TAGE-SC-L引入了双层校正保护机制：

1. SC的校正只在TAGE的置信度低于阈值$c_{\text{weak}}$时才生效（如式 (15.14)）。

2. 当SC的校正连续多次导致错误预测时，动态阈值$\theta$自动增大，使SC变得更保守。

3. TAGE的useful位更新基于最终预测（含SC校正后）的正确性，而非TAGE自身预测的正确性。这使得当SC翻转TAGE的预测并导致错误时，TAGE的useful位不会被错误地递减。

另一种鲁棒性措施是循环预测器的降级保护。当循环预测器连续2次预测错误时，立即将其置信度重置为0，停止循环预测器的覆盖，直到重新确认循环模式。这防止了循环迭代次数突然变化时循环预测器的持续错误预测。

面积估算

在5 nm工艺下，SRAM的密度约为25$\sim$30 Mbit/cm$^2$（包含外围电路）。一个64 KB的TAGE-SC-L预测器的SRAM面积约为：

$$A_{\text{SRAM}} = \frac{64 \times 1024 \times 8}{25 \times 10^6} \approx 0.021 \text{ mm}^2$$

加上索引哈希逻辑、标签比较器、加法器（SC）、控制逻辑等，总面积约为SRAM面积的1.5$\sim$2倍，即约0.03$\sim$0.04 mm$^2$。在一个典型的高性能核心（约5$\sim$10 mm$^2$ @ 5 nm）中，分支方向预测器仅占总面积的0.3%$\sim$0.8%。这一极小的面积占比表明，分支方向预测器的设计几乎不受面积约束——限制预测精度的主要瓶颈是算法本身，而非硬件资源。

TAGE-SC-L的更新端口设计

TAGE-SC-L的更新操作涉及多个表的同时写入：TAGE需要更新提供者表的计数器和useful位，可能需要在另一张表中分配新表项；SC需要更新其所有计数器表；循环预测器需要更新count/limit字段。这些更新操作可能在同一个周期内同时发生（当分支在执行阶段被解析时）。

如果所有表都使用单端口SRAM，更新写入与预测读取之间存在端口冲突。解决方案包括：

• 写缓冲区（Write Buffer）。将更新请求暂存到一个小型FIFO中，在SRAM端口空闲时（预测读取不需要的周期）执行写入。写缓冲区的深度需要足以容纳突发的更新请求——在分支密集的代码段中，可能在短时间内产生多个更新请求。一个4$\sim$8项的写缓冲区通常足以覆盖峰值更新率。

• 读写分离。在每个时钟周期的上半周期进行读取（预测），下半周期进行写入（更新）。这需要SRAM能够在半个周期内完成访问，限制了可用的SRAM大小。

• 优先级仲裁。当读写冲突时，优先执行读取（预测），延迟写入（更新）。由于预测在关键路径上而更新不是，这种优先级分配是合理的。延迟的更新被写入写缓冲区等待后续处理。

TAGE-SC-L的SystemVerilog实现要点

从RTL实现的角度，TAGE-SC-L有几个值得注意的设计要点：

（1）SRAM vs. 寄存器文件。对于较大的预测表（$>512$项），应使用编译器生成的SRAM宏单元而非触发器阵列。SRAM的面积密度是触发器的$6\times\sim10\times$，功耗也显著更低。但SRAM的读取延迟通常为1个周期，这需要在流水线设计中予以考虑。

（2）CSR的并行更新。所有$2M$个CSR需要在每个周期同步更新。由于CSR的更新逻辑很简单（移位+异或），$2M = 24$个CSR的并行更新在面积和时序上都不是问题。但需要注意的是，CSR的检查点保存（用于推测更新的恢复）需要$24 \times k$位的存储（$k$为CSR宽度），在ROB或检查点栈中占用一定的空间。

（3）SC加法器的实现。SC的加权和计算涉及$K$个有符号计数器的求和。每个计数器通常为6位有符号整数，$K = 6$个计数器的求和结果需要$6 + \lceil\log_2 K\rceil = 9$位。这一加法器树可以在一个阶段内完成，但如果与TAGE查询串联，可能延长关键路径。一种优化是使用进位保留加法器（carry-save adder）来加速SC的求和，将加法器树的延迟从$O(K \cdot \log_2 w)$降低到$O(\log_2 K + \log_2 w)$个gate延迟，其中$w$为计数器位宽。

（4）多端口vs.单端口SRAM。TAGE的每张表在每个周期需要支持1次读取（预测）和最多1次写入（更新）。如果使用单端口SRAM，读和写不能在同一周期进行——需要通过时分复用（如半周期读、半周期写）或添加写缓冲区来解决。在实际设计中，通常使用双端口SRAM（1读1写）或单端口SRAM+写缓冲区。

设计提示

分支预测器的设计是一个典型的算法–架构–电路三层协同优化问题。在算法层面，TAGE-SC-L代表了当前已知的最优方案。在架构层面，流水线级数、并行度和推测更新策略决定了预测延迟和吞吐量。在电路层面，SRAM编译器、定制加法器和时钟门控决定了面积、功耗和最大频率。一个成功的分支预测器设计需要在这三个层面之间进行仔细的权衡。特别是，算法的选择不能脱离实现约束——例如，一个理论上精度最高但需要4个流水线阶段才能完成预测的方案，在实际处理器中的效果可能不如一个精度略低但只需2个阶段的方案，因为前者增加了预测错误的惩罚。

高级方向预测主题

本节讨论几个在前面各节的基础上进一步深化的高级主题，包括TAGE的变体BATAGE、基于神经网络的新型预测器探索、以及分支预测器的预热与自适应机制。

路径历史寄存器

除了分支方向历史（GHR）之外，现代分支预测器还使用路径历史寄存器（Path History Register, PHR）来增强预测能力。PHR记录的不是分支的方向（taken/not-taken），而是最近几条分支指令的PC地址信息。

PHR的动机

GHR只记录分支的方向，丢失了“是哪条分支产生了这个方向”的信息。考虑以下场景：两条不同的分支A和B都在某个时刻被预测为taken，GHR中的对应位都是“1”。但分支A的taken可能意味着进入了一个特定的代码路径，而分支B的taken意味着进入了完全不同的代码路径。如果后续的某条分支C的方向取决于“是通过A的taken路径到达的”还是“通过B的taken路径到达的”，则GHR无法区分——两种情况下GHR中的对应位都是“1”。

PHR通过在每次分支执行时将分支的PC地址（通常取低位若干位，如6$\sim$12位）折叠异或到PHR中，从而保留了“路径”信息。TAGE的索引哈希可以同时使用GHR和PHR来计算，使得来自不同路径的分支即使GHR相同，也能映射到不同的表项。

PHR的更新与恢复

PHR的更新方式类似于GHR：每次分支被预测时，将该分支PC的低位折叠异或到PHR中：

$$\text{PHR}_{\text{new}} = (\text{PHR}_{\text{old}} \ll 1) \oplus \text{PC}[b{-}1:0]$$

其中$b$为PHR中每次混入的PC位数（通常$b = 6\sim 8$）。

PHR也需要推测更新和恢复——与GHR的管理方式相同。PHR的检查点存储与GHR检查点合并管理，每条飞行中的分支需要保存PHR的一个副本。PHR的宽度通常为16$\sim$32位（远小于GHR的128$\sim$1000+位），因此检查点的存储开销较小。

PHR在TAGE-SC-L中的应用

在TAGE-SC-L的实现中，PHR被用于以下两个方面：

1. TAGE索引的增强。部分TAGE标记表（通常是使用中等历史长度的表$T_3\sim T_7$）在索引计算中混入PHR的部分位，使得来自不同执行路径的分支能够被区分。这对于函数调用密集的程序特别有效——同一条分支在不同的调用路径下可能表现出不同的方向模式。

2. SC特征的补充。SC的某些计数器表使用PHR作为索引特征的一部分，增加了SC校正的上下文感知能力。

PHR对整体MPKI的改善约为3%$\sim$5%——虽然不大，但在TAGE-SC-L已经非常高的精度基础上，这是有意义的增量改善。

局部历史预测

TAGE使用全局历史（GHR）来预测分支方向，但某些分支的方向主要取决于其自身的历史模式而非全局上下文。局部历史预测器（Local History Predictor）为每条分支维护独立的历史记录，专门捕获这种“自相关”行为。

局部历史的典型应用

以下代码展示了局部历史有效的典型场景：

for (int i = 0; i < N; i++) {
    if (i % 3 == 0) {   // 方向模式：T, NT, NT, T, NT, NT, ...
        process_special(i);
    }
}

该分支的方向序列是严格的周期性模式“T, NT, NT, T, NT, NT, ...”，周期为3。这种模式与全局上下文无关——不管其他分支怎么执行，这条分支的方向只取决于其自身的历史。一个使用3位局部历史的预测器可以完美地捕获这一模式：当局部历史为“100”（上两次NT, 上一次T）时预测NT，当为“001”（上两次NT的后一个位移入T后）时预测T，依此类推。

相比之下，全局历史预测器需要在GHR中找到与该分支的局部周期性相关的全局模式——如果GHR足够长且包含了该分支的最近3次方向记录，TAGE也能捕获这一模式；但如果两次执行之间有大量其他分支的方向记录混入GHR，TAGE可能需要非常长的历史（远超3位）才能“透过”这些噪声找到有用的局部模式。

局部历史表的组织

局部历史预测器使用一个由分支PC索引的局部历史表（Local History Table, LHT），每项存储该分支最近$k$次执行的方向序列（$k$位）。LHT的典型大小为256$\sim$1024项，$k = 8\sim 16$位。

预测时，先用分支PC索引LHT获取局部历史，然后将局部历史与PC一起用作预测器的索引。在TAGE-SC-L的框架中，局部历史可以被集成为SC的一个额外特征表——以PC $\oplus$ 局部历史为索引的SC计数器表。

局部历史的推测管理

与GHR类似，局部历史在超标量处理器中需要推测更新：每次分支被预测时，将预测的方向移入LHT中对应项的历史。但LHT的推测管理比GHR更复杂——LHT有多个表项（每条分支一个），而GHR只有一个全局寄存器。

对LHT的每个表项都维护完整的检查点显然是不可行的（$1024 \times 16 \times 64 = 1048576$位的检查点存储）。一种实用的方案是使用推测缓冲区（Speculative Buffer）：在飞行中的每条分支指令旁边记录其LHT索引和旧的局部历史值。当分支预测失败时，从推测缓冲区中逆序回放，恢复被覆盖的局部历史值。这类似于ROB-walk恢复，但只涉及LHT表项而非整个RAT。

性能分析 6 — 局部历史在TAGE-SC-L中的贡献

在TAGE-SC-L中加入局部历史特征（作为SC的一个额外表）可以将整体MPKI进一步降低约2%$\sim$4%。这一改善主要来自两类分支：（1）具有固定周期性方向模式的分支（如上述的i % 3 == 0）；（2）在不同的调用实例中表现出不同的方向倾向性的分支（如一个函数内的分支，在某些调用者调用时倾向taken，在另一些调用者调用时倾向not-taken）。

然而，局部历史的收益在TAGE已经使用了足够长的全局历史的情况下是递减的。对于一个使用1000+位全局历史的TAGE，许多局部历史能够捕获的模式已经隐含在长全局历史中——只要TAGE的标记表命中了包含该分支自身历史记录的长历史模式。局部历史在全局历史较短（如只有128位）的TAGE配置下收益更大。

BATAGE：无标签的TAGE变体

TAGE的标签字段占据了每个表项存储的很大比例（通常8$\sim$15位，占表项总宽度的50%$\sim$70%）。BATAGE（Best-offset Anti-aliasing TAGE）是Seznec在2020年提出的TAGE变体，尝试通过消除标签字段来大幅提高存储效率。

BATAGE的核心思想

BATAGE的关键观察是：TAGE中标签的主要作用是防止有害别名（destructive aliasing）——两条不相关的分支映射到同一个表项，相互干扰各自的训练。如果能用其他机制来减轻有害别名的影响，就可以去掉标签，将节省的存储空间用于增加表项数量。

BATAGE采用以下策略来替代标签匹配：

1. 多选择哈希（Multiple-choice Hashing）。每张表使用两个不同的哈希函数，为每条分支计算两个候选索引。预测时同时读取两个索引位置，选择置信度更高的那一个。这种“双选择”机制使得一条分支可以在两个位置中选择别名干扰较小的那一个，降低了有害别名的概率。

2. 置信度感知的替换。BATAGE不使用useful位来决定替换，而是直接比较候选位置的计数器绝对值。绝对值越大，说明该位置被训练得越充分，被替换的优先级越低。

3. 增大表项数量。去掉标签后每项只需要3位（计数器），相比原来的16位（12位标签+3位计数器+1位useful），每项存储减少了81%。在相同的总存储预算下，BATAGE可以拥有5$\sim$6倍于TAGE的表项数量。更多的表项意味着更低的别名概率——即使没有标签过滤，巨大的表项数量也能将别名概率控制在可接受的范围内。

BATAGE的精度评估

在64 KB存储预算下，BATAGE的MPKI约为3.3$\sim$3.5，略高于TAGE的3.58$\sim$3.6，但考虑到BATAGE不使用标签，其存储效率显著更高。在更小的预算（如8$\sim$16 KB）下，BATAGE的优势更加明显——小预算下标签的存储占比更高，去掉标签带来的表项数量增益更大。

BATAGE的主要劣势是需要双倍的SRAM读取带宽（每个表需要同时读取两个位置），这在功耗和面积上有一定的开销。此外，双选择哈希的选择逻辑增加了关键路径上的一个比较器延迟。

设计权衡 4 — TAGE vs. BATAGE的存储效率

以16 KB的总存储预算为例进行比较：

参数	TAGE	BATAGE
每项位宽	16位（12T+3C+1U）	3位（3C）
可用表项总数	$\sim$8192	$\sim$43690
标记表数	7	7
每表项数	$\sim$1024	$\sim$6144
别名概率（每表）	$2^{-12} \approx 0.024\%$	$\sim 1/6144 \approx 0.016\%$
MPKI	$\sim$4.9	$\sim$4.5

可以看到，在小预算下BATAGE通过更多的表项数量弥补了标签的缺失，实现了更低的MPKI。

基于神经网络的分支预测器探索

感知机预测器可以看作是一个单层神经网络。自然的扩展是使用多层神经网络（深度学习模型）来进行分支预测。近年来的学术研究探索了这一方向，但面临严格的硬件实现约束。

多层感知机的理论优势

多层感知机（MLP）通过引入隐藏层和非线性激活函数，可以学习任意复杂的非线性函数，包括XOR等单层感知机无法处理的模式。一个具有一层隐藏层的MLP理论上可以逼近任何连续函数（万能逼近定理）。

然而，将MLP应用于分支预测面临以下挑战：

1. 推理延迟。单层感知机的点积计算已经需要$O(\log n)$级加法器树延迟。多层MLP的推理需要串行计算多层的输出，每层包含矩阵乘法和非线性激活，总延迟为$O(L \cdot \log n)$，其中$L$为层数。即使$L = 2$，延迟也翻倍，这在已经时序紧张的分支预测流水线中是不可接受的。

2. 训练复杂度。MLP的训练使用反向传播算法，需要存储中间激活值、计算梯度、并逐层更新权重。在硬件中实现完整的反向传播需要大量的乘法器和存储，面积和功耗开销远超传统预测器。

3. 收敛速度。深层网络的训练通常需要数千甚至数百万次迭代才能收敛。对于分支预测的在线学习场景，每条分支只提供一次训练样本，远不足以训练一个多层网络。

硬件友好的神经预测器

一些研究尝试设计硬件友好的神经预测器，在保持较低实现复杂度的同时引入有限的非线性能力：

TAGE-Neural Hybrid。将TAGE的查表机制与感知机的加权和机制结合：TAGE的各张表的计数器输出被送入一个加权求和电路（类似SC），而非使用“最长匹配优先”规则。这种混合方案兼具TAGE的标签过滤能力和感知机的加权投票能力，但实现复杂度显著增加。

Binary Neural Network。使用二值化权重（$w_i \in \{-1, +1\}$）替代多位权重，将乘法运算简化为XNOR门操作。二值化神经网络的推理延迟可以与传统感知机相当，但预测精度有所下降。一些研究表明，二值化感知机在SPEC CPU工作负载上的MPKI比标准感知机高约10%$\sim$15%。

Temporal Stream Predictor。一种完全不同的方法是放弃传统的“特征$\to$预测”模型，转而使用序列模型——记录分支方向的时间序列，用模式匹配来预测下一个方向。这类似于数据压缩中的LZ77算法：在历史记录中搜索与当前上下文最长匹配的子序列，然后预测下一个方向等于历史中匹配子序列之后的方向。这种方法在理论上可以捕获任意复杂的非线性模式，但需要大量的存储来保存历史记录，且搜索操作的延迟较高（需要并行比较多个候选模式）。

分支预测的信息论极限

从信息论的角度，分支预测的精度存在一个理论上界。对于一个具有熵率$H$的分支方向序列（$H$以每位的比特数衡量），任何预测器的最优误码率（最小错误预测概率）满足Fano不等式：

$$P_{\text{error}} \geq \frac{H - 1}{\log_2(|\mathcal{Y}| - 1)} = H - 1$$

其中$|\mathcal{Y}| = 2$（taken/not-taken）。对于$H = 0.1$（即分支方向序列的熵率为每位0.1比特，意味着方向高度可预测），理论最小错误率约为$P_{\text{error}} \geq H/2 \approx 5\%$（这是一个非常粗糙的下界）。

更实际的下界估计来自经验分析。对于SPEC CPU工作负载中的“内禀不可预测”分支（如依赖于输入数据的比较结果），即使使用无限的存储和历史长度，其方向也无法被正确预测。这些分支的MPKI贡献约为1.5$\sim$2.5，构成了方向预测精度的硬性下限。

这意味着：在SPEC CPU 2017上，当前最好的预测器（MPKI约2.5$\sim$3.0）距离理论极限（MPKI约1.5$\sim$2.5）已经非常接近——进一步改进算法的空间有限。未来的性能提升更可能来自减少预测失败的惩罚（如更快的恢复机制、更浅的流水线）而非提高预测的精度。

查表近似非线性。使用小型LUT（Look-Up Table）来近似非线性激活函数。例如，将$n$个权重分为若干组，每组内部做线性加权和，组间的结果通过一个6位输入$\to$1位输出的LUT进行非线性变换后再求和。这种方案引入了有限的非线性能力，同时将LUT的延迟控制在1$\sim$2个门延迟以内。

设计提示

截至目前，基于神经网络的分支预测器在学术界取得了一些有趣的结果，但尚未在商业处理器中被采用。其根本原因是：TAGE-SC-L已经将方向预测精度推到了非常接近理论极限的水平（MPKI约2.5$\sim$3.0），剩余的预测错误大多来自内禀不可预测的分支。在这种情况下，增加预测器的模型复杂度（如引入深度学习）的边际收益非常有限，而硬件实现成本却大幅增加。分支预测的未来改进可能更多地来自系统层面的优化（如更大的BTB、更好的预取、编译器协助）而非预测算法本身的突破。

特定领域的预测器优化

值得注意的是，不同应用领域的分支行为特征差异巨大，“最佳”预测器的选择因领域而异：

• 数据库查询引擎。数据库的查询执行器包含大量数据依赖分支（如B+树搜索中的比较分支），这些分支的方向取决于查询键与存储数据的比较结果，本质上不可预测。对于这类工作负载，增加TAGE的存储预算的收益有限；更有效的优化是在查询编译层面将分支密集的操作（如过滤器谓词评估）转换为SIMD无分支实现。

• 加密算法。安全的密码学实现要求执行路径不依赖于密钥数据（常数时间执行），因此所有数据依赖分支都被消除或转换为无分支代码。在这类程序中，剩余的分支主要是控制流分支（循环、函数调用），预测精度通常很高。

• 机器学习推理。深度学习推理框架（如TensorFlow Lite、ONNX Runtime）的核心循环通常是高度规则的矩阵运算，分支行为简单且可预测。分支预测对这类工作负载的影响很小——性能瓶颈通常在于内存带宽和计算吞吐量。

• Web浏览器JavaScript引擎。JIT编译的JavaScript代码包含大量的类型检查分支（如“is this value an integer?”）和虚函数调用。这些分支的行为随用户交互和网页内容而变化，预测难度较高。现代浏览器引擎通过内联缓存和类型特化来减少这些分支的影响。

预测器的冷启动与预热

分支预测器在以下场景中需要从空状态开始工作，面临冷启动问题：

1. 程序启动。程序开始执行时，所有预测表为空，每条分支在首次执行时都会预测错误。

2. 上下文切换。当操作系统将CPU从一个进程切换到另一个进程时，新进程的分支模式与旧进程可能完全不同。如果预测器状态没有被清空，旧进程训练的数据可能干扰新进程的预测；如果被清空，则面临冷启动。

3. 相变（Phase Change）。同一个程序在不同执行阶段可能表现出截然不同的分支行为（如从初始化阶段进入主循环，或从一个算法阶段切换到另一个算法阶段）。

冷启动对MPKI的影响

TAGE预测器的冷启动恢复速度取决于各张表的训练需求。基础表$T_0$的2位计数器只需2$\sim$3次训练即可收敛，恢复速度最快。使用短历史的标记表$T_1$、$T_2$的表项也能较快训练充分（需要数十次匹配的分支执行）。但使用长历史的标记表（如$T_{10}$、$T_{11}$使用数百位历史）需要更长时间才能积累足够的训练数据——长历史意味着更多的可能历史模式，每种模式的出现频率更低，训练收敛更慢。

在典型的SPEC CPU工作负载上，TAGE预测器的“热身期”（warm-up period）——即从空状态到达稳态MPKI所需的指令数——约为5000万$\sim$1亿条指令。在这段热身期中，MPKI逐渐从初始的约8$\sim$12降低到稳态的约3$\sim$4。热身期的前1000万条指令MPKI下降最快（短历史表迅速收敛），之后的改善速度逐渐放缓（长历史表慢慢积累数据）。

上下文切换时的预测器管理

处理器在上下文切换时对分支预测器状态的管理有三种策略：

不清空。预测器状态在上下文切换时保持不变。新进程的分支查询可能命中旧进程训练的表项（别名），导致短暂的精度下降。但由于TAGE使用了部分标签匹配，两个不同进程的分支在同一个表项上发生标签碰撞的概率较低（$\approx 2^{-t}$，$t$为标签宽度）。对于大多数表项，新进程的查询会标签不匹配而回退到基础表，基础表虽然精度较低但不会因为别名而给出“反向”的错误预测。这种策略的优势是零切换开销，劣势是可能存在安全隐患（跨进程的预测器侧信道）。

全部清空。上下文切换时将所有预测表清零。这种策略保证了进程间的完全隔离，但代价是每次切换后的冷启动惩罚。对于切换频率为每毫秒一次的典型调度器，冷启动惩罚在热身期的第一毫秒内可能导致10%$\sim$20%的额外IPC损失。

分区隔离。使用ASID（Address Space ID）来标记预测器表项，使不同进程的数据在预测表中共存但互不干扰。查询时只匹配ASID相同的表项。这种策略在不清空表的同时保证了隔离性，但增加了每项的存储开销（需要额外的ASID字段）和比较逻辑。对于TAGE来说，在标签中混入ASID位是一种轻量级的实现方式——将标签的若干位替换为ASID位，在不增加总存储的情况下实现近似隔离。

自适应历史长度

一种应对相变和冷启动的高级技术是自适应历史长度（Adaptive History Length）。其核心思想是在运行时动态调整TAGE使用的历史长度范围。当检测到程序进入了一个不需要长历史的稳定阶段（如紧密循环）时，缩短最长历史的长度，将节省的存储空间重新分配给短历史表以增加其容量；当检测到程序进入复杂的控制流阶段时，恢复长历史表。

自适应历史长度可以通过监控各张表的useful计数器分布来实现：如果长历史表中的useful计数器大多为0（表示这些表项很少提供有用的预测），说明当前工作负载不需要长历史，可以关闭这些表以节省功耗。

冷启动加速技术

为了缩短分支预测器的冷启动恢复时间，可以采用以下技术：

静态预测辅助。在预测器未充分训练时，使用编译器提供的静态预测提示（如__builtin_expect）来辅助方向预测。RISC-V指令集虽然没有专门的分支提示位，但可以通过指令编码中的特定模式（如分支偏移量的符号）来推断静态预测：向后跳转的分支预测为taken（循环回边），向前跳转的分支预测为not-taken（前向条件分支通常在不满足条件时跳过代码块）。

这种静态预测在冷启动阶段可以将MPKI从完全随机预测的50%降低到约30%$\sim$35%——虽然远不及训练充分的TAGE（约3%$\sim$5%），但在热身期的最初几千条指令中可以避免大量的流水线刷新。

快速表填充。一种加速冷启动的方法是在程序开始执行时对预测表进行批量预填充。操作系统可以在上下文切换时将被换出进程的预测器状态保存到内存中（类似于保存浮点寄存器状态），并在该进程被换回时恢复。这种“预测器上下文保存/恢复”的代价取决于预测器状态的大小——对于一个64 KB的TAGE-SC-L，保存和恢复需要传输64 KB的数据，在现代处理器上大约需要$64\text{K} / 128\text{B/cycle} \approx 500$个周期——对于调度周期为数百万周期的操作系统来说，这一开销是可接受的。

然而，预测器上下文保存/恢复在实际处理器中很少被实现，原因包括：（1）需要在ISA层面定义新的指令来访问预测器状态，增加了ISA复杂度；（2）暴露预测器状态可能引入安全隐患（攻击者可以观察或修改预测器状态）；（3）对于长时间运行的工作负载，冷启动的影响已经很小，不值得增加这种复杂机制。

影子训练（Shadow Training）。在预测器的主表之外维护一个小型的影子预测器（通常为简单的bimodal或短GHR预测器），影子预测器训练速度快，在冷启动阶段提供比未训练的主预测器更好的预测。当主预测器的训练逐渐成熟（可以通过监控主预测器的useful计数器分布来判断），逐步将预测权从影子预测器切换到主预测器。

相变检测与自适应重训练

程序的相变（phase change）——即分支行为特征发生突变——会导致预测器的训练状态突然变得“过时”。检测相变并快速适应是保持高预测精度的关键。

一种简单的相变检测方法是监控短期MPKI：使用一个滑动窗口（如最近1000条分支）计算当前的MPKI，当短期MPKI突然上升（超过稳态MPKI的2$\sim$3倍）时，认为发生了相变。

检测到相变后的应对策略包括：

1. 加速aging。将所有TAGE标记表的useful计数器快速重置为0，使旧的表项可以被新的分支模式替换。这本质上是让预测器“忘记”旧的训练数据，从近乎空白的状态重新学习。代价是在重训练期间MPKI会短暂上升。

2. 选择性失效。只重置那些在相变后表现不佳的表项（useful计数器为0且预测错误的），保留仍然有效的表项。这种方案恢复更快，但实现更复杂。

3. 双缓冲表。维护两套TAGE表，一套用于当前的预测，另一套在后台静默训练。当检测到相变时，切换到后台表（如果后台表的表现更好）。这种方案的面积开销是两倍的TAGE存储，只在极少数高端处理器中可行。

硬件描述 4 — 分支预测器的运行时监控

在高性能处理器中，分支预测器通常配备运行时性能监控计数器（PMC），用于调试和性能分析。典型的监控指标包括：

计数器	含义
BR_INST_RETIRED	已退休的分支指令总数
BR_MISP_RETIRED	已退休的预测错误分支数
BR_TAKEN_RETIRED	已退休的taken分支数
BR_IND_MISP	间接跳转预测错误数
BR_RET_MISP	函数返回预测错误数
TAGE_OVERRIDE	TAGE覆盖基础表预测的次数
SC_CORRECTION	SC校正TAGE预测的次数
LOOP_PRED_ACTIVE	循环预测器提供预测的次数

这些计数器使得性能工程师可以诊断分支预测的瓶颈所在——例如，如果BR_IND_MISP占BR_MISP_RETIRED的大部分，说明间接跳转预测是瓶颈，应该增大ITTAGE的容量或优化软件中的虚函数调用模式。

性能分析 7 — 分支预测器冷启动的实际影响

在数据中心工作负载中，冷启动问题比桌面/HPC工作负载更为严重。原因包括：

• 频繁的上下文切换。微服务架构中的容器和虚拟机频繁调度，每次切换都可能导致预测器状态失效。

• 巨大的代码足迹。数据中心应用（如数据库引擎、搜索引擎）的代码足迹可达数十MB，即使在稳态下也可能有大量的“冷”分支指令无法被有限的预测表覆盖。

• 多样化的工作负载。同一台服务器上运行的多个不同应用具有截然不同的分支行为特征，预测器需要同时适应多种模式。

Google的数据中心性能分析团队在2019年报告中指出，分支预测失败在其数据中心工作负载中贡献了约10%$\sim$15%的CPI损失，其中约20%$\sim$30%的预测失败来自冷启动效应。这表明，改善预测器的冷启动性能在数据中心场景下具有显著的实际价值。

分支预测与编译器协同

分支预测精度不仅取决于硬件预测器的设计，还受编译器生成代码的影响。编译器可以通过代码变换来帮助硬件预测器提高精度，或者直接减少需要预测的分支数量。

If-conversion与谓词执行

If-conversion将条件分支替换为条件选择指令（如RISC-V的条件移动或ARM的谓词执行），从而完全消除分支指令。例如：

// 原始代码（产生一条条件分支）
if (a > b) x = c; else x = d;

// if-conversion后（无分支）
t = (a > b);    // 比较，设置条件
x = t ? c : d;  // 条件选择，无分支

在RISC-V中，条件选择可以用slt + and/or指令序列或使用Zicond扩展的条件零指令来实现。If-conversion消除了分支指令，从而消除了预测失败的可能性——但代价是无条件地执行了两个分支路径中的所有指令（增加了指令数量和执行带宽需求）。

If-conversion的适用场景是：分支的两个路径都很短（如单条赋值语句），且分支的预测精度较低。当预测精度已经很高时（如>95%），if-conversion反而可能降低性能——因为5%的预测失败惩罚可能小于100%执行冗余指令的开销。

代码布局优化

编译器可以通过调整代码布局来改善分支预测的效果：

• Hot/Cold分离。将频繁执行的代码（hot path）和不频繁执行的代码（cold path）分开放置，确保hot path中的分支大多被预测为not-taken（顺序执行）。这增加了not-taken分支的比例，减少了预测器的工作量。

• 函数内联。内联函数调用消除了call/ret指令对，减少了RAS的使用和间接跳转的数量。但过度内联会增大代码体积，导致I-Cache缺失率上升——这是一个经典的权衡。

• 循环展开。展开循环体减少了循环分支的执行频率（每$N$次迭代只执行1次循环分支，而非每次迭代1次）。对于预测精度已经很高的循环分支，展开的主要收益不在于减少预测错误，而在于减少分支指令本身的执行开销和提供更多的指令级并行性。

Profile-Guided Optimization（PGO）是编译器利用运行时profiling数据来指导代码布局优化的标准方法。PGO收集每条分支的实际taken/not-taken比例，然后：

1. 将频繁taken的分支反转为not-taken方向（通过交换then/else分支的代码位置），使大多数分支在运行时为not-taken。

2. 将冷代码（如错误处理路径）移到函数末尾或单独的段中。

3. 为编译器提供分支概率信息，指导if-conversion和循环展开的决策。

Google的AutoFDO工具可以从生产环境中收集profiling数据，自动指导GCC/LLVM进行PGO优化，在其数据中心工作负载上带来了约5%$\sim$15%的整体性能提升，其中约1/3来自分支预测的间接改善（更好的代码布局使BTB命中率更高，分支方向更倾向not-taken）。

ISA层面的分支预测支持

一些ISA在指令编码中提供了专门的分支预测提示机制：

• PowerPC的条件分支指令中包含一个2位的“branch prediction hint”字段，编译器可以显式地告诉处理器该分支更可能taken还是not-taken。

• Itanium（IA-64）的EPIC架构广泛使用谓词执行，将大多数条件分支转换为谓词指令，从根本上减少了对分支预测的依赖。但IA-64的指令集复杂度和编译器困难导致了其商业失败。

• RISC-V目前没有标准的分支预测提示机制，但社区正在讨论一个“Code Size Reduction”扩展中的静态分支提示位。此外，RISC-V的Zicond扩展提供了条件零移动指令，使编译器可以更方便地进行if-conversion。

• x86的分支提示前缀（0x2E和0x3E）在早期Pentium 4中被使用，但在后续的Intel处理器中被忽略——因为硬件动态预测器的精度已经超过了编译器静态预测的精度，ISA层面的提示不再有价值。

这些ISA特性的兴衰历史揭示了一个重要的设计原则：当硬件动态预测器的精度足够高时，ISA层面的静态预测提示变得无关紧要。当前TAGE-SC-L达到的98%+方向预测精度使得任何静态提示都无法提供有意义的改善。ISA设计应该避免为分支预测提示分配指令编码空间——这些空间可以用于更有价值的功能。

本章小结

本章系统地介绍了分支方向预测的高级方法。TAGE预测器通过几何级数增长的多历史长度表覆盖了从短程到长程的分支相关性，其“最长匹配优先”策略继承了PPM压缩算法的理论最优性。统计校正器（SC）通过学习TAGE的系统性错误模式，以较小的存储开销实现了10%$\sim$15%的额外MPKI改善。循环预测器（Loop Predictor）专门针对固定迭代次数的循环分支，通过直接计数来消除循环退出时的预测错误。感知机预测器从机器学习角度出发，以线性分类器的形式实现分支预测，在存储效率上具有独特优势但受限于线性不可分问题。TAGE-SC-L将这些组件有机融合，在CBP竞赛中取得了最高的方向预测精度。

从实现角度看，高级方向预测器的关键挑战包括：TAGE的流水线化时序设计、CSR的增量更新与检查点恢复、SC与TAGE的时序串联、以及推测更新的管理与恢复机制。这些工程细节决定了预测算法在真实处理器中的有效性能。

表表 15.9总结了本章讨论的各种方向预测技术及其核心特征。

预测器	核心机制	优势	劣势	典型应用
TAGE	几何级数多历史最长匹配优先	高精度自适应历史长度	标签开销大实现复杂	Intel, ARM
SC	多特征加权和校正TAGE错误	边际改善显著存储开销小	串联延迟需与TAGE配合	TAGE-SC组合
循环预测器	迭代计数精确退出预测	极高精度极低存储	仅限固定迭代循环	TAGE-SC-L
感知机	线性加权和在线学习	存储效率高长历史能力	点积延迟线性不可分	AMD Zen
HashedPerceptron	多表共享权重哈希索引	别名容忍灵活特征	无标签过滤训练慢	AMD Zen 2+
MP Perceptron	多视角特征加权和	最灵活接近TAGE精度	大量特征表功耗高	学术研究
BATAGE	无标签TAGE双选择哈希	存储效率极高小预算优势	双倍读带宽别名风险	学术研究

分支方向预测高级方法总结

从处理器设计的全局视角来看，分支方向预测器是前端子系统中对IPC影响最大的单个组件。在一个典型的6-wide超标量处理器中，方向预测精度每提高1个百分点（如从96%到97%），IPC可以提升约2%$\sim$4%——这一敏感性使得分支预测器的优化在处理器设计中具有极高的投资回报率。然而，预测精度的提升已经进入了深度收益递减区域，未来的性能改善越来越依赖于方向预测器与目标预测器（BTB）、取指单元、执行管线之间的系统级协同优化。

本章聚焦于“分支往哪个方向跳”的方向预测问题。但完整的分支预测还必须回答“分支跳到哪里”——这就是目标地址预测，将在第 16.0 章中详细讨论。TAGE的设计方法论（几何级数历史长度、标签匹配、最长匹配优先）将在第 16.0 章中被扩展到间接跳转目标预测（ITTAGE），展示了这一架构的强大通用性。感知机预测器中的加法链延迟问题也会在目标预测的流水线设计中以不同的形式再次出现。

回调线索。本章的感知机加法器树设计与第 29.0 章中讨论的Wallace tree/Dadda tree加法器技术直接关联——两者本质上是同一类多操作数规约问题。TAGE的折叠历史哈希（CSR）在第 14.0 章的基础预测器中已经初步出现，本章给出了完整的增量更新算法。TAGE-SC-L的系统集成——如何将TAGE、SC、循环预测器和感知机预测器整合为一个统一的预测流水线——将在第 17.0 章中从超标量前端的角度完整展开。