寄存器计算流水线

Pipeline on Registers calculation

我最近在阅读有关管道优化的内容。我想问一下我是否正确理解处理器如何处理流水线。

这是简单测试程序的 C++ 代码:

#include <vector>

int main()
{
    std::vector<int> vec(10000u);
    std::fill(vec.begin(), vec.end(), 0);
    for (unsigned i = 0u; i < vec.size(); ++i)
    {
        vec[i] = 5;
    }

    return 0;
}

以及for循环产生的部分汇编代码:

...
00007FF6A4521080  inc         edx  
    {
        vec[i] = 5;
00007FF6A4521082  mov         dword ptr [rcx+rax*4],5  
00007FF6A4521089  mov         eax,edx  
00007FF6A452108B  cmp         rax,r9  
00007FF6A452108E  jb          main+80h (07FF6A4521080h)  
    }
...

在程序中,向量“vec”被分配为常数大小并用零填充。重要 "work" 发生在 for 循环中,其中所有向量变量都分配给 5(只是一个随机值)。

我想问一下这段汇编代码是否会在流水线中造成一些停顿?原因是所有指令都以某种方式相关并在相同的寄存器上工作。例如,在 mov eax, edx 实际赋值给 eax/rax?

之前,流水线需要等待指令 cmp rax r9

循环 10000 次是分支预测应该开始工作的地方。 jb 指令跳转10000次,最后才通过。这意味着分支预测器应该很容易地预测大部分时间都会发生跳转。但是,如果代码本身在循环内停滞,从我的角度来看,这种优化将毫无意义。


我的目标架构是 Skylake i5-6400

在经典的教科书流水线意义上,是的,这似乎是一种停顿情况,因为您将一个操作的结果用作下一个操作的操作数。但即使在教科书中,您也会看到对此的可能解决方案。

并且以多种方式实际实现 x86 不会像表面价值汇编语言可能暗示的那样影响性能。

这个循环的分支预测也是如此。分支预测可以同时以不同的形式出现。一个是你会想到的第一件事是逻辑以某种方式预先计算结果,以便提取可以提前开始(所有分支预测所做的就是抛出一个额外的提取,顺便说一句,这可能会产生负面影响,一些时钟周期早于正常提取)。或者不打扰预先计算,只是为了以防万一而简单地为该备用路径抛出提取,并允许正常提取以涵盖不满足条件的情况。您 can/will 看到实现的另一个解决方案是一个简单的缓存,无论是深缓存还是短缓存。我记得上次我在 00007FF6A452108E 附近,那是一条分支指令,它让我们提前获取数据,而不用等待条件是否通过。有些人可能只记得最后几个分支,有些人可能记得更多,对于像这样的简单循环 运行 它 10 次或 100 亿次你不一定会看到分支预测。

出于多种原因,我不希望您能够创造出您可以真正看到与简单噪声相比的差异的东西。首先也是最重要的是,您可能 运行 在操作系统上执行此操作,并通过代码层向操作系统询问该循环的时间。我不希望您能够将您在这里尝试做的事情与操作系统的噪音隔离开来。 运行 DOS 和禁用中断将是一个开始,但我仍然认为除了 processor/system 的噪音之外你不会看到任何东西。

如果您想试验或查看这些效果,您需要选择不同的处理器和系统。或者您需要研究特定芯片的英特尔文档(或 amd)以及您正在使用的芯片的步进和固件补丁,然后您应该能够制作一些指令序列,与功能相同但执行不同的序列相比,您可以检测到这些指令序列.

要使代码在 x86 上表现得相当好,需要做大量工作,这就是高成本和高功耗的全部原因。许多经典的性能陷阱已被消除,从 x86 ISA 视图来看,您最终发现它们的位置并不一定很明显(您必须在实现级别查看它才能看到陷阱)。

长话短说:

案例 1:适合 L1D 的缓冲区。矢量构造函数或对 std::fill 的调用会将缓冲区完全放入 L1D 中。在这种情况下,管道和 L1D 缓存的每周期 1 个存储吞吐量是瓶颈。

情况 2:适合 L2 的缓冲区。向量构造函数或对 std::fill 的调用会将缓冲区完全放入 L2。但是,L1 必须将脏线写回 L2,并且 L1D 和 L2 之间只有一个端口。此外,还必须将线路从 L2 提取到 L1D。 L1D 和 L2 之间的 64B/周期带宽应该能够轻松处理,也许偶尔会发生争用(更多详细信息请参见下文)。因此,总体瓶颈与案例 1 相同。您使用的特定缓冲区大小(大约 40KB)不适合 Intel 的 L1D 和最近的 AMD 处理器,但适合 L2。尽管在同步多线程 (SMT) 的情况下,其他逻辑核心可能会有一些额外的争用。

