了解lfence对具有两个长依赖链的循环的影响,以增加长度

我将对T=1的两种代码(有和没有)的情况进行分析 lfence ). 然后,您可以将其扩展为T的其他值。有关可视化信息,请参阅英特尔优化手册的图2.4。

因为只有一个容易预测的分支,前端只有在后端停止时才会停止。前端在Haswell中是4宽的,这意味着可以从IDQ(指令解码队列,这只是一个按顺序保存融合域uop的队列,也称为uop队列)向调度程序的保留站实体发出多达4个融合uop。每个 imul 被解码为无法融合的单个uop。说明书 dec ecx 和 jnz .loop lfence公司 被解码成6个UOP。识别微融合只在后端起作用,在这种情况下,循环中没有微融合。

由于循环分支很容易预测,并且迭代次数相对较多,我们可以假设分配器总是能够在每个周期分配4个UOP,而不会影响精确度。换言之,调度程序每周期将接收4个UOP。由于没有micorfusion,因此每个uop都将作为单个uop发送。

伊穆尔 只能由慢速Int执行单元执行(参见图2.4)。这意味着执行 伊穆尔 UOP将把它们发送到端口1。在Haswell中,慢速Int是很好的流水线,因此 可按周期调度。但是,乘法的结果需要三个周期才能用于任何需要的指令(写回阶段是管道调度阶段的第三个周期)。所以对于每个依赖链,最多一个 伊穆尔

因为 dec/jnz

因此,在任何给定的周期,只要RS有空间,它将收到4 UOP。但是什么样的UOP呢?让我们不带lfence检查循环:

imul eax, eax
imul edx, edx
dec ecx/jnz .loop (macrofused)

有两种可能性:

• 二 伊穆尔 来自同一个迭代,一个 伊穆尔 从相邻的迭代中 dec/jnz公司 从这两个迭代中的一个。
• 一个 dec/jnz公司 一次迭代,两次 伊穆尔 dec/jnz公司

因此,在任何周期的开始,RS将收到至少一个 dec/jnz公司 至少有一个 伊穆尔 从每个链条。同时,在同一个周期内,调度程序将从RS中已经存在的UOP中执行以下两个操作之一:

• 派遣最老的 dec/jnz公司 去6号港把最老的 已经准备好进入1号端口。总共是2个UOP。
• 因为慢Int有3个周期的延迟,但是对于3个周期的每个周期,只有两个链,没有 伊穆尔 将准备好执行死刑。然而,总是至少有一个 dec/jnz公司 在RS中,所以调度程序可以调度它。总共是1个uop。

现在我们可以计算RS,X中的预期uop数 ,在任何给定循环N结束时:

十 =X个 _N-1号 +(在周期N开始时RS中要分配的UOP数量)—(在周期N开始时将被分派的UOP的预期数量)
=X个 _N-1号 +4-((0+1)*1/3+(1+1)*2/3)
=X个 _N-1号 +12/3至5/3
=X个 _N-1号 +7/3全部N>0

_0个 =4个。这是一个简单的递归,可以通过展开X来解决 _N-1号 .

十 =4+2.3*N表示全部N>=0

哈斯韦尔的RS有60个条目。我们可以确定RS预计将满的第一个周期:

60=4+7/3*N
N=56/2.3=24.3

因此,在24.3周期结束时,预计RS将满。这意味着在周期25.3开始时,RS将无法接收任何新的UOP。现在,迭代次数,我,在考虑中,决定了你应该如何进行分析。由于依赖关系链至少需要3*I个周期才能执行,因此要达到24.3个周期,大约需要8.1次迭代。因此,如果迭代次数大于8.1(这里就是这种情况),您需要分析在24.3周期之后发生了什么。

调度程序在每个周期以以下速率发送指令(如上所述):

1
2
2
1
2
2
1
2
.
.

