c - 并行冒泡排序被阻止

Question

我的 OpenMP 程序在以下代码的第一个“for”循环上阻塞，没有任何明显的原因。 我只是想并行化冒泡排序。

下面是重现该问题的完整代码:

#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <omp.h>

static int N_THREADS;
#define CHUNK_SIZE (size/N_THREADS)

void
parallel_bubble_sort(uint64_t *T, const uint64_t size)
{
    register bool swapped;
    register uint64_t swap;
    register int i,j;

    #pragma omp parallel private(swap,i,j)
    do {
        swapped = false;

        #pragma omp for schedule(static) reduction(||:swapped)
        for (j=0; j<N_THREADS; j++)
        for (i=j*CHUNK_SIZE+1; i<=(j+1)*CHUNK_SIZE-1; i++)
        if (T[i-1] > T[i]) {
            swap = T[i-1];
            T[i-1] = T[i];
            T[i] = swap;
            swapped = true;
        }

        #pragma omp for schedule(static) reduction(||:swapped)
        for (i=CHUNK_SIZE-1; i<size-CHUNK_SIZE; i+=CHUNK_SIZE)
        if (T[i] > T[i+1]) {
            swap = T[i];
            T[i] = T[i+1];
            T[i+1] = swap;
            swapped = true;
        }
    } while(swapped);
}

int main ()
{
    uint64_t i;
    uint64_t N = 1024;
    N_THREADS = omp_get_max_threads();

    uint64_t *X = (uint64_t *) malloc(N * sizeof(uint64_t));
    for (i = 0 ; i < N ; i++) X[i] = N-i;

    parallel_bubble_sort(X, N);
    free(X);
}

一些额外的背景:

• T* 是指向 uint64_t 类型数组的指针
• size 是数组的大小
• CHUNK_SIZE 只是大小/NUM_THREADS(这也是 OpenMP 在静态调度模式下使用的默认 block 大小值，因此如果我从子句中删除它，我应该得到相同的行为)

关于代码背后的逻辑:

• 在第一个循环中，我将数组分成 block ，并单独传播气泡，线程之间不会重叠
• 在第二个循环中，我确保气泡在边界传播

有关我在执行时遇到的问题的更多详细信息:

• 我的程序卡在第一个“for”循环上。我已经使用 #pragma omp single 和一个简单的打印语句本地化了程序 block 的位置。

Answer 1

死锁的原因是最外层循环中的数据竞争条件:

do {
   swapped = false;  // <--- here
   ...
} while(swapped);    // <--- here

竞争的发生是因为无法保证所有线程都会同时到达实现 while(swapped) 条件的指令。想象一下你有两个线程。线程 0 完成第二个并行循环，发现 swapped 为 true，通过循环条件，然后通过设置 swapped 再次启动循环体为假。如果线程 1 在线程 0 能够将 swapped 设置为 false 之前达到条件，它也将开始新的迭代。但如果到达得太晚，swapped 将为 false 并且循环将终止。因此，线程 1 将不会加入并行循环，而线程 0 将永远在隐式同步屏障处等待。

解决方案是确保所有线程在决定是否开始新迭代时对 swapped 的值有一致的看法。最简单的解决方案是在将 swapped 设置为 false 之前插入一个屏障:

do {
   #pragma omp barrier
   swapped = false;
   ...
} while(swapped);

此外，让所有线程重置交换并不是真正必要的，而且它可能(不确定)违反 OpenMP 规范，该规范禁止在减少完成之前并发访问原始变量。我不确定它是否适用于缩减区域之前的修改(因为我不确定 a couple of years ago )，并且 OpenMP 4.5 规范中删除了有关并发访问的一段内容，但只是为了为了安全起见，我会给该分配单一处理:

do {
   #pragma omp barrier
   #pragma omp single
   swapped = false;
   ...
} while(swapped);