为什么妈妈在Haswell上只有3个周期,与Agner的指令表不同?

我是一个新手在指令优化。

我简单的分析了一个简单的函数dotp,用来得到两个float数组的点积。

C代码如下:

float dotp( const float x[], const float y[], const short n ) { short i; float suma; suma = 0.0f; for(i=0; i<n; i++) { suma += x[i] * y[i]; } return suma; } 

我使用networkingtesting中的Agner Fog提供的testing框架。

在这种情况下使用的数组是alignment的:

 int n = 2048; float* z2 = (float*)_mm_malloc(sizeof(float)*n, 64); char *mem = (char*)_mm_malloc(1<<18,4096); char *a = mem; char *b = a+n*sizeof(float); char *c = b+n*sizeof(float); float *x = (float*)a; float *y = (float*)b; float *z = (float*)c; 

然后我调用函数dotp,n = 2048,repeat = 100000:

  for (i = 0; i < repeat; i++) { sum = dotp(x,y,n); } 

我用gcc 4.8.3编译它,编译选项-O3。

我在一台不支持FMA指令的计算机上编译这个应用程序,所以你可以看到只有SSE指令。

汇编代码:

 .L13: movss xmm1, DWORD PTR [rdi+rax*4] mulss xmm1, DWORD PTR [rsi+rax*4] add rax, 1 cmp cx, ax addss xmm0, xmm1 jg .L13 

我做一些分析:

  μops-fused la 0 1 2 3 4 5 6 7 movss 1 3 0.5 0.5 mulss 1 5 0.5 0.5 0.5 0.5 add 1 1 0.25 0.25 0.25 0.25 cmp 1 1 0.25 0.25 0.25 0.25 addss 1 3 1 jg 1 1 1 ----------------------------------------------------------------------------- total 6 5 1 2 1 1 0.5 1.5 

运行后,我们得到结果:

  Clock | Core cyc | Instruct | BrTaken | uop p0 | uop p1 -------------------------------------------------------------------- 542177906 |609942404 |1230100389 |205000027 |261069369 |205511063 -------------------------------------------------------------------- 2.64 | 2.97 | 6.00 | 1 | 1.27 | 1.00 uop p2 | uop p3 | uop p4 | uop p5 | uop p6 | uop p7 ----------------------------------------------------------------------- 205185258 | 205188997 | 100833 | 245370353 | 313581694 | 844 ----------------------------------------------------------------------- 1.00 | 1.00 | 0.00 | 1.19 | 1.52 | 0.00 

第二行是从英特尔寄存器读取的值; 第三行由分行号“BrTaken”分隔。

所以我们可以看到,循环中有6条指令,7条微博,与分析一致。

在port0 port1 port 5 port6中运行的uops的数量与分析所说的类似。 我认为,也许uops调度程序这样做,它可能会尝试平衡端口上的负载,对吗?

我绝对不明白为什么每个循环只有大约3个周期。 根据Agner的指令表 ,指令mulss的延迟是5,并且循环之间有依赖关系,据我所知,每个循环至less需要5个周期。

任何人都可以有所了解吗?

================================================== ================

我试图在nasm中编写一个优化的函数版本,将循环展开8倍,并使用vfmadd231ps指令:

 .L2: vmovaps ymm1, [rdi+rax] vfmadd231ps ymm0, ymm1, [rsi+rax] vmovaps ymm2, [rdi+rax+32] vfmadd231ps ymm3, ymm2, [rsi+rax+32] vmovaps ymm4, [rdi+rax+64] vfmadd231ps ymm5, ymm4, [rsi+rax+64] vmovaps ymm6, [rdi+rax+96] vfmadd231ps ymm7, ymm6, [rsi+rax+96] vmovaps ymm8, [rdi+rax+128] vfmadd231ps ymm9, ymm8, [rsi+rax+128] vmovaps ymm10, [rdi+rax+160] vfmadd231ps ymm11, ymm10, [rsi+rax+160] vmovaps ymm12, [rdi+rax+192] vfmadd231ps ymm13, ymm12, [rsi+rax+192] vmovaps ymm14, [rdi+rax+224] vfmadd231ps ymm15, ymm14, [rsi+rax+224] add rax, 256 jne .L2 

