OpenMP reduction 子句中变量的原子操作

Question

我有以下一段代码。它的想法很简单。我的完整程序中有数十亿个事件，我需要计算其中一些未使用 long int 类型的事件。所以，我必须使用 2 int 数字 HIT 和 COUNT 而不是 1 int number 因为会溢出 1 int 变量（非常大的循环计数）。

#include <fstream>
#include <cstring>
#include <cmath>
#include <random>
#include <limits>
#include <chrono>

using namespace std;

int N=1000000000;
long int K=20*N;
int HIT=0;
int COUNT=0;
long int MAX=std::numeric_limits<int>::max();

int main(int argc, char **argv)
{
  auto begin=std::chrono::steady_clock::now();
  for(long int i=0; i<K; ++i)
  {
    ++HIT;
    if(HIT == MAX)
    {
      ++COUNT;
      HIT=0;
      cout<<"COUNT="<<COUNT<<endl;
    }
  }
  auto end=std::chrono::steady_clock::now();
  cout<<"HIT="<<HIT<<endl;
  cout<<"COUNT="<<COUNT<<endl;

  const long int Total = HIT+COUNT*MAX;
  cout<<"Total="<<Total<<" MAX="<<MAX<<endl;
  if(Total==K) cout<<"Total == K"<<endl;
  else         cout<<"Total != K"<<endl;
  auto elapsed_ms=std::chrono::duration_cast<std::chrono::milliseconds>(end-begin);
  std::cout<<"time="<<elapsed_ms.count()<<" ms"<<std::endl;
  return 0;
}

该代码在 1 个线程中正常运行并给出以下输出：

COUNT=1
COUNT=2
COUNT=3
COUNT=4
COUNT=5
COUNT=6
COUNT=7
COUNT=8
COUNT=9
HIT=672647177
COUNT=9
Total=20000000000 MAX=2147483647
Total == K
time=30971 ms

如果可能的话，我需要使用 OpenMP 使其并行工作，而不是使用互斥锁或与编译器实现相关的某些函数。但是当我将其修改为：

#pragma omp parallel for simd reduction(+:HIT,COUNT)
  for(long int i=0; i<K; ++i)

输出如下：

HIT=20000000000
COUNT=0
Total=20000000000 MAX=2147483647
Total == K
time=2771 ms

最后，当我修改代码为：

#pragma omp parallel for simd reduction(+:HIT,COUNT)
for(long int i=0; i<K; ++i)
{
  ++HIT;
  if(HIT == MAX)
  {
    ++COUNT;
  #pragma omp atomic write
    HIT=0;
    cout<<"COUNT="<<COUNT<<endl;
  }
}

输出是：

COUNT=1
COUNT=1
COUNT=1
COUNT=1
COUNT=1
COUNT=1
COUNT=1
COUNT=1
HIT=2820130824
COUNT=8
Total=20000000000 MAX=2147483647
Total == K
time=4232 ms

任何人都可以向我解释发生了什么以及为什么输出如此不同吗？

我需要使用 OpenMP 让代码正确地并行工作，那么如何正确地做到这一点？

是

#pragma omp atomic write

正确还是我应该写

#pragma omp atomic update?

是否可以对 OpenMP reduction 子句中已有的值编写 atomic 操作？

使用 Intel C++ 2019 编译器。

g++不允许在

中使用simd

#pragma omp parallel for simd reduction(+:HIT,COUNT)

如果删除 simd，代码使用 g++ 时将无法正常工作。

Answer 1

问题源于每个线程都有自己的 HIT 和 COUNT 副本。许多线程将以 HIT 中的大值结束。由于循环结束时的 OpenMP reduce 子句，这些被聚合，导致 HIT.

的多个“溢出”

所示代码的 OpenMP 实现的简单修复是包含

COUNT += HIT / MAX;
HIT %= MAX;

在循环结束后。

原子写指令是一个转移注意力的问题。它改变了循环的时间，导致更多线程达到溢出限制。

从您的问题描述来看，您代码中的实际 HIT 听起来像是 int，而不是 long int。这更难解决，因为无法使用上面的简单除法计算多次溢出，因为您没有精确度来完全计算所有内容。您还应该考虑使用 unsigned 而不是带符号的 int 类型，因为这可以延迟溢出问题，并且在溢出的情况下，避免在带符号的值溢出时出现未定义的行为。

可能的解决方案包括：

使用单个 MAX 和 COUNT 变量和互斥保护代码块对两个值进行非原子增加。
使用单个 MAX 和 COUNT 变量，声明为 std::atomic，连同 fetch_add（或可能 exchange）来处理更新。如果您使用 unsigned 类型，您可以让 MAX 翻转为 0，并在翻转发生时更新 COUNT。
将 MAX 更改为较小的数字，以便 (nThreads * MAX) 不超过数字限制。

Answer 2

简单的 + 缩减不适用于两个未完全独立求和的整数，但自 OpenMP 4.0 以来，您可以声明自己的缩减。您需要做的就是将计数器的两个部分抽象为 class（或 struct）并定义一个对这些对象求和的函数。在下面的示例中，使用了重载的复合赋值运算符 (+=)：

#include <limits>
#include <iostream>
#include <omp.h>

using namespace std;

const long int MAX = std::numeric_limits<int>::max();
const long int K = MAX + 20L;

class large_count {
   int count, hit;
public:
   large_count() : count(0), hit(0) {}

   // Prefix increment operator
   large_count& operator++() {
      hit++;
      if (hit == MAX) {
         hit = 0;
         count++;
      }
      return *this;
   }

   // Compound assignment operator
   large_count& operator+=(const large_count& other) {
      count += other.count;
      long int sum_hit = (long)hit + other.hit;
      if (sum_hit >= MAX) {
         count++;
         hit = sum_hit - MAX;
      }
      else
         hit = sum_hit;
      return *this;
   }

   long total() const { return hit + count * MAX; }
};

#pragma omp declare reduction (large_sum : large_count : omp_out += omp_in)

int main() {
   large_count cnt;
   double t = -omp_get_wtime();
   #pragma omp parallel for reduction(large_sum : cnt)
   for (long int i = 0; i < K; i++)
      ++cnt;
   t += omp_get_wtime();
   cout << (cnt.total() == K ? "YES" : "NO") << endl;
   cout << t << " s" << endl;
}

自定义缩减声明使用：

#pragma omp declare reduction (large_sum : large_count : omp_out += omp_in)

声明分为三部分：

large_sum - 这是自定义归约操作的名称
large_count - 这是减少操作的类型[=36=]
omp_out += omp_in - 这是组合表达式。 omp_out 和 omp_in 是 OpenMP 运行时提供的特殊伪变量。它们都是 large_count 类型。组合器表达式必须组合两个值并更新 omp_out.

示例输出：

$ g++ --version
g++ (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
...
$ g++ -std=c++11 -fopenmp -o cnt cnt.cc
$ OMP_NUM_THREADS=1 ./cnt
YES
9.39628 s
$ OMP_NUM_THREADS=3 ./cnt
YES
3.79765 s

OpenMP reduction 子句中变量的原子操作

atomic operations on a variable which is in OpenMP reduction clause

c++

atomic

openmp