MAC Architectures

"Tim Wescott" <tim@seemywebsite.com> wrote in message 
news:ELSdnRzy6pLQ7svenZ2dnUVZ_sydnZ2d@web-ster.com...
> Jeorg's question on sci.electronics.design for an under $2 DSP chip got me to 
> thinking:
>
> How are 1-cycle multipliers implemented in silicon?  My understanding is that 
> when you go buy a DSP chip a good part of the real estate is taken up by the 
> multiplier, and this is a good part of the reason that DSPs cost so much.  I 
> can't see it being a big gawdaful batch of combinatorial logic that has the 
> multiply rippling through 16 32-bit adders, so I assume there's a big table 
> look up involved, but that's as far as my knowledge extends.

In addition to the single-cycle MAC, there is also all the structure needed to 
keep that MAC busy, i.e. dual busses with single-cycle access to memory.

> Yet the reason that you go shell out all the $$ for a DSP chip is to get a 
> 1-cycle MAC that you have to bury in a few (or several) tens of cycles worth 
> of housekeeping code to set up the pointers, counters, modes &c -- 
> so you never get to multiply numbers in one cycle, really.

True, a fast MAC is most useful when you are doing a bunch of them in a row, 
like for example in a FIR filter.  But a fast multiply is pretty darn useful 
too, and often can be taken advantage of 1 or 2 at a time.

BTW, on a SHARC, the set-up is basically 3 cycles: set-up 2 pointers (typically 
one for data, one for coefs) and initialize your loop counter.  You may need to 
pre-fetch the data too, so that could add another cycle, or could be built into 
the main loop.  Not too bad, though.  It doesn't take too long of a filter, 
matrix, vector op, etc. to start paying dividends.
A idiosyncratic feature of the SHARC is that for fixed point, there is a true 
single-cycle MAC, whereas for floating point, you have a parallel multiply/add 
instruction, and you can't use the result of the multiply in the add.  At first 
glance it seems quite restritive, but in practice it just means one more stage 
of pipelining before you can rip off those single-cycle FIRs.  I'm guessing a 
single-cycle 40-bit floating-point MAC would have been the slowest instruction 
on the chip by a mile, and would have forced a much slower max clock rate.

> How much less silicon would you use if an n-bit multiplier were implemented as 
> an n-stage pipelined device?  If I wanted to implement a 128-tap FIR filter 
> and could live with 160 ticks instead of 140 would the chip be much smaller?

I don't think it would save that much total real estate. I'm basing this on the 
fact that Analog Devices started including two complete multipliers and ALUs in 
all their new SHARCs.  Or maybe with die shrinks, silicon area is not such a big 
deal?  When you can take advantage of the second unit, you can get FIRs in 1/2 
cycle per tap, or parallel operation on a second data stream "for free"--nice!

> Or is the space consumed by the separate data spaces and buses needed to move 
> all the data to and from the MAC?  If you pipelined the multiplier _and_ made 
> it a two- or three- cycle MAC (to allow time to shove data around) could you 
> reduce the chip cost much?  Would the amount of area savings you get allow you 
> to push the clock up enough to still do audio applications for less money?

My guess is that going to a 2-stage multiplier would not allow you to get you 
anywhere near twice the clock frequency.  On most DPSs, it's not just the MAC 
but every other instruction is also single cycle, so unless you can get them all 
to run 2x, you can't double the clock rate.  The MAC is probably the slowest 
path, but I would guess there are a lot of other "close seconds".  I've often 
wanted to see data from a DSP manufacturer on the speed of different 
instructions, just out of curiosity.  It would also allow you to determine if 
you could reliably overclock a chip based on what instructions your application 
used. 

langwadt@ieee.org wrote:

> Tim Wescott skrev:
> 
> 
>>Pramod Subramanyan wrote:
>>
> 
> snip
> 
>>>http://www2.ele.ufes.br/~ailson/digital2/cld/chapter5/chapter05.doc5.html
>>>
>>
>>Interesting.  So that's what they actually do in practice, just copy a
>>page out of a textbook?  Wouldn't the stages of adders really cause a
>>speed hit?  To have your signal ripple through so many stages would
>>require you to slow your clock way down from what it could be otherwise
> 
> 
> afair the delay for the straight forward N*N bit parallel multiplier is
> 
> only around double the delay of a N bit adder, i.e. the longest path in
> the multiplier is lsb to msb plus top to bottom
> 
> 
>>-- it seems an odd way to build a chip who's purpose in life is to be
>>really fast while doing a MAC.
> 
> 
> I think its more likely that they look at different options and find
> the
> smallest that is fast enough ;)
> 
> have a look at http://www.andraka.com/multipli.htm
> 
> 
> snip
> 
> 
>>Yet DSP chips cost tons of money, which disappoints Jeorg who designs
>>for high-volume customers who are _very_ price sensitive.  The question
>>was more a hypothetical "what would Atmel do if Atmel wanted to compete
>>with the dsPIC" than "should I have a custom chip designed for my
>>10-a-year production cycle".
> 
> 
> I'm not sure the size of the multiplier makes a big difference, my
> guess
> is that if you look at the die you would see that most of it is memory
> 
> 
> what price are you looking for?, how much memory?, how fast?
> 
> Not that I will build you one, but I'm curious :)
> 
> -Lasse
> 
The original question was for an under-$2 DSP chip capable of doing 
audio frequency stuff, including FFTs.  I'm not the fellow who asked; it 
just sparked a tangential thought in my head about why there isn't some 
intermediate step on the way to a full-speed DSP.

