依赖嵌套循环的并行化

Question

我的目标是在 C++ 上计算一个简单的 N 体程序，我正在使用 OpenMP 来加快计算速度。在某些时候，我有这样的嵌套循环：

int N;
double* S          = new double[N];
double* Weight     = new double[N];
double* Coordinate = new double[N];
 ...

#pragma omp parallel for
for (int i = 0; i < N; ++i)
{
   for (int j = 0; j < i; ++j)
   {
       double K = Coordinate[i] - Coordinate[j];
       S[i]    += K*Weight[j];
       S[j]    -= K*Weight[i];
   }
}

这里的问题是我在删除#pragma 时没有获得完全相同的结果...我猜这与第二个循环依赖于整数 i 这一事实有关，但我不知道看看如何解决这个问题

Answer 1

问题是在更新 S[i] 和 S[j] 期间存在数据竞争。不同的线程可能同时读取 from/write 到数组的同一个元素，因此它应该是一个原子操作（你必须添加 #pragma omp atomic ）以避免数据竞争并确保内存一致性：

for (int j = 0; j < i; ++j)
{
    double K = Coordinate[i] - Coordinate[j];
    #pragma omp atomic
    S[i]    += K*Weight[j];    
    #pragma omp atomic
    S[j]    -= K*Weight[i];
}

依赖嵌套循环的并行化

Parallelization of dependent nested loops

c++

parallel-processing

loops

openmp