但分配器不会在RS中分配任何UOP,除非至少有4个可用条目。否则,它不会浪费能量以次优吞吐量发布UOP。然而,只有在每4个周期的开始,RS中才有至少4个空闲条目。因此,从周期24.3开始,分配器预计每4个周期中有3个会停止。

对正在分析的代码的另一个重要观察是,从来不会有超过4个UOP可以被分派,这意味着每个周期离开其执行单元的UOP的平均数量不超过4个。最多可以从重新排序缓冲区(ROB)中撤消4个UOP。这意味着抢劫永远不会走上关键的道路。换句话说,性能由调度吞吐量决定。

我们现在可以相当容易地计算IPC(每周期的指令数)。ROB条目看起来像这样:

imul eax, eax     -  N
imul edx, edx     -  N + 1
dec ecx/jnz .loop -  M
imul eax, eax     -  N + 3
imul edx, edx     -  N + 4
dec ecx/jnz .loop -  M + 1

右边的列显示指令可以失效的周期。失效按顺序发生,并受关键路径延迟的限制。这里每个依赖链具有相同的路径长度,因此它们都构成长度为3个循环的两个相等的关键路径。所以每3个周期,就有4条指令失效。所以IPC是4/3=1.3,CPI是3/4=0.75。这比理论上的最优IPC 4小得多(即使不考虑微观和宏观融合)。因为退休是按顺序发生的,所以退休行为也会是一样的。

我们可以用这两种方法检查我们的分析 perf 还有艾卡。我来讨论 性能 . 我有一个哈斯韦尔的CPU。

perf stat -r 10 -e cycles:u,instructions:u,cpu/event=0xA2,umask=0x10,name=RESOURCE_STALLS.ROB/u,cpu/event=0x0E,umask=0x1,cmask=1,inv=1,name=UOPS_ISSUED.ANY/u,cpu/event=0xA2,umask=0x4,name=RESOURCE_STALLS.RS/u ./main-1-nolfence

 Performance counter stats for './main-1-nolfence' (10 runs):

         30,01,556      cycles:u                                                      ( +-  0.00% )
         40,00,005      instructions:u            #    1.33  insns per cycle          ( +-  0.00% )
                 0      RESOURCE_STALLS.ROB                                         
         23,42,246      UOPS_ISSUED.ANY                                               ( +-  0.26% )
         22,49,892      RESOURCE_STALLS.RS                                            ( +-  0.00% )

       0.001061681 seconds time elapsed                                          ( +-  0.48% )

有一百万次迭代,每次大约需要3个周期。每次迭代包含4条指令,IPC为1.33。 RESOURCE_STALLS.ROB 显示由于完全ROB而暂停分配器的周期数。这当然不会发生。 UOPS_ISSUED.ANY 性能 RESOURCE_STALLS.RS 统计由于RS满而暂停分配程序的周期数。这接近于 UOPS U发布。任何 因为分配器不会因为任何其他原因暂停(尽管由于某些原因,差异可能与迭代次数成正比,但我必须查看T>1的结果)。

对代码的分析 lfence公司 可以扩展以确定如果 在两者之间添加了 伊穆尔 性能 结果优先(不幸的是,IACA不支持 lfence公司 ):

perf stat -r 10 -e cycles:u,instructions:u,cpu/event=0xA2,umask=0x10,name=RESOURCE_STALLS.ROB/u,cpu/event=0x0E,umask=0x1,cmask=1,inv=1,name=UOPS_ISSUED.ANY/u,cpu/event=0xA2,umask=0x4,name=RESOURCE_STALLS.RS/u ./main-1-lfence

 Performance counter stats for './main-1-lfence' (10 runs):

       1,32,55,451      cycles:u                                                      ( +-  0.01% )
         50,00,007      instructions:u            #    0.38  insns per cycle          ( +-  0.00% )
                 0      RESOURCE_STALLS.ROB                                         
       1,03,84,640      UOPS_ISSUED.ANY                                               ( +-  0.04% )
                 0      RESOURCE_STALLS.RS                                          

       0.004163500 seconds time elapsed                                          ( +-  0.41% )

