为什么英特尔在这些年里改变了静态分支预测机制？

Question

为什么英特尔在这些年里改变了静态分支预测机制？

x86compiler-constructionintelcpu-architecturebranch-prediction

24

根据这里的介绍，我知道英特尔在这些年实现了几种静态分支预测机制：

80486时代：始终不采取
Pentium4时代：反向采取/向前不采取
像Ivy Bridge、Haswell这样的新CPU变得越来越难以捉摸，Matt G在这里进行了实验。

而且英特尔似乎不想再谈论这个问题了，因为我发现在英特尔文档中最新的材料是大约十年前写的。

我知道静态分支预测比动态分支预测（远？）不重要，但在很多情况下，CPU会完全迷失，程序员（带编译器）通常是最好的指南。当然，这些情况通常不是性能瓶颈，因为一旦一个分支被频繁执行，动态预测器将捕获它。

由于英特尔不再在其文档中明确说明动态预测机制，GCC的builtin_expect()只能从热路径中删除不太可能的分支。

我对CPU设计不熟悉，也不知道Intel现在为其静态预测器使用的具体机制，但我仍然认为Intel最好的机制是清楚地记录他的CPU“当动态预测器失效时，我计划向前还是向后走”，因为通常情况下，程序员是那个时候最好的指南。

更新：
我发现你提到的话题逐渐超出了我的知识范围。这里涉及一些动态预测机制和CPU内部细节，我无法在两三天内学习到。所以请允许我暂时退出你的讨论并重新充电。
任何答案仍然受欢迎，在这里可能会帮助更多人

- weiweishuo

3个回答

9

在英特尔优化手册的第3.4.1.3节中，所讨论的静态分支预测如下：

预测无条件分支将被采取。
预测有条件前向分支不会被采取。
预测有条件后向分支将被采取。
预测间接分支不会被采取。

编译器可以相应地组织代码。同一章节还说了以下内容：

英特尔Core微架构不使用静态预测启发式方法。但是，为了在Intel 64和IA-32处理器之间保持一致性，软件应将静态预测启发式作为默认值。

该语句表明，在很多年之后，第3.4.1.3节还没有得到更新。

如果动态预测器未能预测已获取的字节中是否有分支指令，或者它在缓冲区中遇到了一个失误，那么获取单元将只是连续获取，因为没有其他有意义的选择，有效地进行静态预测，即不采取。

然而，如果在指令队列单元中发现在获取的字节流中有条件或间接分支指令，则此时做出静态预测可能比未采取更好。特别是，预测条件直接向后的分支采取。这可以减少动态预测器和未采取获取单元失败的惩罚，特别是前端的性能非常关键。据我所知，在优化手册中没有清楚说明在IQU中有这样的静态预测器，并且适用于现代处理器。然而，正如我在我的其他回答中讨论的那样，一些性能计数器的描述似乎暗示着在IQU可能存在这样的静态预测器。

总的来说，我认为这是英特尔不再记录的实现细节。

编译器辅助的动态分支预测技术确实存在，并且可以非常有用，正如您所建议的那样，但它们在当前的英特尔处理器中不被使用。

- Hadi Brais

你好，这是我找到的Intel文档，但我在4.1.3.3节中没有看到你提到的预测行为，请问你能给我一个链接吗？正如Agner的博客第3.5节所述，Intel在PM和Core2中没有使用静态预测。而Matt G的实验也表明，更新的Intel CPU没有BT/FNT静态预测。 - weiweishuo

@weiweishuo，应该是3.4.1.3，不是4.1.3.3。 - Hadi Brais

1

你确定这部分手册适用于SnB系列吗？优化手册的某些部分写得好像适用于所有情况，但实际上是在P4时代编写的，后来在不再普遍适用时没有更新。那些“编码规则”条目（如3.4.1.3）经常过时。只要它们不会真正损害现代CPU，英特尔通常不会费心去更新它们。（例如，“add”仍然始终比“inc”更推荐，但实际情况更加复杂。INC指令与ADD 1：有关系吗？） - Peter Cordes

@HadiBrais 是的，它是第3.4.1.3节，非常抱歉。根据Matt G的实验，我无法详细说明Intel静态预测的实现方式，但最基本的结论是BT/FNT不再适用。新一代的Intel CPU对于静态预测已经没有了明确的行为规范，这正是我所关心的，因为这种设计不留给程序员（编译器）编写静态预测友好型代码的机会。我很想知道Intel是否实现了更高效、更神秘的静态算法，或者只是放弃了静态预测，认为它不值得？ - weiweishuo

1

@PeterCordes TAGE使用（部分）标记，而BTB通常是（部分）标记的（以允许关联）。如果有BTB未命中，则对于预测一个分支已被采取可能会产生怀疑（可以在同一时间进行静态预测时可用目标地址）。顺便说一句，温度适中的分支作为一类可能足够频繁，并且单独具有足够的静态偏倚，使得静态预测有用。（SPEC CPU以小型分支占用内存著称；甚至gcc可能没有像一些常见代码那样多的活动分支。基准测试指南产品。） - user2467198

