OpenMP归约同步错误

Question

我正在尝试并行化一个具有相互依赖循环的循环，我已经尝试了缩减操作，代码可以运行，但结果是错误的。我认为缩减操作适用于求和，但不适用于正确循环中数组的更新。是否有一种方法可以并行化循环以获得正确的结果？

#pragma omp parallel for reduction(+: sum)
for (int i = 0; i < DATA_MAG; i++)
{
    sum += H[i];

    LUT[i] = sum * scale_factor;
}

- CIVI89

---

在减少值的同时，您不能使用正在减少的值，例如 LUT[i] = sum * scale_factor; 是无法正常工作的。 - Z boson

你需要使用预先计算的求和方法。不幸的是，并行前缀和受到内存带宽的限制，所以我认为它不能帮助你太多。 - Z boson

可以做到，但并不容易，我也不确定它是否值得。你可以在DATA_MAG不太大的情况下使用SIMD前缀。使用OpenMP的问题在于，如果DATA_MAG太小，则OpenMP开销会占主导地位，但如果DATA_MAG太大，则受限于内存带宽。然而，在L2和L3缓存之间可能存在一些甜点，可以通过使用线程来获得一些好处。DATA_MAG的范围是多少？ - Z boson

256 很小！！！如果这真的很重要，请使用前缀SIMD。我认为你不能使用OpenMP的simd结构来做这件事。你需要使用内部函数或汇编语言。没有办法OpenMP的simd或自动向量化会搞定这个问题。 - Z boson

你的CPU是什么？你用的是哪个编译器？这是Linux和GCC吗？cat /proc/cpuinfo命令输出了什么？ - Z boson

Answer 1

减少子句为线程团队中的每个线程创建sum的私有副本，就像在sum上使用私有子句一样。在for循环之后，将每个私有副本的结果与共享sum的原始值组合起来。由于共享的sum仅在for循环之后更新，因此您不能在for循环内依赖它。

在这种情况下，您需要进行前缀和。不幸的是，对于大型DATA_MAG，使用线程的并行前缀和受到内存带宽限制，并且对于小型DATA_MAG，它被OpenMP开销所支配。但是，在小型和大型之间可能存在某些甜点，您可以看到使用线程的一些好处。

但在您的情况下，DATA_MAG仅为256，非常小，并且无法从OpenMP中受益。您可以使用SIMD。但是，据我所知，OpenMP的simd结构对于前缀和来说不够强大。但是，您可以手动使用intrinsics完成此操作，例如：

#include <stdio.h>
#include <x86intrin.h>

#define N 256

inline __m128 scan_SSE(__m128 x) {
  x = _mm_add_ps(x, _mm_castsi128_ps(_mm_slli_si128(_mm_castps_si128(x), 4)));
  x = _mm_add_ps(x, _mm_castsi128_ps(_mm_slli_si128(_mm_castps_si128(x), 8)));
  return x;
}

void prefix_sum_SSE(float *a, float *s, int n, float scale_factor) {
  __m128 offset = _mm_setzero_ps();
  __m128 f = _mm_set1_ps(scale_factor);
  for (int i = 0; i < n; i+=4) {
    __m128 x = _mm_loadu_ps(&a[i]);
    __m128 out = scan_SSE(x);
    out = _mm_add_ps(out, offset);
    offset = _mm_shuffle_ps(out, out, _MM_SHUFFLE(3, 3, 3, 3));
    out = _mm_mul_ps(out, f); 
    _mm_storeu_ps(&s[i], out);
  }
}

int main(void) {
  float H[N], LUT[N];
  for(int i=0; i<N; i++) H[i] = i;
  prefix_sum_SSE(H, LUT, N, 3.14159f);
  for(int i=0; i<N; i++) printf("%.1f ", LUT[i]); puts("");
  for(int i=0; i<N; i++) printf("%.1f ", 3.14159f*i*(i+1)/2); puts("");

}

关于使用SSE和AVX实现SIMD前缀和的更多细节，请参见此处。

- Z boson