Showing results for

- Intel Community
- FPGAs and Programmable Solutions
- Programmable Devices
- can i use quick sorting in HDL(Verilog or VHDL)?

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Highlighted
##

mbran15

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-09-2019
02:44 AM

385 Views

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

Highlighted
##

Some of C/C++ coding may not be synthesized correctly even though sometime it can compile successfully. Advice you can copy out what error you had in here or search any solution/hint to that error in quartus help https://www.intel.com/content/www/us/en/programmable/quartushelp/18.0/index.htm#msgs/msgs/wsta_launc...

GuaBin_N_Intel

Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-09-2019
06:35 AM

25 Views

Highlighted
##

ak6dn

Valued Contributor II

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-09-2019
10:10 PM

25 Views

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.

Highlighted
##

mbran15

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-10-2019
04:29 AM

25 Views

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.

Highlighted
##

ak6dn

Valued Contributor II

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-11-2019
06:23 AM

25 Views

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.

For more complete information about compiler optimizations, see our Optimization Notice.