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

Question

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

如果有如下数组 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}[=11=]

现在按照 Batcher 的奇偶合并排序算法，我必须对上述排序数组的偶数位置元素和奇数位置元素进行排序。

为了以并行方式实现它，我可以只对偶数元素进行并行处理，对奇数元素进行并行处理吗？就像上面两个并行的 for 循环一样。 我需要建议，希望大家能简单点。

完成上述步骤后，我必须交换从上述步骤获得的数组中的相邻元素（第一个元素除外）。我将使用 final parallel 来做到这一点。最好走这条路吗？

Answer 1

标题提到归并排序，但在 wiki 上查找后，Batcher 的算法是一种面向硬件的排序网络：一系列比较/交换电路，其中的组可以并行执行。索引模式比相邻的偶数和奇数对更复杂。 wiki 图显示了一个 8 个整数数组的示例，以及允许并行操作的分组。请注意，索引的示例代码输出顺序与图中的顺序不同。

靠近 wiki Batcher 文章底部的是一种迭代算法，用于 select 用于比较/交换电路的索引。我不知道它是否与 8 元素案例的图表匹配。

http://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort

http://en.wikipedia.org/wiki/Sorting_network

我不确定这是否是软件类型的实用方法，但它是一种测试最终会成为硬件实现的方法。

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

Batcher's odd even merge sort parallel strategy

c

sorting

openmp