分支预测失误是否会刷新整个管道,即使是很短的if语句体



我所读到的一切似乎都表明,分支预测失误总是导致整个管道被刷新,这意味着浪费了很多周期。我从来没有听过任何人提到任何简短的if条件的例外情况。

在某些情况下,这似乎真的很浪费。例如,假设您有一个单独的if语句,它有一个非常简单的主体,它被编译为1条CPU指令。if子句将被编译为一条指令的条件前跳。如果CPU预测不执行分支,则它将开始执行If主体指令,并可以立即开始执行以下指令。现在,一旦对if条件的评估到达管道的末端,也就是说,12个周期后,CPU现在就知道它的预测是对是错了。如果它预测错误,而分支实际上被占用了,那么CPU实际上只需要从管道中丢弃1条指令(If主体中的指令)。然而,如果它刷新了整个管道,那么根据以下说明所做的所有工作也都被浪费了,并且将不得不毫无理由地重复。在一个深度管道化的体系结构上,这是大量浪费的循环。

那么,现代CPU是否有任何机制可以只丢弃短if体中的少数指令呢?或者它真的会冲洗整个管道吗?如果是后者,那么我想使用条件移动指令会获得更好的性能。顺便说一句,有人知道现代编译器是否擅长将简短的if语句转换为cmov指令吗?

大多数通用处理器都会在分支预测失误时刷新管道。除了对分支预测(以及其他技术)的广泛研究外,条件分支对性能的负面影响还促使人们提出了热切执行(两条路径都被执行,稍后选择正确的路径)和动态预测(预测分支阴影中的指令)的建议。(Mark Smotherman关于渴望执行的页面提供了一些细节和参考。我想添加Hyesoon Kim等人的《愿望分支:将条件分支和预测相结合用于自适应预测执行》,2005年,作为一篇重要的论文。)

IBM的POWER7似乎是第一个实现比预取备用路径(即渴望获取)更复杂的功能的主流处理器,而且它只处理单个指令情况。(POWER7使用分支预测置信度估计来选择是断言还是使用预测。)

急切的执行具有资源使用爆炸式增长的明显问题。即使有基于分支预测置信度、推测深度和资源可用性(前端可用的信息)的选择性渴望,在单一路径上进行更深入的推测也很容易更有效。发现多条路径的连接点并避免过多的冗余计算也会增加复杂性。(理想情况下,独立于控制的操作只执行一次,连接和数据流将得到优化,但这种优化增加了复杂性。)

对于深度流水线有序处理器来说,预测短的前向分支为未执行,并且在实际执行分支时仅在流水线中向后刷新执行分支所针对的指令,这似乎很有吸引力。如果管道中一次只允许一个这样的分支(其他分支使用预测),则向每条指令添加一个比特可以控制它是转换为nop还是执行。(如果只处理单个指令被分支的情况,那么在管道中允许多个分支可能不会特别复杂。)

如果采用分支延迟时隙,这将类似于取消。MIPS有"分支可能性"指令,如果,则这些指令将被废除,并且在2.62版中被标记为过时。虽然这样做的一些理由可能是将实现与接口分离,并希望恢复指令编码空间,但这一决定也暗示了该概念存在一些问题。

如果对所有短正向分支都这样做,那么当分支被正确预测为已执行时,它将丢弃指令。(请注意,如果采取的分支在获取重定向时总是遇到延迟,那么这种惩罚可能会更小,这在深度流水线处理器中的多周期指令缓存访问中更可能发生。在这种情况下,像没有分支一样进行获取可能与正确预测的采取分支具有相同的性能en分支,以最大限度地减少这种提取气泡。)

作为一个例子,考虑一个标量管道(每个周期的非分支指令等于1.0),在第八阶段结束时具有分支分辨率,并且在正确预测的执行分支上没有获取重定向惩罚,处理单指令分支切换。假设这种短正向分支的分支预测器准确率为75%(按方向无偏)(2%的指令,占用30%的时间),而其他分支的准确率为93%(18%的指令)。对于预测错误为已执行的短分支(占此类分支的17.5%;占指令的0.35%),将节省8个周期,预测错误为未执行的分支将节省7个周期(7.2%;0.144%),正确预测为已执行时将丢失一个周期(22.5%;0.45%)。每条指令总共将节省0.03358个周期。如果没有这种优化,每条指令的周期将是1.2758。

(虽然以上数字只是示例,但除了非分支指令的1.0 IPC之外,它们可能与现实并不遥远。提供小循环缓存将减少预测失误的惩罚(并在短循环中节省电力),因为指令缓存访问可能是八个周期中的三个。添加缓存未命中的影响将进一步降低此分支优化的改进百分比。避免预测的"强占用"短分支的开销可能是值得的。)

按顺序设计倾向于使用狭窄和较浅的管道,并且更喜欢简单(为了降低设计、功率和面积成本)。由于指令集可能在许多短分支情况下支持无分支代码,因此进一步降低了优化这一方面的动机。

