art*_*ter 3 x86 assembly prefetch
我有一个相当重要的问题,我的计算图有周期和多个"计算路径".我没有做一个调度程序循环,每个顶点将被逐个调用,我有一个想法是将所有预先分配的"框架对象"放在堆中(代码+数据).
这有点类似于线程代码(甚至更好:CPS),只是在堆中跳转,执行代码.每个代码段与堆中自己的"帧指针"相关联,并使用与之相关的数据.帧始终保持分配状态.代码只在已知位置产生副作用,计算(如果需要)下一个goto值并跳转到那里.
我还没有尝试过(这将是一个重要的事情,使它正确,我完全意识到所有的困难)所以我想问x86机械专家:它能比调度程序循环更快吗？我知道在硬件中进行的调用/返回指令有几种优化.
访问相对于堆栈指针的数据或任何其他指针之间有区别吗？是否有预取间接跳转(跳转到存储在寄存器中的值？).
这个想法是否可行？
PS如果你已经读过这个并且仍然无法理解这个想法的意思(原谅我尝试解释事情的失败)想象这整个就像是一堆堆上的预先分配的协同程序,彼此相互影响.标准x86堆栈未在进程中使用,因为所有内容都在堆上.
直接从一个块跳到另一个块通常是分支预测的胜利,而不是返回到一个父间接分支,特别是在比Intel Haswell更早的CPU上.
通过从每个块的尾部跳转,每个分支具有不同的分支预测器历史.通常,给定块通常跳转到相同的下一个块,或者具有一对目标地址的简单模式.这通常可以很好地预测,因为每个分支单独具有更简单的模式,并且分支历史分布在多个分支上.
如果从单个间接分支发生所有调度,则可能只有一个BTB(分支目标缓冲区)条目,并且该模式将太复杂而无法很好地预测.
英特尔Haswell中的现代TAGE分支预测器以及稍后使用最近的分支历史(包括间接分支目标)对BTB进行索引确实解决了这个问题.请参阅有关X86 64位模式的索引分支开销的注释,并在https://danluu.com/branch-prediction/中搜索Haswell
具体而言,Rohou,Swamy和Seznec的分支预测和口译员表现 - 不信任民俗(2015)比较Nehalem,SandyBridge和Haswell的翻译基准,并用单一switch陈述测量调度循环的实际误预测率.他们发现Haswell做得更好,可能使用ITTAGE预测器.
他们不测试AMD CPU. 自从Piledriver使用Perceptron神经网络进行分支预测以来,AMD发布了一些有关其CPU的信息.我不知道他们用一个间接分支处理调度循环的程度如何.
Darek Mihocka 在解释CPU仿真器的上下文中讨论了这种模式,该仿真器针对不同的指令(或简化的uop)从一个块跳转到另一个处理程序块.他详细介绍了Core2,Pentium4和AMD Phenom上各种策略的性能.(它写于2008年).当前CPU的现代分支预测器最像Core2.
他最终以分支预测友好的方式呈现了他所谓的Nostradamus Distributor模式,用于检查提前输出(函数返回函数指针或"火灾逃生"哨兵).如果您不需要,请参阅文章的前半部分,他将讨论块与中央分配器之间的跳转直接链接.
他甚至哀叹x86中缺少代码预取指令.这对Pentium 4来说可能是一个更大的问题,与从跟踪缓存运行相比,填充跟踪缓存的初始解码速度非常慢.Sandybridge-family有一个解码的uop缓存,但它不是一个跟踪缓存,而且当uop缓存未命中时,解码器仍然足够强大,不会吮吸.Ryzen很相似.
访问相对于堆栈指针的数据或任何其他指针之间有区别吗？
不.你甚至可以rsp在跳跃后进行设置,这样每个块都可以拥有自己的堆栈.如果安装了任何信号处理程序,则rsp需要指向有效内存.此外,如果您希望能够使用call任何普通的库函数,则需要rsp将其作为堆栈指针,因为它们需要ret.
是否有预取间接跳转(跳转到存储在寄存器中的值？).
如果在准备执行间接跳转之前很久就知道了分支目标地址,那么预取入L2会很有用.所有当前的x86 CPU都使用拆分的L1I/L1D高速缓存,因此prefetcht0会污染L1D以获得无增益,但prefetcht1可能很有用(获取到L2和L3).如果代码在L2中已经很热,那么它可能根本没用.
同样有用:尽可能早地计算跳转目标地址,因此无序执行可以解析分支,而大量工作在无序核心排队.这最大限度地减少了管道中的潜在气泡.如果可能,保持计算独立于其他东西.
最好的情况是寄存器中的许多指令之前的地址jmp,因此只要jmp在执行端口上获得一个循环,它就可以为前端提供正确的目的地(并且如果分支预测错误则重新引导).最糟糕的情况是分支目标是分支之前的长指令依赖链的结果.一对独立指令和/或内存间接跳转很好; 无序执行应该在GPU调度程序中找到运行这些指令的周期.
还有分裂的L1iTLB和L1dTLB,但L2TLB通常在大多数微体系结构上统一.但是IIRC,L2TLB作为L1 TLB的受害者缓存.预取可能会触发页面遍历以填充L1数据TLB中的条目,但是在一些无法避免iTLB未命中的微体系结构上.(至少它会将页表数据本身放入L1D或者页面遍历硬件中的内部页面目录高速缓存中,因此同一条目的另一个页面遍历会很快.但是,因为除了英特尔Skylake(及更高版本)以外的CPU只有1个硬件页面遍历单元,如果在第一页行走仍然发生时发生iTLB未命中,它可能无法立即启动,所以如果你的代码如此分散以至于你得到了iTLB未命中,那么实际上会受到伤害.)
使用2MB大页面为JIT进入的内存块减少TLB未命中.可能最好将代码放在一个相当紧凑的区域,数据是分开的.DRAM局部效应是真实的.(我认为,DRAM页面通常大于4kiB,但它是硬件,你无法选择.在已经打开的页面中访问的延迟较低.)
请参阅Agner Fog的microarch pdf,以及英特尔的优化手册..(还有AMD的手册,如果你担心AMD CPU).查看x86标签wiki 中的更多链接.
这个想法是否可行？
应该是.
如果可能的话,当一个块总是跳转到另一个块时,通过使块连续来消除跳转.
数据的相对寻址很容易:x86-64具有RIP相对寻址.
您可以lea rdi, [rel some_label]从那里进行索引,或者直接对某些静态数据使用RIP相对寻址.
你将是JITting你的代码或其他东西,所以只需计算从当前指令末尾到要访问的数据的有符号偏移量,这就是你的RIP相对偏移量.在x86-64中,与位置无关的代码+静态数据很容易.