Cost of multiplication relative to addition

I'm doing a rough complexity estimate of an algorithm. What is a reasonable
value of the cost of a real multiplication relative a real addition? That
is, how many real adds is a real multiplication worth?

  /Fred

HSDPA-boy wrote:

> I'm doing a rough complexity estimate of an algorithm. What is a reasonable
> value of the cost of a real multiplication relative a real addition? That
> is, how many real adds is a real multiplication worth?

It depends. There may be no difference at all. There may be a difference 
  as high as 100 times.

What is your hardware?
What is the word size?
How many bits of precision do you need?
What kind of difference are you looking for? Speed, cost, power 
consumption, anything else?

Vladimir Vassilevsky

DSP and Mixed Signal Design Consultant

http://www.abvolt.com

"HSDPA-boy" <fearsome.green@gmail.com> wrote in message 
news:i76dnVkSrL5iZIbYnZ2dnUVZ_t2dnZ2d@giganews.com...
> I'm doing a rough complexity estimate of an algorithm. What is a 
> reasonable
> value of the cost of a real multiplication relative a real addition? That
> is, how many real adds is a real multiplication worth?
>
>  /Fred

Dunno - but don't adders multiply by dividing - or is that worms? 

HSDPA-boy wrote:
> I'm doing a rough complexity estimate of an algorithm. What is a reasonable
> value of the cost of a real multiplication relative a real addition? That
> is, how many real adds is a real multiplication worth?

In terms of instructions, cycles, gates, transistors, chip area/cost,
power, or ?  Integer, floating point, arbitrary/infinite precision,
or ?


-- 
rhn A.T nicholson d.0.t C-o-M

HSDPA-boy wrote:
> I'm doing a rough complexity estimate of an algorithm. What is a reasonable
> value of the cost of a real multiplication relative a real addition? That
> is, how many real adds is a real multiplication worth?
> 
What are you interested in - Execution time on a processor? Silicon area 
on a custom chip or FPGA? Energy consumption? Are you interested in 
fixed point or floating point? The answers are all rather different.

Steve

On Fri, 29 Sep 2006 07:45:41 +0800, Steve Underwood <steveu@dis.org>
wrote:

>HSDPA-boy wrote:
>> I'm doing a rough complexity estimate of an algorithm. What is a reasonable
>> value of the cost of a real multiplication relative a real addition? That
>> is, how many real adds is a real multiplication worth?
>> 
>What are you interested in - Execution time on a processor? Silicon area 
>on a custom chip or FPGA? Energy consumption? Are you interested in 
>fixed point or floating point? The answers are all rather different.
>
>Steve

    Very Good reply Steve!!

[-Rick-]

HSDPA-boy wrote:

> I'm doing a rough complexity estimate of an algorithm. What is a reasonable
> value of the cost of a real multiplication relative a real addition? That
> is, how many real adds is a real multiplication worth?
> 
>   /Fred

What is your target?  Most DSP microprocessors have single cycle 
multipliers.  In that case, a multiply with no more bits than the native 
precision of the processor costs exactly the same as an add in terms of 
instruction cycles or time or code space.

On the other hand, if you are designing into hardware, say an FPGA 
(ignoring the embedded multipliers for the moment), you need to 
construct the multipliers out of gates.  Assuming fixed point, you need 
n-1 adds for an nxn bit multiplier (those may be arranged in different 
ways and there are shortcuts to reduce the size of the adder tree, but 
the point is in terms of gates or circuit area, or delay, the multiplier 
costs several times the cost of a fixed point add.

The balance changes if you throw floating point into the mix too.

So, it really is important that you specify the target hardware before 
you can determine the costs.

The other side of this too, is that since the cost structure changes 
depending on the hardware, the optimum algorithm is also dependent on 
the target.  For example, a phase rotator in a software application 
where memory is plentiful, is probably best done with a look-up for the 
sine/cosine and a complex multiply.  In a hardware implementation 
without sufficient available memory, it may make much more sense to use 
a CORDIC rotator to accomplish the same function with considerably less 
hardware complexity.

Ray Andraka wrote:
> HSDPA-boy wrote:
>
> > I'm doing a rough complexity estimate of an algorithm. What is a reasonable
> > value of the cost of a real multiplication relative a real addition? That
> > is, how many real adds is a real multiplication worth?
> >
> >   /Fred
>
> What is your target?  Most DSP microprocessors have single cycle
> multipliers.  In that case, a multiply with no more bits than the native
> precision of the processor costs exactly the same as an add in terms of
> instruction cycles or time or code space.

But not in terms of power.  A multiply will usually wiggle a lot more
wires and transistors than an add, and the power for a DSP or uP
to do so has to come from somewhere.


IMHO. YMMV.
-- 
rhn A.T nicholson d.0.t C-o-M

Ron N. wrote:


> 
> A multiply will usually wiggle a lot more
> wires and transistors than an add, and the power for a DSP or uP
> to do so has to come from somewhere.

This is true indeed .
A bunch of MAC instructions creates a significant jerk on the power supply.

Vladimir Vassilevsky

DSP and Mixed Signal Design Consultant

http://www.abvolt.com

HSDPA-boy wrote:

> I'm doing a rough complexity estimate of an algorithm. What is a reasonable
> value of the cost of a real multiplication relative a real addition? That
> is, how many real adds is a real multiplication worth?
> 
>   /Fred

What nobody is saying:

A bone-headed algorithm for an N x M multiply (unsigned) requires you to 
add a column of numbers that's M entries tall, N bits wide at the top 
and N+M bits wide at the bottom.  You can get clever by looking for 
strings of '1's or '0's in M and reduce this stack down to at most M/2 
at the cost of doing some subtractions.

If you're counting 'cost' as the number of full adders, then you have to 
figure out how many full adders you have in the stack.

If you're counting cost in execution time, gates, energy consumed, etc., 
then you have to look at the technology you're using:

* In a DSP chip that you've already bought the multiply costs the same
   as an add, because it has a built-in 1-cycle multiply -- but the DSP
   chip cost you more in the first place.
* In a 'regular' processor chip the multiply costs more, maybe; whether,
   and if so how much more depends on the processor.
* In a modern FPGA, as pointed out, a multiply comes 'free' up to the
   limit of the hard-wired multiply block.
* In a mask programmed gate array, a fast multiply costs lots of gates,
   while a slow multiply just requires a shifter, an adder, some logic
   and some clock ticks.
* Etc.

-- 

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

Posting from Google?  See http://cfaj.freeshell.org/google/

"Applied Control Theory for Embedded Systems" came out in April.
See details at http://www.wescottdesign.com/actfes/actfes.html