2.3 分支预测

控制冒险发生在一个指令改变了程序的控制流时，例如分支或跳转指令。分支预测技术的提出就是为了应对控制冒险。由于分支结果（程序将沿哪个路径继续执行）通常需要等待分支指令本身完成才能确定，所以在分支指令和接下来的指令之间形成了一个空隙，导致流水线可能无法被填满。

分支预测技术试图预测分支结果，从而提前取出和准备（预取和预译码）沿预测路径的指令，使得即使分支结果尚未确定，流水线也能继续执行。理论上如果能够实现100%正确的分支预测，处理器的IPC就会得到极大的提升。

好的分支预测技术可以大大减少由于分支和跳转引起的控制冒险，从而提高流水线的效率，使得在同一时间内更多的指令能够并行执行。需要注意的是，分支预测并不能直接导致流水线长度的无限提升。流水线长度的选择需要权衡许多因素，如硬件复杂性、时钟周期长度、指令复杂性等。

如果预测错误，则需要丢弃流水线中的所有预测指令，才能开始进入正确的指令，这被称为分支预测错误的惩罚。分支预测错误的惩罚与流水线的深度成正比：流水线越长，清空和重填流水线所花费的时间就越长。所以在设计超长流水线的CPU时，需要有非常准确的分支预测技术，以减少由于预测错误而导致的性能损失。

如果让你来设计分支预测单元，那么在没有知识储备的情况下，要达成让指令连贯执行的要求，你会如何做？因为我们完全不知道分支跳转的概率，所以可以直接押注其中一个50%的概率，那么最简单的预测策略就是“始终不跳转”或“始终跳转”。

● 始终不跳转（Always Not Taken）：在这种策略下，处理器会假设所有的分支指令都不会跳转，而会顺序执行。这种方法在顺序执行的代码中表现良好，但在有大量控制流跳转的程序中表现就会较差。

● 始终跳转（Always Taken）：这种策略是始终预测分支会被执行，也就是会跳转到某个新的地址继续执行。这在循环和条件跳转很频繁的代码中表现较好。

这两种方法都很简单，实现起来也只需要很少的硬件资源，但预测的准确率取决于代码的具体情况。如果代码中的分支行为比较随机，或者并不符合“始终跳转”或“始终不跳转”的假设，那么预测的准确率就会很低。现代处理器使用的分支预测技术已经远远超过了这些基本策略，采用了更复杂的预测算法和更多的硬件资源，以提高预测的准确性，从而提升处理器的性能。

现代CPU已经采用了一些更复杂的算法，比如基于历史信息的预测、二位饱和计数器、局部分支预测、全局分支预测、混合分支预测等，以提高预测的准确性。

● 基于历史信息的预测：这种方法将过去的分支行为作为未来预测的依据。例如，如果一个分支在过去几次出现时都被取走了，那么预测器可能会假设下一次它也会被取走，先前指令流中遇到的分支跳转目标或者分支跳转方向都是历史信息。理论上记录越长的历史信息越能够保证预测匹配到真实的行为，但这同时也意味着需要消耗大量额外的硬件资源。

● 二位饱和计数器：它是一种简单的预测器，使用二位来记录分支的历史行为。每当一个分支被采用，计数器值就会增加；每当一个分支未被采用，计数器值就会减少。然后根据计数器的值（例如，如果计数器值大于或等于2，则预测为分支被采用，否则预测为分支未被采用）来进行预测。

● 局部分支预测：在这种方法中，处理器会记录每个分支指令的历史信息，然后用这些信息来预测分支指令的行为。这种方法在处理器遇到循环或者条件跳转频繁的代码时表现良好。

● 全局分支预测：这种预测技术考虑的是程序的全局行为，而不是每个分支指令的行为。处理器会记录最近的分支结果，并使用这些信息来预测下一个分支的行为。

● 混合分支预测：混合分支预测器是把以上多种预测方法结合起来，通过一个元预测器（Meta Predictor）根据实际情况选择最佳的预测方法。这种预测方法可以结合多种预测方法的优点，提供更准确的预测。

我们选择一个容易理解的分支预测逻辑进行讲解，即二位饱和计数器，这是一个具有4种状态的状态机：

● 强不跳转（Strongly not taken）。

● 弱不跳转（Weakly not taken）。

● 弱跳转（Weakly taken）。

● 强跳转（Strongly taken）。

二位计数器的值可能有4种状态：00、01、10、11，该状态机的初始状态通常采用强不跳转或者弱不跳转，如图2-4所示。

强跳转意味着分支已经确定会被执行，因此该分支的历史状态被标记为11，表示该分支历史记录的最强状态。当历史记录的状态被标记为11时，预测器预测该分支总是被执行。弱跳转表示分支执行的概率比较大，历史状态被标记为01或10。

