使用 OpenMP 并行化选择排序
Parallelize selection sort using OpenMP
我需要使用 OpenMP 实现并行选择排序算法,尽管我在 SO 或 Internet 上找不到太多信息。
这是我的序列号:
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]);
}
}
有人知道如何并行实现这种排序算法吗?至少在理论上?
由于数组不断变化,外层的for无法并行化,我们需要将内层的for并行化。
所以我们需要使用最大缩减,但由于我们不需要最大值,我们还需要这个最大值的索引,我们需要声明一个新的缩减(仅在 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 发布的解决方案仅适用于自然数数组。
如果你使用这个数组,你会得到错误的结果:
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)
没有指定 initializer-clause 因此在并行循环的每次迭代中 max.val 和 max.index 被初始化为 0,即使我们在循环之前初始化它们。
有关详细信息,请参阅 user defined reduction syntax。
正确的声明应该是:
#pragma omp declare reduction(maximum : \
struct Compare : \
omp_out = omp_in.val > omp_out.val ? omp_in : omp_out) \
initializer(omp_priv=omp_orig)
如果愿意,您也可以用相同的方式进行 'minimum' 缩减(显然,更改索引和关系符号)。
我需要使用 OpenMP 实现并行选择排序算法,尽管我在 SO 或 Internet 上找不到太多信息。
这是我的序列号:
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]);
}
}
有人知道如何并行实现这种排序算法吗?至少在理论上?
由于数组不断变化,外层的for无法并行化,我们需要将内层的for并行化。
所以我们需要使用最大缩减,但由于我们不需要最大值,我们还需要这个最大值的索引,我们需要声明一个新的缩减(仅在 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 发布的解决方案仅适用于自然数数组。
如果你使用这个数组,你会得到错误的结果:
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)
没有指定 initializer-clause 因此在并行循环的每次迭代中 max.val 和 max.index 被初始化为 0,即使我们在循环之前初始化它们。
有关详细信息,请参阅 user defined reduction syntax。
正确的声明应该是:
#pragma omp declare reduction(maximum : \
struct Compare : \
omp_out = omp_in.val > omp_out.val ? omp_in : omp_out) \
initializer(omp_priv=omp_orig)
如果愿意,您也可以用相同的方式进行 'minimum' 缩减(显然,更改索引和关系符号)。