inputs for merge-sort

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.

vizziee@gmail.com

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