c++ - 增加 openMP 中的数组索引

Question

我刚开始使用 OpenMP。我正在尝试并行化嵌套循环，到目前为止我有这种形式的东西......

#pragma omp parallel for
for (j=0;j <m; j++) {
    some work;
    for (i= 0; i < n ; i++) {
        p =b[i];
        if (P< 0 && k < m) {
            a[k] = c[i]; k++ ;
        } else {
            x=c[i];
        }
    }
    some work
}

外循环是并行的，内循环更新k。其他线程需要 k 的当前值才能正确更新 a[k]。问题是所有线程都在更新 a[k]，但 k 的正确顺序没有保留。

有些线程会更新 k 和 a[k]，有些则不会。如何在线程之间传达最新的 k 以正确更新 a[k]，因为 c[i] 对于每个线程都有不同的值？

例如，当它串行运行时，程序可能会将 a 的前七个值设置为 {1,3,5,7,3,9,13} 并以 k 等于 7 终止，但并行完成时，会产生不同的结果，或导致不同(因此错误)的顺序。

如何保持相同的顺序并同时确保并行性？

Answer 1

注意:这个答案是根据OP的澄清完全重写的。原答案在最后。

How do I keep the same order and ensure parallelism at the same time?

顺序依赖性与并行性相反，因为并行运行操作本质上需要放宽它们执行的相对顺序。并非所有计算都可以有效地并行化。

您的情况也不异常(exception)。外循环的第二次和后续每次迭代都需要使用最终值 k (除其他外)由上一次迭代计算。它怎么能得到那个呢？仅通过首先执行先前的迭代。这为并发操作留下了哪些空间？没有任何。并发性与并行性不同，但它是并行性的主要动机之一，因为这就是并行性如何改善运行时间的。

由于没有并发范围，并行性会对您产生适得其反的效果。假设您将外部循环的整个主体设置为关键部分，这样实际上就没有并发性(正如您当前的代码所要求的那样)，并且没有涉及 k 的数据争用。 。那么您仍然会为并行性付出开销，却得不到加速，并且可能仍然会得到错误的结果，因为外循环体的评估是以错误的顺序执行的。

可能可以重写整个过程，以减少或消除阻碍计算有效并行化的数据依赖性，也可能不会。我们没有足够的信息来确定，因为这部分取决于“some work”的详细信息以及数据的重要性。也许您需要一种完全不同的算法来产生所需的结果。

> 当我使用归约子句时，它不会给出 a[n]={0,1,2,3,.......n} ，而是给出 a 的垃圾值。我需要 K 的总和，因此需要减少条款。

连续整数之和有一个闭式方程，当列表中的第一个整数为 0 或 1 时，它的形式特别简单。特别是从 0 到 n 的整数之和。 ，包括 n * (n + 1) / 2 。您不需要为此减少。

如果您无论如何都想使用归约，那么您需要了解它并不像您想象的那样工作。您得到的是执行并行构造的每个线程的归约变量的单独私有(private)拷贝，以及根据归约运算符组合的这些独立变量的每个线程(不是每次迭代)最终值。因此，如果您确实想通过 OpenMP 缩减来进行计算，那么您需要重新构建循环，如下所示:

#pragma omp parallel for reduction (+:k)
for (i = 0; i < 10; i++) {
    a[i] = i;
    k += i;
}

假设 k 的值是 0 紧接在循环之前，正如您确实似乎在做的那样。如果这不是一个安全的假设，那么你需要类似的东西

type_of_k k0 = k;
k = 0;
#pragma omp parallel for reduction (+:k)
for (i = 0; i < 10; i++) {
    a[k0 + i] = i;
    k += k0 + i;
}

请注意，无论哪种情况，这不仅正确设置了归约，而且还打破了先前由表达式 k++ 携带的循环迭代之间的数据依赖性。 。