为什么分支预测非常准确？

Question

为什么分支预测非常准确？

3

为什么分支预测准确？我们可以从高层次上认为它是因为我们代码中某些分支执行了99%的时间，而其余部分则是特殊情况和异常处理吗？

我的问题可能有点模糊，但我只对这个问题的高层次视图感兴趣。让我举个例子，假设你有一个带参数的函数。

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

我在参数不为空的情况下有条件地执行我的函数。99%的时候，这个参数确实是非空的。例如，我能否考虑基于神经网络的分支预测，因为它已经看到了无数次这样的指令流（这种断言相当普遍），它会简单地学习到大多数情况下该参数是非空的，并相应地进行分支操作？

我们是否可以从代码的角度思考 - 代码越干净，越可预测，甚至更常见 - 我们使它更容易被分支预测器理解？

谢谢！

- Mark

3个回答

2

我们能够开发出良好的分支预测器，原因有以下几点：

Bi-modal distribution - the outcome of branches is often bimodally distributed, i.e. an individual branch is often highly biased towards taken or untaken. If the distribution of most branches would be uniform then it'd be impossible to devise a good prediction algorithm.
Dependency between branches - in real-world programs, there is a significant amount of dependency between distinct branches, that is the outcome of one branch affects the outcome of another branch. For example:
```
if (var1 == 3)     // b1
    var1 = 0;
if (var2 == 3)     // b2
    var2 = 0;
if (var1 != var2)  // b3
    ...
```
The outcome of branch b3 here depends on the outcome of branches b1 and b2. If both b1 and b2 are untaken (that is their conditions evaluate to true and var1 and var2 are assigned 0) then branch b3 will be taken. The predictor that looks at a single branch only has no way to capture this behavior. Algorithms that examine this inter-branch behavior are called two-level predictors.

您没有要求任何特定的算法，所以我不会描述任何算法，但是我会提到2位预测缓冲区方案，该方案工作得相当不错，并且非常容易实现（基本上，您需要在缓存中跟踪特定分支的结果，并根据缓存中的当前状态做出决策）。这个方案被实现在MIPS R10000处理器中，结果显示预测准确率约为90%。

我不确定神经网络在分支预测中的应用 - 看起来可能设计一个基于神经网络的算法。然而，我认为它不会有任何实际用途，因为：a）它在硬件上太复杂了（因此需要太多的门并引入很多延迟）; b）与更容易实现的传统算法相比，它不会对预测器的性能有显着的改进。

- dbajgoric

0

许多编程语言都提供了机制来告诉编译器哪个分支是最可能的结果。这有助于编译器组织代码以最大化正面分支预测。例如，gcc __builtin_expect、likely、unlikely。

- 0___________

这些东西可以帮助编译器布置代码，使得常见情况大多数分支都是非占用的，等等类似的内容。这有助于分支预测，因为从来没有被占用的分支通常甚至不会在 BTB 中获得条目。（Intel Pentium 4 实际上有预测器提示指令前缀，但除此之外，编译器到 CPU 的明确分支提示并未被使用。） - Peter Cordes

无论如何，人们对这个答案进行了反对投票，因为分支预测在没有明确提示的情况下也能很好地工作。 - Peter Cordes

@Peter Cordes 我写错了什么吗？有一个神奇的词叫“帮助”。 - 0___________

但它并没有解释为什么分支预测在没有提示的情况下表现良好，这是OP提出的问题。你的答案应该只是一个评论。__builtin_expect不能使分支更可预测，它告诉编译器通常会走哪条路线（你认为）。 - Peter Cordes

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Surt · Accepted Answer

如何预测分支的简要历史：

当曾祖母在编程时，还没有预测和预取，后来她开始在执行当前指令的同时预取下一条指令。大多数情况下这是正确的，在大多数情况下每条指令的时钟周期都可以提高一个，否则就不会有任何损失。这已经有了平均34％（59％-9％，H&P AQA p.81）的误判率。

当祖母在编程时。

问题在于CPU速度越来越快，向流水线中添加了一个解码阶段，使其变为获取 -> 解码 -> 执行 -> 写回。如果分支是向后或向前的，并且分别被采取和不被采取，则每5条指令之间会丢失2个提取。快速研究表明，大多数条件向后分支都是循环，大多数都被采取，而大多数向前分支则不被采取，因为它们大多是坏情况。通过分析，我们可以将其降至3％-24％。

动态分支预测器与饱和计数器

的出现使程序员

的生活更加轻松。观察到大多数分支做与上次相同的事情，有一个低位地址的计数器列表告诉分支是否被采取，分支目标缓冲器提供要获取的地址。在这个本地预测器上，它将误判率降低到1％-18％。

这很好，但是某些分支取决于以前其他分支的操作。因此，如果我们有最后分支采取或不采取的历史记录为1和0，那么根据历史记录，我们有2^H个不同的预测器。实际上，历史位与分支较低地址位进行异或运算，使用与先前版本相同的数组。

这样做的好处是预测器可以快速学习模式，缺点是如果没有模式，分支将覆盖前面分支的位。好处超过缺点，因为本地性比不在当前（内部）循环中的分支更重要。这个全局预测器将误判率提高到1%-11%。

这很好，但在某些情况下，本地预测器能够击败全局预测器，因此我们需要两者兼备。通过将本地分支历史记录与地址进行异或运算，可以改善本地分支预测，使其成为一个二级预测器，而不是全局分支历史。为每个分支添加第三个饱和计数器来计算哪个正确，我们可以在它们之间进行选择。这个竞技预测器相对于全局预测器将误判率提高了约1%。

现在你的情况是100个分支中的一个朝另一个方向。

让我们来看一下本地两级预测器，当我们进入第一个情况时，这些分支的最后H个分支一直朝着同一个方向，假设是taken，使得所有历史都是1，因此分支预测器将选择本地预测表中的单个条目，并且会被饱和为taken。这意味着在这种情况下它将在所有情况下造成误判，而下一次调用分支将很可能被正确预测（除了别名到分支表条目）。因此，不能使用本地分支预测器，因为需要100位长的历史记录将需要2 ^ 100大的预测器。

也许全局预测器能够捕捉到这种情况，在过去99次中，分支已经被执行，因此最后99个预测器将根据最后H个分支的不同行为进行更新，使它们预测分支将被执行。因此，如果最后H个分支与当前分支具有独立的行为，则全局分支预测表中的所有条目都将预测分支将被执行，从而导致误判。

但是，如果以前的分支组合，例如第3、第7和第12个分支，都采取了行动，以便在采取/不采取这些分支的正确组合时，它将预示相反的行为，则此组合的分支预测条目将正确预测分支的行为。问题在于，如果您只偶尔在程序运行时看到此分支条目及其别名分支的行为更新，则可能无法正确预测。

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

注1：“总是”应该带着一小粒沙子看待，因为其他分支可能会污染您的分支表条目，并将其别名分支与相同的条目。设计师已经尝试通过具有8K个不同条目并创造性地重新排列分支的较低地址的位来减少这种可能性。

注2：其他方案可能能够解决这个问题，但不太可能，因为这是100中的1。