分支错误预测是否会冲洗整个管道,即使是非常短的if语句主体？

Question

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

这似乎在某些情况下会非常浪费.例如,假设您有一个单独的if语句,其中包含一个非常简单的主体,该主体被编译为1个CPU指令.if子句将被编译为一条指令的条件跳转.如果CPU预测分支不被采用,则它将开始执行if-body指令,并可立即开始执行以下指令.现在,一旦if条件的评估已经到达管道的末端,也就是说,例如,12个周期之后,CPU现在知道它的预测是对还是错.如果它被错误预测,并且分支实际被占用,则CPU实际上只需要丢弃来自管道的1条指令(if-body中的指令).但是,如果它刷新整个管道,那么在以下指令中完成的所有工作也都被浪费了,并且必须无缘无故地重复.这是一个深度流水线架构上浪费的大量周期.

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

Answer 1

大多数通用处理器会在分支错误预测上冲洗管道.除了对分支预测进行广泛研究之外,条件分支的负面性能影响推动了热切执行的建议(其中两条路径都被执行并且后面选择了正确的路径)和动态预测(分支阴影中的指令被预测)的建议(以及作为其他技术).(Mark Smotherman关于热切执行的页面提供了一些细节和参考资料.我将添加Hyesoon Kim等人的"愿望分支:结合条件分支和自适应预测执行的预测",2005年,作为重要论文.)

IBM的POWER7似乎是第一个实现比预取备用路径(即,急切获取)更复杂的主流处理器,它只处理单个指令案例.(POWER7使用分支预测置信度估计来选择是否预测或使用预测.)

急切执行有明显的资源使用爆炸性问题.即使基于分支预测置信度,投机深度和资源可用性(前端可用信息)的选择性渴望,也可以更加有效地推测单个路径的更深层次.发现多个路径的连接点并避免过多的冗余计算也会增加复杂性.(理想情况下,控制独立操作只会执行一次,并且会优化连接和数据流,但这种优化会增加复杂性.)

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

这类似于annul-if-taken分支延迟时隙.MIPS具有"分支可能"指令,如果不采用则取消,并且在版本2.62中标记为已过时.虽然这样做的一些理由可能是将实现与接口分开以及恢复指令编码空间的愿望,但这一决定也暗示该概念存在一些问题.

如果对所有短前向分支执行此操作,则在正确预测分支时将丢弃指令.(请注意,如果采用的分支始终在获取重定向中遇到延迟,这种惩罚可能会更少,这在深度流水线处理器中使用多周期指令缓存更有可能.在这种情况下,读取就好像没有分支一样具有与正确预测的采用分支相同的性能.然而,有人可能会争辩说处理器特殊情况下这样短的分支以最小化这种获取气泡.)

例如,考虑一个标量流水线(每个周期的非分支指令等于1.0),在第八阶段结束时具有分支分辨率,并且在正确预测的采用分支上没有获取重定向惩罚,处理单指令分支.对于这样的短前向分支(占指令的2%,占30%的时间)和其他分支(占指令的18%)的准确率为93%,假设分支预测准确度为75%(不受方向影响).对于短分支将保存8个周期,这些分支将被错误预测(17.5%的此类分支; 0.35%的指令),7个周期,当错误预测为未采用(7.2%; 0.144%),并且正确时会丢失一个周期预测为(22.5%; 0.45%).每条指令总共可保存0.03358个周期.如果没有这种优化,每条指令的周期将为1.2758.

(虽然上面的数字仅仅是例如,它们可能与现实相差不远,除了非IPC分支指令的1.0 IPC.提供一个小的循环缓存可以减少错误预测惩罚(并在短循环中节省功耗),因为指令缓存访问可能是八个周期中的三个周期.添加缓存未命中的影响将进一步降低此分支优化的百分比改善.避免预测的"强烈采用"短分支的开销可能是值得的.)

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

对于无序实现,必须预测可能分支的指令,因为处理器希望能够执行稍后的非依赖指令.预测引入了额外的数据依赖性,必须对其进行检查以进行调度.指令调度程序通常每条指令只提供两个比较器并分割条件移动(只有三个数据流操作数的简单指令:旧值,替代值和条件;谓词寄存器寄存器添加将具有四个操作数.(有其他方法可以解决这个问题,但这个答案已经很长了.)

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

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

编译器问题

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

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

进一步的复杂性是分支预测器通常忽略预测操作.如果稍后保留的分支与移除的分支的条件相关,则对于该后一分支,分支错误预测率可能增加.(谓词预测可用于保留此类已删除分支的预测效果.)

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

Answer 2

现代高性能乱序 CPU 通常不会在错误预测时刷新整个管道⁰，但它并不真正取决于分支的距离或您建议的工作。

他们通常使用类似于刷新分支指令和所有新指令的策略。该前端被刷新，这这将是完全的误预测路径上的说明，但除此之外的前端现代核一次可飞行指令100多条，其中只有一些可能比分支更年轻。

这意味着分支的成本至少部分与周围的指令相关：如果可以及早检查分支条件，则错误预测的影响可以被限制甚至为零¹。另一方面，如果分支条件处理得晚，在错误的路径上花费了大量资源之后，成本可能会很大（例如，大于 12-20 个周期的“发布”分支错误预测惩罚，您经常会看到）。

⁰确切的术语在这里有待讨论：对于乱序处理器，刷新管道的含义并不完全清楚。这里我的意思是 CPU 不会刷新所有正在执行但可能未执行的指令。

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