案例 3:不适合 L2 的缓冲区。这些行需要从 L3 或内存中获取。 L2 DPL 预取器可以跟踪存储并将缓冲区预取到 L2 中,从而缓解长延迟。单个 L2 端口与 L1 写回和填充缓冲区一起成为瓶颈。这很严重,特别是当缓冲区不适合 L3 时,互连也可能位于关键路径上。 1 个存储吞吐量对于缓存子系统来说太大了,无法处理。两个最相关的性能计数器是 L1D_PEND_MISS.REQUEST_FB_FULLRESOURCE_STALLS.SB.


首先,请注意 vector 的构造函数(可能会内联)本身通过在内部调用 memset 将元素初始化为零。 memset 基本上和你的循环做同样的事情,但它是高度优化的。换句话说,就大O表示法而言,两者在元素数量上都是线性的,但memset具有更小的常数因子。此外,std::fill 还内部调用 memset 将所有元素设置为零(再次)。 std::fill 也可能会被内联(启用适当的优化)。因此,您在那段代码中确实有三个循环。使用 std::vector<int> vec(10000u, 5) 初始化向量会更有效。现在让我们开始循环的微体系结构分析。我只会讨论我期望在现代英特尔处理器上发生的事情,特别是 Haswell 和 Skylake1.

让我们仔细检查一下代码:

00007FF6A4521080  inc         edx
00007FF6A4521082  mov         dword ptr [rcx+rax*4],5  
00007FF6A4521089  mov         eax,edx  
00007FF6A452108B  cmp         rax,r9  
00007FF6A452108E  jb          main+80h (07FF6A4521080h) 

第一条指令将被解码为单个 uop。第二条指令将被解码为在前端融合的两个微指令。第三条指令是寄存器到寄存器的移动,是寄存器重命名阶段移动消除的候选指令。如果不使用 运行 编码 3,很难确定这步棋是否会被淘汰。但即使没被淘汰,也会派出指令如下2:

               dispatch cycle                            |         allocate cycle

cmp         rax,r9                           macro-fused | inc         edx                           (iteration J+3)
jb          main+80h (07FF6A4521080h)     (iteration J)  | mov         dword ptr [rcx+rax*4],5       (iteration J+3)
mov         dword ptr [rcx+rax*4],5       (iteration J+1)| mov         eax,edx                       (iteration J+3)
mov         eax,edx                       (iteration J+1)| cmp         rax,r9                            macro-fused
inc         edx                           (iteration J+2)| jb          main+80h (07FF6A4521080h)     (iteration J+3)
---------------------------------------------------------|---------------------------------------------------------
cmp         rax,r9                           macro-fused | inc         edx                           (iteration J+4)
jb          main+80h (07FF6A4521080h)     (iteration J+1)| mov         dword ptr [rcx+rax*4],5       (iteration J+4)
mov         dword ptr [rcx+rax*4],5       (iteration J+2)| mov         eax,edx                       (iteration J+4)
mov         eax,edx                       (iteration J+2)| cmp         rax,r9                            macro-fused
inc         edx                           (iteration J+3)| jb          main+80h (07FF6A4521080h)     (iteration J+4)

cmpjb 指令将宏融合为一个 uop。因此,融合域中的微指令总数为 4,未融合域中为 5。其中恰好有一个跳跃。因此,每个循环可以发出一个循环迭代。

由于incmov-store之间的依赖关系,这两个指令不能在同一个周期内调度。尽管如此,上一次迭代的 inc 可以使用上一次迭代的微指令进行分派。

有四个端口(p0、p1、p5、p6)可以发送incmov。对于 predicted-taken cmp/jb,只有一个端口 p6。 mov dword ptr [rcx+rax*4],5 的 STA uop 有 3 个端口(p2、p3、p7),STD uop 有 1 个端口 p4。 (虽然p7不能处理指定的寻址方式。)因为每个只有一个端口,所以最大可以达到的执行吞吐量是每个周期迭代1次。

不幸的是,吞吐量会更差;很多店都会错过L1D。 L1D 预取器无法在排他一致性状态下预取行,并且不跟踪存储请求。但幸运的是,许多商店将合并。循环中的连续存储以虚拟地址 space 中的顺序位置为目标。由于一行的大小为 64 字节,而每个存储的大小为 4 字节,因此每 16 个连续的存储都指向同一缓存行。这些商店可以在商店缓冲区中合并,但不会合并,因为一旦商店位于 ROB 的顶部,它们将尽快退出。循环体非常小,因此 16 个商店中的少数商店不太可能合并到商店缓冲区中。然而,当组合存储请求被发送到 L1D 时,它会丢失并分配一个 LFB,它也支持组合存储。 L2 缓存 DPL 预取器能够跟踪 RFO 请求,因此希望我们几乎总是命中 L2。但是至少需要10-15个周期才能从L2到L1。不过,RFO 可能会在存储实际提交之前提前发送。同时,很可能需要从 L1 中逐出一条脏线,以使 space 来自要写入的传入线。逐出的行将写入回写缓冲区。

