使用OpenMP并行化选择排序

Question

我需要使用OpenMP实现并行选择排序算法, 但我无法在Stack Overflow或一般的互联网上找到太多信息。

这是我的串行代码:

void selectionsort(int* arr, int size)
{
    for (int i = size - 1; i > 0; --i)
    {
        int max = i;
        for (int j = i - 1; j >= 0; --j)
        {
            if (arr[j] > arr[max])
            {
                max = j;
            }
        }
        swap(arr[i], arr[max]);
    }
}

---

有没有人知道如何并行实现这种类型的排序算法？至少在理论上？

- Denis Yakovenko

---

并行排序的经典方法可能是对[0，SIZE/N] [SIZE/N，2*SIZE/N] ...进行排序。然后合并结果。 另一种解决方案是在内部循环中使用pragma omp，这可以轻松地并行化。 - P. Brunet

也许你找不到太多信息的原因是因为这个想法太糟糕了！ - Jim Cownie

Answer 1

由于数组中的常量变化，外部循环无法并行化，因此我们需要并行化内部循环。

因此，我们需要使用最大值约简，但由于我们不仅需要最大值，还需要该最大值的索引，因此我们需要声明一个新的约简（仅在OpenMP 4.0中可用）来接收一个结构体，下面是完全功能的代码：

#include <stdio.h>
#include <omp.h>

struct Compare { int val; int index; };
#pragma omp declare reduction(maximum : struct Compare : omp_out = omp_in.val > omp_out.val ? omp_in : omp_out)

void selectionsort(int* arr, int size)
{
    for (int i = size - 1; i > 0; --i)
    {
        struct Compare max;
        max.val = arr[i];
        max.index = i;
        #pragma omp parallel for reduction(maximum:max)
        for (int j = i - 1; j >= 0; --j)
        {
            if (arr[j] > max.val)
            {
                max.val = arr[j];
                max.index = j;
            }
        }
        int tmp = arr[i];
        arr[i] = max.val;
        arr[max.index] = tmp;
    }
}

int main()
{
        int x[10] = {8,7,9,1,2,5,4,3,0,6};
        selectionsort(x, 10);

        for (int i = 0; i < 10; i++)
                printf("%d\n", x[i]);
        return 0;
}

- Gabriel Garcia

Answer 2

Gabriel Garcia发布的解决方案仅适用于自然数数组。

如果您使用此数组，将得到错误的结果：

int x[10] = {-8,-7,-9,-1,-2,-5,-4,-3,0,-6};

减少声明：

#pragma omp declare reduction(maximum : struct Compare : omp_out = omp_in.val > omp_out.val ? omp_in : omp_out)

由于未指定 初始化子句，因此在并行循环的每个迭代中，即使在循环之前将 max.val 和 max.index 初始化过，它们也会被初始化为0。

有关更多信息，请参见用户定义的约简语法。

正确的声明应该是：

#pragma omp declare reduction(maximum : \
                              struct Compare : \
                              omp_out = omp_in.val > omp_out.val ? omp_in : omp_out) \
                              initializer(omp_priv=omp_orig)

你也可以通过同样的方式进行“最小化”减少（显然，需要修改索引和关系符号）。

- Antonio Toncetti