Intel SnB家族CPU中涉及微码指令的循环分支对齐

28
这与此问题相关,但并不相同:x86-64汇编的性能优化 - 对齐和分支预测,与我的上一个问题略有关联:无符号64位转换为双精度:为什么来自g ++的算法 以下是非真实世界测试用例。这个素数测试算法是不明智的。我怀疑任何现实世界的算法都不会执行这么多次如此小的内部循环(num是大小约为2 ** 50的素数)。在C++11中:
using nt = unsigned long long;
bool is_prime_float(nt num)
{
   for (nt n=2; n<=sqrt(num); ++n) {
      if ( (num%n)==0 ) { return false; }
   }
   return true;
}

然后,g++ -std=c++11 -O3 -S 产生以下结果,其中RCX包含n,XMM6包含sqrt(num)。请参见我的先前帖子以获取其余代码(在此示例中永远不会执行,因为RCX永远不会变得足够大而被视为有符号负数)。
jmp .L20
.p2align 4,,10
.L37:
pxor    %xmm0, %xmm0
cvtsi2sdq   %rcx, %xmm0
ucomisd %xmm0, %xmm6
jb  .L36   // Exit the loop
.L20:
xorl    %edx, %edx
movq    %rbx, %rax
divq    %rcx
testq   %rdx, %rdx
je  .L30   // Failed divisibility test
addq    $1, %rcx
jns .L37
// Further code to deal with case when ucomisd can't be used

我使用std::chrono::steady_clock计时。我一直遇到奇怪的性能变化:只要添加或删除其他代码。我最终发现这是一个对齐问题。命令.p2align 4,,10尝试将其对齐到2 ** 4 = 16字节边界,但最多只使用10个字节的填充来实现,我猜是为了在对齐和代码大小之间取得平衡。
我编写了一个Python脚本来用手动控制的nop指令替换.p2align 4,,10。下面的散点图显示了20次运行中最快的15次,时间以秒为单位,字节填充数在x轴上: Scatter plot 从没有填充的objdump中,pxor指令将出现在偏移量0x402f5f处。在笔记本电脑上运行,Sandybridge i5-3210m,禁用turboboost,我发现:
  • 对于0字节填充,性能较慢(0.42秒)
  • 对于1-4字节填充(偏移量为0x402f60至0x402f63),获得略微更好的性能(0.41秒,在图中可见)。
  • 对于5-20字节填充(偏移量为0x402f64至0x402f73),获得快速性能(0.37秒)
  • 对于21-32字节填充(偏移量为0x402f74至0x402f7f),性能较慢(0.42秒)
  • 然后在32字节样本上循环
因此,16字节对齐不会提供最佳性能--它将我们放在略微更好的区域(或者只是从散点图中减少了变化)。对齐32加4到19可以获得最佳性能。

为什么我会看到这种性能差异?为什么这似乎违反将分支目标对齐到16字节边界的规则(例如参见Intel优化手册)

我没有看到任何分支预测问题。这可能是一个uop缓存的怪癖吗?
通过将C ++算法更改为在64位整数中缓存sqrt(num),然后使循环纯粹基于整数,我消除了这个问题--对齐现在完全没有影响。

4
哦,算了吧。这个循环不适合于微操作缓存(uop cache),因为64位除法需要35-57个微操作(uops),它是用可变数量的微操作进行微代码编码的,所以我不知道它是如何存储在前端的。我会看看能否将其写成答案。 - Peter Cordes
2
@PeterCordes 我进行了10万次迭代的 dpps,我的计数器显示有70万个 uops,其中:idq.dsb_uops 499966284idq.ms_dsb_uops 200000595 - Iwillnotexist Idonotexist
2
@PeterCordes 哦,等等,我搞错了。我刚刚编写了一个 loop: div rcx; dec rcx; jne loop 循环,并将零除以计数器进行了 1 亿次迭代。这造成的损害是 37 亿个微操作,其中 32 亿个由微代码序列器馈入 DSB,0.5 亿个直接来自 DSB,没有来自 LSD。 - Iwillnotexist Idonotexist
2
@PeterCordes,说实话,这听起来像是在DSB中融合了100M uops的dec+jne,除法的前4个uop也存在于DSB中,但其余的32个uop则被MS所限制。再加上Haswell的除法是36个uop,并均匀分布在p0 p1 p5 p6(所有这些都有整数ALU,其中p6是预测取的分支的端口),这让我想到,在内部,除法执行高基数、每次迭代4个uop的循环,每次产生约8位商。 - Iwillnotexist Idonotexist
3
有趣的事实是,微码分支(例如 rep movs 启动过程)不受通常的分支预测硬件的动态分支预测影响(这就是为什么它即使在重复使用时也具有如此高的启动开销,正如原始P6 rep-string实现的设计者Andy Glew解释的那样)。据我所知,它们没有错误预测,因此也许微码分支是特殊的,而且没有被推测执行?显然它们可以有效地循环。 - Peter Cordes
显示剩余25条评论
4个回答

