FPGA Design Bubble Sort

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! ! ! ! !

Tags: Algorithm FPGA hardware

Posted by tryin_to_learn on Sun, 15 Jan 2023 15:02:24 +0300