观察到循环数增加了大约1000万,或者每次迭代增加了10个循环。循环次数并不能告诉我们多少。失效指令的数量增加了一百万条,这是意料之中的。我们已经知道 lfence公司 不会让指令更快完成,所以 资源摊位.ROB UOPS U发布。任何 和 资源摊位 特别有趣。在这个输出中, 统计周期,而不是计量单位。也可以计算UOP的数量(使用 cpu/event=0x0E,umask=0x1,name=UOPS_ISSUED.ANY/u 而不是 cpu/event=0x0E,umask=0x1,cmask=1,inv=1,name=UOPS_ISSUED.ANY/u )每次迭代增加了6个UOP(没有融合)。这意味着 介于两者之间 伊穆尔 s被解码成6个UOP。一百万美元的问题现在是这些UOP做什么以及它们如何在管道中移动。

是零。那是什么意思?这表示当分配器看到 lfence公司 lfence公司 直到 退休。由于循环体只包含3个其他UOP,因此60个条目RS永远不会满。事实上,它总是几乎是空的。

实际上,IDQ并不是一个简单的队列。它由多个可以并行操作的硬件结构组成。计量单位数量 lfence公司 lfence公司 UOP在IDQ的任何结构的前面,它暂停该结构的分配,直到ROB为空。因此,不同的计量单位是美元,具有不同的硬件结构。

UOPS U发布。任何 lfence公司 它可以告诉我们退出一条指令并分配下一条指令所需的时间。可以使用以下程序集代码来执行此操作:

TIMES T lfence

T . 对于足够大的T,通过测量 UOPS U发布。任何 lfence公司 . 那是因为 UOPS U发布。任何 每5个周期增加4倍。所以在每4个周期之后,分配器会发出另一个 lfence公司

我们的循环如下:

imul eax, eax
lfence
imul edx, edx
dec ecx
jnz .loop

在任何周期 lfence公司 边界,ROB将包含从ROB顶部开始的以下指令(最早的指令):

imul edx, edx     -  N
dec ecx/jnz .loop -  N
imul eax, eax     -  N+1

imul eax, eax . 这发生在N+4周期。分配器暂停周期计数将在N+1、N+2、N+3和N+4周期期间递增。不过,它将再循环5次,直到 伊穆尔eax,eax lfence公司 IDQ中的UOP并分配下一组指令,然后才能在下一个周期中分派它们。这个 性能 输出告诉我们,每次迭代大约需要13个周期,分配器暂停(因为 lfence公司

这个问题的图表只显示T=100的循环数。然而,在这一点上还有另一个(最后的)膝盖。因此,最好绘制高达T=120的循环,以查看完整的模式。

我认为你的测量是准确的,解释是微体系结构,而不是任何一种测量误差。

我认为你的中到低T的结果支持这样的结论 lfence 阻止前端发出超过 lfence公司 直到所有先前的指令失效 ,而不是让两个链中的所有UOP都已发布并等待 lfence公司 打开开关,让每个链的倍数开始以交替周期分配。

lfence公司 没有阻塞前端,开销也不会随着t而增加。)

你输了 imul 当只有来自第一个链的UOP在调度程序中时的吞吐量,因为前端没有通过 imul edx,edx 还有循环分支。当管道大部分被排干,第二个链上的UOP只剩下时,在窗口的末端循环相同的次数。

头顶三角洲在T=60左右呈线性。我没有查数字,但上面的坡度看起来很合理 T * 0.25 三角洲的增长速度可能是整个无低频周期的1/12 .

