为什么分支预测相当准确？

Question

为什么分支预测准确？我们是否可以从较高的层面来思考代码的某些分支如何在 99% 的时间内执行，而其余的则是特殊情况和异常处理？

我的问题有点模糊，但我只对这个问题的高层观点感兴趣。让我举一个例子

假设你有一个带有参数的函数

void execute(Input param) { 
  assertNotEmpty(param)
  (...)
}

我有条件地执行我的函数，给定的参数不为空。99% 的情况下这个参数确实是非空的。那么我是否可以考虑基于神经网络的分支预测，例如，在某种程度上，由于它已经无数次看到这样的指令流（这样的断言很常见），它会简单地了解到大多数时候该参数非空并且相应地采取分支？

那么我们是否可以从以下角度来思考我们的代码：代码越干净，越可预测，甚至更常见，我们就越容易使用分支预测器？

谢谢！

Answer 1

如何预测分支的简史：

当曾祖母编程时

没有预测，也没有预取，很快她开始在执行当前指令的同时预取下一条指令。大多数情况下，这是正确的，并且在大多数情况下将每条指令的时钟提高了 1，否则没有任何损失。其错误预测率平均仅为 34%（59%-9%，H&P AQA p.81）。

奶奶编程的时候

存在这样的问题：CPU 变得越来越快，并在管道中添加了解码阶段，使其成为“获取”->“解码”->“执行”->“写回”。在分支之间有 5 个指令的情况下，如果分支向后或向前并且分别采用和未采用，则每 5 个指令就会丢失 2 次读取。一项快速研究表明，大多数条件后向分支都是循环，并且大多数被采用，而大多数前向没有被采用，因为它们大多是坏情况。通过分析，我们可以降低到 3%-24%

带有饱和计数器的动态分支预测器的出现

为程序员创造了生活更轻松。从观察来看，大多数分支都会执行上次所做的操作，有一个计数器地址列表，其中分支地址的低位告诉分支是否被采用，并且分支目标缓冲区提供了要获取的地址。在这个局部预测器上，它将错误预测率降低到 1%-18%。

这一切都很好，但有些分支取决于之前其他分支的行为。因此，如果我们有最后一个分支取或不取为 1 和 0 的历史记录，根据历史记录，我们有 2^H 个不同的预测变量。实际上，历史位与分支低地址位进行异或，使用与先前版本中相同的数组。

这样做的优点是预测器可以快速学习模式，缺点是如果没有模式，分支将覆盖以前的分支位。PRO 比 CON 更重要，因为局部性比不在当前（内）循环中的分支更重要。该全局预测器将错误预测率降低至 1%-11%。

这很好，但在某些情况下，局部预测器会击败全局预测器，所以我们两者都需要。将本地分支历史记录与地址进行异或改进了本地分支预测，使其成为 2 级预测器，只是使用本地分支历史记录而不是全局分支历史记录。为每个计数的分支添加第三个饱和计数器，我们可以在它们之间进行选择。与全局预测器相比，该锦标赛预测器将误预测率提高了约 1%。

现在你的情况是另一个方向的百分之一。

让我们检查局部二级预测器，当我们遇到一种情况时，该分支的最后 H 个分支都处于同一方向，假设采用，使所有历史记录为 1，因此分支预测器将选择局部预测表，它将饱和。这意味着在所有情况下，它都会对一种情况做出错误预测，并且很可能正确预测将进行分支的下一次调用（除非对分支表条目使用别名）。因此，不能使用本地分支预测器，因为具有 100 位长的历史记录需要 2^100 的大型预测器。

也许全局预测器会捕获这种情况，在过去 99 个情况下，分支被采用，因此最后 99 个分支的预测器将根据最后 H 个分支的不同行为进行更新，从而移动它们来预测被采用。因此，如果最后 H 个分支具有与当前分支无关的行为，则全局分支预测表中的所有条目都将预测已采取的情况，因此您将得到错误预测。

但是，如果先前分支的组合（例如第 3 个、第 7 个和第 12 个）都采取行动，使得如果采用/未采用这些分支的正确组合，则预示着相反的行为，则该组合的分支预测条目将正确预测该行为的分支机构。这里的问题是，如果您很少在程序运行时看到，用它们的行为更新此分支条目和其他分支别名，那么它可能无论如何都无法预测。

假设全局分支行为实际上根据先前分支的模式预测了正确的结果。那么你很可能会被锦标赛预测器误导，它说本地预测器“总是”正确，而本地预测器总是会错误地预测你的情况。

注 1：“始终”应该持谨慎态度，因为其他分支可能会通过对同一条目使用别名来污染您的分支表条目。设计人员尝试通过使用 8K 不同条目来降低这种可能性，创造性地重新排列分支低地址的位。

注 2：其他方案或许能够解决这个问题，但可能性很小，因为这种情况只有百分之一。