CPU分支预测

本笔记基于有关计算机体系结构与分支预测的最前沿讲座内容整理而成，旨在全面解析分支预测的演进、原理以及各种经典与现代预测器的设计。

1. 预测的本质与哲学背景

在深入探讨硬件级别的分支预测之前，理解“预测”这一概念的本质具有启发意义。正如物理学家尼尔斯·玻尔（Niels Bohr）所言：“预测是非常困难的，特别是关于未来的预测。”

预测不仅在计算机科学中至关重要，它似乎也是大脑工作和人类感知现实的基本方式。现代认知科学的主流观点认为，大脑并不是被动地接收信息，而是积极地生成关于世界的预测。当现实与这些预测不符时，大脑会不断对预测进行更新。这种理论被称为“预测处理”（Predictive processing）或“预测编码框架”（Predictive coding framework），主要由卡尔·弗里斯顿（Karl Friston）和安迪·克拉克（Andy Clark）等学者提出。在计算机硬件中，分支预测（Branch Prediction） 正是这种预测工作机制在极度狭窄且具体领域内的直接体现。

2. 相关预测器（Correlated / Two-level Predictor）

在程序执行中，分支指令的结果往往不是孤立的。相关预测器（也称为两级预测器）利用了分支结果之间存在相关性的这一观察事实。该设计为每个程序计数器（PC）维护独立的预测和相应的分支历史。

预测过程分为两个步骤：

1. 第一级（Level 1）：从分支指令的 PC 中提取若干位作为索引，查找第一级表，该表包含了该分支的历史记录，称为分支历史表（BHT, Branch History Table）。
2. 第二级（Level 2）：利用第一步获得的分支历史作为索引，查找模式历史表（PHT, Pattern History Table），从而得出最终的跳转（Taken, T）或不跳转（Not-Taken, NT）预测。

这种两级自适应训练分支预测机制奠定了现代分支预测的基础。

3. 全局分支预测（Global Branch Prediction）

此前的设计多使用分支自身的历史来进行预测，然而程序代码中的不同分支结果通常也具有极强的相关性。例如，如果两个条件语句存在逻辑上的关联（如 if (aa==2) 与 if (bb==2) 之后的 if (aa != bb)），前序分支的走向会直接影响后续分支的结果。

全局预测器的实现方式如下：

• 采用一个全局的分支历史寄存器（Global BHR, Branch History Register）。
• 将所有分支的执行结果（T 或 NT）逐一移位存入该寄存器中。
• 在进行下一次预测之前，需要推测性地（Speculatively）更新 BHR。
• 如果模式历史表（PHT）也被推测性地更新，一旦发现预测错误，系统必须能够撤销并修复这些错误的更新。

4. 相关预测器的设计空间与分类法

设计高效的相关预测器需要权衡多个关键因素：

设计选择 I：使用全局 BHR 还是每 PC 独立的（局部）BHR？

两者能够捕捉不同类型的模式。通常而言，全局 BHR 的效果更好，因为它不仅能捕捉全局的关联，还能在紧凑的循环中捕捉到局部分支的模式。

设计选择 II：历史记录位数（BHR 大小）应为多少？

在资源无限的假设下，BHR 越长越好。但在现实中，BHR 变长会导致 BHT 的利用率急剧下降：

• 许多历史模式可能在程序运行中永远不会出现。
• 许多分支的走向与历史记录完全无关（Don't care）。
• 经验法则：BHR 的长度应小于 log2(BHT 大小)。
• 此外，过长的 BHR 会导致预测器需要更长的时间来进行训练。典型的长度设定为 8 到 12 位。

设计选择 III：是否需要独立的每 PC 模式表？

相同历史模式下，不同的分支可能需要截然不同的预测。但是，为每个分支提供独立的 PHT 存储成本极其高昂，且实际上只有少数模式真正起作用。

分类与命名（Taxonomy and Nomenclature）

业界通常采用 {G,P}A{g,p,s} 的缩写形式来对分支预测器进行分类：

• 第一位表示 BHR 结构：G（Global，全局）或 P（Per-address，按地址）。
• 第二位为 A：代表 Adaptive（自适应）。
• 第三位表示 PHT 结构：g（global，全局）、p（per-address，按地址）或 s（set，多组映射）。

