Quick Sort with FPGA ?

[Uwe]

Hi,

i am looking for information about how to implement a quick sort algorithm
in an FPGA (VHDL or others). Is there someone who has a fast algorithm or
information or every interresting information about this ?
I have to sort 16 bit binary values with a clock of up to 5 MHz.

Thanks for any help and information !!!

Uwe

[Jonathan Bromley]

Uwe wrote:

> i am looking for information about how to implement a quick sort
> algorithm in an FPGA (VHDL or others).

> I have to sort 16 bit binary values with a clock of up to 5 MHz.

How many values do you have to sort? Size does matter :-)

Sanity check on your wording here: do you really mean "QuickSort"
(Hoare's recursive divide-and-conquer sorting algorithm)? If so,
why? QS is very good on sequential processors because it gives
excellent results in the vast majority of cases, but it is
no better than a stupid insertion-sort in certain pathological
situations (notably, and surprisingly, when the data is already
sorted into order!). And it entails a great deal of messy
bookkeeping, which makes it a poor candidate for a parallel
hardware (FPGA) implementation.

If you just want a quick (rapid) sorting algorithm, there is an
interesting algorithm known as "Batcher's parallel method" which
maps nicely on to hardware, and can be pipelined easily. It's
described in Volume 3 of Donald Knuth's wonderful "The Art of
Computer Programming"; it's superbly indexed so I won't try to
give a page reference that might be out-of-date.

Do you get all the values simultaneously? In many applications,
for example median filters, you need the sorted results on every
clock cycle but new data points appear only one per cycle. In
this situation you can usually do some kind of insertion
sorting which is typically much cheaper than trying to sort
*all* the values every clock; all but one of your values
are already sorted and you only have to find out where in the
list the new one should be fitted.

Hope this is some use

Jonathan Bromley
--

[Peter Sels]

Uwe wrote:
> Hi,

>
> i am looking for information about how to implement a quick sort algorithm

> in an FPGA (VHDL or others). Is there someone who has a fast algorithm or
> information or every interresting information about this ?

> I have to sort 16 bit binary values with a clock of up to 5 MHz.
>

> Thanks for any help and information !!!

I have some thingies that do exactly that in VHDL.
16 bit input, parallel purely combinatorial sort, 16 sorted bits as
output.
I have four versions of them actually.
1) Bitonic Sort (recursive, for all n)
2) Batcher Sort (based on odd even merge, recursive, for all n,
fewer comparators than Bitonic, so I think Bitonic is only of
theoretical interest
really)
3) Green Sort, with the up to now optimal 60 comparators
(only works for n=16), depth 10
4) Van Voorhis Sort for n=16, 61 comparators, optimal up to now depth 9
So this last one is the fastest known on earth...

Please tell me which one you want.
min delay -> 4
min area -> 3

PS: A comparator is a AND and a OR gate really.

You can also do a sequential sort (like Quicksort) which might be
smaller
but if you need it al done in one clock cycle go for one of the above.

Could you tell me what kind of application(s) you are using this for?
You'll get it for free, testbench included. Just wondering how much
people would be ready to pay for these things...hmm...

best regards,

Peter
--
======================================================================
Peter Sels === Easics ===
ASIC Design Engineer === VHDL-based ASIC design services ===
mailto:pe...@easics.be ===================================
NEW Tel: +32-16-395 605 Interleuvenlaan 86, B-3001 Leuven, BELGIUM
NEW Fax: +32-16-395 619 http://www.easics.com/peter/