1.原理

傳統的排序方式是兩兩之間順序進行比較，而全并行算法是基于序列中隨意兩個數進行比較，所以會消耗比較多的比較器。這正詮釋了FPGA技巧里面積換取速度的思想。
原理如下：
（1）第一個時鐘周期，將其中一個數據和其他數據在一個周期中比較。
（2）第二個時鐘周期，將每個數據和其他數據比較后的結果進行累加。
（3）第三個時鐘周期，將每個數據根據自己的得分賦值給新的數組。

2.優缺點

2.1優點

并行比較排序方式在實時性上有明顯的優勢，只需要三個時鐘周期就可以完成排序。

2.2缺點

由于并行比較消耗FPGA的LUT資源，而且在第二個階段需要大量的加法器級聯，考慮到路徑延遲、建立和保持時間的Slack以及時鐘的Jitter，一個時鐘周期的多個加法器級聯會產生問題
代碼的可移植性有所欠缺，比如序列大小改變，在第二和第三階段就需要認為修改多處代碼。

3.傳統的排序例程

如下圖所示，不僅需要多個比較器，而且時序路徑過長，造成布線的數據路徑過長，產生建立時間違例。

從下面的timing報告中可以明顯的看出，該數據過長。

4.全并行比較例程
module sort_paralell(clk, rst, in0, in1, in2, in3, out0, out1, out2, out3);

        input clk;
        input rst;
        input [7:0] in0, in1, in2, in3;//輸入的4個需要比較的數字
        reg [7:0] out_temp[3:0];//輸出數據放入此數組中
        output [7:0] out0, out1, out2, out3;//輸出的比較后的結果
        reg [7:0] out0, out1, out2, out3;
        //下面定義的變量用于存儲比較結果，如in0 > in1,則a0 <= 1,否則a0 <= 0;
        reg  a0, a1, a2;
        reg  b0, b1, b2;
        reg  c0, c1, c2;
        reg  d0, d1, d2;

        reg add_start; //該變量的作用是判斷比較是否結束，比較結束后賦值為1，進入相加模塊
        reg assignm_start; //該變量作用在于判斷相加模塊執行是否結束，結束后賦值為1，進入下一個輸出模塊
        //下面定義的變量用于存儲上述中間變量累加結果，（9個1位2進制數相加最多4位）2的（0,1,2,3）次方的累加，那么4個1位的2進制數相加最多3位，2的（0,1,2）的累加
        reg out_start;
        //reg [3:0] mid0, mid1, mid2, mid3, mid4, mid5, mid6, mid7, mid8, mid9;
        reg [2:0] mid0, mid1, mid2, mid3;//4 input numbers


        //排序算法在FPGA內進行，實現過程主要有以下幾個步驟：
        //1、第一個clk，數據的全比較程序，4個數據排序，輸入數據為in0~in3;
        //2、第二個clk，比較值累加，mid0,mid1,mid2,mid3;
        //3、第三個clk，把輸入值賦給相對應的排序空間；
        //4、第四個clk，把排序結果輸出；
        //并行比較模塊（第一個時鐘）
        always @ (posedge clk)
            begin
                if(rst)
                    begin
                        {a0, a1, a2} <= 3'b0000_0000_0;
                        {b0, b1, b2} <= 3'b0000_0000_0;
                        {c0, c1, c2} <= 3'b0000_0000_0;
                        {d0, d1, d2} <= 3'b0000_0000_0;

                        {mid0, mid1, mid2, mid3} <=
                        30'b0000_0000_0000_0000_0000_0000_0000_0000_0000_0000;
                        out0 <= 0; out1 <= 0; out2 <= 0; out3 <= 0;
                        add_start <= 0;
                        assignm_start <= 0;
                        out_start <= 0;
                    end
                else
                    begin
                        if(in0 > in1) a0 <= 1'b1; //in0和所有除自己外的其他數據比較，大于則標志置1
                        else a0 <= 1'b0;
                        if(in0 > in2) a1 <= 1'b1;
                        else a1 <= 1'b0;
                        if(in0 > in3) a2 <= 1'b1;
                        else a2 <= 1'b0;


                        if(in1 > in0) b0 <= 1'b1;//in1和所有除自己外的數據比較，大于標志位置1，否則為0
                        else b0 <= 1'b0;
                        if(in1 > in2) b1 <= 1'b1;
                        else b1 <= 1'b0;
                        if(in1 > in3) b2 <= 1'b1;
                        else b2 <= 1'b0;


                        if(in2 > in0) c0 <= 1'b1;
                        else c0 <= 1'b0;
                        if(in2 > in1) c1 <= 1'b1;
                        else c1 <= 1'b0;
                        if(in2 > in3) c2 <= 1'b1;
                        else c2 <= 1'b0;


                        if(in3 > in0) d0 <= 1'b1;
                        else d0 <= 1'b0;
                        if(in3 > in1) d1 <= 1'b1;
                        else d1 <= 1'b0;
                        if(in3 > in2) d2 <= 1'b1;
                        else d2 <= 1'b0;


                        add_start <= 1; //比較結束標志，相加開始標志
                    end

            end
    //相加模塊，mid（i）的值代表著in（i）所在輸出數組中的位置，（第二個時鐘）
    always @ (posedge clk)
        begin
            if(add_start == 1)
                begin
                    mid0 <= a0 + a1 + a2; //標志位相加，所得結果就是其所在位置
                    mid1 <= b0 + b1 + b2;
                    mid2 <= c0 + c1 + c2;
                    mid3 <= d0 + d1 + d2;

                end
                assignm_start <= 1;//相加結束，賦值開始標志
        end

        //輸出模塊，將排序好的數據放入輸出數組中（第三個時鐘）
    always @ (posedge clk)
        begin
            if(assignm_start == 1)
                begin
                    out_temp[mid0] <= in0;
                    out_temp[mid1] <= in1;
                    out_temp[mid2] <= in2;
                    out_temp[mid3] <= in3;

                    out_start <= 1;//賦值結束，輸出開始標志位
                end
        end
    always @ (posedge clk)
        begin
            if(out_start == 1)
                begin
                    out0 <= out_temp[0];
                    out1 <= out_temp[1];
                    out2 <= out_temp[2];
                    out3 <= out_temp[3];
                end         
        end

endmodule

上述代碼僅供參考，下圖仿真結果為9個數據進行排序的輸出結果。

Verilog實現全并行比較算法.zip (813.6 KB, 下載次數: 8)

2020-6-3 14:06 上傳

點擊文件名下載附件
Verilog實現全并行比較算法.zip
下載積分: 黑幣 -5