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

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);
}

因此提供的功能较少。

为什么我要使用归约而不是对计数器的原子访问？

Answer 1

简答：

性能

长答案：

因为原子变量是有代价的，这个代价就是同步。为了确保不存在竞争条件，即两个线程同时修改同一个变量，线程必须 synchronize 这实际上意味着你失去了并行性，即线程是连载.

另一方面，归约是一种通用操作，可以使用并行归约算法并行执行。阅读 this and 篇文章，了解有关并行缩减算法的更多信息。

附录：了解并行缩减的工作原理

想象一个场景，您有 4 个线程，并且您想要减少 8 个元素数组 A。您可以通过 3 个步骤完成此操作（查看附加图像以获得更好的感觉我在说什么）：

步骤 0。索引为 i<4 的线程负责求和 A[i]=A[i]+A[i+4].
步骤 1。索引为 i<2 的线程负责求和 A[i]=A[i]+A[i+4/2].
步骤 2。索引为 i<4/4 的线程负责求和 A[i]=A[i]+A[i+4/4]

在此过程结束时，您将得到减少 A 第一个元素的结果，即 A[0]

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

所以大约 atomic=20xserial=80xreduction

'reduction' 适当地利用了并行性，使用 4 核计算机，我们可以获得 3--6 性能提升 vs "serial".

现在，"atomic" 比 "serial" 长 20 倍。正如前面的回答中所解释的，不仅内存访问的序列化禁用了并行性，而且所有内存访问都是由原子操作完成的。这些操作在现代计算机上至少需要 20--50 个周期，如果大量使用，将大大降低您的性能。

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

Why should I use a reduction rather than an atomic variable?

c

parallel-processing

atomic

openmp

简答：

长答案：

附录：了解并行缩减的工作原理