实验原理

  现代CPU通常使用超标量的深度流水线来提高性能，而超标量和深度流水线通常需要分支预测技术来加以配合。在多发射的深度流水线架构中，分支预测的准确率直接影响流水线效率、取指带宽利用率等性能指标。例如，对于5发射的10级流水线，若分支预测的准确率为90%，则取指带宽将浪费47%；若分支预测的准确率提高到96%，则带宽的浪费可降低到26%。

  按照分支预测的工作方式，可将分支预测方法分为静态和动态两种。静态分支预测根据指令的操作码和寻址方式进行预测，而动态分支预测则是根据指令执行时的分支行为历史进行预测。

1. 静态分支预测

  最简单的静态分支预测方法是预测分支指令总是跳转，或预测总是不跳转。显然，使用这种方法对不同的程序进行分支预测时，预测准确率会有很大差异。一种改进的预测方法是若分支指令是往回跳的就预测跳转，否则预测不跳转，这种方法对单循环的预测效果较好。

  静态分支预测的优点是实现简单、硬件开销较小、预测速度较快，但预测准确度相对较低，不能满足通用处理器对性能日益增长的需求。

2. 动态分支预测

  动态分支预测根据分支指令的过去表现来预测其将来的行为。如果分支行为发生变化，那么分支预测的结果也相应地发生改变。因此，动态分支预测与静态分支预测相比具有更好的预测准确率和适应性。

  这里介绍常用的几种动态分支预测方法。

2.1 基于BHT的分支预测

  基于BHT（Branch History Table）的分支预测方法使用分支历史表来记录分支指令的历史行为。BHT的基础结构如图3-1所示。

图3-1 基础BHT的结构

  其中，Tag字段类似于Cache的Tag，是指令地址的一部分；分支历史由若干个2bit饱和计数器组成。预测时，取分支指令的地址去查BHT的Tag字段，然后根据BHT当前行的分支历史，对分支的跳转方向进行预测。

  如果BHT只记录各分支指令最近1次的分支历史，则只需使用1bit的饱和计数器。理论上，可使用任意位宽的饱和计数器来记录分支历史。有研究表明，2bit饱和计数器的预测性能与更高位宽的预测性能差不多。因此在实践中，通常使用2bit饱和计数器。

  基于2bit饱和计数器进行分支预测的原理如图3-2所示。

图3-2 基于2bit饱和计数器的分支预测

想一想

  按照图3-2所示的编码规律，当饱和计数器是3bit时应该如何预测？

  完整的分支预测过程包含预测和更新2个步骤。预测时，用分支指令的地址查BHT，获得相应的饱和计数器值。若饱和计数器的最高位为1，预测分支跳转，否则预测分支不跳转。当分支指令的实际跳转方向被确定时，不管预测是否正确，都根据图3-2对BHT中的饱和计数器进行更新，从而达到动态调整分支预测结果的目的。

  上述方法只能预测分支跳转的方向，不能预测分支目标地址。为此，可在图3-1所示的BHT中增加有效位和分支目标地址2个字段——有效位字段用于表示当前行的记录是否有效，而分支目标地址字段则用于记录分支指令的历史分支目标地址。此时，BHT的结构如图3-3所示。

图3-3 改进的BHT结构

  预测时，取分支指令的地址去查BHT，查得当前行可能无效，也可能有效。如果当前行无效，且分支指令不跳转，则不进行更新操作；如果当前行无效，但分支指令跳转，则将当前行标记为有效，同时复位饱和计数器，并将分支指令的目标地址更新到BHT中。如果当前行有效，则用BHT记录的分支目标地址来预测分支指令的分支目标地址，此时若预测成功，则按照图3-2对饱和计数器进行更新；若预测失败，则将当前行标记为无效。

2.2 基于全局历史的分支预测

  基于BHT的分支预测方法忽视了分支指令之间的关联性。为此，基于全局历史的分支预测方法在BHT的基础上增加了GHR（Global History Register，全局历史寄存器）来将所有分支指令关联起来。

  基于全局历史的分支预测方法使用一个k比特的GHR来记录所有最近k条分支指令的历史跳转方向，并使用PHT（Pattern History Table，模式历史表）来记录各分支指令的分支历史。其中，PHT的结构类似于BHT。

  预测时，首先将分支指令的地址和GHR进行hash运算，再用得到的hash值来查PHT，然后根据PHT当前行的分支历史和分支目标地址，对该分支指令的分支跳转方向和分支目标地址进行预测，如图3-4所示。