对于无序实现,由于处理器希望能够执行以后的非依赖指令,因此必须预测可能分支的指令。谓词引入了一个额外的数据依赖项,必须对其进行调度检查。指令调度器通常只为每条指令提供两个比较器,并拆分一个条件移动(一条只有三个数据流操作数的简单指令:旧值、替代值和条件;一个预测寄存器寄存器相加将有四个操作数

当分支条件不可用时,无序的实现也不会停滞。这是控制依赖性和数据依赖性之间的折衷。对于精确的分支预测,控制依赖性非常便宜,但数据依赖性可以阻碍等待数据操作数的前进。(当然,对于布尔数据依赖性,值预测变得更有吸引力。在某些情况下,使用谓词预测可能是可取的,并且与使用动态成本和置信度估计的简单预测相比具有优势。)

(ARM选择在64位AArch64中放弃广泛的预测,这或许说明了问题。虽然其中很大一部分用于指令编码,但预测对高性能实现的好处可能相对较低。)

编译器问题

无分支代码与分支代码的性能取决于分支的可预测性和其他因素(如果采用,包括重定向获取的任何惩罚),但编译器很难确定分支的可预见性。即使是简档数据通常也只提供分支频率,其可以给出对可预测性的悲观看法,因为这不考虑使用局部或全局历史的分支预测器。编译器也不能完全意识到数据可用性的定时和其他动态方面。如果条件比用于计算的操作数晚可用,则用数据依赖性(预测)替换控制依赖性(分支预测)可能会降低性能。无分支代码也可能引入更多的有效值,可能会增加寄存器溢出和填充开销。

更为复杂的是,大多数只提供条件移动或选择指令的指令集不提供条件存储。虽然这可以通过使用条件移动来选择一个安全的、被忽略的存储位置来解决,但这似乎是一个没有吸引力的复杂问题。此外,条件移动指令通常比简单的算术指令更昂贵;加法和条件移动可能需要三个循环,其中正确预测的分支和加法将需要零(如果加法被分支)或一个循环。

更复杂的是,预测运算通常被分支预测器忽略。如果稍后保留的分支与删除的分支的条件相关,则该稍后分支的分支预测错误率可能会增加。(谓词预测可用于保留此类删除分支的预测效果。)

随着对矢量化的日益重视,无分支代码的使用变得更加重要,因为基于分支的代码限制了对整个向量使用运算的能力。

现代高性能无序CPU通常不会在预测失误时刷新整个管道0,但它并不像您建议的那样真正取决于分支或工作的距离。

它们通常使用类似于刷新分支指令和所有较年轻指令的策略。前端被刷新,这将充满预测错误路径上的指令,但在前端之外,现代核心可能同时有100多条指令在运行,其中只有一些可能比分支更年轻。

这意味着分支的成本至少部分与周围的指令有关:如果分支条件可以在早期检查,则错误预测的影响可以是有限的,甚至为零1。另一方面,如果分支条件处理较晚,在将大量资源花费在错误的路径上之后,成本可能会很大(例如,大于您经常看到的12-20周期"发布"的分支预测失误惩罚)。


0确切的术语在这里还有待商榷:冲洗管道的含义对于乱序处理器来说并不完全清楚。这里我的意思是,CPU不会刷新所有飞行中的指令,但可能不会执行指令。

1特别是,某些指令序列的限制因素可能是依赖链,该依赖链的当前执行远远落后于指令窗口的前沿,因此预测失误不会刷新任何这些指令,也不会减慢代码的速度。

"如果它预测错误,而分支实际上被占用了,那么CPU实际上只需要丢弃管道中的1条指令(if主体中的指令)。">

这并不像你说的那么容易。指令修改其他指令所依赖的体系结构中的各种不同状态(寄存器结果、条件标志、内存等)。当你意识到你预测错误时,你可能会在管道中有大量的指令,这些指令已经根据该指令和管道中所有后续指令所改变的状态开始执行。。。更不用说可能引发故障/异常的说明了。

一个简单的例子:

b = 0
f (a == 0) {
b = 1;
}
c = b * 10;
if (b == 0)
printf("nc = %d.",c);
foo(b);
etc..

要撤消"一个简单的指令"需要做大量的工作。

对于可预测性较差的简单分支,首选diction/cmovs/等。

至少在大多数处理器中,预测失误的分支会刷新整个管道。

这在很大程度上解释了为什么许多(大多数?)当前处理器也提供预测指令。

在ARM上,大多数指令都是谓词的,这意味着指令本身可以包括一个条件,本质上说,"做X,但前提是以下条件为真。">

同样,x86/x64的最近迭代包括一些谓词指令,例如"CMOV"(条件移动),其工作方式相同——只有在满足条件时才执行指令。

这些指令不会刷新管道——指令本身总是流经管道。如果不满足条件,说明基本上没有任何效果。不利的一面是,指令需要执行时间,即使它们没有效果。

因此,在您所说的(一个具有微小主体的if语句)只能在几个指令中实现的情况下,您可以将这些指令实现为谓词指令。

如果正文包含足够的指令(大致相当于指令管道的大小,乘以某个常数因子),那么使用条件跳转就更有意义了。

相关内容

最新更新