25

这是我在Skylake上找到的与同一循环相关的内容。所有的代码都在github上,您可以用自己的硬件进行测试。点击此处

我观察到基于对齐方式有三个不同的性能水平,而OP只看到两个主要的性能水平。这些水平非常明显和可重复2

enter image description here

我们可以从左到右将其分别称为区域1、2和3(区域2由跨越区域3的两个部分组成)。最快的区域(1)是从偏移0到8,中间(2)区域是从9-18和28-31,最慢的(3)是从19-27。 每个区域之间的差异接近或等于每次迭代的1个周期。

根据性能计数器,最快的区域与其他两个区域非常不同:

  • 所有指令都是从Legacy Decoder传递的,而不是从DSB1传递的。
  • 每次循环迭代都有恰好2个解码器<->微码开关(idq_ms_switches)。

另一方面,两个较慢的区域非常相似:

  • 所有指令都是从DSB(uop高速缓存)传递的,而不是从Legacy Decoder传递的。
  • 每次循环迭代都有恰好3个解码器<->微码开关。

从最快区域到中间区域的转变,随着偏移量从8变为9,正好对应于由于对齐问题而开始符合uop缓冲区的循环。您可以按照Peter在他的答案中所做的方式进行精确计算:

偏移量为8:

  LSD? <_start.L37>:
  ab 1 4000a8:  66 0f ef c0             pxor   xmm0,xmm0
  ab 1 4000ac:  f2 48 0f 2a c1          cvtsi2sd xmm0,rcx
  ab 1 4000b1:  66 0f 2e f0             ucomisd xmm6,xmm0
  ab 1 4000b5:  72 21                   jb     4000d8 <_start.L36>
  ab 2 4000b7:  31 d2                   xor    edx,edx
  ab 2 4000b9:  48 89 d8                mov    rax,rbx
  ab 3 4000bc:  48 f7 f1                div    rcx
  !!!! 4000bf:  48 85 d2                test   rdx,rdx
       4000c2:  74 0d                   je     4000d1 <_start.L30>
       4000c4:  48 83 c1 01             add    rcx,0x1
       4000c8:  79 de                   jns    4000a8 <_start.L37>

在第一列中,我已经注释了每个指令的uops如何进入uop缓存。"ab 1"表示它们进入与地址类似的集合中,例如...???a?...???b?(每个集合覆盖32个字节,即0x20),而1表示第1路(最多3路)。

到了!!!这一点,这就超出了uop缓存的限制,因为test指令没有地方可以去,所有3条路都被占用了。

另一方面,让我们看看偏移量为9的情况:

00000000004000a9 <_start.L37>:
  ab 1 4000a9:  66 0f ef c0             pxor   xmm0,xmm0
  ab 1 4000ad:  f2 48 0f 2a c1          cvtsi2sd xmm0,rcx
  ab 1 4000b2:  66 0f 2e f0             ucomisd xmm6,xmm0
  ab 1 4000b6:  72 21                   jb     4000d9 <_start.L36>
  ab 2 4000b8:  31 d2                   xor    edx,edx
  ab 2 4000ba:  48 89 d8                mov    rax,rbx
  ab 3 4000bd:  48 f7 f1                div    rcx
  cd 1 4000c0:  48 85 d2                test   rdx,rdx
  cd 1 4000c3:  74 0d                   je     4000d2 <_start.L30>
  cd 1 4000c5:  48 83 c1 01             add    rcx,0x1
  cd 1 4000c9:  79 de                   jns    4000a9 <_start.L37>

现在没问题了!test指令已滑入下一个 32B 行(cd 行),因此一切都适合于 UOP 缓存。

所以这解释了为什么 MITE 和 DSB 之间的内容会发生变化,但是它并没有解释为什么 MITE 路径更快。我尝试了一些简单的循环测试,例如在循环中使用 div 指令,您可以使用更简单的循环来重现这种情况,而不需要使用任何浮点数操作。这很奇怪并且对您在循环中放置的其他随机元素很敏感。

例如,这个循环在传统解码器中执行速度也比 DSB 更快:

ALIGN 32
    <add some nops here to swtich between DSB and MITE>
.top:
    add r8, r9
    xor eax, eax
    div rbx
    xor edx, edx
    times 5 add eax, eax
    dec rcx
    jnz .top

在那个循环中,加入无意义的add r8, r9指令,并不真正与循环的其余部分互动,使MITE版本的速度提高了(但不是DSB版本)。

