并行化小型网络排序

Question

我正在研究网络排序（对于小于 8 的数组）并注意到所有算法都集中在它允许并行操作的能力上。这是一个大小为 5 的数组的集合。

 #define SWAP(x,y) if (data[y] < data[x]) { int tmp = data[x]; data[x] = data[y]; data[y] = tmp; }

    //Parallelizable
    SWAP(1, 2);
    SWAP(4, 5);

    //Parallelizable
    SWAP(0, 2);
    SWAP(3, 5);

    //Parallelizable
    SWAP(0, 1);
    SWAP(3, 4);
    SWAP(2, 5);

    //Parallelizable
    SWAP(0, 3);
    SWAP(1, 4);

    //Parallelizable
    SWAP(2, 4);
    SWAP(1, 3);

    //Parallelizable
    SWAP(2, 3);

我正在使用 long int 数组（因此每个元素的大小为 8 个字节）。那么有什么简单的方法可以在 C 中并行化这些操作吗？我可以使用任何特定于硬件的命令来实现这一点（SIMD、ASM(x86) 等）

Answer 1

正如 this answer 对有关对小集合进行排序的问题所解释的那样，您实际上可以通过将其定义更改为以下定义来提高交换代码的性能：

#define SWAP(x, y) {                        \
    int dx = data[x];                       \
    data[x] = dx < data[y] ? dx : data[y];  \
    data[y] ^= dx ^ data[x];                \
}

根据研究论文 Applying Sorting Networks to Synthesize Optimized Sorting Libraries，这个版本的 SWAP 是无分支的，在 GCC 或 Clang 上编译到只有 5 条指令，具有相当好的优化级别。该文章还暗示了一个事实，即指令数量少实际上可能会使代码受益于指令级并行性。

如果 xor 对要排序的类型不起作用，您可以使用 SWAP 的替代版本，它使用两个条件而不是一个，这应该几乎与 xor版本。实际上，我在我的排序库中使用了这个技巧，当我介绍这个技巧时，使用排序网络对一个小的固定大小的整数集合进行排序从“并不比插入排序好”到“比插入排序快几倍”。使用排序网络对 8 个整数的集合进行排序比使用我的计算机上的插入排序快约 5 倍。

并行化小型网络排序

Parallelized Small Network sort

c

sorting

algorithm

parallel-processing

sorting-network