implementing sorting algorithm

Discussion in 'VHDL' started by sigithidayat@gmail.com, May 5, 2008.

  1. 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
     
    , May 5, 2008
    #1
    1. Advertising

  2. jeppe

    Joined:
    Mar 10, 2008
    Messages:
    348
    Location:
    Denmark
    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
     
    jeppe, May 5, 2008
    #2
    1. Advertising

  3. 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.
     
    Enno Lübbers, May 5, 2008
    #3
  4. 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
     
    Mike Treseler, May 5, 2008
    #4
  5. Aiken Guest

    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?


    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
     
    Aiken, May 6, 2008
    #5
  6. Aiken Guest

    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, 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
     
    Aiken, May 6, 2008
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Johnsy Joseph
    Replies:
    2
    Views:
    1,096
    Brian Drummond
    Oct 29, 2004
  2. Dmitri Zhukov
    Replies:
    2
    Views:
    486
    Kai-Uwe Bux
    Sep 17, 2004
  3. Jef Driesen
    Replies:
    4
    Views:
    400
    red floyd
    Jan 26, 2005
  4. ech0
    Replies:
    5
    Views:
    318
    Colin J. Williams
    Dec 6, 2005
  5. Robo
    Replies:
    4
    Views:
    174
    Peter Hickman
    Dec 15, 2004
Loading...

Share This Page