因此,我认为区域1和区域2、3之间的差异是由前者在传统解码器中执行(奇怪的是,这使它更快)。


接下来,我们也来看一下从偏移量18到偏移量19的转换(即区域2结束并开始区域3):

偏移量18:

00000000004000b2 <_start.L37>:
  ab 1 4000b2:  66 0f ef c0             pxor   xmm0,xmm0
  ab 1  4000b6: f2 48 0f 2a c1          cvtsi2sd xmm0,rcx
  ab 1  4000bb: 66 0f 2e f0             ucomisd xmm6,xmm0
  ab 1  4000bf: 72 21                   jb     4000e2 <_start.L36>
  cd 1  4000c1: 31 d2                   xor    edx,edx
  cd 1  4000c3: 48 89 d8                mov    rax,rbx
  cd 2  4000c6: 48 f7 f1                div    rcx
  cd 3  4000c9: 48 85 d2                test   rdx,rdx
  cd 3  4000cc: 74 0d                   je     4000db <_start.L30>
  cd 3  4000ce: 48 83 c1 01             add    rcx,0x1
  cd 3  4000d2: 79 de                   jns    4000b2 <_start.L37>

偏移量 19:

00000000004000b3 <_start.L37>:
  ab 1 4000b3:  66 0f ef c0             pxor   xmm0,xmm0
  ab 1 4000b7:  f2 48 0f 2a c1          cvtsi2sd xmm0,rcx
  ab 1 4000bc:  66 0f 2e f0             ucomisd xmm6,xmm0
  cd 1 4000c0:  72 21                   jb     4000e3 <_start.L36>
  cd 1 4000c2:  31 d2                   xor    edx,edx
  cd 1 4000c4:  48 89 d8                mov    rax,rbx
  cd 2 4000c7:  48 f7 f1                div    rcx
  cd 3 4000ca:  48 85 d2                test   rdx,rdx
  cd 3 4000cd:  74 0d                   je     4000dc <_start.L30>
  cd 3 4000cf:  48 83 c1 01             add    rcx,0x1
  cd 3 4000d3:  79 de                   jns    4000b3 <_start.L37>

我看到唯一的区别在于偏移量为18的情况下前4条指令适配到ab缓存行,而偏移量为19的情况下只有3条。如果我们假设DSB只能从一个缓存集向IDQ传递uops,这意味着在某个时刻,在偏移量18的场景中可能会发出并执行一个uop,比在偏移量19的场景中早一个周期(例如,假设IDQ为空)。根据所在uop流的上下文准确跳转到哪个端口,这可能会延迟循环一个周期。实际上,区域2和3之间的差异约为1个周期(在误差范围内)。

因此,我认为我们可以说,2和3之间的差异可能是由于uop缓存对齐 - 区域2比3具有稍好的对齐方式,以在一个周期内更早地发出一个额外的uop。


关于我检查但未被证明是导致减速的可能原因的一些附加说明:

  • 尽管DSB模式(区域2和3)具有3个微代码开关,而MITE路径(区域1)是2个,但似乎并不会直接导致减速。特别地,使用div的简单循环执行相同的周期计数,但仍然显示DSB和MITE路径分别为3和2个开关。因此这是正常的,不直接暗示减速。

  • 两条路径执行基本相同数量的uops,并且特别地,具有相同数量的由微代码序列器生成的uops。因此,不像在不同区域中有更多的总工作量。

  • 在各种级别的缓存未命中(非常低,如预期)中,分支预测错误率(本质上为零3),或者我检查的任何其他类型的惩罚或异常情况中,实际上没有太大的差异。

真正有成果的是查看各个区域内执行单元使用的模式。以下是每周期执行的uop分布和一些停顿指标:

+----------------------------+----------+----------+----------+
|                            | Region 1 | Region 2 | Region 3 |
+----------------------------+----------+----------+----------+
| cycles:                    | 7.7e8    | 8.0e8    | 8.3e8    |
| uops_executed_stall_cycles | 18%      | 24%      | 23%      |
| exe_activity_1_ports_util  | 31%      | 22%      | 27%      |
| exe_activity_2_ports_util  | 29%      | 31%      | 28%      |
| exe_activity_3_ports_util  | 12%      | 19%      | 19%      |
| exe_activity_4_ports_util  | 10%      | 4%       | 3%       |
+----------------------------+----------+----------+----------+

我尝试了几种不同的偏移值,结果在每个区域内是一致的,但在不同的区域之间,结果却相当不同。特别是在区域1中,停顿周期(没有执行uop的周期)较少。非停顿周期也存在显著的差异,尽管没有明显的“更好”或“更差”的趋势。例如,区域1有许多执行4个uop的周期(10% vs 3%或4%),但其他区域往往通过更多执行3个uop的周期和很少执行1个uop的周期来弥补这一点。

