Fast/low area Sorting hardware.

Hi all ,
I wanted to implement a fast and low area sorting algorithm in Verilog
RTL, does anyone have any suggestions?
Any links to IEEE papers, articles are higly welcome...

regards
Deepu John

 

I wanted to sort 48 8bit unsigned numbers

 

[JJ]

Depends on how fast you want it and what the input order usually is.

Do it in C 1st and cost it so that every read and write into data array
is your memory access cost function and every compare done is your hw
compare cost function.

For a 2 input a,b = sort x,y
a,b <= (x<y)? x,y : y,x;

Arrange this into a merge sort should take 24*6*2 clocks using a DP
ram. Thats around 288 clocks worst case. If no swap, you could save
some clocks. If data is always sorted the time can be halved.

Quicksort would be a waste of time & HW design effort here.
Even bubble sorts are ok if you know the data is already mostly in
order most of the time. Sort only as fast as you actually need.

Since your data is also only 8bits wide the other obvious candidate is
counter sorting. Fill an array of 256 counters with 0.
Then scan the 48 inputs and do cntr[data]++; Then scan the cntr list
and for each cntr value emit that index the value no of times. This
will take maybe 256 clocks to 0, 48 clocks to do the ++, then 256
clocks to scan the counts plus 48 more to emit the values. With dual
port you could get around 300 clocks with out using any compares. This
algorithm works very well when you have lots of data inputs with low
precisions, but not so well other way around. 48 inputs is a bit low
for this design.

johnjakson at usa dot com

 

Hi Stephane.
I wanted to sort 48 8bit unsigned numbers

thanks
Deepu

 

[Weng Tianxiang]

Hi,
Here you are for 'carry adder' key word in all patents title field:

PAT. NO. Title
1 5,045,681 Optoelectric ripple carry adder
2 4,931,981 Multi-place ripple-carry adder
3 4,899,305 Manchester carry adder circuit
4 4,839,849 Ripple-carry adder
5 4,704,701 Conditional carry adder for a multibit digital computer
6 4,675,838 Conditional-carry adder for multibit digital computer
7 4,660,165 Pyramid carry adder circuit

 

[Weng Tianxiang]

Stephane,
Can you give a digital example on the median value algorithm or any
references to its original paper.

Thank you.

Weng