为什么我应该使用reduction而不是原子变量？

Question

假设我们想在OpenMP循环中计数某些内容。请比较一下归约。

int counter = 0;
#pragma omp for reduction( + : counter )
for (...) {
    ...
    counter++;
}

使用原子增量

int counter = 0;
#pragma omp for
for (...) {
    ...
    #pragma omp atomic
    counter++
}

原子访问能够立即提供结果，而归约只有在循环结束时才能确定其正确值。例如，归约不允许出现以下情况：

int t = counter;
if (t % 1000 == 0) {
    printf ("%dk iterations\n", t/1000);
}

因此提供的功能较少。

为什么要使用减少而不是原子访问计数器？

- mafu

---

每当您写入原子变量时，都会有一个同步点，其他线程可能需要等待。使用归约操作，直到结束时才需要同步。 - Some programmer dude

Answer 1

简短回答：

性能

详细回答：

因为原子变量是有代价的，这个代价就是同步。 为了确保没有竞态条件，即两个线程在同一时刻修改同一变量，线程必须进行同步，这有效地意味着你会失去并行性，也就是线程串行。

而另一方面的归约则是一种通用的操作，可以使用并行归约算法并行执行。 阅读此文和此文以获取更多关于并行归约算法的信息。

---

附加说明：了解并行归约的工作方式

想象一下这样一种情况：你有4个线程，并且你想要对一个长度为8的数组A进行归约。你可以用三个步骤来完成这个过程（查看所附图像以更好地理解我所说的）：

• 第0步。索引为i<4的线程负责对A[i]=A[i]+A[i+4]进行求和。
• 第1步。索引为i<2的线程负责对A[i]=A[i]+A[i+4/2]进行求和。
• 第二步。索引为i<4/4的线程会处理将A[i]=A[i]+A[i+4/4]的求和结果。

在这个过程的最后，您将得到减少的结果，即A的第一个元素，即A[0]

- Davide Spataro

---

你对并行约简的解释基于OpenMP实现不够现实，至少在CPU上是这样。它们只是为每个线程执行一个部分求和/约简，然后线性地将每个部分结果相加/约简。对于N>>nthreads，这种方法可以正常工作。理论上，在log(nthreads)中进行约简很好，但在实践中并非如此。你可以向OP展示如何手动进行约简以理解这一点。 - Z boson

@Zboson 当然，这并不是实际实现的现实，但至少给了OP一个比使用原子更好的想法。我的回答的目标远非成为OpenMP中如何实现扫描操作的参考。我还更新了你建议的链接的答案。 - Davide Spataro

Answer 2

性能是关键点。

考虑下面的程序

#include <stdio.h>
#include <omp.h>
#define N 1000000
int a[N], sum;

int main(){
  double begin, end;

  begin=omp_get_wtime();
  for(int i =0; i<N; i++)
    sum+=a[i];
  end=omp_get_wtime();
  printf("serial %g\t",end-begin);

  begin=omp_get_wtime();
# pragma omp parallel for
  for(int i =0; i<N; i++)
# pragma omp atomic
    sum+=a[i];
  end=omp_get_wtime();
  printf("atomic %g\t",end-begin);

  begin=omp_get_wtime();
# pragma omp parallel for reduction(+:sum)
  for(int i =0; i<N; i++)
    sum+=a[i];
  end=omp_get_wtime();
  printf("reduction %g\n",end-begin);
}

执行 (gcc -O3 -fopenmp) 后，会得到以下结果：

串行 0.00491182 原子操作 0.0786559 归约操作 0.001103

因此，原子操作约为串行操作的20倍，归约操作约为串行操作的80倍。

“归约操作”恰当地利用了并行性，在一个4核计算机上，与“串行操作”相比，可以获得三至六倍的性能提升。

现在，“原子操作”的时间是“串行操作”的20倍。正如先前的答案所解释的那样，内存访问的序列化禁用了并行性，而所有内存访问都是通过原子操作完成的。这些操作在现代计算机上需要至少20-50个时钟周期，并且如果过度使用，它们将大大降低性能。

- Alain Merigot