CPU设计之分支预测

1、引言

在之前的学习过程中，我们一直在假设程序是顺序执行的。PC每一次都默认+4，一直这样周而复始。然而CPU就和人生一样，不可能一直一帆风顺的向前走。在某些场合我们总是需要做出决策，这些决策点，就像高速公路的一个出口，我们是继续前行，还是离开高速公路，去到另外一条不同的道路？在CPU指令中，这些决策点被称为分支指令。

如果决策正确，那一切安好，无事发生。可是一旦做了错误的判断。其往往是后知后觉的，当你发现情况不对的时候，此时距离原始的出发地已经有了很长的距离。我们不得不告诉流水线开头，去重新定向到另外一条分支。此时在分支指令之后，已经执行了的指令实际上都是不应该执行的指令，因此都应该冲刷（Flush）掉。如果经常出现这种情况，对于性能和功耗都是严重的损耗。因为我们花了大量的时间去做了本不应该做的事情。

如何避免这点呢？有一个非常简单的做法。当我们碰到分支的时候，我们先什么都不做，等待该分支指令的执行，等它确定好，需要跳转还是不需要跳转，我们再执行后续的指令。这样是非常安全的，保证了我们做的决策都是正确的。但这种方法的缺点也非常明显。那就是这种方法太慢了！如果程序代码中有很多的分支，程序性能就会严重受影响，我们会花大量的时间，持续等待分支指令运算出结果，也就是到底要不要跳。而这个阶段，后续的指令，都没有办法进入流水线，严重浪费了处理器的性能。

又有人问了，那可不可以两条分支都走，扩展数据路径，然后根据分支指令的判断结果选择其中的一路结果？当然不行，这样起码浪费了百分之五十的性能。如果没有分支指令的话，那意味着另外一条路径完全在空跑，太浪费了，显然不行。再考虑复杂一点的情况，如果分支有嵌套呢？难不成做四条数据路径？这个方案既然行不通，那到底应该怎么做呢？

2、分支预测概述

如果我们在取指令阶段的时候，就可以“提前知道”该指令是否为分支指令，并且可以知道它的方向（跳或不跳），以及相应的目标地址（target address）的话，那么就可以直接在下一个周期从分支指令的目标地址开始取指令，这样就不会对流水线产生影响，从而避免了做无用功。对于这种不需要等待分支指令的结果真的被计算出来，而是提前就预测结果的过程就是分支预测。一件东西之所以可以被预测，一定是它本身具有某些特点，使得预测其成功的概率是大于百分之五十的，这种情况下做预测才有相应的意义，我们后面再展开讲这一点。对于RISC指令集而言，其分支指令通常包含两个要素。

（1）方向：对于一个分支指令而言，它的方向有且只有两种情况，一种是发生跳转，一种是不发生跳转。有一些分支指令是无条件执行的，比如jump相关的指令，而有一些指令是依赖于指令运算得到的结果来决定是否要进行跳转的，比如BEQ指令。它需要根据两个源操作寄存器的值是否一致来确定是否需要发生跳转。

（2）目标地址：对于不跳转的情况，则地址是原来的PC+4，而对于跳转的情况，我们不光要知道它需要跳转，还需要知道跳到哪里去，也就是跳转的目标地址。其目标地址主要有两种不同的形式，我们后续再讲。

综上我们可以知道，如果对分支指令进行预测，需要对方向和目的地址都进行预测才行。对于中低性能处理器而言，其流水线级数往往只有3~5级，此时通常采用默认不跳转的方式（也被称为静态分支预测，实际上静态分支广义上来说，指的是通过编译器来达到更好的分支预测结果，默认不跳转是最简单的静态分支预测，更复杂的静态分支预测这里不讨论），即预测分支指令总是不执行。这样处理器总是可以顺序的取指令，当分支指令运算到运行到执行阶段以后，可以得到分支指令实际的方向和目标地址，如果需要跳转，则将后续的指令全部冲刷掉。如果确实不需要跳转，那就无事发生，接着顺序取指就可以。

