c++ - OpenMP:for循环避免数据竞争而不使用关键

Question

假设我有以下 C 代码并想使用 OpenMP 对其进行并行化。

for (int i = 0; i < n; ++i)
{
    int key = get_key(i);
    toArray[count[key]++] = fromArray[i];
}

我知道如果我直接使用 parallel for 语法可能会导致数据竞争并得到错误的答案，但如果我使用 critical，性能会很差。

#pragma omp parallel for schedule(static)
for (int i = 0; i < n; ++i)
{
    int key = get_key(i);
    #pragma omp criical
    toArray[count[key]++] = fromArray[i];
}

我想知道是否有一种方法可以将其并行化并获得良好的性能？

Answer 1

恐怕您的假设是错误的。带有关键部分的版本确实会产生正确答案 - 至少不是确定性答案。

为简单起见，以 get_key 始终返回 0 的情况为例。串行版本会复制数组，并行版本会执行任意重新洗牌。 get_key 返回相同值的所有迭代之间存在排序依赖关系。

一般来说。简单的临界区通常可以被缩减取代，它允许独立执行，同时在并行部分之后产生一些合并开销。原子也可以作为简单操作的一种选择，但它们也会受到一般性能损失和通常额外的负面缓存问题的影响。从技术上讲，您不正确的关键部分代码将等同于这个稍微更有效的原子代码:

int index;
#pragma omp atomic capture
index = count[key]++;
#pragma omp atomic write
toArray[index] = fromArray[i];

I wonder if there is a way to parallelize it with good performance?

任何关于性能的问题都需要更具体的信息。涉及的类型、数据大小、并行度级别……是什么？ “这是提高性能的最佳方式” 没有通用的答案。