向量化代码时缓存未命中次数增加

Question

我使用 SSE 4.2 和 AVX 2 向量化了 2 个向量之间的点积，如下所示。该代码是使用带有 -O2 优化标志的 GCC 4.8.4 编译的。正如预期的那样，两者的性能都变得更好（并且 AVX 2 比 SSE 4.2 更快），但是当我使用 PAPI 分析代码时，我发现未命中总数（主要是 L1 和 L2）增加了很多：

没有矢量化：

PAPI_L1_TCM: 784,112,091
PAPI_L2_TCM: 195,315,365
PAPI_L3_TCM: 79,362

使用 SSE 4.2：

PAPI_L1_TCM: 1,024,234,171
PAPI_L2_TCM: 311,541,918
PAPI_L3_TCM: 68,842

使用 AVX 2：

PAPI_L1_TCM: 2,719,959,741
PAPI_L2_TCM: 1,459,375,105
PAPI_L3_TCM: 108,140

我的代码可能有问题还是这种行为正常？

AVX 2 代码：

double vec_dotProduct(const vec& vecs, const unsigned int& start_a, const unsigned int& start_b, const int& n) {
    double dot = 0;
    register int i = 0;
    const int loopBound = n-3;

    __m256d vsum, vecPi, vecCi, vecQCi;

    vsum = _mm256_set1_pd(0);

    double * const pA = vecs.x+start_a ;
    double * const pB = vecs.x+start_b ;

    for( ; i<loopBound ;i+=4){
        vecPi  = _mm256_loadu_pd(&(pA)[i]);
        vecCi  = _mm256_loadu_pd(&(pB)[i]);
        vecQCi = _mm256_mul_pd(vecPi,vecCi);
        vsum   = _mm256_add_pd(vsum,vecQCi);
    }

    vsum = _mm256_hadd_pd(vsum, vsum);

    dot = ((double*)&vsum)[0] + ((double*)&vsum)[2];

    for( ; i<n; i++)
        dot += pA[i] * pB[i];

    return dot;
}

SSE 4.2 代码：

double vec_dotProduct(const vec& vecs, const unsigned int& start_a, const unsigned int& start_b, const int& n) {
    double dot = 0;
    register int i = 0;

    const int loopBound = n-1;

    __m128d vsum, vecPi, vecCi, vecQCi;

    vsum = _mm_set1_pd(0);

    double * const pA = vecs.x+start_a ;
    double * const pB = vecs.x+start_b ;

    for( ; i<loopBound ;i+=2){
        vecPi  = _mm_load_pd(&(pA)[i]);
        vecCi  = _mm_load_pd(&(pB)[i]);
        vecQCi = _mm_mul_pd(vecPi,vecCi);
        vsum   = _mm_add_pd(vsum,vecQCi);
    }

    vsum = _mm_hadd_pd(vsum, vsum);

    _mm_storeh_pd(&dot, vsum);

    for( ; i<n; i++)
        dot += pA[i] * pB[i];

    return dot;
}

非向量化代码：

double dotProduct(const vec& vecs, const unsigned int& start_a, const unsigned int& start_b, const int& n) {
    double dot = 0;
    register int i = 0;

    for (i = 0; i < n; ++i)
    {
        dot += vecs.x[start_a+i] * vecs.x[start_b+i];
    }
    return dot;
}