对于流水线级数较少的处理器而言，使用这种静态分支预测技术是没有问题的（甚至可以这么说，对于这种低端处理器，搭载动态分支预测器反而是不划算的）。对这种处理器而言，即使分支预测失败的话，其损失也不是很严重。以上图为例，分支预测失败的情况下会有三条指令被冲刷掉。我们可以对其做进一步改进，在译码阶段就提前运算得到分支指令的结果（称为Early Branch Resolution），然后做相应的组合逻辑运算，再传给PC的D端，如果需要跳转的话（对于这种静态分支预测，默认是不跳转的，如果需要跳转则称为分支预测失败），在下一个IF阶段，PC的值就已经是需要跳转到达的PC值了（对于分支指令紧挨着的那个指令已经进入取指阶段了，这条指令如果取错了那也没办法了，也就是最少仍然会有一条指令要被冲刷掉）。1988年推出的MIPS R3000处理器就采用了此设计思路。

基于这种设计，我们可以相应的结果，如下图所示，此时只有一条指令需要被冲刷掉。我们想一想，这是一个好方法吗？

其好处在于减少了分支预测失败的惩罚（misprediction penalty）。但是其有可能增加时钟周期，因为此时译码阶段的运算一直到PC的D端这条路径，有可能成为关键路径。除此之外，还会带来额外的硬件开销。这一部分硬件开销对于非分支指令而言，实际上是用不到的。因此分支指令不多的情况，这种设计方法反而有可能不如不做Early Branch Resouliton。

很显然，当流水线级数增加的时候，分支预测失败的惩罚会越来越大。因为会有更多的指令被冲刷掉，单纯预测所有分支指令都不发生跳转的静态分支预测算法已经不能够满足复杂处理器对性能的要求了，此时就需要更加准确的分支预测方法。很显然，最直观的方法，就是根据之前已有的信息，来判断再遇到类似的情况，需不需要跳转。

这和我们现实生活中做决策是一样的，我们往往根据自己的经验做相应的判断。对于这种依赖于历史信息，动态的对分支指令进行预测（所谓动态，即会随着运行情况，持续不断地发生改变），称为动态分支预测。动态分支预测也是我们今天的主角，接下来我们讲的分支预测算法，默认都是动态分支预测。

3、动态分支预测

我们首先看一下动态分支预测的三要素，需要在取指阶段获得以下三个信息：

获取的指令是否是分支指令；
是否是条件分支指令；
如果跳转的话，跳转目的地址在哪里；

我们很容易发现，在程序的运行过程中，条件分支指令跳转的目标地址总是保持不变的。（即某一个PC地址的条件分支指令，它跳转到哪个地址实际上是固定的，这是程序编译好以后就决定了的）。

因此我们可以很自然而然的将某一个PC地址对应的分支指令，以及其相应将要跳转的地址，全部存储起来。当下一次再执行到此分支指令的时候，通过其PC进行索引，然后获取其将要跳转的地址即可。如下图所示：

这一块存储空间称为BTB即Branch Target Buffer。其本质上是Cache。通过PC地址的一部分进行索引，然后与其中的TAG进行比较，判断PC是否一致。如果一致则输出相应的Target address。

PC寻址BTB的具体架构大致上长下面这样：

仅仅依靠BTB，我们只能够存储相应的跳转地址，即上述三要素的第三点。对于第一点而言，也可以借助BTB和缓存实现，但这不是本篇文章的重点。三要素的第二点，即到底要不要跳转我们仍然不知道，那么应该怎么做呢，我们接着往下看。

3.1、基于1位计数器的分支预测

对于分支指令而言，其方向只有两个，发生跳转和不发生跳转。最关键的是，在绝大部分情况下，分支指令的方向是有迹可循的。我们想一想，什么情况下会出现分支指令呢？大概率是代码中写了if/else、for循环、Switch case语句等，其中if/else，switch case反复调用的频率相对较低，规律性没有那么强。而对于for循环，其规律性是非常强的，并且会反复地调用，我们考虑下面这样的一个例子。

for(int i=0;i<1000;i++){ procedure }

我们不考虑编译器的优化。对于上面的这个for语句，理论上会执行1000次循环体的内容，其实际上会转换为机器语言的分支指令，并且这个分支指令会在前1000次都往同一个方向执行（假设此时为跳转），因此它的方向是有规律的。正是因为有这种规律的存在，动态分支预测才是有意义的。对于一个完全混乱的系统，每一次跳往哪个方向都没有任何规律可言的话，这种系统做分支预测是没有任何意义的。

