Sorting Algorithm on an FPGA

Status
Not open for further replies.
T

TrickyDicky

Advanced Member level 7
Joined
Jun 7, 2010
Messages
7,110
Helped
2,081
Reputation
4,181
Reaction score
2,048
Trophy points
1,393
Activity points
39,769
Does anyone have any experience with doing sorting on FPGAs?
Anything else to consider other than a simple bubble sort?

Im going to need to sort up to 25 values (fixed at 10 or 25) to find the median. (and as this is video processing, thats a lot of sorts to do!)

Unfortunatly I dont have a lot of spare resources, and it has to be done on a Stratix 1 EP1S25.

Isnt it great when the algorithms guys come up with a "simple" solution!
 

I wrote such sorting code a couple of months ago,
checked in a simulator, not in any hardware,
may be you will find the idea useful;
Code: 
module sorter
(
    input             clk, reset,
    input      [23:0] data,
    input      [ 3:0] read,

    output reg [23:0] out
);

reg [23:0] reg_file[15:0];
reg [15:0] index/*synthesis direct_enable*/;
reg [15:1] switch;

integer i;

always @(*) for (i=0; i<16; i=i+1)
               index[i] <= ( reg_file[i] > data );
               //clock enable for reg_file registers
               
always @(*) for (i=1; i<16; i=i+1)
               switch[i] <= index[i]&!index[i-1];
            //multiplexer switch at the inputs of reg_files

always @(posedge clk or posedge reset)
      if      ( reset )    reg_file[0] <= 24'hFFFFFF;
      else if ( index[0] ) reg_file[0] <= data;
      else                 reg_file[0] <= reg_file[0];

always @(posedge clk or posedge reset)
   if      ( reset )
      for ( i=1; i<16; i=i+1 )
         reg_file[i] <= 24'hFFFFFF;

   else
      for ( i=1; i<16; i=i+1 )
         if ( index[i] )
            if ( switch[i] ) reg_file[i] <= data;
            else             reg_file[i] <= reg_file[i-1];

   else                     reg_file[i] <= reg_file[i];

always @(posedge clk)
    out <= reg_file[read];

endmodule
---
have fun
 

also, median isn't the same as sorting. You only care about finding the middle sample, not the ordering of other samples that aren't the middle sample. For things like bubble sort, this would mean you would stop after half-finishing the sort. not a tremendous savings there, but you get the idea.

as a second example of an O(N) method:
1.) compare value N to all of the other N-1 values.
2.) count the number of values (greater, less, etc...)
3.) stop once you find a suitable median

a simple way to improve this would be to use the information from the bitcount to determine if it makes sense to check the next value. eg, if there are only 3 values less than the current, and the next value is less than the current, then there is no reason to even attempt that check. (faster speed, but more resources)

area permitting, you can also move to, say 36 compares to determine a 4x4 block of medians at a time (as there is overlap)

edit -- and by O(N), I guess I was assuming the "compare to N-1" to be done in parallel. Really, the algorithm probably isn't the best.
 

**broken link removed** has a nice overview of a couple of sort based algo's for finding the median.

Personally, I'd try to get my hands on some of the typical data your find-the-median module will have to process. Then plug them into these algorithms, and see which one gives the best results (in number of operations), and implement that. Looks like Wirth or quick select are candidates. No extra memory needed besides the one you already have. And as permute suggested, you can always instantiate several of these find-the-median units and have them work in parallel, depending on how much resources you have left for this.

I took a quick look at the **broken link removed**, and I'd say that looks doable...
 

There are lot of algo given in the wiki with their time complexity and memory usage.
Sorting algorithm - Wikipedia, the free encyclopedia

You can select one of them based on the amount of resources left to you. But minimum number of comparisons you can get out of any algo is (n log n). This is assuming that your data is random.
 

vipinlal said:
This is assuming that your data is random.
Click to expand...

This point is actually the biggest one, performance wise... Sounds like TrickyDicky got this part of the project with a "look, it's data, and it's random. good luck". If that is the case it might be worthwhile to check and see if it's really random. If it's not really all that random you might be able to exploit that.
 

Data is video, so in the range 0-255 (8 bit). Also, some values may have to be ignored, so it could be median of any number of values, so cannot always be the central value.

Ive found a couple of papers and the median filter itself is pretty cheap, its the line delays and the "ignore" mask that will eat up the fairly limited available memory.
 

TrickyDicky said:
Ive found a couple of papers and the median filter itself is pretty cheap, its the line delays and the "ignore" mask that will eat up the fairly limited available memory.
Click to expand...

Out of general interest, what median filter for fpga implementation did you decide on using? I don't need median stuff right now, but my keen future feature senses are tingling. Best be prepared...
 

Attachments

  • module05.pdf
    250.7 KB · Views: 123

Status
Not open for further replies.

Similar threads

Menu
Log in
Register
Cookies are required to use this site. You must accept them to continue using the site. Learn more…