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))
}

审核编辑：刘清