结果:

  Clock | Core cyc | Instruct | BrTaken | uop p0 | uop p1 ------------------------------------------------------------------------ 24371315 | 27477805| 59400061 | 3200001 | 14679543 | 11011601 ------------------------------------------------------------------------ 7.62 | 8.59 | 18.56 | 1 | 4.59 | 3.44 uop p2 | uop p3 | uop p4 | uop p5 | uop p6 | uop p7 ------------------------------------------------------------------------- 25960380 |26000252 | 47 | 537 | 3301043 | 10 ------------------------------------------------------------------------------ 8.11 |8.13 | 0.00 | 0.00 | 1.03 | 0.00 

所以我们可以看到L1数据caching达到2 * 256bit / 8.59,非常接近峰值2 * 256/8,使用率约为93%,FMA单元只用了8 / 8.59,峰值为2 * 8 / 8,用法是47%。

所以我认为我已经达到了Peter Cordes所期望的L1D瓶颈。

================================================== ================

特别感谢Boann,在我的问题中修正了很多语法错误。

================================================== ===============

从彼得的答复中,我得到只有“读写”寄存器才是依赖,“只有写者”寄存器才不是依赖。

所以我试图减less循环中使用的寄存器,并且我试着展开5,如果一切正常的话,我应该遇到同样的瓶颈,L1D。

 .L2: vmovaps ymm0, [rdi+rax] vfmadd231ps ymm1, ymm0, [rsi+rax] vmovaps ymm0, [rdi+rax+32] vfmadd231ps ymm2, ymm0, [rsi+rax+32] vmovaps ymm0, [rdi+rax+64] vfmadd231ps ymm3, ymm0, [rsi+rax+64] vmovaps ymm0, [rdi+rax+96] vfmadd231ps ymm4, ymm0, [rsi+rax+96] vmovaps ymm0, [rdi+rax+128] vfmadd231ps ymm5, ymm0, [rsi+rax+128] add rax, 160 ;n = n+32 jne .L2 

结果:

  Clock | Core cyc | Instruct | BrTaken | uop p0 | uop p1 ------------------------------------------------------------------------ 25332590 | 28547345 | 63700051 | 5100001 | 14951738 | 10549694 ------------------------------------------------------------------------ 4.97 | 5.60 | 12.49 | 1 | 2.93 | 2.07 uop p2 |uop p3 | uop p4 | uop p5 |uop p6 | uop p7 ------------------------------------------------------------------------------ 25900132 |25900132 | 50 | 683 | 5400909 | 9 ------------------------------------------------------------------------------- 5.08 |5.08 | 0.00 | 0.00 |1.06 | 0.00 

我们可以看到5 / 5.60 = 89.45%,比8点略小,有什么不对吗?

================================================== ===============

我试图展开6,7和15循环,看看结果。 我也再次展开5和8,以加倍确认结果。

结果如下,我们可以看到这次结果比以前好多了。

虽然结果不稳定,但展开因子较大,效果较好。

  | L1D bandwidth | CodeMiss | L1D Miss | L2 Miss ---------------------------------------------------------------------------- unroll5 | 91.86% ~ 91.94% | 3~33 | 272~888 | 17~223 -------------------------------------------------------------------------- unroll6 | 92.93% ~ 93.00% | 4~30 | 481~1432 | 26~213 -------------------------------------------------------------------------- unroll7 | 92.29% ~ 92.65% | 5~28 | 336~1736 | 14~257 -------------------------------------------------------------------------- unroll8 | 95.10% ~ 97.68% | 4~23 | 363~780 | 42~132 -------------------------------------------------------------------------- unroll15 | 97.95% ~ 98.16% | 5~28 | 651~1295 | 29~68 

