Velocity Reviews > VHDL > implementing sorting algorithm

# implementing sorting algorithm

sigithidayat@gmail.com
Guest
Posts: n/a

 05-05-2008
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 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( <= 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(&data(7)&data(6)&data(5)&data(4)&data(3)&da ta(2)&data(1);
end a;
============================

I can't fix it, any advise??

Sorry english is not my native language..

thanks,
Sigit Hidayat

jeppe
Senior Member
Join Date: Mar 2008
Location: Denmark
Posts: 348

 05-05-2008
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
Guest
Posts: n/a

 05-05-2008
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"

Mike Treseler
Guest
Posts: n/a

 05-05-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> 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
Guest
Posts: n/a

 05-06-2008
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?

(E-Mail Removed) wrote:
> 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 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( <= 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(&data(7)&data(6)&data(5)&data(4)&data(3)&da ta(2)&data(1);
> end a;
> ============================
>
> I can't fix it, any advise??
>
> Sorry english is not my native language..
>
>
> thanks,
> Sigit Hidayat

Aiken
Guest
Posts: n/a

 05-06-2008
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)

On May 5, 12:46*am, (E-Mail Removed) wrote:
> 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 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( <= 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(&data(7)&data(6)&data(5)&data(4)&data(3)&da ta(2)&data(1);
> end a;
> ============================
>
> I can't fix it, any advise??
>
> Sorry english is not my native language..
>
> thanks,
> Sigit Hidayat