我们继续看上面的例子，我们考虑最最简单的分支预测方法。即根据上一次的结果，来做这一次的判断。这种方法被称为last-outcome prediction。使用的预测器叫做1-bit预测器。很显然，对于上面的例子而言，其准确性相比静态分支预测有了明显的提升。静态分支预测基本全错，而使用这种方式，只有分支指令方向发生变化的时候才会出现错误，其准确率非常的高。但事情真的有这么美好吗？

我们假设下面的情况：

对于这种方向变化非常频繁的分支指令，基于1-bit的动态分支预测器，基本有可能全错。其准确率如此的不稳定，在现代处理器中显然是不可以接受的，因此该动态分支预测器，实际上没有被任何商业产品所采纳。现代处理器应用最广泛的分支预测方法都是在2-bit饱和计数器的基础上，进行改进的。

3.2、基于2-bit饱和计数器的分支预测

由于有2-bit，那自然可以表示4个状态，这四个状态分别如下所示：

Strongly taken：计数器处于饱和状态，分支指令预测本次会发生跳转，编码为11；
Weakly taken：计数器处于不饱和状态，预测本次会发生跳转，编码为10；
Weakly not taken：计数器处于不饱和状态，预测本次不会发生跳转，编码为01；
Strongly not taken：计数器处于饱和状态，分支指令本次会预测不发生跳转，编码为00；

上述方式中，我们增加了一个bit，使得其在面对极端情况下有更好的表现，我们重新考虑上面那个方向变化比较频繁的指令。我们此时可以获得50%的准确率。对于典型的循环应用场景，可以获得90+%的准确率。我们还可以进一步提升准确率吗？

一个很直观的想法是再增加1bit，采用3bit进行判断。但实际上是不可取的，这样会引起复杂度的上升和存储资源的增加，根据工业界的实践，这些额外开销带来的负面影响要大于实际获得的精度提升。所以主流处理器仍然采用基于两位的饱和计数器来实现分支预测。

根据实际的评估，大部分程序如果仅仅采用传统的2-bit计数器进行分支预测，大约可以获得85%~90%的准确率。这足够好吗？业界显然不满足于此，于是基于传统的分支预测方案有了新的改进。

3.3、基于局部历史的分支预测器

我们上述的分支预测，仅仅利用了“last time”的结果。所谓的Last-Time Predictor即仅仅依靠于分支指令自己本身上一次或上两次的分支预测结果。我们想一想这样的缺点是什么呢？很显然，那就是从T->NT或者从NT->T跳转的过于频繁了。我们假设按照T、T、NT的情况循环，初始情况为Strongly taken。那么只能获得三分之二的准确率。实际上这个跳转循环是很有规律的，我们肯定能预测的更准！

如果我们如果对一条分支指令进行分支预测的时候，可以多考虑一些东西，那么能不能做的更好呢？大致思路如下

考虑分支指令本身前几次的执行结果，称为基于局部历史的分支预测器；
考虑其他分支指令的结果全局历史，称为基于全局历史的分支预测器；

我们先看基于局部历史的分支预测器，为什么这样可以起作用呢？因为理论上而言，绝大部分程序都是有规律可循的。我们如果使用一个寄存器来记录一条分支指令在过去的历史状态，当历史状态很有规律的时候，就可以为分支预测提供帮助。这个寄存器称为分支历史寄存器（Branch History Register，BHR）。其本质上是一个移位寄存器，它也被称为自适应的两级分支预测（Adaptive Two-level Predictor）。

第一级称为局部历史寄存器组合；
第二级称为每个历史条目的饱和计数；

如下图所示，当目前寄存器的值为1100的话，则代表最近的4次跳转状态，然后根据1100进行寻址，获得2-bit的结果。这种方式相比于原始的2-bit索引，尽管消耗了更多的资源，但明显能够获得准确率提升（Why?）。

为什么这样就可以获得准确率的提升呢？我们想象一下，一个大循环包含一个小循环，假设小循环内部是循环4次，也就是T、T、T、NT这样循环，如下图所示。那自然而然的，就可以根据之前的4次结果，来确定这一次是不是要跳转。因此这种方式对于循环嵌套的场景非常有效。（并且内部的循环不能太大，否则会导致PHT太大或者准确率下降）

如果使用传统方案的话，则大概只能获得75%的准确率。（什么年代了，还在做传统分支预测？）

我们将开始讲的BTB和BHR结合在一起，如下图所示，就形成了一个完整的分支预测器。

