c - 如何处理 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

您的代码当前有一个 race condition ，这就是结果不正确的原因。为了说明这是为什么，让我们用一个简单的例子:

您在 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 循环可以写成:

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

这消除了竞争条件，因为一次只有一个线程访问和写入 sum。但是，critical 指令对性能非常不利，并且可能会扼杀您最初使用 OpenMP 获得的大部分(如果不是全部) yield 。

#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。您可以将 for 循环更改为:

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

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