So I couldn't tell you exactly how much speed and memory, given I don't 
know how often he was considering doing the FFTs, or how many points, etc.

Hey Jeorg!  You listening?  What did you need to do, exactly?

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Peter Alfke wrote:
> Newer FPGAs have lots of fast 18 x 18 multipliers.
> The humble XC4VSX25 has, among other goodies, 128 such multipliers
> running at max 500MHz single-cycle rate.
> The mid-range SX35 has 192, and the top SX55 has 512 such fast 18 x 18
> multipliers each with its associated 48-bit accumulator structure.  We
> invite you to keep that kind of arithmetic performance busy...  No
> wonder these FPGAs can outperform sophisticated and expensive DSP
> chips.

Well, the original question was about $2 DSP's, presumably for
low cost products.  So are there any FPGA's currently available
for $2 or less which include any built-in single-cycle 18 x 18
multipliers, plus enough logic cells to replace the rest of the
functionality of a single low cost DSP?


Thanks.
-- 
rhn A.T nicholson d.O.t C-o-M

Tim Wescott skrev:

snip
> The original question was for an under-$2 DSP chip capable of doing
> audio frequency stuff, including FFTs.  I'm not the fellow who asked; it
> just sparked a tangential thought in my head about why there isn't some
> intermediate step on the way to a full-speed DSP.
>

I never have to buy stuff so I don't know anything about prices, but
philips recently announced  a couple of 70MHz ARM7TDMIs in the 2$
range, it's not DSPs but at 70MHz and one cycle per 8bits of
32*32->64bit multiply it'll do some dsp

-Lasse

langwadt@ieee.org wrote:
> Tim Wescott skrev:
> 
> snip
> 
>>The original question was for an under-$2 DSP chip capable of doing
>>audio frequency stuff, including FFTs.  I'm not the fellow who asked; it
>>just sparked a tangential thought in my head about why there isn't some
>>intermediate step on the way to a full-speed DSP.
>>
> 
> 
> I never have to buy stuff so I don't know anything about prices, but
> philips recently announced  a couple of 70MHz ARM7TDMIs in the 2$
> range, it's not DSPs but at 70MHz and one cycle per 8bits of
> 32*32->64bit multiply it'll do some dsp

  TI have just volume-released their 100MHz FLASH controllers, start at 
sub $5, so not quite a $2 target, but these have FLASH(not ROM) and 
include 12 bit 6Msps ADCs, a 150ps resolution PWM, and CAN bus

150ps PWM is a challenge even for FPGA ....

http://focus.ti.com/docs/pr/pressrelease.jhtml?prelId=sc05231

  The sub $2 Philips devices have quite low code sizes, but they could 
do some 'audio frequency stuff'...


-jg

Tim Wescott wrote:

>> Jeorg's question on sci.electronics.design for an under $2 DSP chip got
>> me to thinking:
>>
>> How are 1-cycle multipliers implemented in silicon?  My understanding is
>> that when you go buy a DSP chip a good part of the real estate is taken
>> up by the multiplier, and this is a good part of the reason that DSPs
>> cost so much.  I can't see it being a big gawdaful batch of
>> combinatorial logic that has the multiply rippling through 16 32-bit
>> adders, so I assume there's a big table look up involved, but that's as
>> far as my knowledge extends.
>>
>> Yet the reason that you go shell out all the $$ for a DSP chip is to get
>> a 1-cycle MAC that you have to bury in a few (or several) tens of cycles
>> worth of housekeeping code to set up the pointers, counters, modes &c --
>> so you never get to multiply numbers in one cycle, really.
>>
>> How much less silicon would you use if an n-bit multiplier were
>> implemented as an n-stage pipelined device?  If I wanted to implement a
>> 128-tap FIR filter and could live with 160 ticks instead of 140 would
>> the chip be much smaller?


