UPGRADE YOUR BROWSER

We have detected your current browser version is not the latest one. Xilinx.com uses the latest web technologies to bring you the best online experience possible. Please upgrade to a Xilinx.com supported browser:Chrome, Firefox, Internet Explorer 11, Safari. Thank you!

cancel
Showing results for 
Search instead for 
Did you mean: 
Adventurer
Adventurer
8,590 Views
Registered: ‎11-07-2007

find max, minimal hardware

Hi, I have 49, 18-bit numbers that I want to find the max value.  This is not a sorting problem, I just want to find the max of that group using the least amount of FPGA resources possible.  I currently use a comparator tree. thanks.
0 Kudos
11 Replies
Explorer
Explorer
8,585 Views
Registered: ‎07-27-2009

Re: find max, minimal hardware

You can use memories to reduce the number of comparators if latency if not directly the biggest issue. Maybe you can use shift registers. Hard to say what the most efficient solution would be without knowing how fast it needs to go or how fast these 49 numbers enter the system.

 

Cheers,

Johan

0 Kudos
Adventurer
Adventurer
8,583 Views
Registered: ‎11-07-2007

Re: find max, minimal hardware

latency is not a constraint.  I'm interested in the least amount of hardware no matter how long the operation takes.
0 Kudos
Explorer
Explorer
8,574 Views
Registered: ‎07-27-2009

Re: find max, minimal hardware

I'd go for a sequential implementation with 1 comparison per step, so 48 comparisons spread over 48 clock cycles. If the numbers are all available at different clock cycles, you do a simple counter or FSM that updates the current maximum as soon as a new data item arrives. Further optimizations seem to make little sense, unless this is for some homework project.

 

Cheers,

Johan

0 Kudos
Adventurer
Adventurer
8,568 Views
Registered: ‎11-07-2007

Re: find max, minimal hardware

the 49 numbers are not in memory and are ready at the same time.  should I put them in BRAM and then read them out 1-by-1 or just leave them in registers and compare sequentially?  would that create a giant mux? I'm doing this because I'm running out of room in the FPGA and I'm looking to optimize wherever I can.
0 Kudos
Highlighted
Advisor evgenis1
Advisor
8,564 Views
Registered: ‎12-03-2007

Re: find max, minimal hardware

If your FPGA has DSP48 you can use it in comparator mode.

 

 

OutputLogic 

Tags (1)
0 Kudos
Explorer
Explorer
8,548 Views
Registered: ‎07-27-2009

Re: find max, minimal hardware

I guess that if you put them in a BRAM, you'd still need a mux on the RAM data input, so the net effect would be very limited. Maybe some sort of shift register structure could at least get rid of the muxing logic but that would assume that the numbers won't change for at least 49 cycles.

Dedicated logic such as DSP slices can be used to reduce routing.

 

Good luck!

0 Kudos
Historian
Historian
8,538 Views
Registered: ‎02-25-2008

Re: find max, minimal hardware


mvalvo wrote:
the 49 numbers are not in memory and are ready at the same time.  should I put them in BRAM and then read them out 1-by-1 or just leave them in registers and compare sequentially?  would that create a giant mux? I'm doing this because I'm running out of room in the FPGA and I'm looking to optimize wherever I can.

Does the complexity you're trying to minimize include the mechanism which loads these 49 numbers?

----------------------------Yes, I do this for a living.
0 Kudos
Adventurer
Adventurer
8,536 Views
Registered: ‎11-07-2007

Re: find max, minimal hardware

are you asking if I'm also interested in reducing the hardware to prepare the comparators? if so, then yes.  the 49 numbers are accumulators that take an indeterminate time to complete, but then remain constant for some time.  when they finish accumulating, then I try to find the max value.
0 Kudos
Historian
Historian
8,534 Views
Registered: ‎02-25-2008

Re: find max, minimal hardware


mvalvo wrote:
are you asking if I'm also interested in reducing the hardware to prepare the comparators? if so, then yes.  the 49 numbers are accumulators that take an indeterminate time to complete, but then remain constant for some time.  when they finish accumulating, then I try to find the max value.

Are all 49 accumulator outputs available simultaneously, and each is presented as a parallel word?

If so, then I think perhaps a max_value register, a simple counter from 1 to 49 and a mux selected by the counter will be the smallest implementation.

Obviously you must have some indicator telling you when the 49 values are valid. Use that to clear the maximum and start the counter. On each clock tick when the counter is not at terminal value (49) compare the max with the mux output, and update max as necessary.

----------------------------Yes, I do this for a living.
Explorer
Explorer
3,644 Views
Registered: ‎07-27-2009

Re: find max, minimal hardware

If these accumulators don't update all at once, you could get away with a BRAM structure where the accumulator value is stored in memory and 1,2...N adders update the accumulators. This requires that you know something about the statistics of the accumulator updates. A single port memory would support 1 update per 2 clocks, a dual port 1 update per clock, etc.

 

This architecture would probably show a significant decrease in resources and the memory can be reused to determine the max function or you can update the max on-the-gi whenever a (limited) number of accumulators update.

 

 

Cheers,

Johan

Adventurer
Adventurer
3,642 Views
Registered: ‎11-07-2007

Re: find max, minimal hardware

unfortunately, the accumulators can update at the same time.  I think  I'll try comparing 1 at a time like bassman suggested.
0 Kudos