• 几个排序器的verilog及其资源占用、延时分析

    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

    前言

    因为课题需要，调研了几个快速排序方法，并手写或者改进了若干待测试对象，包括记分板型冒泡排序（这个是别人的）、插入排序（这个是我写的）、双调排序（这个我改了又改，可能还会接着改进）、堆排序（这个是别人的）。以上都在7035开发板上测试了资源。除了插入排序截了时序图之外，其他几个我就直接给代码，外加资源占用情况和延迟（这个延迟是给定例子的延迟）。不介绍原理了，默认都懂！

    这个领域比较小众，能查到的文献相比时髦的深度学习硬件加速器要少得多得多，但还是有存在价值。外加上开源的排序器硬件加速方案，按照作者的说法要么就是纯粹从原理介绍到电路设计，要么就额外添加几句自己的设计很牛，总之缺乏统一的对比，说服力不够。

    我在这篇博客做的工作就是：

    1、改进双调排序；

    2、纯手撸一个4状态的插入排序；

    3、合理比较。

    书写、修改、调试不易，请大家多多惠存~

    一、记分板型冒泡排序

    以下是.v

    1. // reference: https://mp.weixin.qq.com/s/BesXJzfle_ZvW__C6DBNrA
    2.  
    3. module sort_bubble #(parameter BITWIDTH = 8, parameter ELEMENTS = 32)(
    4.     input                            clk             ,
    5.     input                            rst             ,
    6.     input   [BITWIDTH*ELEMENTS-1:0]  data_in         ,
    7.     input                            data_in_valid   ,
    8.     output  [BITWIDTH*ELEMENTS-1:0]  data_out        ,
    9.     output                           data_out_valid
    10.  
    11. );
    12.     reg [ 5:0]  data_in_valid_ff;
    13.     reg [BITWIDTH*ELEMENTS-1:0]  data_in_ff[5:0] ;
    14.     reg                          v[ELEMENTS-1:0][ELEMENTS-1:0] ;
    15.     reg [ 1:0]  sum_1[31:0][15:0] ;
    16.     reg [ 2:0]  sum_2[31:0][7:0]  ;
    17.     reg [ 3:0]  sum_3[31:0][3:0]  ;
    18.     reg [ 4:0]  sum_4[31:0][1:0]  ;
    19.     reg [ 5:0]  sum_5[31:0]       ;
    20.  
    21.     reg [BITWIDTH-1:0]   data_out_temp[ELEMENTS-1:0] ;
    22.     reg                  data_out_valid_temp;
    23.  
    24.     genvar i;
    25.     genvar j;
    26.  
    27.  
    28.     always @(posedge clk ) begin
    29.         if(rst == 1'b1)begin
    30.             data_in_valid_ff <= 6'b0;
    31.         end
    32.         else begin
    33.             data_in_valid_ff <= {data_in_valid_ff[4:0], data_in_valid};
    34.         end
    35.     end
    36.  
    37.     always @(posedge clk ) begin
    38.         data_in_ff[0] <= data_in;
    39.     end
    40.  
    41.     generate
    42.         for ( i = 0; i < 5 ; i = i + 1 ) begin : LOOP_DATA_IN
    43.             always @(posedge clk ) begin
    44.                 data_in_ff[i+1] <= data_in_ff[i];
    45.             end
    46.         end
    47.     endgenerate
    48.  
    49.     generate
    50.         for ( i = 0 ; i < 32 ; i = i + 1 ) begin : LOOP_V_I
    51.             for ( j = i ; j < 32 ; j = j + 1) begin : LOOP_V_J
    52.                 always @(posedge clk ) begin
    53.                     if(data_in_valid == 1'b1)begin
    54.                         v[i][j] <= data_in[i*8 +: 8] >= data_in[j*8 +: 8]; // 2D Parallel
    55.                         v[j][i] <= data_in[i*8 +: 8] <  data_in[j*8 +: 8]; // 2D Parallel
    56.                     end
    57.                 end
    58.             end
    59.         end
    60.     endgenerate
    62.     generate
    63.         for ( i = 0 ; i < 32 ; i = i + 1 ) begin : LOOP_SUM_1_I
    64.             for ( j = 0 ; j < 16 ; j = j + 1) begin : LOOP_SUM_1_J
    65.                 always @(posedge clk ) begin
    66.                     if(data_in_valid_ff[0] == 1'b1)begin
    67.                         sum_1[i][j] <= v[i][j*2] + v[i][j*2 + 1];
    68.                     end
    69.                 end
    70.             end
    71.         end
    72.     endgenerate
    73.  
    74.     generate
    75.         for ( i = 0 ; i < 32 ; i = i + 1 ) begin : LOOP_SUM_2_I
    76.             for ( j = 0 ; j < 8 ; j = j + 1) begin : LOOP_SUM_2_J
    77.                 always @(posedge clk ) begin
    78.                     if(data_in_valid_ff[1] == 1'b1)begin
    79.                         sum_2[i][j] <= sum_1[i][j*2] + sum_1[i][j*2 + 1];
    80.                     end
    81.                 end
    82.             end
    83.         end
    84.     endgenerate
    86.     generate
    87.         for ( i = 0 ; i < 32 ; i = i + 1 ) begin : LOOP_SUM_3_I
    88.             for ( j = 0 ; j < 4 ; j = j + 1) begin : LOOP_SUM_3_J
    89.                 always @(posedge clk ) begin
    90.                     if(data_in_valid_ff[2] == 1'b1)begin
    91.                         sum_3[i][j] <= sum_2[i][j*2] + sum_2[i][j*2 + 1];
    92.                     end
    93.                 end
    94.             end
    95.         end
    96.     endgenerate
    97.  
    98.     generate
    99.         for ( i = 0 ; i < 32 ; i = i + 1 ) begin : LOOP_SUM_4_I
    100.             for ( j = 0 ; j < 2 ; j = j + 1) begin : LOOP_SUM_4_J
    101.                 always @(posedge clk ) begin
    102.                     if(data_in_valid_ff[3] == 1'b1)begin
    103.                         sum_4[i][j] <= sum_3[i][j*2] + sum_3[i][j*2 + 1];
    104.                     end
    105.                 end
    106.             end
    107.         end
    108.     endgenerate
    110.     generate
    111.         for ( i = 0 ; i < 32 ; i = i + 1 ) begin : LOOP_SUM_5_I
    112.             always @(posedge clk ) begin
    113.                 if(data_in_valid_ff[4] == 1'b1)begin
    114.                     sum_5[i] <= sum_4[i][0] + sum_4[i][1];
    115.                 end
    116.             end
    117.         end
    118.     endgenerate
    119.  
    120.     always @(posedge clk ) begin : LOOP_DATA_OUT_TEMP_CLK
    121.         integer k;
    122.         for ( k = 0; k < 32; k = k + 1) begin : LOOP_DATA_OUT_TEMP
    123.             if(data_in_valid_ff[5] == 1'b1)begin 
    124.                 data_out_temp[sum_5[k]] <= data_in_ff[5][k*8 +: 8];
    125.                 data_out_valid_temp     <= 1'b1;
    126.             end
    127.             else begin
    128.                 data_out_temp[sum_5[k]] <= 8'd0;
    129.                 data_out_valid_temp     <= 1'b0;
    130.             end
    131.         end
    132.     end
    133.  
    134.     generate
    135.         for ( i = 0 ; i < 32 ; i = i + 1) begin : LOOP_DATA_OUT
    136.             assign data_out[i*8 +: 8] = data_out_temp[i]   ;
    137.             assign data_out_valid     = data_out_valid_temp;
    138.         end
    139.     endgenerate
    140.  
    141. endmodule

    以下是testbench 

    1.  
    2. `timescale 1ns / 1ps
    3. module tb_bubble(
    4.  
    5.     );
    6.  
    7.     reg clk;
    8.     reg rst;
    9.  
    10.     reg [7:0] data_in_0;
    11.     reg [7:0] data_in_1;
    12.     reg [7:0] data_in_2;
    13.     reg [7:0] data_in_3;
    14.     reg [7:0] data_in_4;
    15.     reg [7:0] data_in_5;
    16.     reg [7:0] data_in_6;
    17.     reg [7:0] data_in_7;
    18.     reg [7:0] data_in_8;
    19.     reg [7:0] data_in_9;
    20.     reg [7:0] data_in_10;
    21.     reg [7:0] data_in_11;
    22.     reg [7:0] data_in_12;
    23.     reg [7:0] data_in_13;
    24.     reg [7:0] data_in_14;
    25.     reg [7:0] data_in_15;
    26.     reg [7:0] data_in_16;
    27.     reg [7:0] data_in_17;
    28.     reg [7:0] data_in_18;
    29.     reg [7:0] data_in_19;
    30.     reg [7:0] data_in_20;
    31.     reg [7:0] data_in_21;
    32.     reg [7:0] data_in_22;
    33.     reg [7:0] data_in_23;
    34.     reg [7:0] data_in_24;
    35.     reg [7:0] data_in_25;
    36.     reg [7:0] data_in_26;
    37.     reg [7:0] data_in_27;
    38.     reg [7:0] data_in_28;
    39.     reg [7:0] data_in_29;
    40.     reg [7:0] data_in_30;
    41.     reg [7:0] data_in_31;
    42.  
    43.     wire [255:0] data_in;
    44.     reg         data_in_valid;
    45.  
    46.     wire [255:0] data_out;
    47.     wire        data_out_valid;
    48.  
    49.     initial begin
    50.         clk = 1'b0;
    51.         rst = 1'b1;
    52.         #50
    53.         rst = 1'b0;
    54.     end
    56.     always #5 clk = !clk;
    58.     always @(posedge clk ) begin
    59.         if(rst == 1'b1)begin
    60.             data_in_0     <= 8'd0;
    61.             data_in_1     <= 8'd0;
    62.             data_in_2     <= 8'd0;
    63.             data_in_3     <= 8'd0;
    64.             data_in_4     <= 8'd0;
    65.             data_in_5     <= 8'd0;
    66.             data_in_6     <= 8'd0;
    67.             data_in_7     <= 8'd0;
    68.             data_in_8     <= 8'd0;
    69.             data_in_9     <= 8'd0;
    70.             data_in_10     <= 8'd0;
    71.             data_in_11     <= 8'd0;
    72.             data_in_12     <= 8'd0;
    73.             data_in_13     <= 8'd0;
    74.             data_in_14     <= 8'd0;
    75.             data_in_15     <= 8'd0;
    76.             data_in_16     <= 8'd0;
    77.             data_in_17     <= 8'd0;
    78.             data_in_18     <= 8'd0;
    79.             data_in_19     <= 8'd0;
    80.             data_in_20     <= 8'd0;
    81.             data_in_21     <= 8'd0;
    82.             data_in_22     <= 8'd0;
    83.             data_in_23     <= 8'd0;
    84.             data_in_24     <= 8'd0;
    85.             data_in_25     <= 8'd0;
    86.             data_in_26     <= 8'd0;
    87.             data_in_27     <= 8'd0;
    88.             data_in_28     <= 8'd0;
    89.             data_in_29     <= 8'd0;
    90.             data_in_30     <= 8'd0;
    91.             data_in_31     <= 8'd0;
    92.             data_in_valid <= 1'b0;
    93.         end
    94.         else begin
    95.             data_in_0     <= {$random} % 255;
    96.             data_in_1     <= {$random} % 255;
    97.             data_in_2     <= {$random} % 255;
    98.             data_in_3     <= {$random} % 255;
    99.             data_in_4     <= {$random} % 255;
    100.             data_in_5     <= {$random} % 255;
    101.             data_in_6     <= {$random} % 255;
    102.             data_in_7     <= {$random} % 255;
    103.             data_in_8     <= {$random} % 255;
    104.             data_in_9     <= {$random} % 255;
    105.             data_in_10     <= {$random} % 255;
    106.             data_in_11     <= {$random} % 255;
    107.             data_in_12     <= {$random} % 255;
    108.             data_in_13     <= {$random} % 255;
    109.             data_in_14     <= {$random} % 255;
    110.             data_in_15     <= {$random} % 255;
    111.             data_in_16     <= {$random} % 255;
    112.             data_in_17     <= {$random} % 255;
    113.             data_in_18     <= {$random} % 255;
    114.             data_in_19     <= {$random} % 255;
    115.             data_in_20     <= {$random} % 255;
    116.             data_in_21     <= {$random} % 255;
    117.             data_in_22     <= {$random} % 255;
    118.             data_in_23     <= {$random} % 255;
    119.             data_in_24     <= {$random} % 255;
    120.             data_in_25     <= {$random} % 255;
    121.             data_in_26     <= {$random} % 255;
    122.             data_in_27     <= {$random} % 255;
    123.             data_in_28     <= {$random} % 255;
    124.             data_in_29     <= {$random} % 255;
    125.             data_in_30     <= {$random} % 255;
    126.             data_in_31     <= {$random} % 255;
    127.             data_in_valid <= 1'b1;
    128.         end
    129.     end
    130.  
    131.     assign data_in = {data_in_0, data_in_1, data_in_2, data_in_3, data_in_4, data_in_5, data_in_6, data_in_7, data_in_8, data_in_9, data_in_10, data_in_11, data_in_12, data_in_13, data_in_14, data_in_15,data_in_16, data_in_17, data_in_18, data_in_19, data_in_20, data_in_21, data_in_22, data_in_23,data_in_24, data_in_25, data_in_26, data_in_27, data_in_28, data_in_29, data_in_30, data_in_31};
    132.  
    133.     sort_bubble sort_bubble_u(
    134.         .clk                (clk           ),
    135.         .rst                (rst           ),
    136.         .data_in            (data_in       ),
    137.         .data_in_valid      (data_in_valid ),
    138.         .data_out           (data_out      ),
    139.         .data_out_valid     (data_out_valid)
    140.  
    141.     );
    142.  
    143. endmodule

    二、插入排序

    以下是.v： 

    1. module sort_insertion #(parameter BITWIDTH = 8, parameter ELEMENTS = 32)(
    2.     input clk,
    3.     input rst_n,
    4.     input [BITWIDTH*ELEMENTS-1:0] data_in,
    5.     output reg [BITWIDTH*ELEMENTS-1:0] data_out
    6. );
    7.     reg [7:0] array [0:31];
    8.     reg [5:0] i, j;
    9.     reg [7:0] key;
    10.  
    11.     // State machine states
    12.     reg [2:0] state_c;
    13.     reg [2:0] state_n;
    14.  
    15.     parameter IDLE = 3'b000,
    16.               SORT = 3'b001,
    17.               BREAK= 3'b010,
    18.               DONE = 3'b011;
    19.  
    20.     genvar p;
    21.     generate
    22.         for (p=0; p<32; p=p+1) begin: ASSIGN_FOR_DATA_OUT
    23.             always @(posedge clk or negedge rst_n) begin
    24.                 data_out[p*8 +: 8] <= array[p];
    25.             end
    26.         end
    27.     endgenerate    
    28.  
    29.     // State Transfer  - First
    30.     always @(posedge clk or negedge rst_n) begin
    31.         if (!rst_n) begin
    32.             state_c <= IDLE;
    33.         end
    34.         else begin
    35.             state_c <= state_n;
    36.         end
    37.     end
    38.  
    39.     // State Transfer - Second
    40.     always @(*) begin
    41.         case (state_c)
    42.             IDLE: begin
    43.                 state_n = BREAK;
    44.             end
    45.             SORT: begin
    46.                 if (j == 0 || array[j] <= key) state_n = BREAK;
    47.                 else state_n = state_c;
    48.             end
    49.             BREAK: begin
    50.                 if (i > 0 && i < 31) state_n = SORT;
    51.                 else if (i == 31) state_n = DONE;
    52.                 else state_n = state_c;
    53.             end
    54.             default: state_n = DONE;
    55.         endcase
    56.     end
    57.  
    58.     // State Transfer - Third
    59.     always @(posedge clk or negedge rst_n) begin
    60.         if (!rst_n) begin i <= 0; j <= 0; key <= 8'd0; end
    61.         else if (state_c == SORT) begin
    62.             if (j == 0 || array[j] <= key) begin
    63.                 i <= i; j <= j - 1; key <= array[i]; // 同时跳转到break
    64.             end
    65.             else begin
    66.                 i <= i; j <= j - 1; key <= key; // 接着比较
    67.             end
    68.         end
    69.         else if (state_c == BREAK) begin
    70.             if ( i <= 30) begin 
    71.                 i <= i + 1; j <= i; key <= array[i+1];
    72.             end
    73.             else begin
    74.                 i <= i + 1; j <= 0; key <= 8'd0;
    75.             end 
    76.         end
    77.         else begin i <= 0; j <= 0; key <= 8'd0; end
    78.     end
    80.     always @(posedge clk or negedge rst_n) begin
    81.         if (!rst_n) begin
    82.             array[0] <= 0;
    83.             array[1] <= 0;
    84.             array[2] <= 0;
    85.             array[3] <= 0;
    86.             array[4] <= 0;
    87.             array[5] <= 0;
    88.             array[6] <= 0;
    89.             array[7] <= 0;
    90.             array[8] <= 0;
    91.             array[9] <= 0;
    92.             array[10] <= 0;
    93.             array[11] <= 0;
    94.             array[12] <= 0;
    95.             array[13] <= 0;
    96.             array[14] <= 0;
    97.             array[15] <= 0;
    98.             array[16] <= 0;
    99.             array[17] <= 0;
    100.             array[18] <= 0;
    101.             array[19] <= 0;
    102.             array[20] <= 0;
    103.             array[21] <= 0;
    104.             array[22] <= 0;
    105.             array[23] <= 0;
    106.             array[24] <= 0;
    107.             array[25] <= 0;
    108.             array[26] <= 0;
    109.             array[27] <= 0;
    110.             array[28] <= 0;
    111.             array[29] <= 0;
    112.             array[30] <= 0;
    113.             array[31] <= 0;                        
    114.         end
    115.         else begin
    116.         if (state_c == IDLE) begin
    117.             array[0] <= data_in[0*8 +: 8];
    118.             array[1] <= data_in[1*8 +: 8];
    119.             array[2] <= data_in[2*8 +: 8];
    120.             array[3] <= data_in[3*8 +: 8];
    121.             array[4] <= data_in[4*8 +: 8];
    122.             array[5] <= data_in[5*8 +: 8];
    123.             array[6] <= data_in[6*8 +: 8];
    124.             array[7] <= data_in[7*8 +: 8];
    125.             array[8] <= data_in[8*8 +: 8];
    126.             array[9] <= data_in[9*8 +: 8];
    127.             array[10] <= data_in[10*8 +: 8];
    128.             array[11] <= data_in[11*8 +: 8];
    129.             array[12] <= data_in[12*8 +: 8];
    130.             array[13] <= data_in[13*8 +: 8];
    131.             array[14] <= data_in[14*8 +: 8];
    132.             array[15] <= data_in[15*8 +: 8];
    133.             array[16] <= data_in[16*8 +: 8];
    134.             array[17] <= data_in[17*8 +: 8];
    135.             array[18] <= data_in[18*8 +: 8];
    136.             array[19] <= data_in[19*8 +: 8];
    137.             array[20] <= data_in[20*8 +: 8];
    138.             array[21] <= data_in[21*8 +: 8];
    139.             array[22] <= data_in[22*8 +: 8];
    140.             array[23] <= data_in[23*8 +: 8];
    141.             array[24] <= data_in[24*8 +: 8];
    142.             array[25] <= data_in[25*8 +: 8];
    143.             array[26] <= data_in[26*8 +: 8];
    144.             array[27] <= data_in[27*8 +: 8];
    145.             array[28] <= data_in[28*8 +: 8];
    146.             array[29] <= data_in[29*8 +: 8];
    147.             array[30] <= data_in[30*8 +: 8];
    148.             array[31] <= data_in[31*8 +: 8];
    149.         end
    150.         else if (state_c == BREAK && i == 1 && array[j] > key) begin
    151.                 array[j + 1]  <= array[j];
    152.                 array[j]      <= key; 
    153.         end
    154.         else if (state_c == SORT && array[j] > key) begin
    155.                 array[j + 1]  <= array[j];
    156.                 array[j]      <= key;
    157.             end
    158.         end
    159.     end
    161. endmodule

    以下是testbench：

    1. module sort_insertion_tb #(parameter BITWIDTH = 8, parameter ELEMENTS = 32)();
    2.     reg clk;
    3.     reg rst_n;
    4.     reg [BITWIDTH*ELEMENTS-1:0] data_in;
    5.     wire [BITWIDTH*ELEMENTS-1:0] data_out;
    6.  
    7.     sort_insertion #(BITWIDTH, ELEMENTS) uut (
    8.         .clk(clk),
    9.         .rst_n(rst_n),
    10.         .data_in(data_in),
    11.         .data_out(data_out)
    12.     );
    13.  
    14.     // Clock generation
    15.     always #5 clk = ~clk;
    16.  
    17.     initial begin
    18.         // Initialize inputs
    19.         clk = 0;
    20.         rst_n = 0;
    21.  
    22.         // Apply reset
    23.         #10;
    24.         rst_n = 1;
    25.  
    26.         // Load test data
    27.         data_in[BITWIDTH*0 +: BITWIDTH]  = 8'd12;
    28.         data_in[BITWIDTH*1 +: BITWIDTH]  = 8'd3;
    29.         data_in[BITWIDTH*2 +: BITWIDTH]  = 8'd25;
    30.         data_in[BITWIDTH*3 +: BITWIDTH]  = 8'd8;
    31.         data_in[BITWIDTH*4 +: BITWIDTH]  = 8'd15;
    32.         data_in[BITWIDTH*5 +: BITWIDTH]  = 8'd18;
    33.         data_in[BITWIDTH*6 +: BITWIDTH]  = 8'd7;
    34.         data_in[BITWIDTH*7 +: BITWIDTH]  = 8'd1;
    35.         data_in[BITWIDTH*8 +: BITWIDTH]  = 8'd31;
    36.         data_in[BITWIDTH*9 +: BITWIDTH]  = 8'd14;
    37.         data_in[BITWIDTH*10 +: BITWIDTH] = 8'd6;
    38.         data_in[BITWIDTH*11 +: BITWIDTH] = 8'd22;
    39.         data_in[BITWIDTH*12 +: BITWIDTH] = 8'd27;
    40.         data_in[BITWIDTH*13 +: BITWIDTH] = 8'd20;
    41.         data_in[BITWIDTH*14 +: BITWIDTH] = 8'd5;
    42.         data_in[BITWIDTH*15 +: BITWIDTH] = 8'd9;
    43.         data_in[BITWIDTH*16 +: BITWIDTH] = 8'd4;
    44.         data_in[BITWIDTH*17 +: BITWIDTH] = 8'd17;
    45.         data_in[BITWIDTH*18 +: BITWIDTH] = 8'd2;
    46.         data_in[BITWIDTH*19 +: BITWIDTH] = 8'd10;
    47.         data_in[BITWIDTH*20 +: BITWIDTH] = 8'd11;
    48.         data_in[BITWIDTH*21 +: BITWIDTH] = 8'd13;
    49.         data_in[BITWIDTH*22 +: BITWIDTH] = 8'd24;
    50.         data_in[BITWIDTH*23 +: BITWIDTH] = 8'd28;
    51.         data_in[BITWIDTH*24 +: BITWIDTH] = 8'd19;
    52.         data_in[BITWIDTH*25 +: BITWIDTH] = 8'd26;
    53.         data_in[BITWIDTH*26 +: BITWIDTH] = 8'd23;
    54.         data_in[BITWIDTH*27 +: BITWIDTH] = 8'd30;
    55.         data_in[BITWIDTH*28 +: BITWIDTH] = 8'd29;
    56.         data_in[BITWIDTH*29 +: BITWIDTH] = 8'd21;
    57.         data_in[BITWIDTH*30 +: BITWIDTH] = 8'd16;
    58.         data_in[BITWIDTH*31 +: BITWIDTH] = 8'd0;
    59.  
    60.         // Wait for the sorting to complete
    61.         #3000;
    62.  
    63.         // Display sorted data
    64.         $display("Sorted data:");
    65.         $display("data_out[0] = %d", data_out[BITWIDTH*0 +: BITWIDTH]);
    66.         $display("data_out[1] = %d", data_out[BITWIDTH*1 +: BITWIDTH]);
    67.         $display("data_out[2] = %d", data_out[BITWIDTH*2 +: BITWIDTH]);
    68.         $display("data_out[3] = %d", data_out[BITWIDTH*3 +: BITWIDTH]);
    69.         $display("data_out[4] = %d", data_out[BITWIDTH*4 +: BITWIDTH]);
    70.         $display("data_out[5] = %d", data_out[BITWIDTH*5 +: BITWIDTH]);
    71.         $display("data_out[6] = %d", data_out[BITWIDTH*6 +: BITWIDTH]);
    72.         $display("data_out[7] = %d", data_out[BITWIDTH*7 +: BITWIDTH]);
    73.         $display("data_out[8] = %d", data_out[BITWIDTH*8 +: BITWIDTH]);
    74.         $display("data_out[9] = %d", data_out[BITWIDTH*9 +: BITWIDTH]);
    75.         $display("data_out[10] = %d", data_out[BITWIDTH*10 +: BITWIDTH]);
    76.         $display("data_out[11] = %d", data_out[BITWIDTH*11 +: BITWIDTH]);
    77.         $display("data_out[12] = %d", data_out[BITWIDTH*12 +: BITWIDTH]);
    78.         $display("data_out[13] = %d", data_out[BITWIDTH*13 +: BITWIDTH]);
    79.         $display("data_out[14] = %d", data_out[BITWIDTH*14 +: BITWIDTH]);
    80.         $display("data_out[15] = %d", data_out[BITWIDTH*15 +: BITWIDTH]);
    81.         $display("data_out[16] = %d", data_out[BITWIDTH*16 +: BITWIDTH]);
    82.         $display("data_out[17] = %d", data_out[BITWIDTH*17 +: BITWIDTH]);
    83.         $display("data_out[18] = %d", data_out[BITWIDTH*18 +: BITWIDTH]);
    84.         $display("data_out[19] = %d", data_out[BITWIDTH*19 +: BITWIDTH]);
    85.         $display("data_out[20] = %d", data_out[BITWIDTH*20 +: BITWIDTH]);
    86.         $display("data_out[21] = %d", data_out[BITWIDTH*21 +: BITWIDTH]);
    87.         $display("data_out[22] = %d", data_out[BITWIDTH*22 +: BITWIDTH]);
    88.         $display("data_out[23] = %d", data_out[BITWIDTH*23 +: BITWIDTH]);
    89.         $display("data_out[24] = %d", data_out[BITWIDTH*24 +: BITWIDTH]);
    90.         $display("data_out[25] = %d", data_out[BITWIDTH*25 +: BITWIDTH]);
    91.         $display("data_out[26] = %d", data_out[BITWIDTH*26 +: BITWIDTH]);
    92.         $display("data_out[27] = %d", data_out[BITWIDTH*27 +: BITWIDTH]);
    93.         $display("data_out[28] = %d", data_out[BITWIDTH*28 +: BITWIDTH]);
    94.         $display("data_out[29] = %d", data_out[BITWIDTH*29 +: BITWIDTH]);
    95.         $display("data_out[30] = %d", data_out[BITWIDTH*30 +: BITWIDTH]);
    96.         $display("data_out[31] = %d", data_out[BITWIDTH*31 +: BITWIDTH]);
    97.  
    98.         $finish;
    99.     end
    100. endmodule

    看一张调了很久的波形：

    三、双调排序

    以下是双调排序.v（目前来看，这段代码还有很大改进空间）：

    1. //
    2. // 
    3. // Create Date: 22/03/2022 
    4. // Author: Bala Dhinesh
    5. // Module Name: BitonicSortScalable
    6. // Project Name: Bitonic Sorting in Verilog
    7. //
    8. //
    9.  
    10. // This code can work with any number of elements in the powers of 2. There are three primary states in the code, namely SORT, MERGE_SETUP, MERGE.
    11. // **SORT**: Sort the array for every eight elements.
    12. // **MERGE_SETUP**: This will make a bitonic sequence for the entire array.
    13. // **MERGE**: Do the bitonic sort from the bitonic sequence array obtained from MERGE_SETUP.
    14. // This code uses eight elements as a base for hardware and scaled from it. 
    15.  
    16. // reference: https://github.com/BalaDhinesh/Bitonic-Sorting-In-Verilog
    17.  
    18. // another reference: https://github.com/john9636/SortingNetwork
    19.  
    20. module sort_bitonic #(parameter BITWIDTH = 8, parameter ELEMENTS = 32)(
    21.     input clk,
    22.     input rst_n,
    23.     input en_i,
    24.     input [ELEMENTS*BITWIDTH-1:0] in,
    25.  
    26.     // add signal for max
    27.     // 32-max1
    28.     input enable_SORT32_max1,
    29.     // 16-max1
    30.     input enable_SORT16_max1,
    31.  
    32.     // The reason of multipling 8 is 8 group of 4-max1
    33.     // 4 group of 8-max1, 2 group of 16-max1, 1 group of 32-max1
    34.     output reg [BITWIDTH*8-1:0] sort_max, 
    35.  
    36.     output reg done_o,
    37.     output reg [ELEMENTS*BITWIDTH-1:0] out
    38. );
    39.  
    40.     // FSM states
    41.     localparam  START = 3'b000,  // 0
    42.                 SETUP = 3'b001,  // 1
    43.                 SORT = 3'b010,   // 2
    44.                 DONE = 3'b011,   // 3
    45.                 MERGE_SETUP = 3'b100,  // 4
    46.                 MERGE = 3'b101,        // 5
    47.                 IDLE = 3'b111;         // 7
    49.     reg positive;                               // sort ascending or descending for intermediate sub-arrays
    50.     reg [2:0] state;                            // state of FSM
    51.     reg [$clog2(ELEMENTS)-1:0] stage;
    52.     reg [7:0] d[0:7];                           // temporary register array
    53.     reg [2:0] step;               
    55.     // Register variables for Bitonic merge
    56.     reg [$clog2(ELEMENTS):0] compare;
    57.     reg [$clog2(ELEMENTS)-1:0] i_MERGE;
    58.     reg [$clog2(ELEMENTS)-1:0] sum;
    59.     reg [$clog2(ELEMENTS)-1:0] sum_max;
    60.     reg [$clog2(ELEMENTS):0] STAGES = ELEMENTS/16;
    61.     reg [$clog2(ELEMENTS):0] STAGES_FIXED = ELEMENTS/16;
    63.     always @(posedge clk or negedge rst_n)
    64.         if (!rst_n) begin
    65.             out <= 0;
    66.             step <= 4'd0;
    67.             done_o <= 1'd0;
    68.             state <= START;
    69.         end else begin
    70.             case(state)
    71.                 START:
    72.                     begin
    73.                         step <= 0;
    74.                         done_o <= 1'd0;
    75.                         compare <= ELEMENTS;
    76.                         i_MERGE <= 0;
    77.                         positive <= 1;
    78.                         sum <= 8;
    79.                         sum_max <= 8;
    80.                         out <= in;
    81.                         if(en_i) begin
    82.                             state <= SETUP;
    83.                             stage <= 0;
    84.                         end
    85.                     end 
    86.                 SETUP:
    87.                     begin
    88.                         if(stage <= (ELEMENTS/8)) begin
    89.                             d[0] <= in[stage*8*BITWIDTH + 0*BITWIDTH +: 8];
    90.                             d[1] <= in[stage*8*BITWIDTH + 1*BITWIDTH +: 8];
    91.                             d[2] <= in[stage*8*BITWIDTH + 2*BITWIDTH +: 8];
    92.                             d[3] <= in[stage*8*BITWIDTH + 3*BITWIDTH +: 8];
    93.                             d[4] <= in[stage*8*BITWIDTH + 4*BITWIDTH +: 8];
    94.                             d[5] <= in[stage*8*BITWIDTH + 5*BITWIDTH +: 8];
    95.                             d[6] <= in[stage*8*BITWIDTH + 6*BITWIDTH +: 8];
    96.                             d[7] <= in[stage*8*BITWIDTH + 7*BITWIDTH +: 8];
    97.                             state <= SORT;
    98.                         end
    99.                         else begin
    100.                             state <= START;
    101.                         end
    102.                     end
    103.                 SORT:
    104.                     begin
    105.                         case(step)
    106.                             0: begin
    107.                                 if(d[0] > d[1]) begin
    108.                                     d[0] <= d[1];
    109.                                     d[1] <= d[0];
    110.                                 end
    111.                                 if(d[2] < d[3]) begin
    112.                                     d[2] <= d[3];
    113.                                     d[3] <= d[2];
    114.                                 end
    115.                                 if(d[4] > d[5]) begin
    116.                                     d[4] <= d[5];
    117.                                     d[5] <= d[4];
    118.                                 end
    119.                                 if(d[6] < d[7]) begin
    120.                                     d[6] <= d[7];
    121.                                     d[7] <= d[6];
    122.                                 end
    123.                                 step <= step + 1;
    124.                             end
    125.                             1: begin
    126.                                 if(d[0] > d[2]) begin
    127.                                     d[0] <= d[2];
    128.                                     d[2] <= d[0];
    129.                                 end
    130.                                 if(d[1] > d[3]) begin
    131.                                     d[1] <= d[3];
    132.                                     d[3] <= d[1];
    133.                                 end
    134.                                 if(d[4] < d[6]) begin
    135.                                     d[4] <= d[6];
    136.                                     d[6] <= d[4];
    137.                                 end
    138.                                 if(d[5] < d[7]) begin
    139.                                     d[5] <= d[7];
    140.                                     d[7] <= d[5];
    141.                                 end
    142.                                 step <= step + 1;
    143.                             end
    144.                             2: begin
    145.                                 if(d[0] > d[1]) begin
    146.                                     d[0] <= d[1];
    147.                                     d[1] <= d[0];
    148.                                 end
    149.                                 if(d[2] > d[3]) begin
    150.                                     d[2] <= d[3];
    151.                                     d[3] <= d[2];
    152.                                 end
    153.                                 if(d[4] < d[5]) begin
    154.                                     d[4] <= d[5];
    155.                                     d[5] <= d[4];
    156.                                 end
    157.                                 if(d[6] < d[7]) begin
    158.                                     d[6] <= d[7];
    159.                                     d[7] <= d[6];
    160.                                 end
    161.                                 step <= step + 1;
    162.                             end
    163.                             3: begin
    164.                                 if(stage%2 ==0) begin
    165.                                     if(d[0] > d[4]) begin
    166.                                         d[0] <= d[4];
    167.                                         d[4] <= d[0];
    168.                                     end
    169.                                     if(d[1] > d[5]) begin
    170.                                         d[1] <= d[5];
    171.                                         d[5] <= d[1];
    172.                                     end
    173.                                     if(d[2] > d[6]) begin
    174.                                         d[2] <= d[6];
    175.                                         d[6] <= d[2];
    176.                                     end
    177.                                     if(d[3] > d[7]) begin
    178.                                         d[3] <= d[7];
    179.                                         d[7] <= d[3];
    180.                                     end
    181.                                 end
    182.                                 else begin
    183.                                     if(d[0] < d[4]) begin
    184.                                         d[0] <= d[4];
    185.                                         d[4] <= d[0];
    186.                                     end
    187.                                     if(d[1] < d[5]) begin
    188.                                         d[1] <= d[5];
    189.                                         d[5] <= d[1];
    190.                                     end
    191.                                     if(d[2] < d[6]) begin
    192.                                         d[2] <= d[6];
    193.                                         d[6] <= d[2];
    194.                                     end
    195.                                     if(d[3] < d[7]) begin
    196.                                         d[3] <= d[7];
    197.                                         d[7] <= d[3];
    198.                                     end
    199.                                 end
    200.                                 step <= step + 1;
    201.                             end
    202.                             4: begin
    203.                                 if(stage%2 ==0) begin
    204.                                     if(d[0] > d[2]) begin
    205.                                         d[0] <= d[2];
    206.                                         d[2] <= d[0];
    207.                                     end
    208.                                     if(d[1] > d[3]) begin
    209.                                         d[1] <= d[3];
    210.                                         d[3] <= d[1];
    211.                                     end
    212.                                     if(d[4] > d[6]) begin
    213.                                         d[4] <= d[6];
    214.                                         d[6] <= d[4];
    215.                                     end
    216.                                     if(d[5] > d[7]) begin
    217.                                         d[5] <= d[7];
    218.                                         d[7] <= d[5];
    219.                                     end
    220.                                 end
    221.                                 else begin
    222.                                     if(d[0] < d[2]) begin
    223.                                         d[0] <= d[2];
    224.                                         d[2] <= d[0];
    225.                                     end
    226.                                     if(d[1] < d[3]) begin
    227.                                         d[1] <= d[3];
    228.                                         d[3] <= d[1];
    229.                                     end
    230.                                     if(d[4] < d[6]) begin
    231.                                         d[4] <= d[6];
    232.                                         d[6] <= d[4];
    233.                                     end
    234.                                     if(d[5] < d[7]) begin
    235.                                         d[5] <= d[7];
    236.                                         d[7] <= d[5];
    237.                                     end
    238.                                 end
    239.                                 step <= step + 1;
    240.                             end
    241.                             5: begin
    242.                                 if(stage%2 ==0) begin
    243.                                     if(d[0] > d[1]) begin
    244.                                         d[0] <= d[1];
    245.                                         d[1] <= d[0];
    246.                                     end
    247.                                     if(d[2] > d[3]) begin
    248.                                         d[2] <= d[3];
    249.                                         d[3] <= d[2];
    250.                                     end
    251.                                     if(d[4] > d[5]) begin
    252.                                         d[4] <= d[5];
    253.                                         d[5] <= d[4];
    254.                                     end
    255.                                     if(d[6] > d[7]) begin
    256.                                         d[6] <= d[7];
    257.                                         d[7] <= d[6];
    258.                                     end
    259.                                 end
    260.                                 else begin
    261.                                     if(d[0] < d[1]) begin
    262.                                         d[0] <= d[1];
    263.                                         d[1] <= d[0];
    264.                                     end
    265.                                     if(d[2] < d[3]) begin
    266.                                         d[2] <= d[3];
    267.                                         d[3] <= d[2];
    268.                                     end
    269.                                     if(d[4] < d[5]) begin
    270.                                         d[4] <= d[5];
    271.                                         d[5] <= d[4];
    272.                                     end
    273.                                     if(d[6] < d[7]) begin
    274.                                         d[6] <= d[7];
    275.                                         d[7] <= d[6];
    276.                                     end
    277.                                 end
    278.                                 step <= 4'd0;
    279.                                 state <= DONE;
    280.                             end
    281.                             default: step <= 4'd0;
    282.                         endcase
    283.                     end
    284.                     
    285.                 DONE: begin
    286.                     if(stage == (ELEMENTS/8 - 1)) begin                    
    287.                         out[stage*8*BITWIDTH + 0*BITWIDTH +: 8] <= d[0];
    288.                         out[stage*8*BITWIDTH + 1*BITWIDTH +: 8] <= d[1];
    289.                         out[stage*8*BITWIDTH + 2*BITWIDTH +: 8] <= d[2];
    290.                         out[stage*8*BITWIDTH + 3*BITWIDTH +: 8] <= d[3];
    291.                         out[stage*8*BITWIDTH + 4*BITWIDTH +: 8] <= d[4];
    292.                         out[stage*8*BITWIDTH + 5*BITWIDTH +: 8] <= d[5];
    293.                         out[stage*8*BITWIDTH + 6*BITWIDTH +: 8] <= d[6];
    294.                         out[stage*8*BITWIDTH + 7*BITWIDTH +: 8] <= d[7];
    295.                         if(ELEMENTS == 8) state <= IDLE;
    296.                         // add code by dention 20240514 start
    297.                         // add 2 group of 16-max1
    298.                         else begin
    299.                             if (enable_SORT16_max1) begin
    300.                                 if (out[0*8*BITWIDTH + 7*BITWIDTH +: 8] > out[1*8*BITWIDTH + 0*BITWIDTH +: 8]) begin
    301.                                     sort_max[BITWIDTH-1:0] <= out[0*8*BITWIDTH + 7*BITWIDTH +: 8]; // 16-max1
    302.                                 end
    303.                                 else begin
    304.                                     sort_max[BITWIDTH-1:0] <= out[1*8*BITWIDTH + 0*BITWIDTH +: 8];
    305.                                 end
    306.                                 if (out[2*8*BITWIDTH + 7*BITWIDTH +: 8] > out[3*8*BITWIDTH + 0*BITWIDTH +: 8]) begin
    307.                                     sort_max[2*BITWIDTH-1:BITWIDTH] <= out[2*8*BITWIDTH + 7*BITWIDTH +: 8]; // 16-max1
    308.                                 end
    309.                                 else begin
    310.                                     sort_max[2*BITWIDTH-1:BITWIDTH] <= out[3*8*BITWIDTH + 0*BITWIDTH +: 8]; 
    311.                                 end
    312.                                 sort_max[8*BITWIDTH-1:2*BITWIDTH] <= 0;
    313.                                 state <= IDLE;
    314.                                 done_o <= 1;
    315.                             end
    316.                             else begin
    317.                                 sort_max[8*BITWIDTH-1:0] <= 0;
    318.                                 state <= MERGE_SETUP; 
    319.                             end
    320.                         end
    321.                         
    322.                         stage <= 0;
    323.                         sum <= 8;
    324.                         i_MERGE <= 0;
    325.                         compare <= 16;
    326.                     end
    327.                     else if(stage < (ELEMENTS/8)) begin
    328.                         out[stage*8*BITWIDTH + 0*BITWIDTH +: 8] <= d[0];
    329.                         out[stage*8*BITWIDTH + 1*BITWIDTH +: 8] <= d[1];
    330.                         out[stage*8*BITWIDTH + 2*BITWIDTH +: 8] <= d[2];
    331.                         out[stage*8*BITWIDTH + 3*BITWIDTH +: 8] <= d[3];
    332.                         out[stage*8*BITWIDTH + 4*BITWIDTH +: 8] <= d[4];
    333.                         out[stage*8*BITWIDTH + 5*BITWIDTH +: 8] <= d[5];
    334.                         out[stage*8*BITWIDTH + 6*BITWIDTH +: 8] <= d[6];
    335.                         out[stage*8*BITWIDTH + 7*BITWIDTH +: 8] <= d[7];
    336.                         state <= SETUP;
    337.                         stage <= stage + 1;
    338.                     end
    339.                     else begin
    340.                         out <= 110;
    341.                         state <= IDLE;
    342.                     end
    343.                 end
    344.                 MERGE_SETUP:
    345.                     begin
    346.                         if(STAGES == ELEMENTS | STAGES_FIXED == 1) begin
    347.                             if(sum == ELEMENTS/2) begin
    348.  
    349.                                 // add code by dention 20240514 start
    350.                                 // add 32-max1
    351.                                 if (enable_SORT32_max1) begin
    352.                                     // choose double sort bitonic 16 max1 and compare two max1 to gain the max in 32
    353.                                     if (out[1*8*BITWIDTH + 7*BITWIDTH +: 8] > out[2*8*BITWIDTH + 0*BITWIDTH +: 8]) begin
    354.                                         sort_max[BITWIDTH-1:0] <= out[1*8*BITWIDTH + 7*BITWIDTH +: 8]; // 32-max1
    355.                                     end
    356.                                     else begin 
    357.                                         sort_max[BITWIDTH-1:0] <= out[2*8*BITWIDTH + 0*BITWIDTH +: 8]; // 32-max1
    358.                                     end                                    
    359.                                     sort_max[BITWIDTH*8-1:BITWIDTH] <= 0;
    360.                                     
    361.                                     state <= IDLE;
    362.                                     done_o <= 1;
    363.                                 end
    364.  
    365.                                 // add code by dention 20240514 end
    366.  
    367.                                 else begin
    368.                                     sort_max[BITWIDTH*8-1:0] <= 0;
    369.                                     state <= MERGE;
    370.                                 end
    371.                             end
    372.                             else begin
    373.                                 sum <= sum_max * 2; //16
    374.                                 sum_max <= sum_max * 2; //16
    375.                                 state <= MERGE_SETUP;
    376.                                 i_MERGE <= 0;
    377.                                 compare <= sum_max*4; //64
    378.                                 positive <= 1;
    379.                                 stage <= 0;
    380.                                 STAGES <= STAGES_FIXED / 2; // 2
    381.                                 STAGES_FIXED <= STAGES_FIXED / 2;  // 1
    382.                             end
    383.                         end
    384.                         // across-0 min-max-min-max 1 period
    385.                         // across-1 min-max-min-max 2 period
    386.                         // across-3 min-max-min-max 3 period
    387.                         // across-7 min-max-min-max 4 period
    388.                         else begin
    389.                             if((sum + i_MERGE) < compare && (compare <= ELEMENTS) && (stage < STAGES)) begin
    390.                                 if(positive) begin
    391.                                     if(out[i_MERGE*BITWIDTH +: 8] > out[(i_MERGE+sum)*BITWIDTH +: 8]) begin
    392.                                         out[i_MERGE*BITWIDTH +: 8] <= out[(i_MERGE+sum)*BITWIDTH +: 8];
    393.                                         out[(i_MERGE+sum)*BITWIDTH +: 8] <= out[i_MERGE*BITWIDTH +: 8];
    394.                                     end
    395.                                 end
    396.                                 else begin
    397.                                     if(out[i_MERGE*BITWIDTH +: 8] < out[(i_MERGE+sum)*BITWIDTH +: 8]) begin
    398.                                         out[i_MERGE*BITWIDTH +: 8] <= out[(i_MERGE+sum)*BITWIDTH +: 8];
    399.                                         out[(i_MERGE+sum)*BITWIDTH +: 8] <= out[i_MERGE*BITWIDTH +: 8];
    400.                                     end
    401.                                 end
    402.                                 if ((sum + i_MERGE) >= (compare - 1)) begin
    403.                                     i_MERGE <= compare;
    404.                                     compare <= compare + 2*sum;
    405.                                     stage = stage + 1;
    406.                                     if(STAGES == 2) begin
    407.                                         if(stage == 0) positive <= 1;
    408.                                         else positive <= 0;
    409.                                     end
    410.                                     else begin
    411.                                         if((stage%(STAGES*2/STAGES_FIXED)) < STAGES/STAGES_FIXED) positive <= 1;
    412.                                         else positive <= 0;
    413.                                     end
    414.                                     state <= MERGE_SETUP;
    415.                                 end
    416.                                 else begin
    417.                                     i_MERGE = i_MERGE + 1;
    418.                                     state <= MERGE_SETUP;
    419.                                 end
    420.                             end
    421.                             else begin
    422.                                 state <= MERGE_SETUP;
    423.                                 i_MERGE <= 0;
    424.                                 positive <= 1;
    425.                                 sum <= sum / 2;
    426.                                 compare <= sum;
    427.                                 stage <= 0;
    428.                                 STAGES <= STAGES * 2;
    429.                             end
    430.                         end
    431.                     end
    432.                 MERGE:
    433.                     begin
    434.                         if(sum == 1) begin
    435.                             state <= IDLE;
    436.                             done_o <= 1;
    437.                         end
    438.                         else begin
    439.                             if((sum + i_MERGE) < ELEMENTS) begin
    440.                                 if(out[i_MERGE*BITWIDTH +: 8] > out[(i_MERGE+sum)*BITWIDTH +: 8]) begin
    441.                                     out[i_MERGE*BITWIDTH +: 8] <= out[(i_MERGE+sum)*BITWIDTH +: 8];
    442.                                     out[(i_MERGE+sum)*BITWIDTH +: 8] <= out[i_MERGE*BITWIDTH +: 8];
    443.                                 end
    444.                                 if ((sum + i_MERGE) >= (compare - 1)) begin
    445.                                     i_MERGE <= compare;
    446.                                     compare <= compare * 2;
    447.                                 end
    448.                                 else begin
    449.                                     i_MERGE = i_MERGE + 1;
    450.                                     state <= MERGE;
    451.                                 end
    452.                             end
    453.                             else begin
    454.                                 state <= MERGE;
    455.                                 i_MERGE <= 0;
    456.                                 sum <= sum / 2;
    457.                                 compare <= sum;
    458.                             end
    459.                         end
    460.                     end
    461.                 IDLE: state <= IDLE;
    462.                 default: state <= START;
    463.             endcase
    464.         end
    465. endmodule

    以下是testbench：

    1. `timescale 1ns/1ps
    2. `define clk_period 20
    3.  
    4. module BitonicSortScalable_tb #(
    5.     parameter BITWIDTH = 8,         // Bitwidth of each element
    6.     parameter ELEMENTS = 32         // Number of elements to be sorted. This value must be a powers of two
    7. )
    8. ();
    9.  
    10.     reg clk, rst_n, en_i;
    11.     reg [ELEMENTS*BITWIDTH-1:0] in;
    12.     wire done_o;
    13.     wire [ELEMENTS*BITWIDTH-1:0] out;
    14.  
    15.     reg enable_SORT32_max1;
    16.     reg enable_SORT16_max1;
    17.  
    18.     wire [BITWIDTH*8-1:0] sort_max;
    19.  
    20.     sort_bitonic bitonic_SORT_u(
    21.         clk,
    22.         rst_n,
    23.         en_i,
    24.         in,
    25.         enable_SORT32_max1,
    26.         enable_SORT16_max1,
    27.         sort_max,
    28.         done_o,
    29.         out
    30.     );
    31.  
    32.     integer i;
    33.     initial begin
    34.         clk = 1'b1;
    35.     end
    37.     always #(`clk_period/2) begin
    38.         clk = ~clk;
    39.     end
    41.     initial begin
    42.         rst_n = 0;
    43.         en_i = 0;
    44.         in = 0;
    45.         enable_SORT16_max1 = 0;
    46.         enable_SORT32_max1 = 0;
    48.         #(`clk_period);
    49.         rst_n = 1;
    50.         en_i = 1;
    51.         enable_SORT16_max1 = 1;
    53.         // Input array vector to sort. 
    54.         // Increase the number of elements based on ELEMENTS parameter
    55.         in ={   8'd28,  8'd23,  8'd24,  8'd16,  8'd11,  8'd25,  8'd29,  8'd1,
    56.                 8'd10,  8'd32,  8'd21,  8'd2,   8'd27,  8'd31,  8'd3,   8'd30,
    57.                 8'd15,  8'd13,  8'd0,   8'd8,   8'd5,   8'd18,  8'd22,  8'd26,
    58.                 8'd4,   8'd6,   8'd9,   8'd19,  8'd20,  8'd7,   8'd14,  8'd17
    59.             };
    61.         #(`clk_period);
    62.         en_i = 0;
    64.         #(`clk_period*10000);
    65.         $display("Input array:");
    66.         for(i=0;i
    67.         $write(in[i*BITWIDTH +: 8]);
    69.         $display("\nOutput sorted array:");
    70.         for(i=0;i
    71.         $write(out[i*BITWIDTH +: 8]);
    73.         $display("\ndone %d", done_o);
    75.         $finish;
    76.     end
    78. endmodule

    四、堆排序

    以下是堆排序的.v代码：

    1. // reference: https://zhuanlan.zhihu.com/p/32166363
    2.  
    3. `timescale 1ns / 1ps
    4. module sort_heap
    5. #(
    6. 	parameter addr_width = 5,
    7. 	parameter data_width = 8
    8. )
    9. (
    10. 	input clk,
    11. 	input rst_n,
    12. 	input en,
    13. 	input clr,
    14. 	output reg done,
    15. 	
    16. 	input [addr_width - 1:0] parent,
    17. 	input [addr_width - 1:0] length,
    18. 	
    19. 	output reg wea,
    20. 	output reg [ addr_width - 1:0 ] addra,
    21. 	output reg [ data_width - 1:0 ] data_we,
    22. 	input      [ data_width - 1:0 ] data_re	
    23. );
    24.  
    25. reg [data_width - 1:0] temp;
    26. reg [addr_width :0] parent_r;//attention: For recognize the parent, we must expand data width of it
    27. reg [addr_width :0] child_r;
    28. reg [addr_width :0] length_r;
    29.  
    30. parameter IDLE    = 6'b000001;
    31. parameter BEGINA   = 6'b000010;
    32. parameter GET     = 6'b000100;
    33. parameter COMPARE = 6'b001000;
    34. parameter WRITE   = 6'b010000;
    35. parameter COMPLETE= 6'b100000;
    36.  
    37.  
    38. reg [5:0] state;
    39. reg [5:0] next_state;
    40. reg [7:0] cnt;
    41. reg [data_width - 1:0] child_compare;
    42. always@(posedge clk or negedge rst_n)
    43. begin
    44. 	if(!rst_n) begin state <= IDLE; end
    45. 	else       begin state <= next_state; end
    46. end
    47.  
    48. always@(*)
    49. begin
    50. 	case(state)
    51. 		IDLE: begin 
    52. 					if(en) begin next_state = BEGINA; end
    53. 					else   begin next_state = IDLE;  end
    54. 				end
    55. 		BEGINA:begin
    56. 					if(cnt == 8'd2)  begin next_state = GET; end
    57. 					else             begin next_state = BEGINA; end
    58. 				end
    59. 		GET:  begin
    60. 					if(child_r >= length_r) begin next_state = COMPLETE; end
    61. 					else if(cnt == 8'd4)    begin next_state = COMPARE; end
    62. 					else                    begin next_state = GET; end
    63. 				end
    64. 		COMPARE: begin
    65. 						if(temp >= child_compare) begin next_state = COMPLETE; end
    66. 						else                      begin next_state = WRITE;    end
    67. 				   end
    68. 		WRITE:   begin
    69. 						if(cnt == 8'd1) begin next_state = GET; end
    70. 						else            begin next_state = WRITE; end
    71. 					end
    72. 		COMPLETE:begin
    73. 						if(clr) begin next_state = IDLE; end
    74. 						else    begin next_state = COMPLETE; end
    75. 					end
    76. 	endcase
    77. end
    79. reg [data_width - 1:0] child_R;
    80. reg [data_width - 1:0] child_L;
    81. always@(posedge clk or negedge rst_n)
    82. begin
    83. 	if(!rst_n) begin done <= 1'b0; end
    84. 	else
    85. 		begin
    86. 			case(state)
    87. 				IDLE: begin
    88. 							parent_r <= {1'b0, parent};
    89. 							length_r <= {1'b0, length};
    90. 							child_r  <= 2*parent + 1'b1;
    91. 							cnt <= 8'd0; child_R <= 0; child_L <= 0;
    92. 							done <= 1'b0;
    93. 						end
    94. 				BEGINA:begin
    95. 							if(cnt == 8'd0)      begin addra <= parent_r; cnt <= cnt + 1'b1; end 
    96. 							else if(cnt == 8'd2) begin temp <= data_re; cnt <= 1'b0; end
    97. 							else                 begin cnt <= cnt + 1'b1; end
    98. 						end
    99. 				GET:  begin
    100. 							if(child_r >= length_r) begin addra <= addra; end
    101. 							else 
    102. 								begin
    103. 									if(cnt == 8'd0)      begin addra <= child_r; cnt <= cnt + 1'b1; end
    104. 									else if(cnt == 8'd1) begin addra <= child_r + 1'b1; cnt <= cnt + 1'b1; end
    105. 									else if(cnt == 8'd2) begin child_L <= data_re; cnt <= cnt + 1'b1; end
    106. 									else if(cnt == 8'd3) begin child_R <= data_re; cnt <= cnt + 1'b1; end
    107. 									else if(cnt == 8'd4)
    108. 										begin
    109. 											if( (child_r + 1'b1 < length_r) && (child_R > child_L) ) 
    110. 												begin 
    111. 													child_r <= child_r + 1'b1; 
    112. 													child_compare <= child_R;
    113. 												end
    114. 											else 
    115. 												begin 
    116. 													child_r <= child_r; 
    117. 													child_compare <= child_L;
    118. 												end
    119. 											cnt <= 8'd0;
    120. 										end
    121. 									else begin cnt <= cnt + 1'b1; end
    122. 							end
    123. 						end
    124. 				COMPARE: begin end
    125. 				WRITE: begin
    126. 							 if(cnt == 8'd0) begin 
    127. 														addra <= parent_r; wea <= 1'b1; 
    128. 														data_we <= child_compare; cnt <= cnt + 1'b1; 
    129. 												  end
    130. 							 else if(cnt == 8'd1) begin 
    131. 															 wea <= 1'b0; cnt <= 8'd0;
    132. 															 parent_r <= child_r;
    133. 															 child_r <= child_r*2 + 1'b1; 
    134. 														 end	
    135. 							 else                 begin cnt <= cnt; end
    136. 						 end	
    137. 				COMPLETE: begin		 
    138. 								 if(cnt == 8'd0) begin 
    139. 															wea <= 1'b1; addra <= parent_r; 
    140. 															data_we <= temp; cnt <= cnt + 1'b1;
    141. 														end
    142. 								 else if(cnt == 8'd1)
    143. 										begin 
    144. 											wea <= 1'b0;
    145. 											cnt <= cnt + 1'b1;
    146. 											done <= 1'b1;
    147. 										end
    148. 								 else if(cnt == 8'd2)
    149. 										begin
    150. 											done <= 1'b0;
    151. 											cnt <= 8'd2;
    152. 										end
    153. 							 end
    154. 				
    155. 			endcase
    156. 		end	
    157. end
    159. endmodule

    以下是堆排序的top文件（注意事先在vivado的库内例化ROM，并载入coe，网上有大量关于coe的语法，我这边也贴上）

    1. `timescale 1ns / 1ps
    2.  
    3. module sort_heap_top
    4. #(
    5. 	parameter addr_width = 5,   //stack address width
    6. 	parameter data_width = 8,   //stack data width
    7. 	parameter stack_deepth = 31 //stack deepth
    8. )
    9. (
    10. 	input clk,
    11. 	input rst_n
    12. );
    13.  
    14. reg en;                           //initial module input: Enable initial process
    15. reg clr;				                //initial module input: Reset initial process
    16. wire done;                        //initial module output: One initial process have done
    17. reg [addr_width - 1:0] parent;    //initial module input: Parent
    18. reg [addr_width - 1:0] length;    //initial module input: Length of list
    19.  
    20. wire wea;                         //RAM module input: write enable
    21. wire [addr_width - 1:0] addra;	 //RAM module input: write/read address
    22. wire [data_width - 1:0] data_we;  //RAM module input: write data
    23. wire [data_width - 1:0] data_re;	 //RAM module output: read data
    24.  
    25. parameter BEGINA   = 9'b0_0000_0001;//stage 1: stack initial
    26. parameter RANK    = 9'b0_0000_0010;
    27. parameter FINISH  = 9'b0_0000_0100;
    28. parameter DONE    = 9'b0_0000_1000;
    29.  
    30. parameter READ    = 9'b0_0001_0000;//stage 2: rank of stack
    31. parameter WRITE   = 9'b0_0010_0000;
    32. parameter RANK_2  = 9'b0_0100_0000;
    33. parameter FINISH_2= 9'b0_1000_0000;
    34. parameter DONE_2  = 9'b1_0000_0000;
    36. reg [addr_width - 1:0] cnt;           //counter in FSM stage 1/2
    37. reg [addr_width - 1:0] cnt2;          //counter in FSM stage 2
    38. reg [8:0] state;                      //FSM state
    39. reg [8:0] next_state;                 //FSM next state
    40. reg [addr_width - 1:0] addr;          //stack inital process read RAM address
    41. reg initial_done;                     //stack initial done
    42. reg [data_width - 1:0] list_i;        //RANK process reg
    43. reg [data_width - 1:0] list_0;		  //RANK process reg
    44. reg wea_FSM;                          //wea signal from FSM
    45. reg [data_width - 1:0] data_we_FSM;   //write data form FSM
    47. //FSM stage 1: state transform
    48. always@(posedge clk or negedge rst_n)
    49. begin
    50. 	if(!rst_n) begin state <= BEGINA; end
    51. 	else       begin state <= next_state; end
    52. end
    54. //FSM stage 2: state change
    55. always@(*)
    56. begin
    57. 	case(state)
    58. 		BEGINA: begin next_state = RANK; end //stack initial process begin
    59. 		RANK:  begin
    60. 					 if(done) begin next_state = FINISH; end
    61. 					 else     begin next_state = RANK; end
    62. 				 end
    63. 		FINISH:begin 
    64. 					if(addr == stack_deepth - 1 & cnt != {addr_width{1'b1}})       begin next_state = BEGINA; end
    65. 					else if(addr == stack_deepth - 1 & cnt == {addr_width{1'b1}} ) begin next_state = DONE; end
    66. 					else                                                           begin next_state = FINISH; end
    67. 				 end
    68. 		DONE:  begin next_state = READ; end //stack initial process have done
    69. 		
    70. 		
    71. 		READ: begin                         //stack rank process begin
    72. 					if(cnt == 3) begin next_state = WRITE; end
    73. 					else         begin next_state = READ; end
    74. 				end
    75. 		WRITE:begin
    76. 					if(cnt == 2) begin next_state = RANK_2; end
    77. 					else         begin next_state = WRITE; end
    78. 				end
    79. 		RANK_2:begin
    80. 					 if(done) begin next_state = FINISH_2; end
    81. 					 else     begin next_state = RANK_2; end
    82. 				 end
    83. 		FINISH_2:begin
    84. 						if(addr == stack_deepth - 1 & cnt2 != 0)      begin next_state = READ; end
    85. 						else if(addr == stack_deepth - 1 & cnt2 == 0) begin next_state = DONE_2; end
    86. 						else                                          begin next_state = FINISH_2; end
    87. 					end
    88. 		DONE_2:begin next_state = DONE_2; end//stack rank process done
    89. 	endcase
    90. end
    92. //FSM stage 3: state output
    93. always@(posedge clk or negedge rst_n)
    94. begin
    95. 	if(!rst_n)  begin cnt <= stack_deepth/2; addr <= {addr_width{1'b1}}; initial_done <= 1'b0; wea_FSM <= 1'b0; end
    96. 	else 
    97. 		begin
    98. 			case(state)
    99. 				BEGINA: begin                           //stack initial begin
    100. 							en <= 1'b1;
    101. 							clr <= 1'b0;
    102. 							parent <= cnt;
    103. 							length  <= stack_deepth;
    104. 						 end
    105. 				RANK:  begin
    106. 							clr <= 1'b0;
    107. 						   if(done) begin cnt <= cnt - 1'b1; clr <= 1'b1; en <= 1'b0; addr <= 4'd0; end
    108. 						 end
    109. 				FINISH:begin clr <= 1'b0; addr <= addr + 1'b1; end
    110. 				DONE:  begin 
    111. 								initial_done <= 1'b1;     //stack initial have done
    112. 								cnt2 <= stack_deepth - 1;
    113. 								cnt  <= 0;
    114. 						 end 
    115.  
    116.  
    117. 			   READ: begin                           //stack rank process begin
    118. 							if(cnt == 0)      begin addr <= 0;         cnt <= cnt + 1'b1; end
    119. 							else if(cnt == 1) begin addr <= cnt2;      cnt <= cnt + 1'b1; end
    120. 							else if(cnt == 2) begin list_0 <= data_re; cnt <= cnt + 1'b1; end
    121. 							else if(cnt == 3) begin list_i <= data_re; cnt <= 0; end
    122. 							else              begin cnt <= cnt; end						
    123. 						end
    124. 				WRITE:begin
    125. 							if(cnt == 0)     begin 
    126. 														wea_FSM <= 1'b1;
    127. 														addr <= 0; data_we_FSM <= list_i;
    128. 														cnt <= cnt + 1'b1;
    129. 												    end
    130. 							else if(cnt == 1) begin
    131. 													   wea_FSM <= 1'b1;
    132. 														addr <= cnt2; data_we_FSM <= list_0;
    133. 														cnt <= cnt + 1'b1;
    134. 													end
    135. 							else if(cnt == 2) begin wea_FSM <= 1'b0; cnt <= 0; parent <= 0; length <= cnt2; en <= 1'b1; end
    136. 							else              begin cnt <= cnt; end
    137. 						end
    138. 				RANK_2:begin
    139. 							 if(done) begin cnt2 <= cnt2 - 1'b1; clr <= 1'b1; en <= 1'b0; addr <= 0; end
    140. 						 end
    141. 				FINISH_2:begin
    142. 								clr <= 1'b0; addr <= addr + 1'b1;
    143. 							end
    144. 			endcase
    145. 		end
    146. end
    147.  
    148. wire wea_initial;
    149. wire [data_width - 1:0] data_we_initial;
    150. //stack initial process
    151. sort_heap U1
    152. (
    153. 	.clk(clk),
    154. 	.rst_n(rst_n),
    155. 	.en(en),
    156. 	.clr(clr),
    157. 	.done(done),
    158. 	
    159. 	.parent(parent),
    160. 	.length(length),
    161. 	
    162. 	.wea(wea_initial),
    163. 	.addra(addra),
    164. 	.data_we(data_we_initial),
    165. 	.data_re(data_re)	
    166. );
    167.  
    168. wire [addr_width - 1:0] RAM_addr;
    169. assign wea = (state == WRITE) ? wea_FSM:wea_initial;
    170. assign RAM_addr = (state == FINISH || state == READ || state == WRITE || state == FINISH_2) ? addr:addra;
    171. assign data_we = (state == WRITE) ? data_we_FSM:data_we_initial;
    172. //RAM module 
    173. blk_mem_gen_0 RAM1
    174. (
    175.   .clka(clk),
    176.   .wea(wea),
    177.   .addra(RAM_addr),
    178.   .dina(data_we),
    179.   .douta(data_re)
    180. );
    181.  
    182. endmodule

    对应的coe文件如下：

    1. ;分号后的代码都被认为是注释内容
    2. memory_initialization_radix=10;
    3. memory_initialization_vector=
    4. 1,
    5. 3,
    6. 4,
    7. 5,
    8. 2,
    9. 6,
    10. 9,
    11. 7,
    12. 8,
    13. 0,
    14. 11,
    15. 15,
    16. 13,
    17. 19,
    18. 20,
    19. 16,
    20. 12,
    21. 10,
    22. 14,
    23. 11,
    24. 25,
    25. 21,
    26. 23,
    27. 22,
    28. 18,
    29. 27,
    30. 36,
    31. 29,
    32. 17,
    33. 24,
    34. 26,
    35. 30;

     以下为对应的testbench：

    1. `define clk_period 20
    3. module sort_hep_top_tb
    4. ();
    6. reg clk;
    7. reg rst_n;
    9. initial begin
    10.     clk = 1'b1;
    11. end
    13. always #(`clk_period/2) begin
    14.     clk = ~clk;
    15. end
    16.  
    17. initial begin
    18.     rst_n = 0;
    19.  
    20.     #(`clk_period);
    21.     rst_n = 1;
    22.  
    23.     #(`clk_period*100000);
    24.  
    25.     $finish;
    26. end
    27.  
    28. sort_heap_top sort_heap_top_u(
    29. 	clk,
    30. 	rst_n
    31. );
    32.  
    33. endmodule

    五、资源占用和延时对比

    直接贴图表示，不多废话！

  • 相关阅读:
    【mysql】--记一次delete删除语句使用别名的坑
    HBRD-212/5电源监视继电器
    [附源码]java毕业设计医学季节性疾病筛查系统
    Vue3 + Nodejs 实战 ，文件上传项目--大文件分片上传+断点续传
    HttpServletResponse HttpServletRequest
    C++ 逻辑运算符
    【21天Python进阶学习挑战赛】[day3]json标准库大总结
    定时任务cron
    nginx服务中使用用户认证功能，对Web后台url进行用户验证【加一层认证】
    HTTP 到 HTTPS 再到 HSTS 的转变
  • 原文地址：https://blog.csdn.net/weixin_41029027/article/details/138925616