If you leave out FFT-based multipliers which are only benefitial for
really large mutliplicands (a few hundred bits) you need to perform
N^2 1-bit additions for a multiplication.
These N^2 1-bit adders can be arranged in different ways called for
example array multipliers or wallace tree multipliers to change the
critical path and the layout. But we proved that they all can be
transformed into each other just by swapping wires around.
http://eis.eit.uni-kl.de/eis/research/publications/papers/iccd04.pdf

The only thing you can do about area is trading off area for delay. You
can forexample reuse the same N adders over N clock cycles.

Pipelining does not save area. But it can increase performance a little.
You can cut the critical path in half by adding N pipeline stages.
(Beware that without pipelining while you perform N additions of N bits
the length of the critical path is only O(N) for all multiplier
architectures achieved by reordering)

The multiplier is a large part of the CPU core, probably the largest in
a DSP, but the area of most processor chips including DSPs is dominated
by caches and other memory like reordering buffers, shadow registers,
TLA buffers, etc.

Kolja Sulimma

Bevan Weiss wrote:
> Getting single cycle high speed multipliers is a very challenging
> prospect, and one which much research is still ongoing.
Actually, if you cannot do full custom circuit optimizations
(e.g. because you do standard cell design or because you are using
LUTs in an FPGA) swapping wires is the only possible structural
optimization. All other multiplier transformations can be reduced to swaps.

An extremely nice property of swapping wires is, that it can be done
after placement. This is such a huge advantage that we were able to beat
sophisticated multiplier generators with a simple greedy algorithm when
applying it after placement:
http://eis.eit.uni-kl.de/eis/research/publications/papers/iccd04.pdf



Kolja Sulimma

On Wed, 19 Oct 2005 09:25:12 -0700, Tim Wescott wrote:

> Jeorg's question on sci.electronics.design for an under $2 DSP chip got 
> me to thinking:
> 
> How are 1-cycle multipliers implemented in silicon?

I don't know how they do it this days, but I do know that with a 
whole shitpot load of adders, you could do it in n propagation delays,
where n is the width of whichever operand you arrange to come in 
sideways. I almost drew a schematic. You have a set of adders as
wide as operand "A", and its inputs are operand "A" and the "latest"
partial product - and its outputs go to another bank of adders whose
other inputs are either "A" again or 0, and so on - the other operand,
"B", would be presented down the side of the array, deciding which
partial products get added to and which don't. The LSB, of course,
gets sent out as "product", and the carry is the MSB of the next
partial product. They form a parallelogram.

I just fired up that Xilinx S/W to see what it's got in the way of
symbols, and it already has a 16-bit adder. With 16 of them, and 256 
AND gates, I could build a 16 x 16 multiplier that would have an 
answer in about 16 or 17 propagation delays. :-)
<Rich fires up  Xilinx ISE...>

OK, it's gonna be a day or so. Please be gentle, it's my first time. :-)

Thanks!
Rich

Kolja Sulimma wrote:
> Bevan Weiss wrote:
>> Getting single cycle high speed multipliers is a very challenging
>> prospect, and one which much research is still ongoing.
> Actually, if you cannot do full custom circuit optimizations
> (e.g. because you do standard cell design or because you are using
> LUTs in an FPGA) swapping wires is the only possible structural
> optimization. All other multiplier transformations can be reduced to swaps.
> 
> An extremely nice property of swapping wires is, that it can be done
> after placement. This is such a huge advantage that we were able to beat
> sophisticated multiplier generators with a simple greedy algorithm when
> applying it after placement:
> http://eis.eit.uni-kl.de/eis/research/publications/papers/iccd04.pdf
> 

I was referring to custom design, not the use of standard cells or 
FPGAs.  It is certainly obvious that if you can't design your cells from 
scratch then you're just arranging the cells that you have available. 
I'm not sure if it can be reduced to swapping wires however, though 
certainly in FPGAs where the entire logic design is already laid out and 
the only configuration possible is via routing changes then this is the 
case.

>I don't know how they do it this days, but I do know that with a 
>whole shitpot load of adders, you could do it in n propagation delays,
>where n is the width of whichever operand you arrange to come in 
>sideways. I almost drew a schematic. You have a set of adders as
>wide as operand "A", and its inputs are operand "A" and the "latest"
>partial product - and its outputs go to another bank of adders whose
>other inputs are either "A" again or 0, and so on - the other operand,
>"B", would be presented down the side of the array, deciding which
>partial products get added to and which don't. The LSB, of course,
>gets sent out as "product", and the carry is the MSB of the next
>partial product. They form a parallelogram.

Wouldn't it go faster (log N) if you used a tree rather than
a long skinny chain?

-- 
The suespammers.org mail server is located in California.  So are all my
other mailboxes.  Please do not send unsolicited bulk e-mail or unsolicited
commercial e-mail to my suespammers.org address or any of my other addresses.
These are my opinions, not necessarily my employer's.  I hate spam.