c - 并行化小型网络排序

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 倍。