implementing sorting algorithm

Guest
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
 
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;
Click to expand...
won't work as you expect. Find a section about "signals vs. variables"
in your favourite VHDL reference/textbook.
 
sigithidayat@gmail.com wrote:
I have an assignment to make vhdl code for implementing bubble sort
algorithm and I got problem with it, since this language
Click to expand...
That is a very silly problem for vhdl synthesis.
I would write the code as a function rather than an entity.

-- Mike Treseler
 
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?


sigithida...@gmail.com 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 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
Click to expand...
 
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, sigithida...@gmail.com 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 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
Click to expand...
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top