所以(鉴于 在T<60的情况下:

no_lfence cycles/iter ~= 3T                  # OoO exec finds all the parallelism
lfence    cycles/iter ~= 3T + T/4 + 9.3      # lfence constant + front-end delay
                delta ~=      T/4 + 9.3

@玛格丽特报告说 T/4 2*T / 4 ,但我本来希望在开始和结束时都是T/4,因为三角洲的总坡度是2T/4。

大约T=60之后,delta增长得更快(但仍然是线性的),其斜率约等于总无lfence循环,因此约为3c/T。 which have a 60-entry or 54-entry scheduler respectively . 天空湖是97号入口。

RS跟踪未执行的UOP。每个RS条目包含一个未使用的域uop,该uop正在等待其输入准备就绪,以及其执行端口,然后才能分派和离开RS .

之后 lfence公司 ,前端每时钟发出4个,后端每3个时钟执行1个,在大约15个周期内发出60个UOP,在此期间只有5个 伊穆尔 来自 edx ^2个 .)

对于大T,RS很快就会填满,此时前端只能以后端的速度前进。(对于小T,我们点击下一个迭代的 lfence公司 在这种情况发生之前,这就阻碍了前端的发展)。 当T>RS_大小时 ,后端看不到来自 eax imul链,直到足够的后端进程通过 链子在RS里腾出了空间。在那一点上,一个 伊穆尔

记得从第一部分开始 lfence公司 只执行第一个链=之前的时间 lfence公司 只执行第二个链。这也适用于这里。

即使没有 lfence公司 ,对于T>RS U大小 ,但在长链的两边都有重叠的机会。抢劫犯的大小至少是RS的两倍,所以当没有被 即使T比调度程序的容量稍大,也应该能够保持两条链的连续运行。(记住UOP一执行完就离开RS。我不确定这是否意味着他们必须 完成 执行并转发它们的结果,或者只是开始执行,但对于简短的ALU指令来说,这是一个小的区别。一旦他们完成了,只有抢劫犯会按程序顺序抓住他们直到他们退休。)

