我正在尝试并行处理批处理程序的奇偶合并排序。 到目前为止我取得的进展是这样的
如果有如下数组 a[8] = {8,6,4,2,1,7,3,5} 我在上面数组的两半上使用了 omp parallel for,如下所示
#pragma omp parallel for num_threads(4)
for (i = 0; i < halfSize; ++i)
{
for (j = i + 1; j < halfSize; ++j)
{
if (a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
#pragma omp parallel for num_threads(4)
for (i=halfSize; i < arraySize; ++i)
{
for (j = i + 1; j < arraySize; ++j)
{
if (a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
上面的 halfSize 是 4,arraySize 是 8,这基本上并行化了给定数组的两半,所以最终结果如下 a[8] = {2,4,6,8,1,3,5,7}
现在按照 Batcher 的奇偶合并排序算法,我必须对上述排序数组的偶数位置元素和奇数位置元素进行排序。
要以并行方式实现它,我可以只对偶数元素进行并行处理,对奇数元素进行并行处理吗?就像上面两个并行的 for 循环一样。 我需要建议,希望你们能简单点。
完成上述步骤后,我必须交换从上述步骤获得的数组中的相邻元素(第一个元素除外)。我将使用 final parallel 来做到这一点。最好走这条路吗?
最佳答案
标题提到归并排序,但在 wiki 上查找后,Batcher 的算法是一种面向硬件的排序网络:一系列比较/交换电路,其中的组可以并行执行。索引模式比相邻的偶数和奇数对更复杂。 wiki 图显示了一个 8 个整数数组的示例,以及允许并行操作的分组。请注意,索引的示例代码输出与图中的顺序不同。
靠近 wiki Batcher 文章底部的是一种迭代算法,用于选择要用于比较/交换电路的索引。我不知道它是否与 8 元素情况下的图表匹配。
http://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
http://en.wikipedia.org/wiki/Sorting_network
我不确定这是否是软件类的实用方法,但它会是一种测试最终会成为硬件实现的方法。
关于c - Batcher的奇偶归并排序并行策略,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33949171/