上述执行分布中的UPC4差异充分解释了性能差异(这可能是一个类似自证明的道理,因为我们已经确认它们之间的uop计数是相同的)。

让我们看看toplev.py对此有何看法...(省略结果)。

好吧,toplev建议主要瓶颈是前端(50+%)。我认为您不能相信这一点,因为它计算FE-bound的方式在长字符串的微码指令情况下似乎有问题。 FE-bound基于frontend_retired.latency_ge_8,定义为:

在前端在8个周期内未传递uops的情况下获取的退役指令,其中未被后端阻塞打断。 (支持PEBS)

通常这很有道理。您正在计算由于前端未传递周期而延迟的指令。 “不受后端停顿中断”的条件确保在前端未传递uops仅因为后端无法接受它们时(例如,当RS已满时,因为后端正在执行一些低吞吐量的指令)不会触发此操作。

对于div指令而言,似乎即使是非常简单的循环也会出现问题:

FE      Frontend_Bound:                57.59 %           [100.00%]
BAD     Bad_Speculation:                0.01 %below      [100.00%]
BE      Backend_Bound:                  0.11 %below      [100.00%]
RET     Retiring:                      42.28 %below      [100.00%]

换句话说,瓶颈只存在于前端(“退役”不是瓶颈,它代表有用的工作)。显然,这样的循环由前端轻松处理,而实际上被后端的能力限制,可以咀嚼所有由

操作生成的UOP。Toplev可能会非常错误,因为(1)微代码序列器提供的UOPS可能没有计入frontend_retired.latency...计数器中,因此每个div操作都会导致该事件计算所有后续指令(即使CPU在那段时间内很忙-没有真正的停顿),或者(2)微代码序列器可能会将所有UPS基本上一次性提供,并将~36 UOPs猛烈地抛进IDQ,此时它不再提供任何UOP,直到div完成为止,或类似于此类的东西。

尽管如此,我们可以查看toplev的低级别提示:

