基于FPGA的排序

关于排序，通常大家熟悉的都是基于CPU时序结构的排序算法，比如冒泡排序、快速排序等等。但在FPGA上有时也需要进行排序，比如想得到FFT输出的若干点中最大的几十个点，或者我们只关心输出中那些较大的值的情况。如果我们只需要最大的一个值，这比较好办，用一个比较器树就行了。但是如果我们需要取出例如前128个最大值或者最小值，那么通常需要采用排序模块。

在FPGA上实现一个固定输入个数的排序，通常使用排序网络(Sorting Network)，一个不错的排序网络就是双调排序网络(Bitonic Sorting Network)，这可以在wiki上查到。这个排序网络很好理解，下面简单介绍一下。

看一下下面这个同样是来自wiki的图

它很清楚地介绍了双调排序网络的结构。这是一个16输入的排序网络。所谓双调，就是指这个网络的两组输入都要是单调的，也就是排好序的。例如最后面的一个框里的16输入网络，它可以对两个分别是单调递增的8个排好序的数据和单调递减的8个排好序的数据进行排序；同样地，在第三级的蓝框和绿框里（篮框表示最终输出是单调递增的，绿框表示最终输出是单调递减的），每部分的输入都是由两组增长特性相反的排好序的输出组成的。所以这就是所谓的双调排序网络。

如果从前往后看，数据首先进行两两比较，调整次序，然后再如图所示地进行13、24比较，之后再12、23比较，这样得到的4个输出数据就是排好序的了。以此类推。

设计排序网络的一个重点在于证明该网络对于任意顺序的输入得到的排序结果都是有效的、正确的，这一点在此不展开了，因为双调排序网络已经得到了证明。

verilog代码实现

源码在我的github仓库里，欢迎造访。

因为我仿真的时候为了方便用了一系列工具，包括Icarus, myHDL and gtkwave，而且是在ubuntu16.04下做的，用python写的testbench。如果你看了嫌麻烦，给你一个懒人传送门，直接看到4个verilog代码，确定排序数据个数、位宽、每个输入对应的索引或者是标签(label)的位宽、递增还是递减、有符号还是无符号，改改top模块里对应的5个parameter，放入vivado，enjoy。关于参数的细节，可以看下面配置参数部分。

如果想了解这个仿真怎么用，找台linux机器，按照那三个工具的网站上的手册安装好，应该就可以愉快地使用了。如果他们用起来实在不够友好，之后我再优化。

如果用户体验不佳，告诉我改进方向，我再继续完善。

verilog实现细节和配置参数

如果你不仅想使用该模块，还想知道模块是怎么实现的，那就接着往下看。

起先我想直接一个模块一个模块地编下去，于是就有了nonrecursion（非递归）那个文件夹下的rtl和仿真。我从头往后编，尝试实现一个16输入的模块。先来一个2输入的，升降序可调、有无符号可选、位宽和label宽度可调，测一下，没问题；再来一个4输入的，测一下，没问题；再写8输入的，没问题；写到16输入发现输入信号实在太多了，所以把所有输入放到了一个向量里，label也放到了一个向量里，输出也一样。最终，16输入地非递归实现的排序网络诞生了。但是如果要实现一个256输入的排序网络岂不是要崩溃。

于是，recursion（递归）那个文件夹下的rtl和仿真诞生了。只需要4个verilog文件！你就可以实现任意多的输入排序！只要你的FPGA有足够多的硬件资源，想要多少输入，就有多少输入！只需4个verilog文件！4个！4个！只需4个！喜欢的话别忘了点个赞哦！

在递归实现中，除了非递归中实现的升降序可调、有无符号可选、位宽和label宽度可调，又增加了一个LOG_INPUT_NUM参数，这是用来选定通道数的，正是它让你想要多少输入，就能有多少输入。所以输入x向量的宽度就是DATA_WIDTH*(2^{LOG_INPUT_NUM})，也就是输入数为 2^{LOG_INPUT_NUM}个，每个数的位宽为DATA_WIDTH；同样地输入的x_label的宽度就是LABEL_WIDTH*(2^{LOG_INPUT_NUM})；输出向量也一样。比如说，4输入网络，位宽8bit，label位宽4bit，那么x[7:0]就是第一个输入，x_label[3:0]就是第一个输入对应的标签或者索引；第二个输入就是x[15:0]和x_label[7:4]。

如果你想搞清楚硬件实现的方式，就看非递归的，因为比较好理解；如果你想搞个比如256输入的排序，那还是从递归的下手改改参数更方便。

模块性能

不难算出，当输入数量为K时，该模块延迟的周期数为 (log⁡K*(log⁡K+1))/2 。这里面log的底数是2，这个可以通过16输入的情况推算出来和验证。最终需要的2输入比较器的数量为 (log⁡K*(log⁡K+1))/2 * K/2 = (K * logK * (log⁡K+1))/4 个，具体到了FPGA上会映射出多少资源，大体上应该正比于比较器数量。这个排序网络性能还是不错的，做个512输入或者256输入的排序，一般的资源消耗还可以接受，延迟也不高。

如有任何疑问，欢迎交流指正。