显示剩余7条评论

4

我的理解是，对于当前的设计，现代TAGE分支方向预测器始终索引到一个条目，使用最近分支的取或不取历史记录。（这可能会将单个分支的状态扩散到大量内部状态中，从而使其能够预测非常复杂的模式，如10个元素的BubbleSort。）

CPU不尝试检测别名，只是使用找到的预测来决定条件分支的取或不取。即分支方向预测始终是动态的，永远不是静态的。

但是，在分支甚至被解码之前，仍然需要目标预测以防止前端停顿。分支目标缓冲区通常是带标记的，因为别名的其他分支的目标不太可能有用。

正如@Paul A Clayton指出的那样，BTB未命中可能会让CPU决定使用静态预测，而不是在动态取/不取预测器中找到的内容。我们可能只是看到了使动态预测器足够频繁地未命中以测量静态预测变得更加困难的情况。

我可能会歪曲事实。现代TAGE预测器可以预测间接分支的复杂模式，因此我不确定它们是否尝试按照取/不取来进行预测，或者第一步是否总是尝试预测下一个地址，无论它是否为下一个指令。在X86 64位模式下索引分支开销。

在正确预测的情况下，未被执行的分支仍然略微更便宜，因为前端可以更容易地从uop缓存中在同一周期获取更早和更晚的指令。(Sandybridge系列的uop缓存不是跟踪缓存；uop缓存行只能缓存来自连续x86机器代码块的uops。) 在高吞吐量代码中，已执行的分支可能成为一个小型前端瓶颈。它们还通常将代码扩展到更多的L1i和uop缓存行中。

对于间接分支，"默认"分支目标地址仍然是下一条指令，因此在jmp rax之后放置ud2或类似内容可以防止错误推测（特别是进入非代码部分），如果您不能简单地将一个真实的分支目标作为下一条指令。（尤其是最常见的那个。）

分支预测是CPU厂商不公开详细信息的“秘密武器”之一。

Intel实际上会自行发布指令吞吐量/延迟/执行端口等信息（通过IACA和一些文档），但是这些信息很容易通过实验进行测试（就像https://agner.org/optimize/和http://instlatx64.atw.hu/所做的那样），所以即使Intel想保守这个秘密，也无法做到。

分支预测成功率可以通过perf计数器轻松测量，但要知道某个特定分支在某个特定执行中为什么被错误预测或未被预测是非常困难的；即使对于一个分支的单个执行来说，测量也很困难，除非你使用rdtsc或rdpmc等工具对代码进行仪器化。

- Peter Cordes

2

虽然我之前说过同样的话，但我认为仅仅说英特尔（可能是类似TAGE的）预测器只使用历史哈希预测而没有别名检查是不正确的。毕竟，TAGE中的T代表“标记”-基于当前哈希的某个标记用于选择具有高概率映射到当前历史记录的预测器表条目。这是TAGE选择在第一次使用哪个历史长度的基础：最长的历史记录获得标记匹配。如果所有更长的历史记录都无法匹配，则使用零长度预测器是可能的... - BeeOnRope

2

历史记录的使用并不进行标记检查，这会导致“无别名检查”所建议的随机行为。您提到如果BTB查找未命中，则可以使用静态预测，但这实际上并不可行，因为所有这些都发生在解码之前（在Intel上，可能至少有半打管道阶段在解码结束之前）。稍后在解码之后，静态预测可能会启动并重定向前端，但这要少得多（特别是考虑到错误预测的可能性）。 - BeeOnRope

1

@BeeOnRope: 你是对的，如果预测器可以在解码之前预测分支的存在，他们可能有关于目标的一些信息。当我写这篇文章时，我知道它感觉太过模糊。非常感谢关于TAGE的额外细节。我不知道足够的细节来修复这个答案；如果您有好的想法，请随意编辑它或将部分内容复制到您自己的回答中。 - Peter Cordes

1

@PeterCordes 这个 Stack Overflow 回答中对 BPU_CLEARS.EARLY 事件的描述似乎表明，如果正确预测 / 在同一缓存级别中，那么假设未被采取的分支只有在它们不在“快速” BTB 中时才能优于采取的分支。这篇文章提供了一些关于 AMD 上连续跳转速度的数据，但似乎有两个峰值，可能是当 BTB 的昂贵早期电路用完时和当完整的 BTB 溢出时。 - Noah

2

@Noah，没错。它们的速度可以达到每个周期1个分支，非常快。如果每次跳转（平均而言）之间至少有几个指令（尽管“可能不是瓶颈”也适用于更慢的已取分支吞吐量：您只需要更大的基本块），那么在这种速度下，前端可能不会成为瓶颈。每次出现已取分支时，您肯定无法立即得到BPU_CLEARS。 - BeeOnRope

显示剩余2条评论

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

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

- BeeOnRope · Accepted Answer

