我如何处理OpenMP中的数据竞争？

Question

我正在尝试使用OpenMP在数组中添加数字.以下是我的代码:

  int* input = (int*) malloc (sizeof(int)*snum);
  int sum = 0;
  int i;
  for(i=0;i<snum;i++){
      input[i] = i+1;
  }
  #pragma omp parallel for schedule(static)
  for(i=0;i<snum;i++)
  {
      int* tmpsum = input+i;
 sum += *tmpsum;
  }

这不会产生正确的结果sum.怎么了？

Answer 1

您的代码目前有竞争条件,这就是结果不正确的原因.为了说明这是为什么,让我们使用一个简单的例子:

你正在运行2个线程,数组是int input[4] = {1, 2, 3, 4};.您初始化sum到0正确,并准备开始循环.在循环的第一次迭代中,线程0和线程1 sum从内存中读取0,然后将它们各自的元素添加到sum,并将其写回内存.但是,这意味着线程0正在尝试写入sum = 1内存(第一个元素是1,和sum = 0 + 1 = 1),而线程1正在尝试写入sum = 2内存(第二个元素是2,和sum = 0 + 2 = 2).此代码的最终结果取决于哪个线程最后完成,因此最后写入内存,这是一个竞争条件.不仅如此,在这种特殊情况下,代码所能产生的答案都不正确!有几种方法可以解决这个问题; 我将在下面详细介绍三个基本内容:

#pragma omp critical:

在OpenMP中,有一个所谓的critical指令.这限制了代码,以便一次只有一个线程可以执行某些操作.例如,您的for-loop可以写成:

#pragma omp parallel for schedule(static)
for(i = 0; i < snum; i++) {
    int *tmpsum = input + i;
#pragma omp critical
    sum += *tmpsum;
}

这消除了竞争条件,因为一次只有一个线程访问和写入sum.但是,该critical指令对于性能非常非常糟糕,并且可能会在很大程度上消除您从使用OpenMP获得的大部分(如果不是全部)增益.

#pragma omp atomic:

该atomic指令与该指令非常相似critical.主要区别在于,虽然该critical指令适用于您希望一次执行一个线程的任何操作,但该atomic指令仅适用于内存读/写操作.正如我们在这个代码示例中所做的一样是读取和写入sum,这个指令将完美地工作:

#pragma omp parallel for schedule(static)
for(i = 0; i < snum; i++) {
    int *tmpsum = input + i;
#pragma omp atomic
    sum += *tmpsum;
}

性能atomic通常明显优于critical.但是,它仍然不是您特定情况下的最佳选择.

reduction:

您应该使用的方法以及其他人已经建议的方法是reduction.您可以通过将for-loop 更改为:

#pragma omp parallel for schedule(static) reduction(+:sum)
for(i = 0; i < snum; i++) {
    int *tmpsum = input + i;
    sum += *tmpsum;
}

该reduction命令告诉OpenMP,当循环运行时,您希望每个线程跟踪其自己的sum变量,并在循环结束时将它们全部添加.这是最有效的方法,因为整个循环现在并行运行,唯一的开销是在循环结束时sum,每个线程的值需要加起来.