编辑：非矢量化代码的汇编：

   0x000000000040f9e0 <+0>:     mov    (%rcx),%r8d
   0x000000000040f9e3 <+3>:     test   %r8d,%r8d
   0x000000000040f9e6 <+6>:     jle    0x40fa1d <dotProduct(vec const&, unsigned int const&, unsigned int const&, int const&)+61>
   0x000000000040f9e8 <+8>:     mov    (%rsi),%eax
   0x000000000040f9ea <+10>:    mov    (%rdi),%rcx
   0x000000000040f9ed <+13>:    mov    (%rdx),%edi
   0x000000000040f9ef <+15>:    vxorpd %xmm0,%xmm0,%xmm0
   0x000000000040f9f3 <+19>:    add    %eax,%r8d
   0x000000000040f9f6 <+22>:    sub    %eax,%edi
   0x000000000040f9f8 <+24>:    nopl   0x0(%rax,%rax,1)
   0x000000000040fa00 <+32>:    mov    %eax,%esi
   0x000000000040fa02 <+34>:    lea    (%rdi,%rax,1),%edx
   0x000000000040fa05 <+37>:    add    [=16=]x1,%eax
   0x000000000040fa08 <+40>:    vmovsd (%rcx,%rsi,8),%xmm1
   0x000000000040fa0d <+45>:    cmp    %r8d,%eax
   0x000000000040fa10 <+48>:    vmulsd (%rcx,%rdx,8),%xmm1,%xmm1
   0x000000000040fa15 <+53>:    vaddsd %xmm1,%xmm0,%xmm0
   0x000000000040fa19 <+57>:    jne    0x40fa00 <dotProduct(vec const&, unsigned int const&, unsigned int const&, int const&)+32>
   0x000000000040fa1b <+59>:    repz retq 
   0x000000000040fa1d <+61>:    vxorpd %xmm0,%xmm0,%xmm0
   0x000000000040fa21 <+65>:    retq

Edit2：您可以在下面找到更大 N 的矢量化代码和非矢量化代码之间的 L1 缓存未命中比较（X 标签上的 N 和 y 标签上的 L1 缓存未命中）。基本上，对于更大的 N，矢量化版本中的未命中数仍然多于非矢量化版本。

Answer 1

Rostislav 是正确的，编译器是 auto-vectorizing，从 GCC 文档中关于 -O2 的内容：

“-O2 优化更多。GCC 执行几乎所有支持的优化，不涉及 space-speed 权衡。” （来自这里：https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html）

带有 -O2 标志的 GCC 正在尝试生成最高效的代码，而不偏向于代码大小或速度。

因此，就 CPU 周期而言，-O2 auto-vectorized 代码需要的瓦特最少运行，但不会是最快或最小的代码。这是运行在移动设备和 multi-user 系统上的代码的最佳案例，这些往往是 C++ 的首选用法。如果您想要绝对最大速度而不管它使用多少瓦特，请尝试 -O3 或 -Ofast 如果您的 GCC 版本支持它们，或者使用您的 hand-optimized 更快的解决方案。

这可能是两个因素共同作用的结果。

首先，更快的代码在相同的时间内生成更多对 memory/cache 的请求，这强调了 pre-fetch 预测算法。 L1 缓存不是很大，通常为 1MB - 3MB，并且在该 CPU 核心上的所有运行ning 进程之间共享，因此 CPU 核心不能 pre-fetch 直到之前 pre-fetched 块不再使用。如果代码运行ning 更快，块之间 pre-fetch 的时间就会减少，并且在有效 pipe-lines 的代码中，更多缓存未命中将在 CPU 核心之前执行完全停止，直到挂起的提取完成。

其次，现代操作系统通常通过动态调整线程亲和力在多个内核之间划分 single-threaded 进程，以便跨多个内核使用额外的缓存，即使它不能运行并行的任何代码 - 例如用您的数据填充核心 0 的缓存，然后运行它同时填充核心 1 的缓存，然后运行在核心 1 上同时重新填充核心 0 的缓存，round-robin 直到完成。这 pseudo-parallelism 提高了 single-threaded 进程的整体速度，并且应该大大减少缓存未命中，但只能在非常特殊的情况下才能完成……好的编译器会尽可能生成代码的特定情况。

Answer 2

正如您在一些评论中看到的，缓存未命中来自性能的提高。

例如，对于最新的 CPU，您将能够在每个周期执行 2 个 AVX2 add 或 mul，因此每个周期 512 位。您需要加载数据的时间会更长，因为它需要多个缓存行。

此外，根据您的系统配置方式、超线程、亲和力等，您的调度程序可以同时做其他事情，从而用其他 threads/processes.

污染您的缓存

最后一件事。 CPU 现在非常有效地将简单模式识别为具有非常小循环的模式，然后在几次迭代后自动使用预取。无论如何都不足以解决缓存大小问题。

尝试使用不同大小的 N，您应该会看到有趣的结果。此外，首先对齐您的数据并确保如果您使用 2 个变量，则不会共享相同的缓存行。

向量化代码时缓存未命中次数增加

Increased number of cache misses when vectorizing code

c++

caching

profiling

vectorization

papi