如何删除此 OpenMP 求和示例中的依赖项

Question

我现在开始使用 OpenMP，需要在这个任务中使用 OpenMP 实现并行：

for (i = 0; i < N; i++){
 index += i*alpha + 4;
 sum += array[index];
}

我打算使用归约运算符来获取 sum 变量的正确值，但为此我需要先解决索引变量的依赖关系。我该怎么做？

感谢大家的帮助！

Answer 1

由于顺序依赖性，循环无法直接并行化。不过可以先分成两部分:

for (i = 0; i < N; i++) {
 index += i*alpha + 4;
 tmp[i] = index;
}
for (i = 0; i < N; i++) {
 sum += array[tmp[i]];
}

一旦拆分，第一个循环会呈现出扫描模式并且可以并行化，尽管并行版本可能不会比顺序版本快。第二个循环是一个简单的 reduction，可以很容易地并行化。

使用 OpenMP 执行扫描模式通常有点棘手。希望，因为 alpha 似乎是一个循环常数 ，所以 index 的所有值都可以很容易地预测 感谢 basic数学属性：

index_i = index_init + 0*alpha+4 + 1*alpha+4 + 2*alpha+4 + ... + i*alpha+4
        = index_init + (0+1+2+...+i)*alpha + 4*(i+1)
        = index_init + (i*(i+1)/2)*alpha + 4*(i+1)
        = index_init + (i+1)*(i*alpha + 8)/2

因此我们可以编写最终结果代码：

#pragma omp parallel for reduction(+:sum)
for (i = 0; i < N; i++) {
 sum += array[index + (i*(i+1)/2)*alpha + 4*(i+1)];
}

此外，如果alpha是一个整数并且index从零开始，数组索引可以稍微快一些：

#pragma omp parallel for reduction(+:sum)
for (i = 0; i < N; i++) {
 sum += array[(i+1)*(i*alpha+8)/2];
}

如何删除此 OpenMP 求和示例中的依赖项

How to remove dependencies in this OpenMP summation exemple

c++

parallel-processing

dependencies

openmp