使用OpenMP原子操作进行Fetch-and-add

Question

使用OpenMP原子操作进行Fetch-and-add

8

我正在使用OpenMP，并且需要使用fetch-and-add操作。然而，OpenMP没有提供适当的指令/调用。我想保持最大的可移植性，因此我不想依赖于编译器内置函数。

相反，我正在寻找一种方法来利用OpenMP的原子操作来实现这一点，但我已经陷入了僵局。这是否可以实现？请注意，以下代码几乎可以做到我想要的：

#pragma omp atomic
x += a

几乎可以实现，但不完全，因为我真正需要的是x的旧值。fetch_and_add应该被定义为产生与以下代码相同的结果（只有非锁定操作）：

template <typename T>
T fetch_and_add(volatile T& value, T increment) {
    T old;
    #pragma omp critical
    {
        old = value;
        value += increment;
    }
    return old;
}

（如果我没记错的话），也可以用“比较并交换”问题来问，但是一个可以用另一个来实现。

- Konrad Rudolph

仅仅是说atomic并不像它的名字所承诺的那样，因为任何一个线程如果被修改了内存中的atomic(在任何其他线程上)，都需要重新缓存。因此频繁和重复的atomic可能会降低性能(最好使用锁和缓冲区竞争写入)。 - Walter

@Walter 这也是我通过实证发现的：无锁算法的性能仅与使用锁的等效算法相当。而无锁算法在同步方面使用了极其复杂的逻辑（并因此存在引入错误的机会），而非性能方面。 - Konrad Rudolph

2个回答

2

如果您想获取 x 的旧值，并且 a 没有更改，请使用 (x-a) 作为旧值：

fetch_and_add(int *x, int a) {
 #pragma omp atomic
 *x += a;

 return (*x-a);
}

更新：这并不是一个真正的答案，因为x可以在原子操作后被另一个线程修改。因此，似乎不可能使用OMP Pragmas创建通用的“Fetch-and-add”。通用的意思是该操作可以轻松地从任何OMP代码中使用。

您可以使用omp_*_lock函数来模拟原子操作：

typedef struct { omp_lock_t lock; int value;} atomic_simulated_t;

fetch_and_add(atomic_simulated_t *x, int a)
{
  int ret;
  omp_set_lock(x->lock);
  x->value +=a;
  ret = x->value;
  omp_unset_lock(x->lock);
}

这是丑陋而缓慢的（执行 2 次原子操作而不是 1 次）。但如果您希望您的代码非常可移植，在某些情况下它不会是最快的。

你说“如下所示（仅非锁定）”。但是“非锁定”操作（使用 CPU 的“LOCK”前缀或 LL/SC 等）和锁定操作（本身实现了几个原子指令、短暂等待解锁的繁忙循环以及长时间等待时的操作系统休眠）之间有什么区别呢？

- osgx

对于cas - openmp支持一种条件原子的变体，但仅限于fortran。它是MIN和MAX;它们是有条件的。可用于实现CAS操作的子集。 - osgx

@Konrad Rudolph，我也需要一周时间才能理解这个问题。对我来说，必要的步骤是在不同平台上学习LL/SC操作。 - osgx

@osgx：这实际上不是问题，因为您可以事先将类型强制转换为适当位大小的整数。当然，这是UB和平台相关的，但是如果有适当的保护措施，这是一种非常可靠的技术。 - Konrad Rudolph

2

该死，这个答案也不正确：在原子更新和最后一行之间，另一个线程当然可能会修改 x！ - Konrad Rudolph

@Konrad Rudolph，是的，第一次尝试是错误的。已更新答案。 - osgx

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jason · Accepted Answer

自OpenMP 3.1开始，已经支持捕获原子更新，可以捕获旧值或新值。由于我们必须将该值从内存中带入以便进行增量计算，因此很明显，我们应该能够从CPU寄存器中访问它并将其放入线程专用变量中。

如果您正在使用GCC（或g++），则有一个不错的解决方案，请查阅原子内置函数： http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html 我认为英特尔的C/C++编译器也支持此功能，但我尚未尝试过。

目前（在实现OpenMP 3.1之前），我在C++中使用了内联包装函数，在编译时可以选择使用哪个版本。

template <class T>
inline T my_fetch_add(T *ptr, T val) {
  #ifdef GCC_EXTENSION
  return __sync_fetch_and_add(ptr, val);
  #endif
  #ifdef OPENMP_3_1
  T t;
  #pragma omp atomic capture
  { t = *ptr; *ptr += val; }
  return t;
  #endif
}

更新：我刚试用了英特尔的C++编译器，它目前支持openmp 3.1（原子捕获已实现）。英特尔为非商业用途在Linux上提供免费使用其编译器。

http://software.intel.com/en-us/articles/non-commercial-software-download/

当GCC 4.7发布时，将支持openmp 3.1...希望很快 :)