如果没有 运行 代码,很难预测整体效果。两个最相关的性能计数器是 L1D_PEND_MISS.REQUEST_FB_FULLRESOURCE_STALLS.SB.

L1D在Ivy Bridge、Haswell和Skylake上只有一个存储端口,分别为16字节、32字节、64字节宽。因此商店将以这些粒度进行承诺。但是单个 LFB 始终可以容纳完整的 64 字节缓存行。

存储融合微指令的总数等于元素的数量(在本例中为 100 万)。要获得所需的 LFB 数量,除以 16 得到 62500 个 LFB,这与 L2 的 RFO 数量相同。在需要另一个 LFB 之前需要 16 个周期,因为每个周期只能调度一个商店。只要 L2 可以在 16 个周期内交付目标行,我们就永远不会阻塞 LFB,实现的吞吐量将接近每个周期 1 次迭代,或者就 IPC 而言,每个周期 5 条指令。这只有在我们几乎总是及时击中 L2 时才有可能。缓存或内存中的任何持续延迟都会显着降低吞吐量。它可能是这样的:16 次迭代的突发将快速执行,然后管道在 LFB 上停滞一些周期。如果此数字等于 L3 延迟(约 48 个周期),则吞吐量约为每 3 个周期迭代 1 次 (= 16/48)。

L1D 具有有限数量(6 个?)的写回缓冲区来保存逐出的行。此外,L2 只有一个 64 字节的端口,用于 L1D 和 L2 之间的所有通信,包括写回和 RFOs.The 写回缓冲区的可用性也可能在关键路径上。在这种情况下,LFB 的数量也是一个瓶颈,因为在写回缓冲区可用之前,LFB 不会被写入缓存。否则,LFB 将很快填满,尤其是在 L2 DPL 预取器能够及时交付行的情况下。显然,将可缓存的 WB 存储流式传输到 L1D 的效率非常低。

如果您执行 运行 代码,您还需要考虑对 memset.

的两次调用

(1) 在 Sandy Bridge 和 Ivy Bridge 上,the instruction mov dword ptr [rcx+rax*4],5 will get unlaminiated,导致融合域中每次迭代 5 微指令。所以前端可能在关键路径上。

(2) 或类似的东西,取决于循环的第一次迭代的第一条指令是否获得分配器的第一个槽。如果不是,则需要相应地移动显示的迭代次数。

(3) @PeterCordes 发现 Skylake 上大部分时间确实发生了移动消除。我也可以在 Haswell 上确认这一点。

Out-of-order 执行隐藏了 inc 提供存储寻址模式的延迟,如 Hadi 所解释的。

直到迭代执行 inc 之后的循环才能执行存储,但是 inc 在大多数 uarches 上只有 1 个周期的延迟,所以 [=50 的延迟不多=]执行隐藏。


编译器发出带有额外 mov eax,edx 的低效循环的原因是您使用了 unsigned(32 位)循环计数器和64 位 size_t 上限。

C++ 中的

unsigned 类型具有编译器必须实现的 well-defined 溢出行为(回绕)(不同于有符号溢出是 UB)。如所写,如果 vec.size() > UINT_MAX,则循环是无限的,并且 gcc 必须编写与 abstract-machine 在这种情况下的行为相匹配的代码。这会停止你的编译器 auto-vectorizing.

(而且编译器通常不会对无限循环是 UB 持积极态度,即使 ISO C++ 说它们是 UB,如果它们不包含 volatile 或原子操作,或库调用。)

如果您使用 int i,就不会遇到这个问题。有符号溢出是 UB,因此编译器可以假设它不会发生并将 i 提升到 size_t 和指针的宽度。 或者更好,使用 size_t i,这就是它的用途。 无论哪种方式,希望编译器可以将循环转换为 pointer-increment 并使用简单的寻址模式,并且auto-vectorize 使用 SSE 或 AVX 进行 16 或 32 字节存储。


不过,额外的 mov eax,edx 是 100% 多余的。 i 已经正确 zero-extended 进入 RDX,因此编译器 可以 使用 inc edx / cmp rdx, r9。无论您使用什么编译器,这都是一个遗漏的优化。