在CPU仿真中使用switch case时如何处理分支预测

Question

我最近在这里阅读了这个问题为什么处理排序数组比未排序数组更快？并且发现答案绝对令人着迷,在处理基于Data的分支时,它完全改变了我对编程的看法.

我目前有一个用C编写的相当基本但功能完备的解释型Intel 8080仿真器,操作的核心是一个256长的交换机案例表,用于处理每个操作码.我最初的想法是,这显然是最快的工作方法,因为操作码编码在整个8080指令集中并不一致,并且解码会增加很多复杂性,不一致性和一次性情况.一个装有预处理器宏的开关盒表非常整洁,易于维护.

不幸的是,在阅读上述帖子之后,我发现我的电脑中的分支预测器绝对没有办法预测开关盒的跳跃.因此,每次切换案例时,必须完全擦除管道,导致几个周期延迟,否则应该是一个非常快速的程序(在我的代码中甚至没有多次乘法).

我相信大多数人都在想"哦,这里的解决方案很简单,转向动态重新编译".是的,这看起来似乎会削减大部分开关盒并大大提高速度.不幸的是,我的主要兴趣是模拟旧的8位和16位时代控制台(这里的英特尔8080只是一个例子,因为它是我最简单的模拟代码),其中保持精确指令的周期和时序对于视频和声音很重要必须根据这些确切的时间进行处理.

当处理这种级别的准确性时,性能成为一个问题,即使对于旧的控制台(例如,查看bSnes).在处理具有长管道的处理器时,是否有任何追索权或者这仅仅是事实？

Answer 1

相反,switch语句可能会转换为跳转表,这意味着它们可能执行几个ifs(用于范围检查)和单个跳转.的if,因为它是不太可能你将有一个不好的操作码,不可以引起分支预测的问题.跳转对管道不太友好,但最后,它只是整个switch声明的一个..

我不相信你可以将长switch代码的操作码转换成任何其他可以提高性能的形式.当然,如果您的编译器足够智能,可以将其转换为跳转表.如果没有,您可以手动执行此操作.

如有疑问,请实施其他方法并衡量绩效.

编辑

首先,确保不要混淆分支预测和分支目标预测.

分支预测仅适用于分支语句.它决定分支条件是否会失败或成功.它们与跳转语句无关.

另一方面,分支目标预测试图猜测跳跃将在何处结束.

所以,你的陈述"分支预测器无法预测跳跃"应该是"分支目标预测器无法预测跳跃".

在您的特定情况下,我认为您实际上无法避免这种情况.如果您的操作非常少,也许您可​​以提出一个涵盖所有操作的公式,例如逻辑电路中的操作.但是,如果指令集与CPU一样大,即使它是RISK,该计算的成本也远高于单次跳转的代价.

Answer 2

由于256路交换机语句中的分支密集,编译器会将其实现为跳转表,所以你是正确的,每次你通过这个代码时你都会触发一个分支误预测(作为间接跳转)不会显示任何可预测的行为).与此相关的惩罚在现代CPU(Sandy Bridge)上约为15个时钟周期,或者在缺少微操作缓存的旧微架构上可能高达25个.对于这类事情的一个很好的参考是agner.org上的"软件优化资源"."用C++优化软件"中的第43页是一个很好的起点.

http://www.agner.org/optimize/?e=0,34

避免这种惩罚的唯一方法是确保执行相同的指令,而不管操作码的值如何.这通常可以通过使用条件移动(添加数据依赖性,因此比可预测的分支慢)或以其他方式在代码路径中寻找对称来完成.考虑到你正在尝试做什么,这可能是不可能的,如果是这样的话,它几乎肯定会增加一个大于15-25个时钟周期的错误预测的开销.

总而言之,在现代架构中,没有太多可以做到的事情比交换机/案例更有效率,错误预测分支的成本并不像您预期​​的那么多.

Answer 3

间接跳转可能是指令解码的最佳选择.

在较旧的机器上,比如说1997年的英特尔P6,间接跳跃可能会导致分支错误预测.

在像英特尔酷睿i7这样的现代机器上,有一个间接跳转预测器可以很好地避免分支错误预测.

但即使在没有间接分支预测器的旧机器上,您也可以发挥作用.顺便提一下,这个技巧是英特尔代码优化指南中记录的,从英特尔P6时代开始:

而不是生成看起来像的东西

    loop:
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_00h_ADD: ...
       jmp loop
    label_instruction_01h_SUB: ...
       jmp loop
    ...

生成代码为

    loop:
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_00h_ADD: ...
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_01h_SUB: ...
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    ...

即通过每个地方循环顶部的代码将跳转替换为指令获取/解码/执行循环的顶部.

事实证明,即使没有间接预测器,这也有更好的分支预测.更准确地说,一个有条件的,单个目标,PC索引的BTB在后一个,线程化的代码中比在原始时只有一个间接跳转的副本要好得多.

大多数指令集都有特殊的模式 - 例如在Intel x86上,比较指令几乎总是跟着一个分支.

祝好运并玩得开心点!

(如果你关心的话,工业中的指令集模拟器使用的指令解码器几乎总是做一个N路跳转树,或者数据驱动的双重导航,导航N路表的树,树中的每个条目都指向到其他节点,或到要评估的函数.

哦,也许我应该提一下:这些表,这些switch语句或数据结构都是由专用工具生成的.

一个N路跳转树,因为当跳转表中的个案数量变得非常大时会出现问题 - 在工具中,我在20世纪80年代写的mkIrecog(制作指令识别器),我通常会跳表达到64K条目大小,即跳过16位.当跳转表超过16M(24位)时,编译器的时间就破裂了.

数据驱动,即指向其他节点的节点树,因为(a)在较旧的机器上间接跳转可能无法很好地预测,并且(b)事实证明,大多数情况下指令之间存在公共代码 - 而不是当跳转到每条指令的情况,然后执行公共代码,然后再次切换,再次进行错误预测时,你会使用稍微不同的参数执行公共代码(例如,您消耗的指令流的位数,以及下一组要分支的位是(是).

我在mkIrecog中非常咄咄逼人,正如我所说的那样允许在交换机中使用多达32位,尽管实际限制几乎总是阻止我在16-24位.我记得我经常看到第一个解码为16或18位开关(64K-256K条目),所有其他解码都小得多,不超过10位.

嗯:我张贴mkIrecog入USENET回大约1990 ftp://ftp.lf.net/pub/unix/programming/misc/mkIrecog.tar.gz 您可以看到使用的表,如果你的关心.(善良:我当时很年轻.我不记得这是Pascal还是C.我已经多次重写过了 - 尽管我还没有改写它以使用C++位向量.)

我认识的其他大多数人做这类事情一次做一个字节 - 即8位,256路,分支或表查找.)