================================================== ===================

我尝试在web“ https://gcc.godbolt.org ”中用gcc 7.1编译这个函数。

编译选项是“-O3 -march = haswell -mtune = intel”,类似于gcc 4.8.3。

 .L3: vmovss xmm1, DWORD PTR [rdi+rax] vfmadd231ss xmm0, xmm1, DWORD PTR [rsi+rax] add rax, 4 cmp rdx, rax jne .L3 ret 

再看看你的循环: movss xmm1, src不依赖xmm1的旧值,因为它的目的地是只写的 。 每个迭代的mulss是独立的。 无序执行可以并且利用这个指令级的并行性,所以你绝对不会mulss延迟。

可选阅读:在计算机体系结构方面:寄存器重命名避免了重复使用相同体系结构寄存器的WAR反依赖性数据危险 。 (registry重命名之前的一些stream水线+依赖关系跟踪scheme并没有解决所有的问题,因此计算机体系结构领域对于各种数据隐患有很大的帮助。

使用Tomasuloalgorithm进行寄存器重命名,除了实际的真正依赖关系(写入后读取)之外,所有事情都会消失,因此,目的地不是源寄存器的任何指令都不会与涉及该寄存器的旧值的依赖链进行交互。 (除了错误的依赖关系,比如Intel CPU上的popcnt ,只写一部分寄存器而不清除其余部分(如mov al, 5或者sqrtss xmm2, xmm1 )相关: 为什么大部分的x64指令都是32的上半部分位寄存器 )。


回到您的代码:

 .L13: movss xmm1, DWORD PTR [rdi+rax*4] mulss xmm1, DWORD PTR [rsi+rax*4] add rax, 1 cmp cx, ax addss xmm0, xmm1 jg .L13 

循环运行的依赖关系(从一个迭代到下一个迭代)分别是:

  • xmm0 ,由addss xmm0, xmm1在Haswell上有3个周期延迟。
  • rax ,阅读rax书写add rax, 1 。 1C的延迟,所以它不是关键path。

看起来你正确地测量了执行时间/周期数,因为3c上的循环瓶颈会addss延迟。

这是预料之中的:点积中的序列依赖是单个和(又称还原)的加法,而不是向量元素之间的相乘。

这是迄今为止这个循环的主要瓶颈,尽pipe各种小的低效率:


short i产生了愚蠢的cmp cx, ax ,它需要一个额外的操作数大小的前缀。 幸运的是,gcc设法避免实际add ax, 1 ,因为签名溢出是C中的未定义行为。 所以优化器可以认为它不会发生 。 (更新: 整数推广规则使它不同 ,所以UB不进入,但海湾合作委员会仍然可以合法优化,相当古怪的东西。

如果你用-mtune=intel编译,或者更好的话, -march=haswell ,gcc会把cmpjg放在他们可以macros定义的地方。

我不知道为什么你有一个*在你的表在cmpadd说明。 (更新:我纯粹猜测你正在使用像IACA这样的符号,但显然你没有)。 他们都没有融合。 唯一融合发生的是mulss xmm1, [rsi+rax*4]微融合。

而且由于它是一个具有读 – 修改 – 写目的地寄存器的2操作数ALU指令,所以即使在Haswell上的ROB也保持macros融合。 (桑迪布里奇将在问题时间解开它。) 注意, vmulss xmm1, xmm1, [rsi+rax*4]也将在Haswell上解压 。

这些都不重要,因为FP-add延迟完全是瓶颈,比任何uop吞吐量限制要慢得多。 没有-ffast-math ,没有什么编译器可以做。 用-ffast-math ,clang通常会展开多个累加器,并且会自动vector化,所以它们将成为vector累加器。 所以如果你打在L1Dcaching中,你可能会使Haswell的吞吐量限制达到1个vector或每个时钟的标量FP增加。

由于FMA在Haswell上具有5c的延迟和0.5c的吞吐量,因此您需要10个累加器来保持10个FMA的运行,并通过使p0 / p1保持FMA饱和来最大化FMA吞吐量。 (Skylake将FMA延迟减less到4个周期,并在FMA单元上运行乘法,加法和FMA,所以它实际上比Haswell具有更高的延迟延迟)。

(因为每个FMA需要两个负载,在其他情况下,通过用乘法器1.0replace一个vaddps指令,实际上可以获得vaddps吞吐量,这意味着需要隐藏更多的延迟,所以在一个更加复杂的algorithm中,最好使用一个不在关键path上的add。)


Re:每个端口的uops

端口5的每个回路有1.19个uops,这比预期的0.5多得多,这是关于uops调度器试图在每个端口上进行微调的问题

是的,类似的东西。

uops不是随机分配的,或者以某种方式均匀分布在每个可以运行的端口上。 你认为addcmp uops会平均分配到p0156,但事实并非如此。

问题阶段根据有多less微软已经在等待那个端口来分配uops给端口。 由于addss只能在p1上运行(并且是循环瓶颈),所以通常会有很多p1 uop被发出但是不被执行。 所以很less有其他的微软将被安排到port1。 (这包括mulss :大部分mulss将最终计划到0。

被采取的分支只能在端口6上运行。端口5在这个环路中没有任何的uops, 只能在那里运行,所以它最终吸引了许多端口的uops。

调度程序(从保留站中select未保护的域的uop)不够智能,无法运行关键path优先,所以这是分配algorithm减less了资源冲突的延迟(其他的addssaddss可能的时候偷取了port1的周期跑)。 在某个端口吞吐量瓶颈的情况下,这也很有用。

据我所知,调度已经分配的uops通常是最早的。 这个简单的algorithm并不令人惊讶,因为它必须在每个时钟周期从60个inputRS中为每个端口准备一个input ,而不会使CPU熔化。 发现和利用ILP的乱序机器是现代CPU中的重要电力成本之一,与执行实际工作的执行单位相当。

相关/更多细节: x86 uops是如何计划的?


更多性能分析的东西:

除了caching未命中/分支预测失败以外,CPU绑定循环的三个主要可能的瓶颈是:

  • 依赖链(就像在这种情况下一样)
  • 前端吞吐量(Haswell的每个时钟最多发布4个融合域uops)
  • 执行端口的瓶颈,就像大量的uops需要p0 / p1或者p2 / p3一样,就像在展开的循环中一样。 计算特定端口的未保真域uops。 一般来说,你可以假设最好的情况下分配,可以运行在其他端口上的uops不会经常地占用繁忙的端口,但是确实发生了一些。

循环体或短代码块可以近似表示为3种情况:融合域计数,可以运行的执行单元的非融合域计数以及假设关键path最佳情况调度的总关键path延迟。 (或从inputA / B / C到输出的每一个的等待时间…)

举个例子,比较几个较短的序列,看看我的答案: 在一个位置或更低的位置上设置位的有效方法是什么?

对于短循环来说,现代CPU具有足够的无序执行资源(物理寄存器文件大小,所以重命名不会超出寄存器,ROB大小),以便有足够的迭代循环来find所有的并行性。 但随着循环内的依赖链变长,最终它们耗尽。 有关详细信息,请参阅“ 测量重新sorting缓冲区容量” ,了解CPU在用完重新命名之后会发生什么情况。

另请参阅x86标记wiki中的大量性能和参考链接。


调整你的FMA循环:

是的,Haswell的dot-product产品只会在FMA单元吞吐量的一半上产生L1D吞吐量的瓶颈,因为每乘法+加载需要两个负载。

如果你在做B[i] = x * A[i] + y;sum(A[i]^2) ,则可能使FMA吞吐量饱和。

看起来你仍然在试图避免寄存器复用,即使在像vmovaps加载的目标这样的只写的情况下,所以在展开之后你用完了8个寄存器 。 这很好,但对于其他情况可能很重要。

此外,使用ymm8-15可以稍微增加代码长度,如果这意味着需要3字节的VEX前缀而不是2字节。 有趣的事实: vpxor ymm7,ymm7,ymm8需要一个3字节的VEX,而vpxor ymm8,ymm8,ymm7只需要一个2字节的VEX前缀。 对于交换操作,sorting源从高到低。

我们的负载瓶颈意味着最佳的FMA吞吐量是最大的一半,所以我们至less需要5个vector累加器来隐藏它们的延迟。 8是好的,所以在依赖链上有很多的松懈,让他们赶上意外等待时间或竞争p0 / p1的延迟。 7或甚至6也可以:你的展开因子不一定是2的幂。

正确地展开5意味着你也正处于依赖链的瓶颈 。 任何时候,FMA不能在确切的周期内运行,其input就绪就意味着该依赖链中的一个丢失循环。 如果负载较慢(例如,它在L1高速caching中丢失并且必须等待L2),或者如果负载完全不按顺序并且来自另一个依赖链的FMA窃取了该FMA计划的端口,则会发生这种情况。 (请记住,调度发生在问题时间,所以坐在调度程序中的uops是port0 FMA或port1 FMA,而不是FMA,可以将任何端口闲置)。

如果在依赖关系链中留下一些空白,乱序执行可能会在FMA上“赶上”,因为它们不会在吞吐量或延迟上受到瓶颈,只是等待加载结果。 @Forward发现(在一个更新的问题),展开5的性能从93%的L1D吞吐量降低到89.5%的这个循环。

我的猜测是,在6倍的展开(比隐藏延迟的最小值多一个)是可以的,并且获得与8倍展开相同的性能。如果我们更接近于最大化FMA吞吐量(而不是仅仅是负载的瓶颈吞吐量),比最小值多一个可能是不够的。

更新:@前锋的实验testing显示我的猜测是错误的 。 unroll5和unroll6没有太大的区别。 而且,unroll15的值是unroll8的两倍,以达到理论上每个时钟最大吞吐量为2x 256b的最大吞吐量。 使用循环中的独立负载进行度量,或者使用独立负载和仅寄存器的FMA进行度量,会告诉我们有多less是由于与FMA依赖链的交互作用造成的。 即使是最好的情况下,如果仅仅是因为测量错误和定时器中断造成的中断,也不会达到理想的100%吞吐量。 (Linux perf只测量用户空间周期,除非以root用户身份运行,但时间仍然包括中断处理程序所花费的时间,这就是为什么你的CPU频率以非root用户身份报告为3.87GHz,而运行时为3.900GHz作为根和测量cycles而不是cycles:u 。)


我们不是前端吞吐量的瓶颈,但是我们可以通过避免非mov指令的索引寻址模式来减less融合域uop数量。 与其他方式共享一个内核时,越less越好,并且使这个更友好的超线程

简单的方法就是在循环中做两个指针增量。 复杂的方法是将一个数组相对于另一个数组进行索引的巧妙方法:

 ;; input pointers for x[] and y[] in rdi and rsi ;; size_t n in rdx ;;; zero ymm1..8, or load+vmulps into them add rdx, rsi ; end_y ; lea rdx, [rdx+rsi-252] to break out of the unrolled loop before going off the end, with odd n sub rdi, rsi ; index x[] relative to y[], saving one pointer increment .unroll8: vmovaps ymm0, [rdi+rsi] ; *px, actually py[xy_offset] vfmadd231ps ymm1, ymm0, [rsi] ; *py vmovaps ymm0, [rdi+rsi+32] ; write-only reuse of ymm0 vfmadd231ps ymm2, ymm0, [rsi+32] vmovaps ymm0, [rdi+rsi+64] vfmadd231ps ymm3, ymm0, [rsi+64] vmovaps ymm0, [rdi+rsi+96] vfmadd231ps ymm4, ymm0, [rsi+96] add rsi, 256 ; pointer-increment here ; so the following instructions can still use disp8 in their addressing modes: [-128 .. +127] instead of disp32 ; smaller code-size helps in the big picture, but not for a micro-benchmark vmovaps ymm0, [rdi+rsi+128-256] ; be pedantic in the source about compensating for the pointer-increment vfmadd231ps ymm5, ymm0, [rsi+128-256] vmovaps ymm0, [rdi+rsi+160-256] vfmadd231ps ymm6, ymm0, [rsi+160-256] vmovaps ymm0, [rdi+rsi-64] ; or not vfmadd231ps ymm7, ymm0, [rsi-64] vmovaps ymm0, [rdi+rsi-32] vfmadd231ps ymm8, ymm0, [rsi-32] cmp rsi, rdx jb .unroll8 ; } while(py < endy); 

使用非索引寻址模式作为vfmaddps的内存操作数,可以让它在无序内核中保持微熔,而不是在层叠问题上。 微融合和寻址模式

所以我的循环是8个向量的18个融合域的uops。 对于每个vmovaps + vfmaddps对,您需要3个融合域uops,而不是2个,因为未分层的索引寻址模式。 他们两个当然每对还有2个未encryption的域负载(端口2/3),所以这仍然是瓶颈。

更less的融合域uops让乱序执行看到更多的迭代,可能有助于更好地吸收caching未命中。 尽pipe如此,当我们遇到执行单元的瓶颈时(这种情况下加载uops),即使没有caching未命中,也是一件小事。 但是在超线程的情况下,除非另一个线程被阻塞,否则你只能得到前端问题带宽的每一个周期。 如果负载和p0 / 1没有太多的竞争,那么融合域uops越less,这个循环在共享内核的时候就会运行得更快。 (例如,也许另一个超线程正在运行大量的port5 / port6并存储微软?)

由于un-lamination发生在uop-cache之后,因此你的版本不会在uop cache中占用额外的空间。 与每个uop的disp32是好的,不占用额外的空间。 但是庞大的代码大小意味着uopcaching不太可能有效地打包,因为在uopcaching行更为常见之前,您会达到32B的边界。 (实际上,较小的代码并不能保证更好,较小的指令可能会导致填充一个uopcaching行,并在跨越32B边界之前在另一行中需要一个入口)。这个小的循环可以从环回缓冲区(LSD)运行,所以幸运的是,高速caching不是一个因素。


然后在循环之后:高效清理是小数组高效向量化的难点,这可能不是展开因子的倍数,尤其是向量宽度

  ... jb ;; If `n` might not be a multiple of 4x 8 floats, put cleanup code here ;; to do the last few ymm or xmm vectors, then scalar or an unaligned last vector + mask. ; reduce down to a single vector, with a tree of dependencies vaddps ymm1, ymm2, ymm1 vaddps ymm3, ymm4, ymm3 vaddps ymm5, ymm6, ymm5 vaddps ymm7, ymm8, ymm7 vaddps ymm0, ymm3, ymm1 vaddps ymm1, ymm7, ymm5 vaddps ymm0, ymm1, ymm0 ; horizontal within that vector, low_half += high_half until we're down to 1 vextractf128 xmm1, ymm0, 1 vaddps xmm0, xmm0, xmm1 vmovhlps xmm1, xmm0, xmm0 vaddps xmm0, xmm0, xmm1 vmovshdup xmm1, xmm0 vaddss xmm0, xmm1 ; this is faster than 2x vhaddps vzeroupper ; important if returning to non-AVX-aware code after using ymm regs. ret ; with the scalar result in xmm0 

有关最后水平和的更多信息,请参阅在x86上执行水平浮点向量和的最快方法 。 我使用的两个128b shuffle甚至不需要立即控制字节,所以它比较明显的shufps节省了2个字节的代码量。 (和4个字节的代码大小与vpermilps ,因为操作码总是需要3个字节的VEX前缀以及立即)。 与SSE相比,AVX 3操作数的东西是非常不错的,尤其是当用C写入内部函数的时候,所以你不能简单地select一个冷寄存器来movhlps