排序算法是圖像處理中經常使用一種算法，常見的排序算法有插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序。

如下圖：

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

整個排序的過程就是兩兩比較，然后做交換。整個過程的時間復雜度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))
}

?

審核編輯：劉清