前缀总和花费太长的OpenMP

Question

我在OpenMP中实现前缀总和问题,我似乎没有得到任何加速.实际上,并行实现比顺序实现花费的时间更长.

这是我的前缀和的代码:

for (k = 1; k < n; k = kk) {
    kk = k << 1;

    #pragma omp parallel for 
    for (i = kk - 1; i < n; i += kk) {
        x[i] = x[i-k] + x[i];
    }
 }

for (k = k >> 1; k > 1; k = kk) {
    kk = k >> 1;

    #pragma omp parallel for
    for (i = k - 1; i < n - kk; i += k) {
        x[i + kk] = x[i] + x[i + kk];
    }
}

我使用gcc -fopenmp -O3 prefix_sums.c编译了这个.我得到的1 000 000个整数的结果是:

对于顺序实现(也使用-O3编译):

0.001132
0.000929
0.000872
0.000865
0.000842

并行实现(5个内核重新运行5次):

0.025851
0.005493
0.006327
0.007092
0.030720

有人可以解释一下问题是什么吗？实现是给出正确的输出,但为什么需要这么长时间？

谢谢.

Answer 1

对于MIMD(例如,使用OpenMP)和使用SIMD(例如,使用SSE/AVX),前缀和可以是并行的.

使用OpenMP进行前缀总计会有点痛苦,但这并不算太糟糕.我已经详细介绍了这个simd-prefix-sum-on-intel-cpu和这里的parallel-cumulative-prefix-sums-in-openmp-communic-values-between-thread

编辑:您正在进行前缀(原位).上面的链接不是就地(非原生境). 我修改了代码(见下文),在你做的时候就地进行前缀和测试. 您可能需要两个以上的物理内核来查看任何内容.

基本上你是两次通过.在第一遍中,你做部分和,然后在第二遍中你用每个部分和的常数校正部分和.第二遍将由良好的编译器(例如,使用GCC但不使用MSVC)进行矢量化.也可以在第一次传递时使用SIMD,但是我使用的编译器都没有矢量化,所以你必须自己使用内在函数.

该算法为O(n),因此它很快变为内存绑定而不是计算绑定.这意味着对于仅适合L1高速缓存的阵列,OpenMP开销过大.在这种情况下,最好只使用SIMD(没有开销).对于较大的阵列,您可以从SIMD和MIMD中受益,但在某些时候算法变为内存限制,并且它不比非并行算法快得多.

#include <stdio.h>
#include <omp.h>

void prefixsum_inplace(float *x, int N) {
    float *suma;
    #pragma omp parallel
    {
        const int ithread = omp_get_thread_num();
        const int nthreads = omp_get_num_threads();
        #pragma omp single
        {
            suma = new float[nthreads+1];
            suma[0] = 0;
        }
        float sum = 0;
        #pragma omp for schedule(static)
        for (int i=0; i<N; i++) {
            sum += x[i];
            x[i] = sum;
        }
        suma[ithread+1] = sum;
        #pragma omp barrier
        float offset = 0;
        for(int i=0; i<(ithread+1); i++) {
            offset += suma[i];
        }
        #pragma omp for schedule(static)
        for (int i=0; i<N; i++) {
            x[i] += offset;
        }
    }
    delete[] suma;
}

int main() {
    const int n = 20;
    float x[n];
    for(int i=0; i<n; i++) x[i] = 1.0*i;
    prefixsum_inplace(x, n);
    for(int i=0; i<n; i++) printf("%f %f\n", x[i], 0.5*i*(i+1));
}