现代设计中为什么不喜欢静态预测，甚至可能不存在静态预测，主要原因是与动态预测相比，静态预测发生得太晚了。基本问题在于，在获取它们之前必须知道分支方向和目标位置，但静态预测只能在解码后（在获取之后）进行。

更详细地说...

CPU流水线

简而言之，在执行期间需要从内存中获取指令，对这些指令进行解码，然后执行它们。在高性能CPU上，这些阶段将被管道化，这意味着它们通常都会并行进行-但对于任何给定时刻的不同指令。您可以在维基百科上阅读一些关于此的内容，但请记住，现代CPU更加复杂，通常具有许多更多的阶段。

在现代x86上，由于复杂的可变长指令集而涉及许多管道“阶段”仅用于获取和解码指令，可能有半打或更多个。这样的指令也是超标量的，能够同时执行多条指令。这意味着在执行时，将有许多指令正在飞行，处于获取、解码、执行等各个阶段。

重定向获取

当一个分支被执行时，其影响将在流水线的整个初始部分（通常称为前端）中感知：当你跳转到一个新地址时，需要从该新地址获取、解码等。我们说，一个已执行的分支需要“重定向取指”。这对分支预测可以使用的信息施加了一定的限制，以使其能够高效执行。

考虑静态预测的工作原理：它查看指令，如果是分支，则比较其目标地址以确定其是“向前”还是“向后”。所有这些都必须在大部分解码发生之后才能进行，因为那时才知道实际指令。然而，如果检测到一个分支并且预测其为已执行（例如，向后跳转），则预测器需要重定向取指，这要早得多。在解码指令N之后重定向取指时，已经有许多后续指令在错误的（未执行）路径上被获取和解码。这些必须被丢弃。我们说，在前端引入了一个“气泡”。

总之，即使静态预测是100%正确的，在已执行分支的情况下，其效率也非常低下，因为前端流水线被破坏了。如果在取指和解码结束之间有6个流水线阶段，那么每个已执行的分支都会在流水线中引入一个6个周期的气泡，这是基于预测本身和清除错误路径指令需要“零周期”的慷慨假设。

动态预测挽救了这一局面。

现代x86 CPU能够在每个周期执行一次分支，比静态预测的限制好得多。为了实现这一点，预测器通常不能使用解码后可用的信息，必须能够每个周期重定向抓取，并且仅使用上一个预测后一个周期才能获得的输入。基本上，这意味着预测器是一个完全自包含的流程，仅使用其自己的输出作为下一个周期预测的输入。

这就是大多数CPU上的动态预测器。它预测下一个周期从哪里获取，然后根据该预测预测下一个周期从哪里获取，依此类推。它不使用任何有关解码指令的信息，而只使用分支的过去行为。它最终会从执行单元中获得反馈，关于分支的实际方向，并根据此更新其预测，但这些都是异步发生的，许多周期后才通过预测器。

所有这些都有助于削弱静态预测的有用性。首先，预测来得太晚，因此即使在完美工作时，对于Intel现代处理器的taken分支（确实是Intel所谓的“前端重定向”观察到的数字）也会产生6-8个周期的气泡。这极大地改变了做出任何预测的成本/效益方程。当您在抓取之前有一个动态预测器时，您想要进行一些预测，即使它只有51%的准确率，也可能会得到回报。

对于静态预测，如果你想进行“取出”预测，就需要高准确度。例如，在某个程序中，冷退回分支被采取的频率是不采取的两倍。这应该是静态分支预测的胜利，预测退回到正确状态（与默认策略相比，总是预测为未采取）。但要注意的是，如果假设重新转向成本为8个周期，全面错误预测成本为16个周期，则它们最终具有相同的混合代价，即10.67个周期。此外，不使用静态预测的情况已经将静态预测的另一半正确性（前向分支不采取的情况）得到了，所以静态预测的效用并不像人们想象的那么大。

为什么现在改变呢？也许是因为管道前端的部分长度与其他部分相比更长，或者因为动态预测器的性能和内存提高了，意味着更少的冷分支符合静态预测。改进静态预测器的性能还意味着对于冷分支而言，退回采取预测的力量会变得较弱，因为循环（这是退回采取规则的原因）更容易被动态预测器记住。

节省动态预测资源

这种变化可能是由于与动态预测的交互作用导致的：对于一个动态预测器的设计，不使用任何分支预测资源来处理从未被观察到的分支。由于这样的分支很常见，可以节省大量历史表和BTB空间。然而，这种方案与静态预测器不一致，因为静态预测器会将向后分支预测为已经被采取：如果向后分支从未被采取，您不希望静态预测器选择这个分支，并将其预测为已采取，从而破坏了节省资源以处理未采取分支的策略。

¹ ...然后做更多的事情，比如退休，但是执行之后大部分内容对我们在这里的目的并不重要。

² 我在这里加了“预测”的引号，因为从某种意义上来说，这甚至不算是预测：如果没有任何相反的预测，取指和译码的默认行为就是不取，所以如果你根本没有输入任何静态预测，并且你的动态预测也没有告诉你相反的结果，那么你得到的就是默认的结果。