c - 具有归约和操作数组的并行 for 循环

Question

我是 openMP 的新手，我尝试优化循环。结果与预期不同，for 循环无法正常工作(由于依赖性)。我不明白如何通过以下示例获得完美的并行循环:

    #pragma omp parallel for default(shared) reduction(+...)
    for(i = rest - 1; i >= 0; i--) {
        scounts[i] += N;
    }

    #pragma omp parallel for private(i)
    for(i = 1; i < p; i++) {
        disp[i] = disp[i-1] + scounts[i-1];
    }

我尝试了这 2 个 pragma 指令但没有成功。在这些情况下，最好的处理方法是什么？

Answer 1

您已经选择了一个并行处理的难题。通常，在编写数组时，您不希望数组的元素依赖于之前的元素，而这正是您在第二个循环中拥有的元素。

大多数人在看到依赖时就放弃了。但这些都是需要思考的有趣案例。在你的情况下，你的第二个循环相当于

type sum = 0; //replace type with int, float, double...
for(i = 1; i < p; i++) {
    sum += scounts[i-1];
    disp[i] = disp[0] + sum;
}

这是一个累积总和(又名 prefix sum )。 OpenMP 不提供简单的结构来进行前缀和。你必须分两次完成。这是你如何做的(我假设 disp 和 scounts 的类型是 int 但你可以用 float 或其他):

int *suma;
#pragma omp parallel
{
    int ithread = omp_get_thread_num();
    int nthreads = omp_get_num_threads();
    #pragma omp single
    {
        suma = malloc(nthreads * sizeof *suma);
        suma[0] = 0;
    }
    int sum = 0;
    #pragma omp for schedule(static)
    for (int i=1; i<p; i++) {
        sum += scounts[i-1];
        disp[i] = disp[0] + sum;
    }
    suma[omp_get_thread_num()+1] = sum;
    #pragma omp barrier
    int offset = 0;
    for(int i=0; i<(ithread+1); i++) {
        offset += suma[i];
    }
    #pragma omp for schedule(static)
    for(int i=1; i<p; i++) {
        disp[i] += offset;
    }
}
free(suma);

但如果您只是学习 OpenMP，我建议您先从一个更简单的案例开始。