FPGA排序-冒泡排序介绍

排序算法是图像处理中经常使用算法，常见的排序算法有插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序。
如下图：

冒泡排序的排序过程如下：

整个排序的过程就是两两比较，然后做交换。整个过程的时间复杂度n的平方，也就是说需要交换很多次，如果把这么多交换过程都在一个时钟周期内完成的话，组合逻辑会很长，这样直接影响最后的时序。如果每个时钟周期进行一次交换的话，pipeline是会很长的。

那么我们可以通过变通一下，整个排序过程只做比较，而不做交换。每一次比较的结果都记录下来，然后设置一个计分板，通过计分板就可以知道排序的结果了。

首先是比较的过程：判断输入的两个数哪个大，使用1bit变量来记录比较结果。

然后是计分板的生成：

最后是排序结果的输出：

仿真代码如下：

仿真波形：

一共三级流水，占用的资源也不多，可以自己通过reduceBalancedTree来增加更多的流水。

照例提供SpinalHDL的源码，Verilog有需要的私聊：

import spinal.core._import spinal.lib._class BubbleSort(DATA_WIDTH: Int, DATA_NUM: Int) extends Component { val io = new Bundle { val dataIn = in Vec(UInt(DATA_WIDTH bits), DATA_NUM) val dataInValid = in Bool() val dataOut = out Vec(Reg(UInt(DATA_WIDTH bits)), DATA_NUM) val dataOutValid = out(Reg(Bool()) init False) } noIoPrefix() val sortV = Vec(Vec(UInt(1 bits), DATA_NUM - 1), DATA_NUM) for (i <- 0 until DATA_NUM) { for (j <- (i + 1) until DATA_NUM) { sort(io.dataIn(i), io.dataIn(j), sortV(i)(j - 1), sortV(j)(i)) } } val scoreBoard = Vec(Reg(UInt(log2Up(DATA_NUM - 1) bits)), DATA_NUM) for (i <- 0 until DATA_NUM) {        scoreBoard(i) := sortV(i).reduceBalancedTree(_ +^ _).resized    }    def sort(data1: UInt, data2: UInt, out1: UInt, out2: UInt): Unit = {        val out = Reg(UInt(1 bits))        when(data1 >= data2) { out := 1 } otherwise { out := 0 } out1 := out out2 := ~out1 } val dataTemp = RegNext(RegNext((io.dataIn))) val dataTempValid = RegNext(RegNext(io.dataInValid, init = False), init = False) for (i <- 0 until DATA_NUM) { io.dataOut(scoreBoard(i)) := dataTemp(i) } io.dataOutValid := dataTempValid}object BubbleSort extends App { SpinalConfig(inlineConditionalExpression = true,anonymSignalPrefix="temp").generateVerilog(new BubbleSort(8, 8))}

审核编辑：刘清