Multiple additions

How fast do you need the result and how fast are these numbers coming in ? You're presenting your problem as if someone is giving you all these 250 numbers in cycle n and wants the sum in cycle n+1. If the numbers are coming one at a time and you need the sum after number

250, the problem is quite different. Please tell us little bit more on your data (speed, format etc).

Many thanks for your response,

Actually the problem is as you said, 250 filters are giving me at time n 250 different values, then i need to get the addition of those 250 values at time n+1, and this new value conforms an input for a comparator. Each data is a 32 bits unsigned integer, which is generated by a lowpass filter at 300MHz, is in fact the impulse response of such a filter.

So your sample frequency is what?? 300MHz??

"blackduck" a écrit dans le message de news: snipped-for-privacy@g14g2000cwa.googlegroups.com...

As you say, carry save adders may be the best way. It is still a lot of logic, and will take some number of FPGAs to do.

You probably won't get them by time n+1, but you can pipeline it so that you can get a new result out every clock cycle. An N bit carry save adder turns three N bit numbers into two N bit numbers. Before you do that, you should be sure that it is significantly faster than the carry chain adder in your FPGA. At 300MHz you might get only one set of adders per pipeline stage, though maybe more. Assuming it is one, each stage reduces the numbers by a factor of (2/3). log(250)/log(1.5)=14 In the end, you should end up with a 40 bit sum, so some of the adders will be 40 bits long. If you can do it with carry chain adders log(250)/log(2)=8, so eight levels of adders.

If the carry chain adders will run at 300MHz, pipelining those is probably the best way to do it. (Given the FFs in each CLB.)

It may take up to 14 clock cycles but you will get one result out each cycle. Find a book with a name similar to "Architecture of Pipelined computers", probably from the 1970's or 1980's, or look up the IBM 360/91 or Cray-1.

-- glen

Aha, but this filter does not output 250 samples every clock, its just 1 sample, isnt it? Otherwise, how will you just handle the transfer of 250x32 = 8000 Bit every 300 MHz clock cycle?? Not even thinking off adding them up in one clock cycle.

Regards Falk

generated

250x32

With a lot of pins? :-)

Alun Harford

You may be limited by how many adders fit in the fpga. If you can fit

250 adders in it (125 ; 62 ; 32 ; 16 ; 8 ; 4 ; 2 ; 1 in stages) and route it all, then you can get the answer in 8 propagation delays of a 32bit add (or 8 cascades). If you need faster you probably need to use merged 4-input adders and similar.

--
	Sander

+++ Out of cheese error +++

300Mhz * 250 * 4B = 300 GB/s. I *SERIOUSLY* doubt that you can get that high bandwidth into a single fpga. It sounds like that you should be looking at a number of FPGA-s, say 8 to do the first stage additions and feed the results to the ninth that then adds their results (the first level fpgas need not necessarily send just one numebr each to the final one, depending on how you have on-chip vs io pin resources).

--
	Sander

+++ Out of cheese error +++