toplev在区域1和区域2和3之间所述的主要区别是后两个区域的ms_switches的惩罚增加了(因为它们每次迭代都产生3,而遗留路径只产生2的开销。在内部,toplev为这些开关估算前端的2个周期惩罚。当然,这些惩罚是否实际上会减慢任何东西取决于指令队列和其他因素的复杂方式。如上所述,具有div的简单循环不显示DSB和MITE路径之间的任何差异,具有其他指令的循环则会显示差异。因此,可能是额外的切换泡沫在更简单的循环中被吸收了(其中由div产生的所有UOP的后端处理是主要因素),但是一旦您在循环中添加一些其他工作时,切换就会成为至少在div和非div 工作之间的过渡期间成为一个因素。

因此,我认为结论是div指令与前端uop流和后端执行的相互作用还没有完全理解。我们知道它涉及大量UOPS,其中许多来自MITE/DSB(似乎每个div有4个UOPS)和微代码序列器(似乎每个div有~32个UOPS,尽管它随着对div操作的不同输入值而改变)-但我们不知道那些UOPS是什么(我们可以看到它们的端口分配,尽管如此)。所有这些都使得行为相当不透明,但我认为它可能是由于MS开关瓶颈前端,或UOP传递流程中微小的差异导致不同的调度决策最终使MITE顺序成为主导。


1.当然,大多数uops根本不是从传统解码器或DSB传送的,而是由微代码序列器(ms)传送的。因此,我们粗略地谈论传递的指令,而不是UOPS。

2 注意这里的x轴是“偏移字节距离32B对齐”的意思。也就是说,0表示循环顶部(标签.L37)对齐到32B边界,5表示循环在32B边界以下5个字节处开始(使用nop进行填充),以此类推。因此,我的填充字节和偏移量是相同的。如果我正确理解了,OP使用了另一种偏移的含义:他的1个字节填充导致偏移为0。因此,你需要从OP的填充值中减去1来得到我的偏移值。

3 实际上,对于一个typical测试,即prime=1000000000000037,分支预测率为~99.999997%,整个运行中仅出现了3次错误的预测分支(很可能是在第一次循环通过和最后一次迭代中发生)。

4 UPC,即每个周期的微操作数 - 一种与IPC类似的度量方式,当我们详细研究微操作流时,它更加精确。在这种情况下,我们已经知道所有对齐变化的微操作数量是相同的,因此UPC和IPC将直接成比例。


光辉灿烂的、决定性的答案。 - Iwillnotexist Idonotexist
2
最近我测试了很多相关的东西,禁用超线程对使用perf进行测量的稳定性有着显著且可重复的影响。这是有道理的,因为操作系统可能会偶尔在另一个逻辑核心上调度其他线程,这可能会减少您的线程可用的资源。这是最大的帮助。 - BeeOnRope
2
禁用Turbo(我使用了这个脚本)和各种电源管理功能似乎也有所帮助。这对墙钟和CPU时间产生了很大的影响(这是有道理的),但也对未停止周期计数产生了一些影响(我认为)。正如你指出的那样,这似乎很奇怪,因为周期应该在这些事情上更或多或少不变。然而,转换可能会导致计数发生变化(例如,如果流水线被刷新),并且任何访问内存或(在某些情况下L3-L4)的东西都会受到影响,因为时钟速度比例发生了变化。 - BeeOnRope
我添加了源代码以便任何想尝试的人可以这样做。 - BeeOnRope
除此之外,非常好的答案。我开始想到一些疯狂的事情,比如REX前缀可能并不真正算作指令的开头。 - Peter Cordes
显示剩余11条评论

10
我没有具体的答案,只有几个假设,但由于缺乏硬件,我无法进行测试。我本以为找到了什么确定性的东西,但是由于问题从0x5F填充而不是从对齐边界开始计数,所以我对齐错误了。希望把这个发出来能够有所用处,以描述可能在起作用的因素。

此外,该问题还未指定分支的编码(短(2B)或近(6B))。这留下了太多的可能性来查看和推测哪个指令穿越32B边界或未穿越边界会导致问题。


我认为这要么是循环是否适配uop缓存的问题,要么是对齐是否重要,因为这会影响遗留解码器的解码速度。
显然,这个asm循环可以得到很大的改进(例如通过提升浮点数来优化它,更不用说完全使用不同的算法了),但这不是问题所在。我们只想知道为什么对于这个精确的循环而言,对齐很重要。
你可能会认为一个瓶颈在除法上的循环不会在前端瓶颈或者被对齐影响,因为除法很慢,每个时钟周期运行的指令非常少。这是正确的,但是64位DIV在IvyBridge上微代码化为35-57微操作码(uops),因此实际上可能存在前端问题。
对齐的两种主要影响方式是:
1. 前端瓶颈(在获取/解码阶段),导致保持乱序核心有足够的工作来做时出现泡沫。
2. 分支预测:如果两个分支具有相同的地址模数,则它们可以在分支预测硬件中别名。一个目标文件中的代码对齐影响了另一个目标文件中的函数的性能只是涉及了这个问题的表面,但已经有很多关于它的文章写过。

我怀疑这是一个纯粹的前端问题,而不是分支预测问题,因为代码在这个循环中花费了所有时间,并没有运行可能与此处别名的其他分支。

你的英特尔IvyBridge CPU是SandyBridge的缩小版。它有一些变化(如mov-elimination和ERMSB),但SnB/IvB/Haswell之间的前端相似。Agner Fog's microarch pdf提供了足够的细节来分析CPU运行此代码时应该发生什么。还可以参考David Kanter's SandyBridge writeup for a block diagram of the fetch/decode stages,但他将fetch/decode与uop缓存、微码和已解码uop队列分开。最后,有一个整个核心的完整块图。他的Haswell文章有一个包括整个前端的块图,直到解码-uop队列,该队列馈送问题阶段。(IvyBridge和Haswell在不使用超线程时都有一个56 uop队列/回路缓冲区。即使禁用HT,Sandybridge也会静态分配它们为2x28 uop队列。)

David Kanter's SnB writeup

这张图片是从David Kanter的出色的Haswell文章中复制而来,他在其中将解码器和uop-cache放在同一个图表中。

让我们看看一下,当事情稳定下来时,uop缓存将如何缓存这个循环。(即假设具有跳转到循环中间的jmp的循环入口不会对循环在uop缓存中的位置产生任何严重的长期影响)。

根据英特尔的优化手册(2.3.2.2 解码ICache):

  • Way中的所有微操作(uop缓存行)代表静态连续的指令,其EIP位于相同对齐的32字节区域内。(我认为这意味着超出边界的指令将放入包含其开始而不是结束的块的uop缓存中。跨越指令必须放置在某个地方,运行该指令的分支目标地址是指令的开始,因此将其放入该块的行中最有用)。
  • 多个微操作指令不能跨越Way。
  • 打开MSROM的指令会消耗整个Way。(即任何需要超过4个uops(对于reg,reg形式)的指令都是微码化的。例如,DPPD没有微码化(4个uops),但DPPS有(6个uops)。不能微合并的内存操作数的DPPD将成为5个总uops,但仍不需要打开微码序列器(未经测试)。
  • 每个Way允许最多两个分支。
  • 一对宏合并指令被保留为一个微操作。
David Kanter的SnB文档提供了一些关于uop缓存的重要细节

让我们看看实际的代码将如何进入uop缓存

# let's consider the case where this is 32B-aligned, so it runs in 0.41s
# i.e. this is at 0x402f60, instead of 0 like this objdump -Mintel -d output on a  .o
# branch displacements are all 00, and I forgot to put in dummy labels, so they're using the rel32 encoding not rel8.

0000000000000000 <.text>:
   0:   66 0f ef c0             pxor   xmm0,xmm0    # 1 uop
   4:   f2 48 0f 2a c1          cvtsi2sd xmm0,rcx   # 2 uops
   9:   66 0f 2e f0             ucomisd xmm6,xmm0   # 2 uops
   d:   0f 82 00 00 00 00       jb     0x13         # 1 uop  (end of one uop cache line of 6 uops)

  13:   31 d2                   xor    edx,edx      # 1 uop
  15:   48 89 d8                mov    rax,rbx      # 1 uop  (end of a uop cache line: next insn doesn't fit)

  18:   48 f7 f1                div    rcx          # microcoded: fills a whole uop cache line.  (And generates 35-57 uops)

  1b:   48 85 d2                test   rdx,rdx      ### PROBLEM!!  only 3 uop cache lines can map to the same 32-byte block of x86 instructions.
  # So the whole block has to be re-decoded by the legacy decoders every time, because it doesn't fit in the uop-cache
  1e:   0f 84 00 00 00 00       je     0x24         ## spans a 32B boundary, so I think it goes with TEST in the line that includes the first byte.  Should actually macro-fuse.
  24:   48 83 c1 01             add    rcx,0x1      # 1 uop 
  28:   79 d6                   jns    0x0          # 1 uop

使用32字节对齐启动循环,必须从遗留解码器运行,这可能比从uop缓存运行慢。甚至在从uop缓存切换到遗留解码器时可能会有一些开销。
@Iwill的测试(请参见问题的评论)显示任何微编码指令都会阻止循环从回路缓冲区运行。请参见问题的评论。(LSD = Loop Stream Detector = 循环缓冲区;物理上与IDQ(指令解码队列)相同的结构。DSB = Decode Stream Buffer = uop缓存。MITE = 遗留解码器。)
即使循环足够小以从LSD(IvB和Haswell上的超线程最少28个uops,否则为56个)运行,打破uop缓存也会影响性能。
英特尔的优化手册(第2.3.2.4节)指出,LSD的要求包括:
  • 所有微操作也驻留在已解码的ICache中。
因此,这就解释了为什么微码不符合条件:在这种情况下,uop-cache仅保存指向微码的指针,而不是uops本身。还要注意,这意味着如果由于任何其他原因(例如大量单字节NOP指令)破坏了uop缓存,则循环无法从LSD运行。
根据OP的测试结果,最小填充可实现更快速度。
# branch displacements are still 32-bit, except the loop branch.
# This may not be accurate, since the question didn't give raw instruction dumps.
# the version with short jumps looks even more unlikely

0000000000000000 <loop_start-0x64>:
    ...
  5c:   00 00                   add    BYTE PTR [rax],al
  5e:   90                      nop
  5f:   90                      nop

  60:   90                      nop         # 4NOPs of padding is just enough to bust the uop cache before (instead of after) div, if they have to go in the uop cache.
          # But that makes little sense, because looking backward should be impossible (insn start ambiguity), and we jump into the loop so the NOPs don't even run once.
  61:   90                      nop
  62:   90                      nop
  63:   90                      nop

0000000000000064 <loop_start>:                   #uops #decode in cycle A..E
  64:   66 0f ef c0             pxor   xmm0,xmm0   #1   A
  68:   f2 48 0f 2a c1          cvtsi2sd xmm0,rcx  #2   B
  6d:   66 0f 2e f0             ucomisd xmm6,xmm0  #2   C (crosses 16B boundary)
  71:   0f 82 db 00 00 00       jb     152         #1   C

  77:   31 d2                   xor    edx,edx     #1   C
  79:   48 89 d8                mov    rax,rbx     #1   C

  7c:   48 f7 f1                div    rcx       #line  D

  # 64B boundary after the REX in next insn    
  7f:   48 85 d2                test   rdx,rdx     #1   E
  82:   74 06                   je     8a <loop_start+0x26>#1 E
  84:   48 83 c1 01             add    rcx,0x1     #1   E
  88:   79 da                   jns    64 <loop_start>#1 E
< p > test rdx,rdx的REX前缀与DIV在同一块中,因此应该会使uop缓存失效。再填充一个字节将其放入下一个32B块中,这将非常合理。也许OP的结果是错误的,或者前缀不计算,而操作码字节的位置很重要。也许这很重要,或者可能使宏融合的测试+分支到下一个块?< /p>

宏融合确实会跨越64B L1I缓存线边界,因为它不落在指令之间的边界上。< /p> < blockquote >

如果第一条指令在缓存行的第63个字节结束,第二条指令是从下一个缓存行的第0个字节开始的条件分支,则不会发生宏融合。 - - 英特尔优化手册,2.3.2.1< /p> < /blockquote >

或者也许对于一个跳转的短编码或另一个跳转,情况就不同了?< /p>

也许清除uop缓存与此无关,只要解码速度快就可以了,这种对齐方式可以实现。这个填充量刚好将UCOMISD的结尾放入一个新的16B块中,所以也许这实际上通过让它与下一个对齐的16B块中的其他指令一起解码来提高了效率。然而,我不确定16B预解码(指令长度查找)或32B解码块是否必须对齐。


我也想知道CPU是否经常从uop缓存切换到传统解码。这可能比一直从传统解码运行更糟糕。
根据Agner Fog的微架构指南,从解码器切换到uop缓存或反之需要一个周期。英特尔表示:
“当由于限制而无法将微操作存储在解码ICache中时,它们将从传统解码管道传递。一旦微操作从传统管道传递,只有在下一个分支微操作之后,才能恢复从解码ICache获取微操作。频繁切换可能会产生惩罚。”

我组装和反汇编的源代码:

.skip 0x5e
nop
# this is 0x5F
#nop  # OP needed 1B of padding to reach a 32B boundary

.skip 5, 0x90

.globl loop_start
loop_start:
.L37:
  pxor    %xmm0, %xmm0
  cvtsi2sdq   %rcx, %xmm0
  ucomisd %xmm0, %xmm6
  jb  .Loop_exit   // Exit the loop
.L20:
  xorl    %edx, %edx
  movq    %rbx, %rax
  divq    %rcx
  testq   %rdx, %rdx
  je  .Lnot_prime   // Failed divisibility test
  addq    $1, %rcx
  jns .L37

.skip 200  # comment this to make the jumps rel8 instead of rel32
.Lnot_prime:
.Loop_exit:

@IwillnotexistIdonotexist:我的SnB系统已经变砖了,目前我正在使用Core2Duo。(令人惊讶的是,它在运行Web浏览器和Emacs时表现得非常好,尽管编译有点慢)。 - Peter Cordes
就我所知,我不认为最近的处理器在映射分支历史时使用二次幂函数。大多数处理器使用IP的未指定哈希值,因此当代码具有特定对齐方式时,冲突并不会出现病态情况,但仍然会随机发生。 - BeeOnRope
我同意分支预测不会影响它。我提到它是因为上面提到了二的幂行为,在某些情况下,它将是相关的。 - BeeOnRope
2
@PeterCordes - 我在下面添加了有关Skylake的一些细节,特别是uop缓存肯定会对其产生影响:某些对齐方式将1个uop推入下一个缓存行(注意,不同于下一个“路”),这可能导致该uop稍后出现在IDQ中,并可能最终使循环减速1个周期。我还发现了“破坏uop”的高速缓存效应,就像你上面讨论的那样,但它的效果与您可能期望的相反:当uop缓存“破坏”并且代码从MITE发出时,我们获得了最佳性能! - BeeOnRope
所以我上面的评论是指出现在还不清楚DSB是否能够在同一周期内从同一组中的多个路径(都对应着相同的32B代码块)发出指令。如果可以,它可能无法在同一周期内从多个不同的_组_中发出指令。我认为它不能做后者,但前者我不确定。实际上很容易测试... - BeeOnRope
显示剩余11条评论

-1

从您的算法中我所看到的,您确实没有太多可以改进的地方。

您遇到的问题可能不是分支到对齐位置,虽然这仍然有帮助,但您目前的问题更可能是流水线机制。

当您连续编写两个指令时,例如:

  mov %eax, %ebx
  add 1, %ebx

为了执行第二条指令,必须先完成第一条指令。因此编译器倾向于混合指令。比如说你需要将%ecx设为零,你可以这样做:
  mov %eax, %ebx
  xor %ecx, %ecx
  add 1, %ebx

在这种情况下,movxor 都可以并行执行。这样可以加快速度... 可以同时处理的指令数量在处理器之间差异很大(Xeon 处理器通常更擅长)。
分支语句增加了另一个参数,最好的处理器可以同时执行分支语句的两侧(真和假...)。但实际上,大多数处理器会猜测并希望它们是正确的。
最后,显然将 sqrt() 的结果转换为整数会使速度变得更快,因为您将避免所有与SSE2代码无关的问题,如果仅用于转换+比较,则明显较慢,当这两个指令可以用整数完成时。
现在... 您可能仍然想知道为什么整数对齐不重要。事实上,如果您的代码适合 L1 指令缓存,那么对齐就不重要了。如果丢失 L1 缓存,则必须重新加载代码,这就是对齐变得非常重要的地方,因为在每个循环中,它可能正在加载无用的代码(可能是15字节的无用代码...),并且内存访问仍然非常慢。

1
如果你的代码适合于L1指令缓存,那么对齐就不重要了。有时候是正确的,但这里不是。在一个对齐的16B块的最后几个字节中的分支目标比在16B块的早期稍微糟糕一些,即使它在L1缓存中很热。接近32B边界的末尾是不好的,即使它在L0 uop缓存中很热(除非你在一个适合于循环缓冲区的循环中)。 - Peter Cordes
2
同时,最好的处理器可能会开始执行分支的两个方向(真和假...)。据我所知,没有微架构会沿着分支的两个方向进行推测。是的,这是一种理论上可能的设计,但没有人这样做。我也不确定答案的前半部分(关于指令级并行性)如何有所帮助。(而且不,Xeon 没有更宽的乱序核心,或者单个线程中不受缓存未命中限制的更多 ILP。Xeon 有与 i7 相同的更多核心,但那是线程级并行性,而不是指令级并行性。) - Peter Cordes
1
如果解码不是瓶颈,按照这个答案中所示重新排序指令对于乱序处理器几乎没有影响。它可能会产生负面影响,因为读取更新了许多指令之前的寄存器时,必须从寄存器文件中获取值,这在许多代英特尔核心(从Pentium M开始)中都是一个瓶颈。有关详细信息,请在http://www.agner.org/optimize/microarchitecture.pdf中搜索“register file”。答案的其余部分模糊或明显错误,正如已经指出的那样。 - Pascal Cuoq
@PascalCuoq,让我试着搞清楚一下... "乱序不是瓶颈" 而且 "它可能有负面影响" ...那么你是说指令的顺序既不重要又重要吗?也许你应该考虑一下? - Alexis Wilke
1
@PascalCuoq:Intel SnB系列没有寄存器读取停顿。SnB改用物理寄存器文件,而不是直接在ROB中存储操作数值。当一个发射组需要读取太多未最近写入的寄存器时,P6系列CPU(PPro / PII到Nehalem)会出现寄存器读取停顿。 Pentium M是Intel在Netburst / P4失败后回到P6的时候(它也使用了物理寄存器文件并且没有ROB读取停顿),但这个限制可以追溯到PPro。TL:DR:Alexis:乱序执行可以找到任何顺序无关的并行性。 - Peter Cordes

-3

性能差异可以通过指令编码机制“看到”指令的不同方式来解释。CPU以块(我相信在Core2上是16字节)读取指令,并尝试为不同的超标量单元提供微操作。如果指令处于边界或顺序不太可能,一个核心中的单元很容易饥饿。


1
SnB家族的CPU(例如OP的IvyBridge CPU)具有循环缓冲区,可以在非常短的循环中回收已解码的uops。请参见Agner Fog的微架构PDF。这个答案完全不足以解释任何东西。仅仅说“对齐可能很重要”并没有增加任何内容。 - Peter Cordes
是的,我知道LSD存在于英特尔CPU中。此外,uop-cache自 Pentium4 时代就回来了...如果这不是原因,如果icache misses也不是原因,该怎么解释呢?如果您比我更懂,请使用VTune自行查看。我可能无法重现精确的代码,因为编译器是旧版本(哪个版本呢?),汇编转储不完整(不是我的错)...而且你自己评论说它不适合 LSD...我不知道你的问题在哪里。 - Quonux
我认为在这里可能是在解码器和uop缓存之间切换,如果IDIV的uops不能适合循环的缓存行。如果您拥有类似的硬件,OP的asm循环已经足够完整以在独立的.S文件中进行微基准测试(但不幸的是,我没有)。我之前没有意识到整数除法可能会成为前端瓶颈而不是除法单元,但是对此的足够回答将不得不提到uop缓存。OP已经知道对齐很重要。 - Peter Cordes
我一直在思考一个答案,但是我意识到 OP 留下了太多的空白。我们无法确定这些分支中哪些是 rel8,哪些是 rel32,因此有四种可能性需要考虑对齐点截断。即,使用 skip 0x5e; nop 组合达到...5F,然后使用 .skip 5, 0x90 查看最小的填充大小以使其快速。这比使 DIV 后面的指令开始于下一个 32B 块要短一步,我认为这样应该可以让包含 DIV 的块适配 3 个 uop 缓存行(如果 JB 是一个 6 字节 rel32 的话)。总之,4 倍的搜索空间很糟糕 :( - Peter Cordes
我终于发布了我一直在拖延的答案。尽管它仍然只是一个猜测,但比这个更具体一些... - Peter Cordes
显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接