implementing sorting algorithm

[sigithidayat]

I have an assignment to make vhdl code for implementing bubble sort
algorithm and I got problem with it, since this language

is new to me

=========================
bubble sort algorithm

for i in 1 to 8 do
for j in 8 downto i+1 do
if(A[j-1] > A[j])then
swap(A[j-1],A[j])
end if
end for
end for
=========================
my vhdl code

library ieee;

use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;

entity bubblesort is
port(
in0,in1,in2,in3,in4,in5,in6,in7 : in std_logic_vector(3 downto 0);
clk,ena : in std_logic;
output : out std_logic_vector(31 downto 0)
);
end bubblesort;

architecture a of bubblesort is
type data_array is array (1 to 8) of std_logic_vector(3 downto 0);
signal data : data_array;
signal tem_data : std_logic_vector(3 dwonto 0);
begin
data(1) <= in0;
data(2) <= in1;
data(3) <= in2;
data(4) <= in3;
data(5) <= in4;
data(6) <= in5;
data(7) <= in6;
data(8) <= in7;
sorting : process(clk,ena) is
variable i,j : integer;
begin
if(clk'event and clk='1')then
if(ena='1')then
for i in 1 to 8 loop
for j in 8 downto 1 loop
if(j>i)then
k := j-1;
if(data(k) > data(j))then
tem_data <= data(k);
data(k) <= data(j);
data(j) <= tem_data;
end if;
end if;
end for;
end for;
end if;
end if;
end process;
output <=
data(8)&data(7)&data(6)&data(5)&data(4)&data(3)&data(2)&data(1);
end a;
============================

I can't fix it, any advise??

Sorry english is not my native language..


thanks,
Sigit Hidayat

 

[jeppe]

well well
Will this be for simulation only?
Otherwise must you "think in hardware" - you algoritm surely needs a clock signal in connection with a FSM
Jeppe

 

[Enno Lübbers]

Since it's your assignment, you shouldn't expect others to solve it
for you.
Two things to get you started:

1.) In VHDL, loops unroll in space, not in time. That means, your
synthesis tool will try to create logic that does what your for loop
describes without sequentially iterating over the statements inside
the loop. It probably will go for creating a block of logic for every
loop iteration, so that it can exploit the parallelism in the loop.
Since your loops iterations are data dependent, this is going to be
somewhat tricky, large, and slow, if not impossible. Try doing one
compare and swap per clock cycle; that is, try to explicitly code the
sequential execution of the loop.

2.) Since your using signals inside a sequential (i.e. clocked)
process, this:

                tem_data <= data(k);
                data(k) <= data(j);
                data(j) <= tem_data;

won't work as you expect. Find a section about "signals vs. variables"
in your favourite VHDL reference/textbook.

 

[Mike Treseler]

I have an assignment to make vhdl code for implementing bubble sort
algorithm and I got problem with it, since this language

That is a very silly problem for vhdl synthesis.
I would write the code as a function rather than an entity.

-- Mike Treseler

 

[Aiken]

Do you have any more requirement for your assignment?
We cannot help you to do it. But we can give you tips for it.

For my understanding, you need to use pipline to do it?
or use one cycle to do it?

 

[Aiken]

I already try to design one with only 4 byte input.
If it is run on Xilinx V5, it can run near 480Mhz. (using pipeline).

Suggestion for you:
1. Use something (but not your i and j integer) keep track on the
flow.
2. You need to have +7x code(compare with your code in here)
3. Don't have "tem_data" in hardware world. ( We dont' create
something "temp" in hardware)