什么是分支预测？

在几乎任何计算机程序中，都有部分代码分支到不同的路径。为了 example, if-then-else 语句有两种可能的结果。这些语句不会给顺序处理器带来任何问题，因为 CPU 会按顺序处理每个命令。分支对于流水线处理器来说是一个大问题，因为同时执行多个指令。

情景

对于具有两个可能结果的分支语句的程序，两个可能的代码路径不能在同一个地方。完成任一选项所需的处理将有所不同。否则，程序不会分支。可能会有相当多的分支语句只使用一次，例如 if 语句。

还有形成循环的分支语句。虽然这些在数字上可能不像一次性声明那样普遍，但它们通常在统计上是重复的。可以假设分支更有可能将您带回循环而不是循环。

为什么这是个问题？

在完全顺序的处理器中怎样表达这个问题并不重要。这根本不是问题。在处理以下指令的第一部分之前，将采用哪个分支是已知的。

然而，在流水线处理器中，以下指令排队。当处理器知道正在采用哪个分支时，它们已经在处理。那么处理器应该怎样处理这种情况呢？有几个选项。最糟糕的情况是等待并让管道处于空闲状态，同时等待选择哪个分支的答案。这意味着每次你有一个分支语句时，你总是会损失至少与管道中的阶段一样多的处理器时间周期。

或者，您可以尝试在管道中运行这两个选项并放弃错误的选择。这将有一半的惩罚是什么都不做，但仍然会在每个分支语句上产生性能损失。鉴于现代 CPU 也可以乱序运行指令，您可能会尝试尽快运行每条分支指令。所以它的结果在需要之前就知道了。此选项可能会有所帮助，但它不可扩展。假设您有相对较高密度的分支语句。在这种情况下，如果没有空闲时间，您将无法提前运行所有这些。

这个问题是怎样真正解决的

实际上，处理器包括一个分支预测器。分支预测器尝试猜测将采用分支选择的哪个结果。然后处理器假定预测是正确的并安排指令。如果分支预测器是准确的，则没有性能损失。

如果分支预测器出错，您必须刷新管道并开始处理实际结果。这确实会导致比什么都不做而只是等待结果稍差的性能损失。为了获得最佳性能，确保分支预测器尽可能准确非常重要。对此有一系列不同的方法。

匹配代码

在机器代码中，分支始终是在读取下一条指令或跳转到其他地方的一组指令之间的选择。分支预测器的一些早期实现只是假设所有分支总是或永远不会被采用。如果编译器知道这种行为并且旨在调整机器代码以使最可能的结果与处理器的一般假设一致，则此实现可以具有令人惊讶的良好成功率。这需要大量的调优和调整软件开发习惯。

另一种选择是从统计数据中学习，循环通常被采用，并且如果分支在指令流中向后移动，则总是跳转，如果跳转是向前的，则永远不会跳转，因为这通常是统计上不太可能离开循环的状态。这些都是静态分支预测的两种类型，其中分支的结果是在编译时预测的。

动态分支预测器

现代分支预测器是动态的，使用来自当前运行程序的统计数据来实现更好的预测成功率。饱和计数器是所有当前分支预测器的基础。第一个猜测是静态或随机决定的。一旦一个分支被采用或没有被采用，该结果将存储在内存的一部分中。下次出现相同的分支时，分支预测器会预测与以前相同的结果。

这自然会产生良好的循环预测率。这有两个版本。早期版本仅使用一位数据来指示分支是否被采用。以后的版本使用两位来表示弱或强采用或未采用的选择。如果程序返回到该设置，此设置仍然可以预测执行循环的结果，通常会提高成功率。

跟踪模式

为了跟踪模式，一些分支预测器会跟踪所采取的选择的历史记录。为了 example，假设一个循环被连续调用，但在跳出循环之前只循环了四次。在这种情况下，两级自适应预测器可以识别这种模式并预测它再次发生。这比简单的饱和计数器进一步提高了成功率。现代分支预测器通过使用神经网络来发现和预测模式，进一步建立在此之上。

一个 2 位饱和分支预测器仍然可以预测一个分支被采用，即使它以前没有。这允许它预测循环将被重新执行，即使它已经离开一次。

一些分支预测器使用多种算法，然后比较结果以决定使用哪个预测。一些系统在所谓的本地分支预测中分别跟踪每个分支指令。其他人使用全局分支预测系统来跟踪所有最近的分支指令。两者都有其用途和缺点。

当采用某些分支时，使用模式历史表的分支预测器可以识别重复模式。例如，预测一个循环在离开之前只执行了 3 次。