gpt4 book ai didi

c - Batcher的奇偶归并排序并行策略

转载 作者:太空宇宙 更新时间:2023-11-04 04:32:53 25 4
gpt4 key购买 nike

我正在尝试并行处理批处理程序的奇偶合并排序。到目前为止我取得的进展是这样的

如果有如下数组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/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com