c - OpenMP 中数组内容的并行更新 - 并发添加元素

Question

我有以下代码，我想让它并行化(伪代码)

int na = 10000000;
int nb = na;
double A[na];
double B[2*na];
double a;

for(int j=0;j<nb;j++)
{
  i = rand() % na;
  A[i]+=5.0*i;
  B[i+10]+=6.0*i*i;
}

当然，我不能使用#pragma omp parallel for，因为有时(无法预测)同一个元素会被两个线程同时访问。这个代码块如何并行化？谢谢

Answer 1

有两种方法:

• 对值使用原子更新

  #pragma omp parallel for
  for(int j=0;j<nb;j++)
  {
      // make sure to declare i locally!
      int i = fun();
      #pragma omp atomic
      A[i]+=5.0*i;
  }
  

  这是最简单的方法。每次写入都是原子执行的，因此成本更高。您还需要考虑从多个线程访问相邻元素变得昂贵(错误共享)。如果 A 很大并且每次更新需要进行大量计算，请使用它。

• 使用数组归约

  #pragma omp parallel for reduction(+:A)
  for(int j=0;j<nb;j++)
  {
      // make sure to declare i locally!
      int i = fun();
      A[i]+=5.0*i;
  }
  

  这会为每个线程创建 A 的本地副本，并在并行区域之后将它们一起添加到外部 A。这需要更多的内存和一些计算，但并行代码本身可以最有效地工作。如果 A 很小并且每次更新的计算量很小，请使用它。

顺便说一句:永远不要在并行应用程序中使用rand()，它没有被定义为线程安全的，有时它是用锁和becomes horribly inefficient实现的。 .

编辑:在您使用 B 的示例中，您可以安全地将 omp atomic 或 reduction 分别应用于语句，因为每个操作只需要以原子方式独立执行。