类似地，强不跳转和弱不跳转分别表示该分支不会被执行的可能性较大或者不确定。总体而言，饱和计数器中的“强”和“弱”表示预测器对分支行为的信心程度，“强”表示高度信心，“弱”表示信心程度较低。

当一个分支被评估时，相应的状态机就会被更新。评估为“不跳转”的分支会将状态改变为“强不跳转”，评估为“跳转”的分支则会将状态改变为“强跳转”。二位饱和计数器方案相比于一位饱和计数器方案的优势在于，一个条件跳转必须偏离其过去的主要行为两次，才会改变预测。例如，一个关闭循环的条件跳转只会被错误预测一次，而不是两次。

我们把类似始终跳转和始终不跳转的情况归类到静态分支预测（Static Branch Prediction）。这种方法是在编译时进行的，根据代码的编写方式和常规编程习惯进行预测。更为复杂的静态分支预测可能会根据分支指令的类型或位置（如循环语句的末尾）进行预测。

和静态分支预测相对应的就是动态分支预测（Dynamic Branch Prediction）。这种方法是在运行时进行的，根据处理器过去执行的分支的行为进行预测。基于历史信息的预测、二位饱和计数器、局部分支预测、全局分支预测、混合分支预测等都属于动态分支预测。这种预测方法通常比静态分支预测更准确，因为它可以适应程序运行时的实际行为。

动态分支预测通常涉及一些专门的硬件结构，如分支目标缓冲区（Branch Target Buffer，BTB）、分支历史表（Branch History Table，BHT）、方向预测器（Direction Predictor，DP）、返回地址栈（Return Address Stack，RAS）等，它们共同工作来提高分支预测的准确性。

● 分支目标缓冲区：如图2-5所示，BTB是一个存储结构，记录了已经发现的分支指令的地址以及这些分支指令的目标地址。当处理器遇到一个分支指令时，会查看 BTB中是否已经有这个分支指令的记录，如果有，就直接使用BTB 中的信息进行预测，避免了计算分支目标地址的时间开销。此外，BTB中的记录还可以包括这个分支指令上一次是取还是不取的信息，这也可以用来帮助预测这次分支的行为。分支预测不仅需要预测器来预测分支将如何执行（将要采取哪条路径），还需要一个单元来提供分支指令的目标地址，BTB的设计就是为了这个目标。BTB的容量是一个重要的设计参数。一个更大的BTB 可以存储更多的分支目标地址，从而降低缓存未命中的可能性。然而，较大的BTB 也需要更多的硬件资源，并可能增加访问时间，这会影响处理器的时钟速度。

● 分支历史表：这是一个存储结构，用于记录最近的一些分支指令的行为，比如哪些分支被取，哪些没有被取。这些历史信息可以用来帮助预测下一次遇到同样的分支指令时是应该取还是不取。

● 方向预测器：这是一个逻辑电路，用于根据BTB和BHT的信息来预测分支指令的行为，即是应该取还是不取。

● 返回地址栈：用来预测函数返回时的地址。返回指令是一种特殊的分支指令，它通常在一个函数执行结束后，将控制流转移到调用该函数的位置。因为一个函数可以在程序中的多个位置被调用，所以预测返回指令的目标地址特别困难，如果只使用通用的分支目标缓冲区进行预测，则很容易出现错误。返回地址栈的一种常见设计是基于循环 LIFO（先进后出）缓冲区，其中存储了返回地址和一个访问当前栈顶部的指针。在程序调用指令时，返回目标地址被压入堆栈；在返回指令时，预测目标地址从堆栈中被弹出。如果发现分支预测错误，则可以使用备份的栈顶指针值来恢复当前的栈顶指针，从而快速纠正错误。

通过这些结构的协同工作，动态分支预测可以根据过去的行为来预测未来的行为，提高分支预测的准确性。分支行为可能会受到程序运行状态的影响，动态分支预测并不能保证100%准确率。当预测错误时，还需要有机制来处理预测错误，比如快速丢弃预测错误后的指令，以及从正确的地址重新获取指令等。

由于分支预测可能会出错，所以处理器需要有一种机制来纠正预测错误，这就是分支指令顺序缓冲区的主要作用。“Branch Order Buffer”通常被翻译成“分支指令顺序缓冲区”，它在处理器的设计中起着重要的作用，记录了预测的分支指令和对应的预测结果，如果后来发现预测结果是错误的，处理器就可以使用这些信息来回滚到错误预测前的状态，并按照正确的路径继续执行。分支指令顺序缓冲区通常与之后我们要讲到的重排序缓冲区（ROB）一起工作，因为ROB也需要记录执行的指令和对应的状态信息，以便处理其他种类的执行错误，如内存访问冲突或者异常处理等。在乱序执行的处理器中，当一个指令被译码的时候，它就会被放入重排序缓冲区，这是在指令发射之前的步骤。