3.4、基于全局历史的分支预测器

除了记录自己这条指令的历史执行情况，还可以记录其它分支指令的执行结果以辅助判断。这种预测方法被称为为基于全局历史（Global History）的分支预测。这似乎有点奇怪，这条分支指令的结果，难道和别的分支指令的结果有关系吗？

实际上是有的，我们看下面这两个例子。对于第一个例子而言，如果第一个分支没有执行，那么第二个分支也不会执行。对于第二个例子而言，如果第一个分支执行，则第二个分支会执行。

基于上述的例子，我们有了一个很直观的想法。将分支预测的结果和所有分支的T/NT历史结合起来。相应的我们就需要一个GHR寄存器，用来记录最近执行的所有分支指令的结果。典型方案是使用GHR寄存器来寻址PHT。我们来看个实际的例子，来了解该方案是怎么工作的。

我们假设GR为1101，此时的j=1，其结果应该是满足，则taken，GR相应的更新为1011。（GR本质就是移位寄存器）；然后j=2，继续taken，GR更新为0111；然后j=3，此时的结果是not taken，GR更新为1110；然后判断i，假设满足，则taken，GR更新为1101，又回到了初始状态。

显然一开始的结果大概率不准确，但是随着时间的推移，相应的GHR寄存器指向的2-bit值会趋向于稳定，这个过程称之为训练。对于上述这段代码而言，在训练完成以后。除了循环的出口以外，整个判断准确率会非常高。

我们将GHR和BTB结合起来，其硬件架构大致如下：

还可以更复杂一点，将PC信息和全局分支历史信息结合起来进行寻址。

3.5、混合分支预测器

所谓的混合分支预测器，就是使用超过一种的分支预测器，来获得最好的分支预测结果。因此该预测器不是特指某一种预测器，它可能有着各种各样的组合。

我们来看一个例子：下图通过局部历史和全局历史相结合。选择其中某一个以获得最好的分支预测结果。显然其需要消耗更多的资源，延迟也更长。但它也确实可以提高准确率。尤其是对于某些需要训练的预测器而言，在训练完成之前可以先用不怎么需要训练的预测器，以获得更好的预测结果。

4、现代分支预测器

4.1、基于感知机的分支预测器

学习过人工智能的朋友应该都清楚，感知机在处理线性函数的时候非常有效。可以简单的将其作为二元分类器进行使用。关于感知机本身这里不做介绍，我们直接看它是怎么用作分支预测器的。

感知机预测器由德州农工大学的教授Daniel A. Jiménez提出。通过手工编码的特征，尝试通过学习如何对这些特征进行加权从而识别对象。

我们使用BHR寄存器的不同Bit作为输入向量X，输出为0或者1即是否跳转。其本质上也是基于全局历史分支预测器的变种。其运算过程和训练过程如下所示。根据地址选择相应的GHR寄存器，寄存器的每个bit即相应的xi，我们计算得出相应的y，即是否跳转。如果错误则需要使用梯度下降法进行更新w系数，最终趋于稳定。该过程和AI的训练过程是一样的。

我们看下其优点和缺点：

优点：

更复杂的学习机制，从而有更高的准确率；
支持较长的分支历史长度，从而获得更高的准确率；

缺点：

硬件设计较为复杂（需要引入加法树来计算感知机结果）；
只能够学习线性函数；

基于感知机的分支预测器非常成功。典型代表是AMD的Zen和Zen2（TAGE加感知机）。

4.2、基于Tage的分支预测器

Tage是标记几何历史长度（TAgged GEometric history length）的缩写。该预测器由法国科学家André Seznec提出。其名字非常抽象，这里简单解释一下。所谓的历史，就是在运行时间内分支指令运行情况（跳转与否）。该预测器依赖于基础预测器以及由多个标签（Tag）的预测器组件组成的全局预测器。这些组件使用不同的分支历史信息长度进行索引计算，这些历史长度形成几何级数。

为什么这样是有效的呢？因为通过实际的研究发现，不同的分支依赖于不同的历史长度，从而可以获得最好的预测准确率。正因为如此，所以有了这样的想法。使用具有不同历史长度的GHR去索引PHT，并且可以智能的将PHT条目分配到不同的分支。我们可以发现Tage其实就是上面所说的，基于全局历史分支预测器的变种。

下图是一个经典的带有一个T0和4个TN的TAGE预测器结构：