用FPGA实现双调排序（1）

典型的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、计数排序、双调排序等。这其中，双调排序以其高度的并行性著称，非常适合于在FPGA上实现。

双调排序（Bitonic Sort）是数据独立（Data-independent）的排序算法，即比较顺序与数据无关，特别适合并行执行。在了解双调排序算法之前，我们先来看看什么是双调序列。

双调序列（Bitonic Sequence）的定义：双调序列是一个先单调递增后单调递减的序列，即存在两种单独特性，故为“双调”。从数学角度而言，对于序列(a[0],a[1],…,a[n-1])：

（1）如果存在索引号j，其中0≤j<n，使得(a[0],a[1],…,a[j])是单调递增，同时(a[j],…,a[n-1])是单调递减的；

（2）在条件（1）无法满足的情况下，如果存在索引号i，且0≤i<n，使得(a[i],…,a[n-1],a[0],…,a[i-1])满足条件（1）

换言之，序列本身先单调递增后单调递减或者序列经过循环移位后先单调递增再单调递减，那么该序列就是双调序列。

下图所示序列满足条件（1），j=5，先单调递增后单调递减。

下图所示序列满足条件（2），其中i=4，j=5，循环移位后变为先单调递增后单调递减。

上述两种情形比较简单，所以也比较容易判断是否为双调序列。但其实下面几种情形都是双调序列，图①和图②不再赘述。图③“升->降->升”，通过循环移位即可变为先单调递增再单调递减序列。图④“降->升->降”，仍可通过循环移位变为先单调递增再单调递减序列。需要注意的是完全单调递增或者完全单调递减的序列也是双调序列，例如(0,1,4,5)和(7,5,3)均为双调序列。

双调序列的性质：

（1）双调序列的子序列仍为双调序列。

例如，序列(0,1,4,5,6,7,5,3)其子序列(6,7,5,3)仍为双调序列。

（2）将一个双调序列循环移位后仍为双调序列

（3）任意两个实数都可以组成双调序列

（4）如果序列(a[0],…,a[i])是单调递增序列，(b[i+1],…,b[n-1])是单调递减序列，那么(a[0],…,a[i],b[i+1],…,b[n-1])是一个双调序列

Batcher定理：

若序列S为双调序列，即

令

那么S1和S2仍为双调序列，且S2中的任意一个元素不小于S1中的任意一个元素。

对一个双调序列重复使用Batcher定理最终可以得到一个完全单调递增或单调递减的序列，也就完成了排序。不难看出，在使用Batcher定理时下一次序列长度总是当前序列长度的一半，因此，双调排序算法要求序列长度为2的整数次幂。

使用Batcher定理，我们可以完成一个双调序列的排序，如下图所示案例：原始序列长度为16，第1次分割后产生两个序列，每个序列长度为8；第2次分割时，产生4个序列，每个序列长度为4；第3次分割时，产生8个序列，每个序列长度为2；第4次分割时，产生16个序列，每个序列长度为1。依据此规律可以得出：若序列长度为2n，那么第i次(i=1,2,…,n)分割时，会产生2i个序列，每个序列长度为2(n-i)，要最终完成排序，需要经过n次分割，每次分割需要比较n/2次也就是需要n/2个比较器，该比较器会同时输出最大值和最小值。