常见的组合形式包括：

• GAg：采用全局 BHR，并映射到全局 PHT。
• PAg：每个 PC 拥有独立的 BHR，但映射到同一个全局 PHT。
• PAp：每个 PC 拥有独立的 BHR，并且映射到各自独立的 PHT。
• 其他变体还包括 GAs, PAs 和 PSg（静态）等。

5. GShare 预测器

GShare 是一种廉价且快速的实现方式，能够在全局分支历史与每地址模式之间取得平衡。其核心在于使用按位异或（XOR）操作将全局 BHR 和分支的 PC 结合起来，以此作为查找 PHT 的索引。

为什么使用 XOR？

1. 非线性（Non-Linearity）：输出不再是输入位的简单线性组合。
2. 雪崩效应（Avalanche Effect）：输入的微小改变会导致输出发生显著的改变。
3. 性能提升：消除了对 Per-PC 分支历史寄存器的二次查找需求，速度更快。
4. 空间利用：有效地将索引分散在整个 PHT 中，减少了哈希碰撞，极大地提高了可用存储的利用率。

6. 混合预测器（Hybrid Predictor）

混合预测器旨在将多种不同预测器的优势结合起来。其基本思想是：

• 使用一个简单的二态分支历史表（BHT）来预测与历史无关的分支。
• 使用相关预测器（例如 GShare）来专门预测那些高度依赖历史的分支。
• 引入一个元预测器（Meta predictor / Chooser），它负责决定当前分支应当听取哪一个预测器的结果。

在运行过程中，分支默认先在简单的 BHT 中进行预测；一旦其预测错误率超过一定阈值，就会切换至更复杂的预测器中。研究表明，在硬件预算有限（例如总大小一致）的情况下，混合预测器（如 bimodal / gshare）的表现显著优于单一预测器。当容量增加到 2KB 甚至更大时，其准确率可以逼近 98.1%。

7. 现代与最先进的分支预测器

为进一步减少预测器中的条目冲突并提升准确率，业界提出了多种演进型设计：

Bi-mode 预测器

• 核心机制是将 PHT 划分为 T（跳转）和 NT（不跳转）两个相等的半区，并通过一个选择器来决定使用哪一边的结果。
• 这种设计的目的是减少负面干扰（Negative interference）：PHT0 中的多数条目通常倾向于 NT，而 PHT1 中的条目倾向于 T。
• 该架构曾被成功应用于 ARM Cortex-A15 处理器中。

Gskewed 预测器

• 使用多个不同的 PHT 库（Banks），且每个库使用不同的哈希函数进行索引。
• 其理论基础是：两个发生冲突的分支对，极不可能在采用不同哈希函数的多个 PHT 库中同时发生冲突。
• 最终预测结果由多个库的输出进行“多数投票（Majority vote）”来决定。此设计被应用于 Alpha EV8 处理器中。

YAGS 预测器

• 基于 Bi-mode 预测器进行改进。
• 在 YAGS 设计中，T 和 NT 的 PHT 表不再保存所有信息，而是仅缓存异常情况（Exceptions），这极大降低了对存储空间的需求并进一步减缓了别名冲突问题。

TAGE 预测器（Tagged Geometric History Length）

在 2003 年左右，基于 GShare 改进的 2bcgskew 曾是当时的行业顶尖设计，但在某些工作负载下，它仍落后于受神经网络启发的预测器。为解决此问题，TAGE 预测器应运而生，并成为了当今性能最好的分支预测器架构之一。

• 核心理念：仅依赖全局历史记录，但同时维护多个带有标签（Tagged） 的表，这些表对应着不同长度的全局历史。
• 几何级数长度：不同的历史长度呈现几何级数递增关系，例如：0, 2, 4, 8, 16, 32, 64, 128, 256, ..., 2048 位。
• 匹配机制：在预测时，系统会查找所有历史表。能够提供最长匹配历史记录的表将输出最终的预测结果，同时该结果也会受到分支置信度的约束。（举例而言，如果表 1 的标签匹配成功，表 2 未命中，表 3 标签也命中，那么提供预测结果的将是代表更长历史的表 3）。