ROB和register文件不应该限制无序窗口的大小( http://blog.stuffedcow.net/2013/05/measuring-rob-capacity/ )在这种假设的情况下,或者在你的真实情况下。它们都应该很大。

阻塞前端是 lfence公司 关于英特尔的uarches . 手册只说以后的说明不能 执行 . 这一措辞将允许前端将它们全部发布/重命名为调度程序(预订站)并在 lfence公司 仍在等待,只要没有发送到执行单元。

所以一个弱者 lfence公司 可能会有平顶高达T=RS_大小,然后相同的坡度,你现在看到的T>60。

请注意,在 lfence公司 执行 ,而不是(据我所知)代码获取。仅仅触发代码获取(AFAIK)对幽灵或崩溃攻击没有用处。可能是一个定时侧通道来检测它是如何解码的,它可以告诉你一些关于获取的代码。。。

我认为AMD的LFENCE至少在实际的AMD CPU上同样强大,当相关的MSR被启用时。( Is LFENCE serializing on AMD processors?

额外的 lfence公司 间接费用:

你的结果很有趣,但我一点也不惊讶 lfence公司 本身(对于小T),以及与T成比例的成分。

记住这一点 lfence公司 不允许以后的指令启动,直到以前的指令 . 这可能至少比结果准备好绕过其他执行单元(即正常延迟)时晚几个周期/管道阶段。

所以对于小T来说,通过要求结果不仅准备好,而且还要写回寄存器文件,将额外的延迟添加到链中是非常重要的。

可能需要一个额外的周期 允许发出/重命名阶段在检测到之前最后一条指令的失效后重新开始操作。问题/重命名过程需要多个阶段(周期),可能在 开始 而不是在将UOP添加到核心的OoO部分之前的最后一步。

即使是背靠背 根据Agner Fog的测试,它本身在SnB家族上有4个周期的吞吐量。 Agner Fog reports 2个融合域UOP(没有未融合),但在Skylake上,如果我只有1个融合域,我将其测量为6个融合域(仍然没有未融合) lfence公司 . 但更多 lfence公司 背对背,UOP更少!低至~2 uops/ lfence公司 有很多背对背的,这就是艾格纳的测量方法。

lfence公司 / dec jnz (一个没有工作的紧循环)在SKL上每10个周期运行1次迭代,所以这可能会让我们了解真正的额外延迟 lfence公司 即使没有前端和RS的全部瓶颈,也会添加到dep链中。

测量 lfence公司 头顶上只有 dep链 ,OoO exec不相关:

.loop:
    ;mfence                  ; mfence here:  ~62.3c (with no lfence)
    lfence                   ; lfence here:  ~39.3c
    times 10 imul eax,eax    ; with no lfence: 30.0c
    ; lfence                 ; lfence here:  ~39.6c
    dec   ecx
    jnz   .loop

没有 lfence公司 ,按预期的30.0c/iter运行。与 ,每iter运行约39.3c,因此 lfence公司 有效地为关键路径dep链增加了约9.3c的“额外延迟”。(和6个额外的融合域UOP)。

与 lfence公司 lfence公司 允许继续执行。既然如此,我想知道为什么会慢。不是因为分支失误。

像@BeeOnRope在comments中建议的那样,按程序顺序交错链不需要无序执行就可以利用ILP,因此这非常简单:

.loop:
    lfence      ; at the top of the loop is the lowest-overhead place.

%rep T
    imul   eax,eax
    imul   edx,edx
%endrep

    dec     ecx
    jnz    .loop

你可以把一双短的 times 8 imul 内链 %rep 让OoO高管过得轻松。

脚注1:前端/RS/ROB如何交互

我的思维模式是,前端的issue/rename/allocate阶段向两个RS添加新的uop 和 同时抢劫。

UOP在执行后离开RS,但在ROB中呆到退休。ROB可能很大,因为它从未被扫描到查找第一个就绪的uop的顺序不正确,只是被扫描以检查最旧的uop是否已完成执行,从而准备退出。

UOP类 nop , xor eax,eax lfence公司 ,它在前端处理(不需要任何端口上的任何执行单元) 只有 对抢劫犯来说,已经被处决了。(一个ROB条目可能有一点标记它已经准备好退出,而不是仍在等待执行完成。这就是我说的状态。对于那些 做 需要一个执行端口,我假设ROB位是通过 completion port

UOP从发行到 退休 .

UOP从发行到 执行 . ,例如。 for the other half of a cache-line-split load ,或者如果它是在预期加载数据到达时发送的,但实际上它没有。(缓存未命中或其他冲突,如 Weird performance effects from nearby dependent stores in a pointer-chasing loop on IvyBridge. Adding an extra load speeds it up? )或者当加载端口推测它可以在开始TLB查找之前绕过AGU,从而以较小的偏移量缩短指针跟踪延迟- Is there a penalty when base+offset is in a different page than the base?

所以我们知道RS不能在uop发送时删除它,因为它可能需要重播。(甚至可以发生在消耗加载数据的非加载uop上)但是任何需要重放的推测都是短期的,而不是通过uop链,因此一旦结果从执行单元的另一端出来,uop就可以从RS中删除。这可能是完成端口所做的一部分,以及将结果放到旁路转发网络上。

脚注2:微融合uop需要多少RS条目?

TL:DR:P6家族:RS融合,SnB家族:RS未融合。

在Sandybridge家族中,一个微熔合uop被发布到两个独立的RS条目 Micro fusion and addressing modes . Sandybridge家族更紧凑的uop格式在所有情况下都不能表示ROB中的索引寻址模式。)

在ALU uop准备就绪之前,负载可以独立调度。(或者对于微熔合存储,存储地址或存储数据UOP中的任何一个都可以在其输入准备就绪时发送,而无需等待两者。)

我用问题中的双dep链方法在Skylake上进行了实验测试(RS size=97) ,带微型保险丝 or edi, [rdi] mov + or ,和另一个dep链 rsi . ( Full test code, NASM syntax on Godbolt )

; loop body
%rep T
%if FUSE
    or edi, [rdi]    ; static buffers are in the low 32 bits of address space, in non-PIE
%else
    mov  eax, [rdi]
    or   edi, eax
%endif
%endrep

%rep T
%if FUSE
    or esi, [rsi]
%else
    mov  eax, [rsi]
    or   esi, eax
%endif
%endrep

uops_executed.thread (未使用的域)每周期(或每秒 perf 为我们计算),我们可以看到一个吞吐量数字,它不依赖于单独的和折叠的负载。

在小T(T=30)条件下,所有的ILP都可以被利用,无论有无微融合,每个时钟都可以得到约0.67uops。(我忽略了dec/jnz中每个循环迭代1个额外uop的小偏差。与我们看到的微熔合UOP仅使用1个RS入口的效果相比,这可以忽略不计)

记住这一点+ 或 是2个UOP,飞行中有2个dep链,所以这是4/6,因为 或edi,[rdi] 有6个周期的延迟。(不是5,这是令人惊讶的,见下文。)

T=60时,对于FUSE=0,每个时钟仍有约0.66个未使用的UOP执行,对于FUSE=1,仍有约0.64个未使用的UOP执行。我们仍然可以找到基本上所有的ILP,但它只是刚刚开始下降,因为这两个dep链是120 uops长(相比之下,a RS的大小为97)。

当T=120时,对于FUSE=0,每个时钟有0.45个未使用的UoP,对于FUSE=1,则有0.44个未使用的UoP。我们肯定已经过了膝盖,但仍然发现 一些 在国际生命周期计划中。

. 相反,FUSE=0或1在任何T处几乎没有差别(包括较大的T=200:FUSE=0:0.395uops/时钟,FUSE=1:0.391uops/时钟)。我们得去 非常 大T在我们开始之前,1个dep链在飞行,完全控制2个在飞行的时间,并下降到0.33 uops/时钟(2/6)。

奇怪的是:我们有一个很小但仍然可以测量的差异,在吞吐量融合与未融合,与单独 压敏电阻

其他怪事:总数 是 轻微地 对于保险丝=0,在任何给定T下都要降低,例如2418826591,而对于T=60,则要降低2419020155。这一差异在2.4G中可重复至+60k,非常精确。FUSE=1在总时钟周期中较慢,但大多数差异来自每个时钟的较低UOP,而不是更多UOP。

简单的寻址模式,如 [rdi] 应该只有4个周期的延迟,所以load+ALU应该只有5个周期。但是我测量了6个周期的负载使用延迟 or rdi, [rdi] ,或者使用单独的MOV加载,或者使用任何其他ALU指令,我永远无法将加载部分设置为4c。

[rdi + rbx + 2064] 当dep链中有一个ALU指令时具有相同的延迟,因此看起来Intel的简单寻址模式的4c延迟 当一个加载转发到另一个加载的基址寄存器时应用(最多具有+0..2047位移且没有索引)。

指针跟踪非常常见,因此这是一种有用的优化,但我们需要将其视为一种特殊的负载转发快速路径,而不是一种为ALU指令提前准备好使用的通用数据。

P6系列是不同的:RS条目包含一个融合域uop。

@哈迪发现了 an Intel patent from 2002 ,其中图12显示融合域中的RS。

对Conroe(第一代Core2Duo,E6600)的实验测试表明,T=50时,FUSE=0和FUSE=1之间存在很大差异。( The RS size is 32 entries ).

• T=50保险丝=0:3.272G周期的总时间(0.62IPC=0.31负载+或每时钟)。( 性能 / ocperf.py 没有活动 uops_executed 在尼哈林之前的厕所里,我没有 oprofile 安装在那台机器上。)

• T=24熔丝=0和熔丝=1之间的差别可以忽略不计,分别为0.47 IPC和0.9 IPC(约0.45负载+或每时钟)。

T=24在循环中的代码仍然超过96字节,对于Core2的64字节(预解码)循环缓冲区来说太大了,所以它不会更快,因为它适合循环缓冲区。没有uop缓存,我们不得不担心前端,但我认为我们很好,因为我只使用2字节的单uop指令,该指令应该很容易解码为每个时钟4个融合域uop。