图3-4 基于全局历史的分支预测

  当分支指令的实际跳转行为被确定时，GHR通过移位的方式进行更新——若指令跳转，则$GHR = (GHR << 1) | 1$，否则$GHR = (GHR << 1) | 0$。

2.3 基于局部历史的分支预测

  基于全局历史的分支预测方法将所有分支指令都关联到一起。然而事实上，并非所有的分支指令都具有关联性。为此，基于局部历史的分支预测方法使用LHT（Local History Table，局部历史表）来代替全局历史预测中的GHR。

  LHT一般具有64条记录，每条记录均包含Tag和局部转移历史2个字段。其中，Tag字段是分支指令地址的一部分，局部转移历史字段则是k比特的移位寄存器，其作用等同于GHR。

  预测时，首先用分支指令的地址查LHT，得到分支指令的局部转移历史LHT[i]；然后将分支指令的地址和LHT[i]进行hash运算，再用得到的hash值来查PHT；最后根据PHT当前行的分支历史和分支目标地址，对该分支指令的分支跳转方向和分支目标地址进行预测，如图3-5所示。

图3-5 基于局部历史的分支预测

  当分支指令的实际跳转行为被确定时，LHT[i]和GHR一样，也通过移位的方式进行更新——若指令跳转，则$LHT[i] = (LHT[i] << 1) | 1$，否则$LHT[i] = (LHT[i] << 1) | 0$。

2.4 锦标赛分支预测

  锦标赛分支预测（又称混合分支预测或组合分支预测）是一种博采众长的分支预测方法，其基本原理是将两个或以上的分支预测方法进行结合，充分发挥各预测方法的优势，以进一步提高分支预测的准确度，如图3-6所示。

图3-6 锦标赛分支预测原理

  下面仅对内部含有2个子预测器的锦标赛预测方法进行讨论。

  选择逻辑有2种实现方法：基于全局选择历史的选择方法和基于局部选择历史的选择方法。

• 基于全局选择历史的选择方法

  基于全局选择历史的选择方法使用一个2bit的GSHR（Global Selection History Register，全局选择历史寄存器）来记录子预测器预测结果的历史选择情况。

  预测时，若GSHR的最高位为0，则输出子预测器1的预测结果；否则输出子预测器2的预测结果。当分支指令的实际跳转行为被确定时，需要同时对子预测器和GSHR进行更新。对于子预测器，根据分支指令的实际跳转行为和锦标赛预测结果等信息，使用子预测器自身的更新策略进行更新。对于GSHR，按如图3-7所示的规则更新：若只有子预测器1预测正确，则对GSHR进行“减1”操作；若只有子预测器2预测正确，则对GSHR进行“加1”操作；其余情况下不更新GSHR。

图3-7 GSHR的更新规则

• 基于局部选择历史的选择方法

  基于局部选择历史的选择方法使用LSHT（Local Selection History Table，局部选择历史表）来记录子预测器预测结果的历史选择情况。

  LSHT一般具有4096条记录，每条记录均包含Tag和局部选择历史2个字段。其中，Tag字段是分支指令地址的一部分，局部选择历史字段则是2bit的饱和技术器，其作用等同于GSHR。

  预测时，先取分支指令的地址查LSHT，得到相应的选择历史LSHT[i]。若LSHT[i]的最高位为0，则输出子预测器1的预测结果；否则输出子预测器2的预测结果。当分支指令的实际跳转行为被确定时，需要同时对子预测器和LSHT[i]进行更新。对于子预测器，根据分支指令的实际跳转行为和锦标赛预测结果等信息，使用子预测器自身的更新策略进行更新。对于LSHT[i]，按照图3-7所示的规则进行更新。

2.5 TAGE分支预测

  为了获得更高的预测准确率和更稳定的预测效果，现代处理器通常将多个基本预测器组合起来，形成复合预测器。上一小节所述的锦标赛预测器就是一种简单的复合预测器。本小节将介绍一种更先进的复合预测器 —— TAGE (partially TAgged GEometric history length branch predictor)。

  TAGE是由Andre Seznec和Pierre Michaud于2006年发表的分支预测器。自发表后，TAGE及其变体长期占据了Championship Branch Prediction的榜首位置。时至今日，TAGE仍被当代的典型处理器架构所使用，如RISC-V的BOOM（Berkeley Out-of-Order Machine）、AMD Zen2架构等。

