OpenMP 中的并行编程

Question

我有如下一段代码。

for (i = 0; i < n; ++i) {
  ++cnt[offset[i]];
}

其中 offset 是一个大小为 n 的数组，包含 [0, m) 范围内的值，而 cnt 是一个大小为 m 且初始化为 0 的数组.我用OpenMP并行化如下

#pragma omp parallel for shared(cnt, offset) private(i)
for (i = 0; i < n; ++i) {
  ++cnt[offset[i]];
}

根据本post中的讨论，如果offset[i1] == offset[i2]为i1 != i2，则上述代码可能导致cnt不正确。我该怎么做才能避免这种情况？

Answer 1

此代码：

#pragma omp parallel for shared(cnt, offset) private(i)
for (i = 0; i < n; ++i) {
  ++cnt[offset[i]];
}

在更新数组 cnt 期间包含竞争条件，要解决它，您需要保证这些更新相互排斥。这可以通过（例如） #pragma omp atomic update 来实现，但正如评论中已经指出的那样：

However, this resolves just correctness and may be terribly inefficient due to heavy cache contention and synchronization needs (including false sharing). The only solution then is to have each thread its private copy of cnt and reduce these copies at the end.

另一种解决方案是为每个线程创建一个私有数组，并在并行区域的末尾手动将所有这些数组缩减为一个。可以在 here.

中找到这种方法的示例
幸运的是，使用 OpenMP 4.5 您可以使用专用编译指示减少数组，即：

#pragma omp parallel for reduction(+:cnt)

您可以查看 this example 如何应用该功能。

值得一提的是，关于数组的缩减与原子方法如 @Jérôme Richard:
友善指出

Note that this is fast only if the array is not huge (the atomic based solution could be faster in this specific case regarding the platform and if the values are not conflicting). So that is m << n. –

一如既往，分析是关键！；因此，您应该使用上述方法测试您的代码，以找出最有效的方法。

OpenMP 中的并行编程

parallel programming in OpenMP

c

c++

parallel-processing

multithreading

openmp