登记册计算管道

Question

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

这是简单测试程序的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”以恒定大小分配并用零填充。重要的“工作”发生在html" target="_blank">for循环中，其中所有向量变量都分配给5（只是一个随机值）。

我想问一下，这个汇编代码是否在管道中造成了一些暂停？原因可能是所有指令都以某种方式相互关联，并在相同的寄存器上工作。例如，管道需要等待指令cmp-rax r9，然后mov eax，edxactually assign value to eax/rax？

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

我的目标体系结构是天湖 i5-6400

Answer 1

正如Hadi所解释的，无序执行隐藏了< code>inc供给存储寻址模式的延迟。

在该迭代中的inc执行后的循环执行之前，存储无法执行，但在大多数UARCHE上只有1个周期的延迟，因此没有太多的延迟来隐藏无序执行。

编译器发出带有额外< code>mov eax，edx的低效循环的原因是，您使用了带有64位< code>size_t上限的< code >无符号 (32位)循环计数器。

C语言中的无符号类型具有编译器必须实现的定义良好的溢出行为（环绕）（不像有符号溢出是UB）。因此，正如所写的那样，循环是无限的，如果vec.size（）

（编译器通常不会对无限循环是UB进行攻击，即使ISO C表示，如果它们不包含易失性或原子操作或库调用，则它们是。

如果你使用int i，你就不会有这个问题。签名溢出是 UB，因此编译器可以假定它不会发生，并将 i 提升为size_t和指针的宽度。或者更好的是，使用size_t i，这就是它的用途。无论哪种方式，希望编译器可以将循环转换为指针增量并使用简单的寻址模式，并使用 SSE 或 AVX 进行自动矢量化，以进行 16 或 32 字节存储。

不过，额外的mov eax， edx是100%冗余的。i已经正确地零扩展到RDX，因此编译器可以使用inc edx/cmp rdx， r9。无论您使用什么编译器，这都是错过的优化。

Answer 2

在经典的教科书管道意义上，是的，这似乎是一种停滞情况，因为您有一个操作的结果被用作下一个操作的操作数。但即使在教科书中，你也会看到可能的解决方案。

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

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

出于许多原因，我不指望你能创造出一些你能真正看出与简单的噪音有什么不同的东西。首先，你可能在一个操作系统上运行它，并通过代码层询问操作系统这个循环的时间。我不指望你能从操作系统的噪音中分离出你要做的事情。运行DOS和禁用中断将是一个开始，但我仍然认为除了处理器/系统的噪声之外，你不会看到任何东西。

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

为了让代码在x86上表现得相当好，需要做大量的工作，这就是高成本和高功耗的原因。许多经典的性能陷阱已经被消除，从x86 ISA的角度来看，您最终在哪里找到它们并不一定是显而易见的(您必须在实现级别查看它，才能发现陷阱，如果有的话)。

Answer 3

TL；博士:

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

案例2：适合L2的缓冲区。向量构造函数或对std::fill的调用将把缓冲区完全放在L2中。然而，L1必须将脏线写回L2，L1D和L2之间只有一个端口。此外，这些线必须从L2获取到L1D。L1D和L2之间的64B/周期带宽应该能够轻松处理，也许偶尔会有争用（更多细节见下文）。所以总的来说，瓶颈与案例1相同。您使用的特定缓冲区大小约为40KB，不适合Intel和最近的AMD处理器的L1D，但适合L2。尽管在同时多线程（SMT）的情况下，可能会有来自其他逻辑内核的一些额外争用。

情况3：不适合二级缓存的缓冲区。需要从三级缓存或内存中提取行。二级DPL预取器可以跟踪存储并将缓冲区预取到二级缓存，从而缓解长延迟。单个L2端口与L1写回和填充缓冲区一起成为瓶颈。这很严重，尤其是当缓冲区不适合L3时，因为L3中的互连也可能位于关键路径上。缓存子系统无法处理1存储吞吐量。最相关的两个性能计数器是L1D_PEND_MISS。REQUEST_FB_FULL和RESOURCE_STALLS.SB。

