打开MP。两个连续周期的并行化

Question

正在研究OpenMP，写了一个摇床排序的实现。这里有2个连续的循环，为了顺序调用，我加了omp_init_lock、omp_destroy_lock形式的blocker，结果还是不对。请告诉我如何并行化两个连续的周期。我的代码如下：

int Left, Right;
Left = 1;
Right = ARR_SIZE;

while (Left <= Right)
{
    omp_init_lock(&lock);
    #pragma omp parallel reduction(+:Left) num_threads(4)
    {
        #pragma omp for
        for (int i = Right; i >= Left; i--) {
            if (Arr[i - 1] > Arr[i]) {
                int temp;
                temp = Arr[i];
                Arr[i] = Arr[i - 1];
                Arr[i - 1] = temp;
            }
        }
        Left++;
    }
    omp_destroy_lock(&lock);

    omp_init_lock(&lock);
    #pragma omp parallel reduction(+:Right) num_threads(4)
    {
        #pragma omp for
        for (int i = Left; i <= Right; i++) {
            if (Arr[i - 1] > Arr[i]) {
                int temp;
                temp = Arr[i];
                Arr[i] = Arr[i - 1];
                Arr[i - 1] = temp;
            }
        }
        Right--;
    }
    omp_destroy_lock(&lock);

}

Answer 1

如果迭代是独立的，您只能将某些内容设为 omp for。你的显然不是。
你的锁没有用。两个平行区域总是按顺序进行。这样你就可以解除锁定了。

Answer 2

您似乎对 OpenMP 的工作原理存在一些误解。

两个并行部分不会并行执行。这是 fork-join 并行性。并行部分本身由多个线程执行，然后在并行部分的末尾重新加入。

您的代码看起来像您期望的那样工作 pragma omp sections。旁注：除非您别无选择and/or您完全知道您在做什么，否则不要使用节。它们不能很好地扩展。

你对锁API的使用是错误的。 omp_init_lock 初始化一个锁对象。它不会获取它。同样 destroy 函数会释放它，它不会释放锁。如果您想获得锁，请在进入并行部分之前对初始化一次的锁使用 omp_set_lock 和 omp_unset_lock。

一般来说，如果您需要为代码的扩展部分加锁，它不会并行化。继续阅读 Amdahl's law。锁只有在很少使用或两个线程同时竞争同一个锁的可能性很小的情况下才有用。

您的代码包含竞争条件。由于您使用了 pragma omp for，因此两个不同的线程可能会同时执行第 i 次和第 (i-1) 次迭代。这意味着它们将触及相同的整数。这是未定义的行为，可以说会导致他们踩到对方的脚趾。
我不知道你想用这些折扣做什么。

如何解决这个问题

嗯，传统的摇床排序不能并行工作，因为在外循环的一次迭代中，一个元素可能会移动整个距离直到范围的末尾。这需要大量 inter-thread 协调，这是不可行的。

您可以做的是冒泡排序的变体，其中每个线程查看两个值并交换它们。来回移动此 window，值将慢慢移动到正确的位置。

这应该有效：

#include <utility>
// using std::swap

void shake_sort(int* arr, int n) noexcept
{
  using std::swap;
  const int even_to_odd = n / 2;
  const int odd_to_even = (n - 1) / 2;
  bool any_swap;
  do {
    any_swap = false;
#   pragma omp parallel for reduction(|:any_swap)
    for(int i = 0; i < even_to_odd; ++i) {
      int left = i * 2;
      int right = left + 1;
      if(arr[left] > arr[right]) {
        swap(arr[left], arr[right]);
        any_swap = true;
      }
    }
#   pragma omp parallel for reduction(|:any_swap)
    for(int i = 0; i < odd_to_even; ++i) {
      int left = i * 2 + 1;
      int right = left + 1;
      if(arr[left] > arr[right]) {
        swap(arr[left], arr[right]);
        any_swap = true;
      }
    }
  } while(any_swap);
}

请注意如何不能排除左右边框，因为一次外部迭代不能保证那里的值是正确的。

其他备注：

其他人已经评论过 std::swap 如何使代码更具可读性
您不需要指定 num_threads。 OpenMP 可以自己解决这个问题

打开MP。两个连续周期的并行化

OpenMP. Parallelization of two consecutive cycles

c++

multithreading

concurrency

parallel-processing

openmp

如何解决这个问题

其他备注：