1. Write in front
In the front, we have learned the principle of parallel full sorting algorithm and double tone sorting algorithm and the writing of RTL code. In this article, we will continue to learn the classic sorting algorithm - bubble sorting algorithm, learn its principle and its Verilog implementation .
2. The principle of bubble sorting
Bubble Sort is a simple sorting algorithm that repeatedly traverses the input list element by element, compares the current element with the following elements, and exchanges their values according to ascending or descending order. The list is traversed repeatedly from front to back or back to front until no swaps have to be performed during one pass, which means the list is fully sorted. A sequence of length N, the number of traversals of the list is N-1 times. Then, the specific steps can be divided into the following steps:
(1) Compare two adjacent values in sequence from front to back in a sequence, and if the previous value (value one) is greater than the latter value (value two), exchange the two values;
(2) Repeat the operation of step (1) (N-1) times, and the sorting is completed;
Then, for a sequence of length N=5, the sorting process is shown in the figure below.
3. Bubble sort RTL implementation
Then, according to the principle of bubble sorting, we can write the Verilog code for it, as follows. For a sequence of length N, a total of (N-1) comparisons are required for each round of sorting, and a total of (N-1) rounds of sorting are required, so in the code we set the single theory sorting counter cnt_1 and sorting The round number counter cnt_2 is used for counting. If the single round sorting counter cnt_1 reaches N-2, it means that the single round sorting ends and the next round of sorting starts. If the sorting round counter cnt_2 reaches N-2, it means sorting the sequence At the end, output the sorted values and labels. In addition, we can modify the parameter value ASCEND to set whether to sort the sequence in ascending or descending order.
module bubble_sort #( parameter DATA_WIDTH = 8, parameter LABEL_WIDTH = 8, parameter DATA_NUMBER = 8, parameter ASCEND = 1 ) ( clk, rst_n, start, data_unsort, label_unsort, data_sorted, label_sorted, data_valid ); input clk; input rst_n; input start; input [DATA_NUMBER*DATA_WIDTH-1:0] data_unsort; //unsorted values input [DATA_NUMBER*LABEL_WIDTH-1:0] label_unsort; //unsorted tags output reg [DATA_NUMBER*DATA_WIDTH-1:0] data_sorted; //sorted value output reg [DATA_NUMBER*LABEL_WIDTH-1:0] label_sorted; //sorted label output reg data_valid; //Data output valid flag reg [DATA_NUMBER*DATA_WIDTH-1:0] data_temp; reg [DATA_NUMBER*LABEL_WIDTH-1:0] label_temp; reg [2:0] FSM_state; //Sort state machine reg [$clog2(DATA_NUMBER)-1:0] cnt_1; //Single round sort counter reg [$clog2(DATA_NUMBER)-1:0] cnt_2; //sort round counter localparam Initial = 3'b001; //initialization localparam Sort = 3'b010; //to sort localparam Finish = 3'b100; //sort end // state machine always @(posedge clk or negedge rst_n) if(!rst_n) FSM_state <= Initial; else begin case(FSM_state) Initial: begin if(start) FSM_state <= Sort; else FSM_state <= Initial; end Sort: begin if(cnt_2 == DATA_NUMBER-2) FSM_state <= Finish; else FSM_state <= Sort; end Finish: begin FSM_state <= Initial; end default: FSM_state <= Initial; endcase end // Single round sort counter always @(posedge clk or negedge rst_n) if(!rst_n) cnt_1 <= 0; else if(FSM_state == Sort && cnt_1 == DATA_NUMBER-2) cnt_1 <= 0; else if(FSM_state == Sort) cnt_1 <= cnt_1 + 1'b1; else cnt_1 <= 0; // sort round counter always @(posedge clk or negedge rst_n) if(!rst_n) cnt_2 <= 0; else if(FSM_state == Sort && cnt_1 == DATA_NUMBER-2) cnt_2 <= cnt_2 + 1'b1; else if(FSM_state == Sort) cnt_2 <= cnt_2; else cnt_2 <= 0; // Sort Values and Labels always @(posedge clk or negedge rst_n) if(!rst_n) begin data_temp <= 0; label_temp <= 0; end else if(FSM_state == Initial) begin data_temp <= data_unsort; label_temp <= label_unsort; end else if(FSM_state == Sort) begin if(ASCEND == 1'b1) //ascending order if(data_temp[cnt_1*DATA_WIDTH+:DATA_WIDTH] > data_temp[(cnt_1+1)*DATA_WIDTH+:DATA_WIDTH]) begin data_temp[cnt_1*DATA_WIDTH+:DATA_WIDTH] <= data_temp[(cnt_1+1)*DATA_WIDTH+:DATA_WIDTH]; data_temp[(cnt_1+1)*DATA_WIDTH+:DATA_WIDTH] <= data_temp[cnt_1*DATA_WIDTH+:DATA_WIDTH]; label_temp[cnt_1*LABEL_WIDTH+:LABEL_WIDTH] <= label_temp[(cnt_1+1)*LABEL_WIDTH+:LABEL_WIDTH]; label_temp[(cnt_1+1)*LABEL_WIDTH+:LABEL_WIDTH] <= label_temp[cnt_1*LABEL_WIDTH+:LABEL_WIDTH]; end else begin data_temp[cnt_1*DATA_WIDTH+:DATA_WIDTH] <= data_temp[cnt_1*DATA_WIDTH+:DATA_WIDTH]; data_temp[(cnt_1+1)*DATA_WIDTH+:DATA_WIDTH] <= data_temp[(cnt_1+1)*DATA_WIDTH+:DATA_WIDTH]; label_temp[cnt_1*LABEL_WIDTH+:LABEL_WIDTH] <= label_temp[cnt_1*LABEL_WIDTH+:LABEL_WIDTH]; label_temp[(cnt_1+1)*LABEL_WIDTH+:LABEL_WIDTH] <= label_temp[(cnt_1+1)*LABEL_WIDTH+:LABEL_WIDTH]; end else if(ASCEND == 1'b0) //sort descending if(data_temp[cnt_1*DATA_WIDTH+:DATA_WIDTH] < data_temp[(cnt_1+1)*DATA_WIDTH+:DATA_WIDTH]) begin data_temp[cnt_1*DATA_WIDTH+:DATA_WIDTH] <= data_temp[(cnt_1+1)*DATA_WIDTH+:DATA_WIDTH]; data_temp[(cnt_1+1)*DATA_WIDTH+:DATA_WIDTH] <= data_temp[cnt_1*DATA_WIDTH+:DATA_WIDTH]; label_temp[cnt_1*LABEL_WIDTH+:LABEL_WIDTH] <= label_temp[(cnt_1+1)*LABEL_WIDTH+:LABEL_WIDTH]; label_temp[(cnt_1+1)*LABEL_WIDTH+:LABEL_WIDTH] <= label_temp[cnt_1*LABEL_WIDTH+:LABEL_WIDTH]; end else begin data_temp[cnt_1*DATA_WIDTH+:DATA_WIDTH] <= data_temp[cnt_1*DATA_WIDTH+:DATA_WIDTH]; data_temp[(cnt_1+1)*DATA_WIDTH+:DATA_WIDTH] <= data_temp[(cnt_1+1)*DATA_WIDTH+:DATA_WIDTH]; label_temp[cnt_1*LABEL_WIDTH+:LABEL_WIDTH] <= label_temp[cnt_1*LABEL_WIDTH+:LABEL_WIDTH]; label_temp[(cnt_1+1)*LABEL_WIDTH+:LABEL_WIDTH] <= label_temp[(cnt_1+1)*LABEL_WIDTH+:LABEL_WIDTH]; end end else begin data_temp <= data_temp; label_temp <= label_temp; end // Data output valid flag always @(posedge clk or negedge rst_n) if(!rst_n) data_valid <= 1'b0; else if(FSM_state == Finish) data_valid <= 1'b1; else data_valid <= 1'b0; // Sorted data and labels always @(posedge clk or negedge rst_n) if(!rst_n) begin data_sorted <= 0; label_sorted <= 0; end else if(data_valid)begin data_sorted <= data_temp; label_sorted <= label_temp; end else begin data_sorted <= data_sorted; label_sorted <= label_sorted; end endmodule
4. TestBench
Here, we take the sequence length N=8 as an example and write a simple test file as follows. The input sequence is: 9, 3, 15, 10, 11, 8, 4, 5, and the corresponding labels are: 0, 1, 2, 3, 4, 5, 6, 7. Then, the sorted numerical order should be: 3, 4, 5, 8, 9, 10, 11, 15, and the sorted labels should be: 1, 6, 7, 5, 0, 3, 4, 2.
`timescale 1ns/1ns
module tb_bubble_sort();
parameter DATA_WIDTH = 8;
parameter DATA_NUMBER = 8;
parameter LABEL_WIDTH = $clog2(DATA_NUMBER);
parameter ASCEND = 1'b1;
reg clk,rst_n,start;
reg [DATA_WIDTH-1:0] data_unsort [DATA_NUMBER-1:0];
reg [LABEL_WIDTH-1:0] label_unsort [DATA_NUMBER-1:0];
wire [DATA_WIDTH-1:0] data_sorted [DATA_NUMBER-1:0];
wire [LABEL_WIDTH-1:0] label_sorted [DATA_NUMBER-1:0];
wire data_valid;
initial begin
clk = 1'b1;
rst_n = 1'b0;
start <= 0;
#20
rst_n = 1'b1;
data_unsort[0] <= 9;
data_unsort[1] <= 3;
data_unsort[2] <= 15;
data_unsort[3] <= 10;
data_unsort[4] <= 11;
data_unsort[5] <= 8;
data_unsort[6] <= 4;
data_unsort[7] <= 5;
label_unsort[0] <= 0;
label_unsort[1] <= 1;
label_unsort[2] <= 2;
label_unsort[3] <= 3;
label_unsort[4] <= 4;
label_unsort[5] <= 5;
label_unsort[6] <= 6;
label_unsort[7] <= 7;
#40 start <= 1'b1;
#20 start <= 1'b0;
end
always #10 clk = ~clk;
bubble_sort
#(
.DATA_WIDTH(DATA_WIDTH),
.LABEL_WIDTH(LABEL_WIDTH),
.DATA_NUMBER(DATA_NUMBER),
.ASCEND(ASCEND)
)
bubble_sort
(
.clk(clk),
.rst_n(rst_n),
.start(start),
.data_unsort({data_unsort[7],data_unsort[6],data_unsort[5],data_unsort[4],data_unsort[3],data_unsort[2],data_unsort[1],data_unsort[0]}),
.label_unsort({label_unsort[7],label_unsort[6],label_unsort[5],label_unsort[4],label_unsort[3],label_unsort[2],label_unsort[1],label_unsort[0]}),
.data_sorted({data_sorted[7],data_sorted[6],data_sorted[5],data_sorted[4],data_sorted[3],data_sorted[2],data_sorted[1],data_sorted[0]}),
.label_sorted({label_sorted[7],label_sorted[6],label_sorted[5],label_sorted[4],label_sorted[3],label_sorted[2],label_sorted[1],label_sorted[0]}),
.data_valid(data_valid)
);
endmodule
5. Simulation results
Run the simulation program, and the simulation results are as follows. It can be seen that the sorted results are consistent with our theoretical results, and the simulation is passed.
Six, write on the back
In this article, we have learned the principle of the classic sorting algorithm - the bubble sorting algorithm and its Verilog code implementation. Compared with the parallel full sorting algorithm and the double tone sorting algorithm, the bubble sorting algorithm has a higher time complexity. The performance is not good, so it is rarely used in practical applications, and it is mostly used in experiments.
Well, the above are some study notes about implementing bubble sorting in FPGA. If you have any doubts, please feel free to discuss and learn in the comment area! ! ! ! !
