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]];
}

根据这篇文章的讨论，如果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来实现，但正如评论中已经指出的那样：

但是，这仅解决了正确性问题，并且由于大量缓存争用和同步需求（包括错误共享），效率可能非常低下。唯一的解决方案是让每个线程拥有自己的 cnt 私有副本，并在最后减少这些副本。

另一种解决方案是每个线程都有一个私有数组，在并行区域的末尾，您将所有这些数组手动缩减为一个。可以在此处找到此类方法的示例。

幸运的是，使用OpenMP 4.5，您可以使用专用编译指示减少数组，即：

#pragma omp parallel for reduction(+:cnt)

您可以查看此示例以了解如何应用该功能。

值得一提的是，@Jérôme Richard亲切地指出，关于减少数组与原子方法的问题：

请注意，只有当数组不是很大时，这才很快（在这种特定情况下，关于平台并且值不冲突，基于原子的解决方案可能会更快）。所以这就是 m << n。——

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