c++ - 如何在每个例程OpenMP中处理子数组

Question

我有一些代码，并行计算一些数组前缀的总和(例如 out_arr[0] = in_arr[0], out_arr[1 ] = in_arr[0]+in_arr[1] .. 等)。 我的代码有 N 个线程，N 是一些 in_arr 元素，每个线程只处理数组的 1 个元素。这不是好的解决方案，所以我想在每个线程中处理 N/num_of_threads，但我失败了。

我尝试用 N/num_of_threads 值创建共享变量，并在第一个 #pragma 指令后面用这个变量组织 for 循环，但我无法在标准输出中调试那些神奇的数字。

这是“坏”解决方案的工作版本:

void CalcSum2(int a[], int s[], int n) { 
    int* old = new int [n], *cnt = new int [n]; 
    #pragma omp parallel num_threads(N) {
    int i = omp_get_thread_num(), d = 1; 
    s[i] = a[i]; 
    cnt[i] = 1; 
     #pragma omp barrier 
    while (d < n) { 
        old[i] = s[i]; 
     #pragma omp barrier 
         if (i >= d) { 
             s[i] += old[i-d]; 
         cnt[i]++; 
         } 
         d += d; 
     #pragma omp barrier 
    }
    }
    delete[] old; delete[] cnt; 
    return; 
} 

Answer 1

您正在计算累加和。也称为前缀和。这可以与 OpenMP 并行完成。我最近用 OpenMP 解决了这个问题 Parallel cumulative (prefix) sums in OpenMP: communicating values between threads

您必须并行遍历数组两次。第一次做部分和，第二次用偏移量校正部分和。

我在下面为您将您的代码转换成了这个。作为测试，我计算了计数的总和，它具有 i*(i+1)/2 的封闭形式解。您可以看到 prefix_sum 函数得到了正确的答案。

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

void prefix_sum(int a[], int s[], int n) {
    int *suma;
    #pragma omp parallel
    {
        const int ithread = omp_get_thread_num();
        const int nthreads = omp_get_num_threads();
        #pragma omp single
        {
            suma = new int[nthreads+1];
            suma[0] = 0;
        }
        int sum = 0;
        #pragma omp for schedule(static) nowait // do partial sum in parallel
        for(int i=0; i<n; i++) {
            sum += a[i];
            s[i] = sum;
        }
        suma[ithread+1] = sum;
        #pragma omp barrier
        int offset = 0;
        for(int i=0; i<(ithread+1); i++) {
            offset += suma[i];
        }

        #pragma omp for schedule(static) //run over array again in parallel for full sum
        for(int i=0; i<n; i++) {
            s[i] += offset;
        }
    }
    delete[] suma;
}

int main() {
    const int n = 100;
    int *a = new int[n];
    int *s = new int[n];
    for(int i=0; i<n; i++) {
        a[i] = i;
    }
    prefix_sum(a, s, n);
    for(int i=0; i<n; i++) {
        printf("%d ", s[i]);
    } printf("\n");

    for(int i=0; i<n; i++) {
        printf("%d ", i*(i+1)/2);
    } printf("\n");
}

编辑 此方法的问题之一是，对于大型数组，大多数值在第二次传递开始时已从缓存中逐出。我想出了一个解决方案，它并行运行一个 block ，然后按顺序移动到下一个 block 。我将 chunck_size 设置为二级缓存(由于有四个内核，实际上是四倍)。这为更大的阵列提供了很大的改进。这是该功能的概述。完整的功能可以在我的回答中找到 simd-prefix-sum-on-intel-cpu .

void scan_omp_SSEp2_SSEp1_chunk(float a[], float s[], int n) {
    float *suma;
    const int chunk_size = 1<<18;
    const int nchunks = n%chunk_size == 0 ? n / chunk_size : n / chunk_size + 1;    
    #pragma omp parallel
    {
        //initialization code 
        for (int c = 0; c < nchunks; c++) {
            const int start = c*chunk_size;
            const int chunk = (c + 1)*chunk_size < n ? chunk_size : n - c*chunk_size; 
            //pass1: pass1_SSE(&a[start], &s[start], chunk);                
            //get offset
            //pass2: pass2_SSE(&s[start], offset, chunk);
        }
    }
    delete[] suma;
}