OpenMP:for 循环避免数据竞争，而无需使用关键

Question

>假设我有以下 C 代码并希望使用 OpenMP 并行化它。

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

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

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

我想知道是否有办法以良好的性能并行化它？

任何关于性能的问题都需要更具体的信息。涉及的类型、数据大小、并行度级别等是什么？对于"这是最好的性能方式">，没有通用的答案。