使用 OpenMP 对数组进行排序：为什么一些随机数组以长数字结尾并且排序不正确？

Question

我们的作业涉及创建一个排序算法，对随机生成的整数数组进行排序。执行程序时设置为参数的数组大小。

为了测试，我们打印已排序数组的前 10 个元素以及执行时间。

当我们不在生成随机数组的函数中插入多线程时，我们的实现工作正常。然而，当使用并行代码时，在大约 10% 的情况下我们会得到意想不到的结果。以12000000大小的数组为例：

第一次执行输出：0 1 2 2 4 7 7 9 9 9

第二次执行输出：0 1 1 1 1 2 4 4 7 7

第三次执行输出：0 1 1 1 1 2 2 2 4 4

第4次执行输出：0 1 1 2 4 7 7 9 12 16

第5次执行输出：0 10278907 1671508 1716191 145377 3825599 1265238 859463 6112391 11065992

第n次执行输出：更多的预期结果和偶尔的意外结果。

起初，我认为问题是我们使用的 rand() 函数不是线程安全的。所以我改变了我们的功能：

void randomizeArray(int* array, int size, int max_value) {
int i;
#pragma omp parallel for
for (i = 0; i < size; i++) {
    array[i] = rand() % max_value;
}
}

为此：

void randomizeArray(int* array, int size, int max_value) {
int i;
unsigned int seed = 1;
#pragma omp parallel for
for (i = 0; i < size; i++) {
    array[i] = rand_r(&seed) % max_value;
}
}

结果是一样的。一堆正确排序的 1-2 位数字输出和偶尔未排序的大整数数组。这与随机化功能有关吗？或者它可能是别的东西？

提前谢谢你。

Answer 1

你是对的，函数 rand 不能保证是线程安全的，应该使用 rand_r 代替。

但是，您的替换实现也不是线程安全的。尽管函数 rand_r 本身是线程安全的，但您通过函数 rand_r 使用多个线程写入变量 seed，而没有任何线程同步，这会导致未定义的行为。

即使您假设对 unsigned int 的写入在您的平台上是原子的，因此对同一个变量的部分写入会导致数据损坏，您仍然会有多个线程不断地覆盖 seed，这有时可能会用它以前的值覆盖它，因此下一次调用 rand_r 将再次生成相同的“随机”值。这可能就是为什么您发布的输出连续多次具有相同的“随机”值。

因此，您需要每个线程都有自己的 seed 副本。一种方法是更改行

#pragma omp parallel for

至：

#pragma omp parallel for private(seed)

但是，这将导致每个线程的随机数生成器使用相同的种子值，这将导致每个线程的伪随机数生成器 (PRNG) 生成相同的随机数序列。根据情况，这可能是个问题。

如果不希望每个线程都生成相同的随机数序列，那么可以根据omp_get_thread_num()的return值设置每个线程的PRNG种子。这样，每个线程都应该有自己的种子并生成一组不同的随机数。

但是，您必须在 for 循环之外设置 PRNG 的种子，这意味着您必须将 #pragma omp parallel for 子句拆分为 #pragma omp parallel 和 #pragma omp for 子句：

void randomizeArray(int* array, int size, int max_value)
{
    #pragma omp parallel
    {
        unsigned int seed = omp_get_thread_num();
        #pragma omp for
        for ( int i = 0; i < size; i++ )
        {
            array[i] = rand_r(&seed) % max_value;
        }
    }
}

使用 OpenMP 对数组进行排序：为什么一些随机数组以长数字结尾并且排序不正确？

Sorting arrays using OpenMP: why do some randomized arrays end up with long numbers and not sorted correctly?

c

multithreading

parallel-processing

openmp

random-seed