Forum Discussion

mbran15's avatar
mbran15
Icon for New Contributor rankNew Contributor
6 years ago

can i use quick sorting in HDL(Verilog or VHDL)?

module sort_ex ( clk, rst, out);
 
parameter SIZE = 10;
 
input	clk, rst;
output	reg	[6:0]out;
 
reg	set_end, loop_check, loop_on1, loop_on2, loop_on3;
reg	[8:0] arr [SIZE-1:0];
reg	[8:0] temp;
reg	[8:0] pivot;
reg	[9:0] stack_num;
 
integer	 stack [SIZE+2:0];
integer   low, high, cnt, first, last, seed, i, loop_temp;
 
 
/*initial begin
seed = 6;
for(i=0; i<SIZE; i=i+1) 
	arr[i] = $random(seed);
end
*/
 
initial begin
arr[0] = 9;	arr[1] = 8;	arr[2] = 7;	arr[3] = 6;	arr[4] = 5;
arr[5] = 4;	arr[6] = 3;	arr[7] = 2;	arr[8] = 1;	arr[9] = 0;
end
 
 
always @ (posedge clk) begin
if(rst) begin
	stack_num <= 0;
	set_end <= 0;
	first <= 0;
	last <= SIZE-1;
	stack[stack_num] <= last;
	stack_num <= stack_num + 1'b1;
	stack[stack_num] <= first;
	stack_num <= stack_num + 1'b1;
	pivot <= 0;
	cnt <= 0;
	loop_check <= 1'b0;
	loop_on1 <= 1'b0;
	loop_on2 <= 1'b0;
	loop_on3 <= 1'b0;
	end
else
	if(!set_end) begin
		loop_check <= 1'b0;
	while((loop_check == 0) && (stack_num != 0)) begin
		stack_num <= stack_num - 1'b1;
		first <= stack[stack_num];
		stack_num <= stack_num - 1'b1;
		last  <= stack[stack_num];
		if((last - first + 1) > 1) begin
			pivot = arr[last];
			low <= first - 1;
			high <= last;
			//while(low < high) begin
			
			for(cnt = 0; cnt < 10; cnt=cnt+1) 
			if(loop_on3 == 0) begin
			
				/*while(arr[low+1] < pivot)
					low = low + 1;
				low = low + 1;*/
 
				for(low=low; low<last+1; low=low+1) begin
					if((arr[low+1] >= pivot)&&(loop_on1==0)) begin
						loop_temp <= low+1;
						loop_on1 <= 1;
					end
				end
 
				low <= loop_temp;
				loop_on1 <= 1;
 
				/*while(arr[high-1] > pivot)
					high = high - 1;
				high = high - 1;*/
				
				for(high=high; high > first-1; high=high-1) begin
					if((arr[high-1] <= pivot) && (loop_on2 == 0)) begin
						loop_temp <= high-1;
						loop_on2 <= 1;
					end
				end
				high <= loop_temp;
				loop_on2 <= 1;
				
				
				if(low < high)  begin
					temp <= arr[low];
					arr[low] <= arr[high];
					arr[high] <= temp;
				end
				
				if(low >= high) loop_on3 <= 1;
			end
			
			temp <= arr[low];
			arr[low] <= arr[last];
			arr[last] <= temp;
			stack[stack_num] <= last;
			stack[stack_num+1] <= low + 1;
			stack[stack_num+2] <= low - 1;
			stack[stack_num+3] <= first;
			stack_num <= stack_num + 4;
			loop_check <= 1;
		end
	if(stack_num == 0)
		set_end <= 1;
	end
	end
end
 
 
endmodule
		

i want to program quick sorting in Verilog.

this code is compiled in ModelSim, but in quartus, it makes a compilation stuck.

i know Hardware language is different from C/C++...

but i don't know how program quick sorting in Verilog.

i can't find any information in Google..

someone helps me how program the sorting module in Verilog.

4 Replies

  • ak6dn's avatar
    ak6dn
    Icon for Regular Contributor rankRegular Contributor

    You are writing your verilog code thinking like a sequential C programmer. This code is NOT going to work the way you expect it to:

    always @ (posedge clk) begin
    if(rst) begin
    	stack_num <= 0;
    	set_end <= 0;
    	first <= 0;
    	last <= SIZE-1;
    	stack[stack_num] <= last;
    	stack_num <= stack_num + 1'b1;
    	stack[stack_num] <= first;
    	stack_num <= stack_num + 1'b1;
    	pivot <= 0;
    	cnt <= 0;
    	loop_check <= 1'b0;
    	loop_on1 <= 1'b0;
    	loop_on2 <= 1'b0;
    	loop_on3 <= 1'b0;
    	end
    else

    Lines 5 thru 10 in particular are expecting to use the result of a computation in the next line (or so) and that is NOT how the non-blocking '<=' assignment works. It will evaluate the RHS based on current values, then save the result until the trigger event (enclosing posedge CLK with RST set) and then assign the result to the LHS. I can guarantee this is not what you are expecting.

    You need to go and get a good verilog reference tex.t to understand blocking vs non-blocking assignment, event driven simulation, and the synthesis subset of the verilog language.

    It should certainly be possible to code a quicksort module in verilog operating on a memory structure, but this is not going to work as written.

    • mbran15's avatar
      mbran15
      Icon for New Contributor rankNew Contributor

      sorry, i show the wrong code.

      in my code, every non-blocking '<=' was blocking '='.

      i just wrote my code thinking like C.

      but if the non-blocking is blocking, i think the code is sequence code. i don't know why didnt operate.

  • ak6dn's avatar
    ak6dn
    Icon for Regular Contributor rankRegular Contributor

    Well, even beyond the blocking/non-blocking assignment issue, using constructs like 'for' and 'while' are going to produce non-synthesizable code.

    Ok for behavioral simulation, not so much for synthesis.