Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > VHDL > inputs for merge-sort

Reply
Thread Tools

inputs for merge-sort

 
 
vizziee@gmail.com
Guest
Posts: n/a
 
      03-31-2005
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.

 
Reply With Quote
 
 
 
 
Jonathan Bromley
Guest
Posts: n/a
 
      03-31-2005
On 30 Mar 2005 21:44:06 -0800, http://www.velocityreviews.com/forums/(E-Mail Removed) 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:(E-Mail Removed)
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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
google URL-based searchplugins can have *two* inputs as_q= q= Splibbilla Firefox 0 04-17-2005 11:15 PM
ISE problem - multiplier inputs on schematic are not assigned correctly. AndyAtHome VHDL 1 05-25-2004 12:48 PM
R: pullup on inputs Max VHDL 0 09-25-2003 10:46 AM
pullup on inputs Max VHDL 0 09-25-2003 09:49 AM
Coding style to prioritize certain inputs Willem Oosthuizen VHDL 5 09-04-2003 05:17 PM



Advertisments