使用openmp + SIMD没有加速

Question

我是Openmp的新手,现在尝试使用Openmp + SIMD内在函数来加速我的程序,但结果远非期望.

为了简化案例而不丢失太多重要信息,我写了一个简单的玩具示例:

#include <omp.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <sys/time.h>

#include "immintrin.h" // for SIMD intrinsics

int main() {
    int64_t size = 160000000;
    std::vector<int> src(size);

    // generating random src data
    for (int i = 0; i < size; ++i)
        src[i] = (rand() / (float)RAND_MAX) * size;

    // to store the final results, so size is the same as src
    std::vector<int> dst(size);

    // get pointers for vector load and store
    int * src_ptr = src.data();
    int * dst_ptr = dst.data();

    __m256i vec_src;
    __m256i vec_op = _mm256_set1_epi32(2);
    __m256i vec_dst;

    omp_set_num_threads(4); // you can change thread count here

    // only measure the parallel part
    struct timeval one, two;
    double get_time;
    gettimeofday (&one, NULL);

    #pragma omp parallel for private(vec_src, vec_op, vec_dst)
    for (int64_t i = 0; i < size; i += 8) {
        // load needed data
        vec_src = _mm256_loadu_si256((__m256i const *)(src_ptr + i));

        // computation part
        vec_dst = _mm256_add_epi32(vec_src, vec_op);
        vec_dst = _mm256_mullo_epi32(vec_dst, vec_src);
        vec_dst = _mm256_slli_epi32(vec_dst, 1);
        vec_dst = _mm256_add_epi32(vec_dst, vec_src);
        vec_dst = _mm256_sub_epi32(vec_dst, vec_src);

        // store results
        _mm256_storeu_si256((__m256i *)(dst_ptr + i), vec_dst);
    }

    gettimeofday(&two, NULL);
    double oneD = one.tv_sec + (double)one.tv_usec * .000001;
    double twoD = two.tv_sec + (double)two.tv_usec * .000001;
    get_time = 1000 * (twoD - oneD);
    std::cout << "took time: " << get_time << std::endl;

    // output something in case the computation is optimized out
    int64_t i = (int)((rand() / (float)RAND_MAX) * size);
    for (int64_t i = 0; i < size; ++i)
        std::cout << i << ": " << dst[i] << std::endl;

    return 0;
}

使用它编译icpc -g -std=c++11 -march=core-avx2 -O3 -qopenmp test.cpp -o test并测量并行部分的经过时间.结果如下(中间值从每次5次运行中挑选出来):

1 thread: 92.519

2 threads: 89.045

4 threads: 90.361

计算似乎令人尴尬地并行,因为不同的线程可以在给定不同索引的情况下同时加载所需的数据,并且类似于写入结果,但为什么没有加速？

更多信息:

1. 我检查了汇编代码icpc -g -std=c++11 -march=core-avx2 -O3 -qopenmp -S test.cpp,发现了生成的矢量化指令;

2. 为了检查它是否受内存限制,我在循环中评估了计算部分,并且测量的时间减少到了大约60,但是如果我更改了线程计数,它没有太大变化1 -> 2 -> 4.

欢迎任何建议或线索.

编辑-1:

感谢@JerryCoffin指出可能的原因,所以我使用Vtune进行了内存访问分析.结果如下:

1-thread: Memory Bound: 6.5%, L1 Bound: 0.134, L3 Latency: 0.039

2-threads: Memory Bound: 18.0%, L1 Bound: 0.115, L3 Latency: 0.015

4-threads: Memory Bound: 21.6%, L1 Bound: 0.213, L3 Latency: 0.003

它是英特尔4770处理器,最大25.6GB/s(Vtune测量为23GB/s).带宽.内存限制确实增加了,但我仍然不确定这是否是原因.有什么建议？

EDIT-2(只是试图提供全面的信息,所以附加的东西可能很长,但不是很乏味的希望):

感谢@PaulR和@bazza的建议.我尝试了3种方法进行比较.需要注意的一点是,处理器具有4内核和8硬件线程.结果如下:

(1)只是dst提前初始化为全零:1 thread: 91.922; 2 threads: 93.170; 4 threads: 93.868---似乎没有效果;

(2)没有(1),将并行部分放在100个迭代的外环中,并测量100次迭代的时间:1 thread: 9109.49; 2 threads: 4951.20; 4 threads: 2511.01; 8 threads: 2861.75---除8个线程外非常有效;

(3)基于(2),在100次迭代之前再放一次迭代,并测量100次迭代的时间:1 thread: 9078.02; 2 threads: 4956.66; 4 threads: 2516.93; 8 threads: 2088.88---与(2)相似但对8个线程更有效.

似乎更多的迭代可以暴露openmp + SIMD的优点,但计算/内存访问比率不管循环计数都没有变化,并且地点似乎也不是原因,因为src或者dst太大而无法保留在任何缓存中,因此没有任何关系在连续迭代之间存在.

有什么建议？

编辑3:

如果有误导性,有一点需要澄清:在(2)和(3)中,openmp指令在添加的外部循环之外

#pragma omp parallel for private(vec_src, vec_op, vec_dst)
for (int k = 0; k < 100; ++k) {
    for (int64_t i = 0; i < size; i += 8) {
        ......
    }
}

即外环使用多线程并行化,内环仍然是串行处理的.因此,(2)和(3)中的有效加速可以通过增强线程之间的局部性来实现.

我做了另一个实验,将openmp指令放在外部循环中:

for (int k = 0; k < 100; ++k) {
    #pragma omp parallel for private(vec_src, vec_op, vec_dst)
    for (int64_t i = 0; i < size; i += 8) {
        ......
    }
}

而且加速仍然不好:1 thread: 9074.18; 2 threads: 8809.36; 4 threads: 8936.89.93; 8 threads: 9098.83.

问题仍然存在.:(

编辑-4:

如果我用这样的标量操作替换矢量化部分(相同的计算但是以标量方式):

#pragma omp parallel for
for (int64_t i = 0; i < size; i++) { // not i += 8
    int query = src[i];
    int res = src[i] + 2;
    res = res * query;
    res = res << 1;
    res = res + query;
    res = res - query;
    dst[i] = res;
}

加速是1 thread: 92.065; 2 threads: 89.432; 4 threads: 88.864.我可以得出结论,看似尴尬的并行实际上是内存限制(瓶颈是加载/存储操作)？如果是这样,为什么不能很好地并行加载/存储操作？

Answer 1

我是否可以得出这样的结论：看似尴尬的并行实际上是内存限制（瓶颈是加载/存储操作）？如果是这样，为什么加载/存储操作不能很好地并行化？

是的，这个问题是令人尴尬的并行，因为由于缺乏依赖性而很容易并行化。这并不意味着它将完美扩展。您仍然可能会遇到糟糕的初始化开销与工作比率或限制加速的共享资源。

就您而言，您确实受到内存带宽的限制。首先考虑实际情况：当使用 icpc（16.0.3 或 17.0.1）进行编译时，“标量”size版本会生成更好的代码constexpr。这并不是因为它优化掉了这两条冗余线：

res = res + query;
res = res - query;

确实如此，但这没有什么区别。主要是编译器使用与内在函数完全相同的指令，除了存储之外。在存储之前，它使用vmovntdq而不是vmovdqu，利用有关程序、内存和体系结构的复杂知识。不仅vmovntdq需要对齐内存而且因此可以更加高效。它为 CPU 提供非临时提示，防止该数据在写入内存期间被缓存。这提高了性能，因为将其写入缓存需要从内存加载缓存行的其余部分。因此，虽然您的初始 SIMD 版本确实需要三个内存操作：读取源、读取目标缓存行、写入目标，但具有非临时存储的编译器版本只需要两个。事实上，在我的 i7-4770 系统上，编译器生成的版本将 2 个线程的运行时间从约 85.8 毫秒减少到 58.0 毫秒，几乎完美地实现了 1.5 倍加速。这里的教训是相信你的编译器，除非你非常了解架构和指令集。

考虑到此处的峰值性能，传输 2*160000000*4 字节需要 58 毫秒，相当于 22.07 GB/s（汇总读取和写入），这与您的 VTune 结果大致相同。（有趣的是，考虑到 85.8 毫秒与两次读取和一次写入的带宽大致相同）。没有更多直接的改进空间。

为了进一步提高性能，您必须对代码的操作/字节比率进行一些处理。请记住，您的处理器可以执行 217.6 GFLOP/s（我猜操作的速度是相同或两倍int），但只能读取和写入 3.2 G int/s。这让您了解需要执行多少操作才能不受内存限制。因此，如果可以的话，请处理块中的数据，以便可以重用缓存中的数据。

我无法重现您的 (2) 和 (3) 结果。当我围绕内部循环进行循环时，缩放行为相同。结果看起来很可疑，特别是考虑到结果与其他方面的峰值性能非常一致。一般来说，我建议在并行区域内进行测量并omp_get_wtime像这样利用杠杆：

  double one, two;
#pragma omp parallel 
  {
    __m256i vec_src;
    __m256i vec_op = _mm256_set1_epi32(2);   
    __m256i vec_dst;

#pragma omp master
    one = omp_get_wtime();
#pragma omp barrier
    for (int kk = 0; kk < 100; kk++)
#pragma omp for
    for (int64_t i = 0; i < size; i += 8) {
        ...
    }
#pragma omp master
    {
      two = omp_get_wtime();
      std::cout << "took time: " << (two-one) * 1000 << std::endl;
    }
  }

最后一点：台式机处理器和服务器处理器在内存性能方面具有非常不同的特征。在现代服务器处理器上，您需要更多的活动线程来使内存带宽饱和，而在桌面处理器上，内核通常几乎会使内存带宽饱和。

编辑：关于 VTune 不将其归类为内存限制的另一种想法。这可能是由于计算时间与初始化时间短造成的。尝试看看 VTune 对循环中的代码有何说明。