2.5.1 TAGE基本结构

  结合分支历史进行预测，其目的是利用分支的局部性来提高分支预测的性能。不管是全局历史预测方法，还是局部历史预测方法，预测器都使用固定长度的移位寄存器来存储最近的分支历史。一个很合理的猜想是，不同程序的分支局部性不同。因此，分支预测器如果采用固定长度的历史寄存器，则将无法获得稳定的预测效果。TAGE是将若干个GHR位宽呈几何倍数关系增长的全局历史预测器结合起来做预测的复合预测器，其基本结构形如图3-8所示。

图3-8 TAGE预测器结构图

  TAGE的子预测器数量、各子预测器的GHR位宽、PHT表大小等参数均可配置。图3-8所示的TAGE预测器 示例 含有5个子预测器，分别标记为$T0$ ~ $T4$。其中，$T0$是一个按地址索引的饱和计数器表（即BHT预测器），用于提供基础的预测结果；$T1$ ~ $T4$则为全局历史预测器，其GHR的长度分别为$L(1)$ ~ $L(4)$。$L(1)$ ~ $L(4)$的位宽满足$L(i) = \alpha ^ {i-1} \cdot L(1)$，$1 \leq i \leq 4$。

小小扩展

  关于$L(1)$ ~ $L(4)$的关系，TAGE论文指出"the exact formula of the series is not important, but the general form of the series is important"，即关键在于让$L(1)$ ~ $L(4)$保持相对的渐变关系，从而使得预测器对不同大小的分支局部具有适应性，至于$L(1)$ ~ $L(4)$之间具体满足什么样的关系，则是相对次要的。

  在图3-8中，子预测器$T1$ ~ $T4$的PHT表具有相同的entry数，且每条entry均包含$pred$、$tag$和$u$三个字段 —— $pred$是用于产生预测结果的饱和计数器；$tag$是指令地址与$GHR_i$经过hash函数后，再截断至特定位宽的值；$u$是"$usefulness$"的简写，表示entry的有用程度。

补充说明

  在TAGE论文中，$T0$的饱和计数器位宽取2bit，其他子预测器的$pred$字段取3bit，$usefulness$字段取2bit。

2.5.2 TAGE预测机制

  预测时，将指令地址同时送往子预测器$T0$ ~ $T4$。$T0$提供基础预测结果；$T1$ ~ $T4$则各自将指令地址与$GHR_1$ ~ $GHR_4$进行两种类型的hash映射，产生两个hash值$h_1$和$h_2$。$h_1$用于查PHT得到$pred$、$tag$和$usefulness$，$h_2$用于选择子预测器 —— 若$h_1$查表得到的$tag$等于$h_2$，则称相应的子预测器发生了 tag匹配。

  若多个子预测器均发生了$tag$匹配，则在这些子预测器里，选择GHR位宽最大的作为$provider$，选择GHR位宽次最大的作为$altpred$（alternate prediction，候选预测）；若$T1$ ~ $T4$当中只有一个子预测器发生匹配，则选择发生匹配者为$provider$，选择$T0$作为$altpred$；若$T1$ ~ $T4$均无匹配，则选择$T0$作为$provider$和$altpred$。$provider$的预测结果将作为TAGE预测器的最终预测结果。

2.5.3 TAGE更新策略

  当分支指令的实际跳转行为被确定时，首先需要更新$provider$中发生$tag$匹配的entry。只有在$provider$的预测结果与$altpred$不相同时，才更新entry中的$usefulness$字段 —— 若$provider$预测正确，则令$usefulness$增加1，否则令其减小1。至于entry中的$pred$字段，其更新规则与一般的饱和计数器相同，详见2.1小节-图3-2，此处不赘述。

  此外，为了防止某些entry被一直标记为useful，需定期对所有子预测器的全部$usefulness$的高、低位分别进行清零。

补充说明

  清零周期以分支指令的数量计算。在TAGE论文中，每256K条分支指令进行一次清零操作。

  除了更新$provider$和各子预测器的$usefulness$字段，当TAGE预测失败时，还要视情况进行entry的分配。分配时，首先寻找满足以下条件的子预测器：

• a) GHR位宽比$provider$大
• b) 对应entry的$usefulness$字段为零

在所有同时满足条件a)、b)的子预测器中，选出GHR位宽最小的子预测器进行更新。更新时，将对应entry的$pred$字段设置为"$weak taken$"，并将$usefulness$字段清零。若所有满足条件a)的子预测器都不满足条件b)，则令这些子预测器的对应entry的$usefulness$字段减小1。

小提示

  对于N比特的饱和计数器，"$weak taken$"（或"$weak correct$"）所对应的值为$2 ^ {N - 1}$。