首先，注意vector本身的构造函数（可能会内联）通过内部调用memset来将元素初始化为零memset基本上与循环做的事情相同，但它是高度优化的。换句话说，就big-O表示法而言，两者在元素数量上都是线性的，但memset的常数因子较小。此外，std:：fill也在内部调用memset将所有元素设置为零（再次）std:：fill也可能会内联（启用适当的优化）。因此，在这段代码中确实有三个循环。使用std:：vector初始化向量会更有效

让我们仔细检查代码：

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。第二条指令将解码为两个uop，在前端融合。第三条指令是寄存器到寄存器的移动，是寄存器重命名阶段移动消除的候选指令。如果不运行代码3，很难确定移动是否会被消除。但即使没有消除，指令也将按如下方式发送：

               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)

cmp 和 jb 指令将被宏注入到单个 uop 中。因此，融合域中的 uop 总数均为 4，未融合域中的 uop 总数为 5。他们之间正好有一个跳跃。因此，可以每个周期发出单个循环迭代。

由于< code>inc与< code>mov-store之间的依赖关系，这两条指令不能在同一个周期内分派。尽管如此，来自前一个迭代的< code>inc可以与来自前一个迭代的UOP一起调度。

有四个端口(p0、p1、p5、p6)可供< code>inc和< code>mov调度。对于预测占用的< code>cmp/jb，正好有一个端口p6。< code>mov dword ptr [rcx rax*4]，5的STA uop有三个端口(p2、p3、p7)，STD uop有一个端口p4。(虽然p7不能处理指定的寻址模式。)因为每个只有一个端口，所以可以达到的最大执行吞吐量是每个周期1次迭代。

可惜吞吐量会更差；许多商店将错过L1D。L1D预取器不能预取处于独占一致性状态的行，并且不跟踪存储请求。不过还好很多店会合并。循环中的连续存储以虚拟地址空间中的顺序位置为目标。由于行的大小是64字节，并且每个存储的大小是4字节，所以每16个连续的存储都是针对同一高速缓存行的。这些商店可以在商店缓冲区中合并，但它们不会合并，因为一旦它们成为ROB的顶部，它们将尽可能早地退出。循环体非常小，所以16个存储中不太可能有几个被合并到存储缓冲区中。然而，当组合存储请求被发送到L1D时，它将未命中，并且将分配一个LFB，这也支持组合存储。L2缓存DPL预取器能够跟踪RFO的请求，所以希望我们几乎总是能命中L2。但是从L2到L1至少需要10-15个周期。但是，在存储实际提交之前，RFO可能会提前发送。同时，很可能需要从L1中逐出脏行，以便从传入行中腾出空间进行写入。被逐出的行将被写入写回缓冲区。

如果不运行代码，很难预测整体效果如何。两个最相关的性能计数器是< code>L1D_PEND_MISS。REQUEST_FB_FULL和< code>RESOURCE_STALLS。SB。

L1D在Ivy Bridge、Haswell和Skylake上只有一个16字节、32字节、64字节宽的存储端口。因此，商店将致力于这些粒度。但单个LFB始终可以保存完整的64字节缓存线。

存储融合uop的总数等于元素的数量（本例中为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 之间的所有通信，包括写回和 RFO。在这种情况下，LFB 的数量也是一个瓶颈，因为在写回缓冲区可用之前，LFB 不会写入缓存。否则，LFB将很快填满，特别是如果L2 DPL预取器能够及时交付生产线。显然，将可缓存的 WB 存储流式传输到 L1D 中非常低效。

如果您运行代码，您还需要考虑对< code>memset的两次调用。

（1） 在Sandy Bridge和Ivy Bridge上，指令mov dword ptr[rcx rax*4]，5将被取消限制，导致融合域中的每次迭代为5 uops。因此，前端可能处于关键路径上。

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

（3） @PeterCordes发现，移动消除在Skylake上大部分时间都会发生。我也可以在Haswell上确认这一点。