为 64 个元素排序网络交换

Question

我正在尝试使用 Sorting Network in a C program to sort a small list A of n elements. A Sorting Network consists of SWAP(x, y) macros, each of which compares two elements A[x] and A[y], and swaps if necessary. This website 生成 SWAP(x, y) 宏序列来对 n <= 32 元素进行排序。

现在，我正在寻找用于对 n = 64 元素进行排序的 SWAP(x, y) 序列。在这一点上，我不确定排序网络是否会比对 n = 64 元素使用其他排序算法更快，但我想测试一下。我的问题是：是否有 website/paper/project 列出了这个序列？或者是否有任何算法可以从 n <= 32 的排序网络生成 n = 64？

谢谢。

Answer 1

这与移动圆形阵列有关（https://leetcode.com/articles/rotate-array/# 中的方法 #3）

有一些算法可以确定序列，即 Bose-Nelson 算法 (https://metacpan.org/pod/Algorithm::Networksort), a C implementation is in https://github.com/atinm/bose-nelson/blob/master/bose-nelson.c

Answer 2

如果有人（我）对排序网络对 32 位整数的 64 个元素序列有多合适的问题感兴趣，我自己看了看并发现了以下内容：

qsort 每个序列大约需要 2600ns
std::sort 每个序列花费大约 1100 ns
Bose-Nelson 排序网络每个序列大约需要 1200 ns
Batcher 奇偶网络每个序列花费大约 850ns
使用 AVX2 指令同时处理 8 个序列的 Batcher 奇偶网络每个序列花费 70ns

序列是均匀生成的，因此最大熵，即最坏情况，有利于排序网络。

您可能期望使用 AVX2 的理论加速为 8 倍，为什么有 12 倍的加速？查看程序集，Clang 在块中执行排序网络的多次交换，例如：

00007FF6DA081374  vpminsd     ymm4,ymm0,ymm1  
00007FF6DA081379  vpmaxsd     ymm0,ymm0,ymm1  
00007FF6DA08137E  vpminsd     ymm1,ymm2,ymm3  
00007FF6DA081383  vpmaxsd     ymm2,ymm2,ymm3  
00007FF6DA081388  vpminsd     ymm3,ymm4,ymm1  
00007FF6DA08138D  vpmaxsd     ymm1,ymm4,ymm1  
00007FF6DA081392  vpminsd     ymm4,ymm0,ymm2  
00007FF6DA081397  vpmaxsd     ymm0,ymm0,ymm2  
00007FF6DA08139C  vpminsd     ymm2,ymm4,ymm1  
00007FF6DA0813A1  vpmaxsd     ymm1,ymm4,ymm1

而标量代码使用 cmp、cmovgt、cmovlt 指令，这些指令也与 mov 指令混合使用，并且来自内存。随心所欲。

我在 https://github.com/jamesthomasgriffin/sorting_networks and, for the Bose-Nelson network, https://github.com/Vectorized/Static-Sort.

上为 Batcher odd/even 网络使用了我自己的实现和基准测试代码

Answer 3

为 64 个输入提供最佳结果的方法可能是 David C. Van Voorhis 描述的方法。请参阅下面的 link 了解类似的网络：

https://bertdobbelaere.github.io/sorting_networks_extended.html#N64L521D22

为 64 个元素排序网络交换

Sorting Network SWAPs for 64 elements

c

sorting

swap

sorting-network