OpenMP：for循环避免数据竞争而不使用关键

Question

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

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

我知道如果我直接使用 parallel 语法可能会导致数据竞争并得到错误的答案，但如果我使用 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 总是 returns 0。串行版本会复制数组，并行版本会执行任意重新洗牌。 get_key returns 相同值的所有迭代之间存在排序依赖关系。

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

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?

任何关于性能的问题都需要更具体的信息。涉及的类型、数据大小、并行度级别……是什么？ "this is the best way for performance".

没有通用的答案

OpenMP：for循环避免数据竞争而不使用关键

OpenMP: for loop avoid data race without using critical

c++

parallel-processing

openmp

hpc