inputs for merge-sort

Discussion in 'VHDL' started by vizziee@gmail.com, Mar 31, 2005.

  1. Guest

    Hi All,

    I am looking for a concurrent implementation of merge-sort wherein two
    sorted arrays (with same number of elements) are to be merged in a
    single sorted array.

    I tried using generate statement to form an insertion vector for final
    implementation. But it is not working.

    Is it possible to use generate statement to form two arrays which use
    (i-1)th element values of each other (ie array 1 uses array2 values and
    vice versa) to compute ith element value?

    If anyone has inputs on merge-sort (parallel implementation) in VHDL,
    plz. help. I have written a skeletal code (but is defective with the
    problems I just discussed) and will be interested in discussing that.

    KVM.
     
    , Mar 31, 2005
    #1
    1. Advertising

  2. On 30 Mar 2005 21:44:06 -0800, wrote:

    >I am looking for a concurrent implementation of merge-sort wherein two
    >sorted arrays (with same number of elements) are to be merged in a
    >single sorted array.


    If by "concurrent" you mean single-cycle with no iteration, then
    I think you need rather a lot of comparators and other logic.

    >I tried using generate statement to form an insertion vector for final
    >implementation. But it is not working.


    .... which doesn't help us much ... what does "not working" mean?

    >Is it possible to use generate statement to form two arrays which use
    >(i-1)th element values of each other (ie array 1 uses array2 values and
    >vice versa) to compute ith element value?


    Yes, definitely. Especially given that the two arrays are the same
    size. Why not just iterate one generate loop over a common
    array subscript? Maybe you would need to use a nested
    generate-if to deal with any special cases at the beginning
    and end of the arrays.

    >If anyone has inputs on merge-sort (parallel implementation) in VHDL,
    >plz. help. I have written a skeletal code (but is defective with the
    >problems I just discussed) and will be interested in discussing that.


    How about this.... It's parallel, sure enough. The "for" loop
    with its embedded incrementers and comparators will synthesise
    to a frighteningly large amount of logic - I just did a very
    rough trial synthesis run, targeting Virtex-2, and got 605 LUTs
    and a delay of 56ns for the default-sized design (signed 8-bit
    inputs, 5 elements per array). However, I guess you don't want
    an O(2) implementation of an O(1) algorithm, do you?

    Tell us what the architecture of your merge-sorter will be,
    and perhaps we can guide you to a suitable VHDL implementation.
    Meanwhile, you could at least use my code as a reference
    model, to help you build a test fixture.

    I am aware of an architecture that, for input arrays of N elements
    each, needs O(1) magnitude comparators and O(2) multiplexers; it
    exhibits O(1) propagation delay and would be fairly easy to
    code in VHDL. I wonder if you have a better idea? I am
    disappointed that I can't think of a strictly O(1) implementation.

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    package sorter_types is
    subtype word is integer range -128 to 127; -- signed byte
    type word_array is array (natural range <>) of word;
    end;

    use work.sorter_types.all;
    entity merge_sort is
    generic (input_size: positive := 5);
    port (
    inA, inB: in word_array(0 to input_size-1);
    sorted : out word_array(0 to 2*input_size-1)
    );
    end;

    architecture Naive of merge_sort is
    begin
    process (inA, inB)
    variable indexA, indexB: natural range 0 to input_size;
    variable pickB: boolean;
    begin

    indexA := 0;
    indexB := 0;

    for i in sorted'range loop

    -- Decide which list to pick from...
    pickB := FALSE;
    if (indexA = input_size) then
    pickB := TRUE;
    elsif (indexB /= input_size) then
    pickB := inA(indexA) > inB(indexB);
    end if;

    -- Pick
    if pickB then
    sorted(i) <= inB(indexB);
    indexB := indexB + 1;
    else
    sorted(i) <= inA(indexA);
    indexA := indexA + 1;
    end if;

    end loop;

    end process;

    end;

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    --
    Jonathan Bromley, Consultant

    DOULOS - Developing Design Know-how
    VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

    Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
    Tel: +44 (0)1425 471223 mail:
    Fax: +44 (0)1425 471573 Web: http://www.doulos.com

    The contents of this message may contain personal views which
    are not the views of Doulos Ltd., unless specifically stated.
     
    Jonathan Bromley, Mar 31, 2005
    #2
    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. Replies:
    2
    Views:
    4,496
  2. Seth G.

    Merge Sort question

    Seth G., Aug 11, 2003, in forum: Java
    Replies:
    10
    Views:
    1,240
    Jordan Zimmerman
    Aug 15, 2003
  3. Kevin King

    merge sort #of comparisons

    Kevin King, Nov 29, 2003, in forum: C++
    Replies:
    3
    Views:
    786
    Elie Nader
    Nov 29, 2003
  4. rkk
    Replies:
    9
    Views:
    813
    CBFalconer
    Sep 24, 2006
  5. Navin
    Replies:
    1
    Views:
    699
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page