从这里我知道英特尔近年来实现了几种静态分支预测机制:
-
80486年龄:总是不服用
-
Pentium4年龄:向后/未向前
-
Ivy Bridge、Haswell等较新的CPU已经变得越来越无形,请参阅Matt G的实验。
英特尔似乎不想再谈论它了,因为我在英特尔文档中发现的最新材料是大约十年前写的。
我知道静态分支预测(远远?)不如动态分支预测重要,但在相当多的情况下,CPU将完全丢失,程序员(带编译器)通常是最佳指南。当然,这些情况通常不是性能瓶颈,因为一旦分支频繁执行,动态预测器就会捕获它
由于英特尔在其文档中不再明确说明动态预测机制,GCC的内置_expect()只能从热路径中删除不太可能的分支。
我不熟悉CPU的设计,也不知道英特尔现在对其静态预测器使用的确切机制是什么,但我仍然觉得英特尔最好的机制应该是清楚地记录他的CPU"当动态预测器出现故障时,我计划去哪里,向前或向后",因为通常程序员是当时最好的指导。
更新:
我发现你提到的话题逐渐超出了我的知识范围。这里涉及到一些动态预测机制和CPU内部细节,我在两三天内无法了解。所以请允许我暂时退出你的讨论,重新充电
这里仍然欢迎任何答案,也许会帮助更多的人
静态预测在现代设计中不受欢迎,甚至可能不存在的主要原因是,与动态预测相比,静态预测在管道中发生得太晚。基本问题是,在提取分支方向和目标位置之前,必须知道它们,但静态预测只能在decode(在提取之后)之后进行。
更详细地说。。。
CPU流水线
简而言之,在执行过程中,需要从内存中提取指令,解码这些指令,然后执行它们1。在高性能CPU上,这些阶段将是流水线,这意味着它们通常都将并行发生,但在任何给定时刻都适用于不同的指令。你可以在维基百科上读到一些关于这方面的内容,但请记住,现代CPU更复杂,通常有更多的阶段。
在现代x86上,有一个复杂的可解码可变长度指令集,可能有许多管道"阶段"只涉及获取和解码指令,可能有六个或更多。这样的指令也是超标量的,能够同时执行多个指令。这意味着,当以最高效率执行时,将有许多指令在飞行中,处于被提取、解码、执行等各个阶段
重定向获取
执行分支的影响会影响到管道的整个初始部分(通常称为前端):当你跳到一个新地址时,你需要从该新地址提取,从该新位置解码,等等。我们说执行分支需要重定向提取。这对分支预测可以使用的信息施加了某些限制,以便有效地执行。
考虑一下静态预测是如何工作的:它查看指令,如果它是一个分支,则比较其目标,看看它是"向前"还是"向后"。所有这些都必须在解码发生后发生,因为那是已知实际指令的时候。然而,如果检测到分支并预测其执行(例如,向后跳转),则预测器需要重定向获取,这要早于许多管道阶段。在解码指令N
之后重新定向提取时,已经有许多后续指令在错误的(未执行的)路径上被提取和解码。那些必须扔掉。我们说在前端引入了气泡。
所有这些的结果是,即使静态预测是100%正确的,在采用分支的情况下也是非常低效的,因为前端流水线被击败了。如果在获取和解码结束之间有6个管道阶段,则每个执行的分支都会在管道中产生6个周期的气泡,并假定预测本身和清除坏路径指令需要"零个周期"。
救援动态预测
然而,现代的x86 CPU能够在每个周期以高达1的速度执行占用的分支,即使对于完全预测的静态执行来说,也比限制要好得多。为了实现这一点,预测器通常不能使用解码后可用的信息。它必须能够在每个周期重定向提取,并且只使用在上次预测后一个周期延迟的可用输入。本质上,这意味着预测器基本上是一个独立的过程,它只使用自己的输出作为下一个周期预测的输入。
这是大多数CPU上的动态预测器。它预测从下一个循环中提取的位置,然后基于该预测预测从下个循环中获取的位置,依此类推。它不使用任何关于解码指令的信息,只使用分支过去的行为。它最终会从执行单元获得关于分支的实际方向的反馈,并在此基础上更新其预测,但这一切基本上都是异步发生的,在相关指令通过预测器后的许多周期内。
将其相加
所有这些都削弱了静态预测的有用性。
首先,预测来得太晚了,所以即使工作得很好,这也意味着现代英特尔的分支机构将出现6-8个周期的泡沫(事实上,这些都是从英特尔所谓的"前端rester"中观察到的数据)。这大大改变了进行预测的成本/效益等式。当你在提取预测之前有一个动态预测器时,你或多或少地想做一些预测,如果它的准确率达到51%,它可能会有回报
然而,对于静态预测,如果你想做出"实际"预测,你需要有高精度。例如,考虑8个周期的前端rester成本,而16个周期的"完全预测失误"成本。假设在某个程序中,冷反向分支的执行频率是未执行的两倍。这应该是预测向后采取的静态分支预测的胜利,对吧(与总是"预测">2不采取的默认策略相比)?
不要那么快!如果你假设8个周期的重新引导成本和16个周期的完全预测失误成本,它们最终会产生10.67个周期的相同混合成本,因为即使在正确预测的情况下,也会出现8个周期泡沫,但在贯穿性情况下,没有静态预测的情况也没有相应的成本。
再加上无静态预测的情况已经使另一半的静态预测正确(前向分支未采用的情况),静态预测的效用并不像人们想象的那么大。
为什么现在要改变?也许是因为与其他部分相比,管道的前端部分已经加长,或者是因为动态预测器的性能和内存的增加意味着更少的冷分支有资格进行静态预测。提高静态预测器的性能也意味着,对于冷分支,后取预测变得不那么强,因为循环(这是后取规则的原因)更频繁地被动态预测器记住。
节省动态预测资源
这种变化也可能是因为与动态预测的交互作用:动态预测器的一种设计是,对于从未被观察到的分支,根本不使用任何分支预测资源。由于这样的分支很常见,因此可以节省大量的历史表和BTB空间。然而,这样的方案与将向后分支预测为已执行的静态预测器不一致:如果从未执行向后分支,则您不希望静态预测器拾取该分支,并将其预测为已完成,从而打乱了为未执行分支节省资源的策略。
1。。。然后做更多的事情,比如退休,但执行后发生的事情对我们这里的目的来说并不重要。
2我把"预测"放在这里的恐吓引号里,因为在某种程度上它甚至不是预测:在没有任何相反预测的情况下,不采取是获取和解码的默认行为,所以如果你根本不进行任何静态预测,而你的动态预测器不会告诉你其他情况,那就是你得到的。
《英特尔优化手册》第3.4.1.3节中讨论的静态分支预测如下:
- 预测要执行的无条件分支
- 预测不执行的条件正向分支
- 预测要执行的条件后向分支
- 预测不采用的间接分支
编译器可以相应地组织代码。同一部分说:
英特尔酷睿微体系结构不使用静态预测启发式。但是,为了在英特尔64和IA-32之间保持一致性处理器,软件应该保持静态预测启发式作为默认值。
此声明表明第3.4.1.3节已多年未更新。
如果动态预测器未能预测在所提取的字节中存在分支指令,或者如果其缓冲区中发生未命中,则提取单元将仅按顺序继续提取,因为没有其他有意义的选择,从而有效地进行Not Take的静态预测。
然而,如果在指令队列单元中,在提取的字节流中存在条件或间接分支指令,那么在这一点上,进行一个可能比Not Take更好的静态预测是有意义的。特别是预测有条件的直接后向分支Taken。这可以减少动态预测器和Not Take获取单元失败的代价,尤其是在前端的性能非常关键的情况下。据我所知,优化手册中没有明确的说明IQU有这样的静态预测器,这适用于现代处理器。然而,正如我在另一个答案中所讨论的,一些性能计数器的描述似乎意味着IQU中可能存在这样的静态预测因素。
总的来说,我认为这是英特尔不再记录的实现细节。
编译器辅助的动态分支预测技术确实存在,并且如您所建议的那样非常有用,但目前的英特尔处理器中尚未使用这些技术。
我的理解是,在当前的设计中,现代TAGE分支方向预测器总是使用最近分支的已执行/未执行历史来索引一个条目。(这可能会将单个分支的状态扩展到许多内部状态,从而可以预测非常复杂的模式,如10元素的BubbleSort。)
CPU不尝试检测混叠,只使用它找到的预测来决定条件分支是否执行。即分支方向预测总是动态的,而不是静态的。
但是在解码分支之前仍然需要目标预测,以防止前端停滞。分支目标缓冲区通常会被标记,因为别名的其他分支的目标不太可能有用。
正如@Paul A Clayton所指出的,BTB失误可能会让CPU决定使用静态预测,而不是在动态已采取/未采取预测器中发现的任何预测。我们可能只是看到,要使动态预测器经常遗漏,以测量静态预测要困难得多。
(我可能在歪曲事实。现代TAGE预测器也可以预测间接分支的复杂模式,所以我不确定他们是否试图根据已执行/未执行进行预测,或者第一步是否总是试图预测下一个地址,无论这是否是下一条指令。X86 64位模式上的索引分支开销。)
在正确预测的情况下,未执行的分支仍然稍微便宜一些,因为前端可以更容易地从uop缓存中在同一周期中获取较早和较晚的指令(Sandybridge系列中的uop缓存是而不是跟踪缓存;uop缓存行只能缓存来自x86机器代码的连续块的uop。)在高吞吐量代码中,占用的分支可能是一个较小的前端瓶颈。它们通常还将代码分布在更多的L1i和uop缓存行上。
对于间接分支,"默认"分支目标地址仍然是下一条指令,因此,如果不能简单地将一个真正的分支目标作为下一条指示,则在jmp rax
之后放置ud2
或其他东西可以很有用,以防误推测(尤其是在非代码中)。(尤其是最常见的一种。)
分支预测是CPU供应商不公布详细信息的"秘密酱汁">
英特尔实际上自己发布指令吞吐量/延迟/执行端口信息(通过IACA和一些文档),但实验测试相当简单(比如https://agner.org/optimize/和http://instlatx64.atw.hu/已经这样做了),所以即使英特尔愿意,他们也不能保守这个秘密
分支预测成功率很容易用性能计数器来衡量,但很难知道为什么一个特定的分支在一次特定的执行中被错误预测或没有被预测;对于一个分支的单个执行来说,即使是测量也很困难,除非您使用rdtsc
或rdpmc
之类的工具来插入代码。