Logic required for multiplication

[spanchag]

Hi

I would like to find out if there is some sort of an equation where we
give the size of the two inputs and it tells us how many flip flops it
is going to use to implement the multiplier function.

(It may be specific to the architecture of the chip but a rough
estimate would do)

Thanks,

 

[Peter Alfke]

In the newer FPGAs (like Virtex-II etc) you get ready-made multipliers that
do not "cost" any flip-flops, but you can use pipeline flip-flops inside for
free.
For multiplier-intensive applications, you ask the wrong question.
Multiplication is often implemented as a combinatorial function, without any
flip-flops, except for pipelining.
You can of course do it sequntially, and there is an endless number of
option. But for speed reasons, most users prefer the "hard" combinatorial
multipliers in the newer chipc.
Peter Alfke

From: spanchag@yahoo.com (spanchag)
Organization: http://groups.google.com
Newsgroups: comp.arch.fpga
Date: 2 Apr 2004 15:23:01 -0800
Subject: Logic required for multiplication

Hi

I would like to find out if there is some sort of an equation where we
give the size of the two inputs and it tells us how many flip flops it
is going to use to implement the multiplier function.

(It may be specific to the architecture of the chip but a rough
estimate would do)

Thanks,

 

[Thomas Womack]

In article <80e4f9e8.0404021523.856f188@posting.google.com>,
spanchag <spanchag@yahoo.com> wrote:

Hi

I would like to find out if there is some sort of an equation where we
give the size of the two inputs and it tells us how many flip flops it
is going to use to implement the multiplier function.

For the multiplier function produced by compiling Verilog a <= b*c for
my Spartan 2, it seems to use a little over n^2 flip-flops, but there
are serious arrangement constraints: to use the carry chains, it
builds columns of height n/2. So that's not very helpful to see how
many multipliers fit on chip: it's not clear that I could fit much more
than three 16x16->32 on the XC2S150 before I run out of columns. I've
not tried fitting more than one.

Of course, those are full-parallel multipliers, and a serial one taking
n cycles requires roughly 3n flip-flops, again arranged in columns
to use the carry chain for the accumulator.

[my dev board has arrived; I may shortly start asking some incredibly
newbie questions about why horribly-naive designs don't work ...]

Tom

 

[spanchag]

Thanks for your reply. I am working on something that will require
more multipliers than the dedicated ones in the Virtex II, where I may
have to implement some in logic and use the dedicated ones as well.

I was wondering if there is some sort of a computation method whereby
we know the widths of the multiplier and the multiplicand and using
the method we can compute the resources (like LUTs) the multiplication
operation would use.

Peter Alfke <peter@xilinx.com> wrote in message news:<BC9340F2.5D96%peter@xilinx.com>...

In the newer FPGAs (like Virtex-II etc) you get ready-made multipliers that
do not "cost" any flip-flops, but you can use pipeline flip-flops inside for
free.
For multiplier-intensive applications, you ask the wrong question.
Multiplication is often implemented as a combinatorial function, without any
flip-flops, except for pipelining.
You can of course do it sequntially, and there is an endless number of
option. But for speed reasons, most users prefer the "hard" combinatorial
multipliers in the newer chipc.
Peter Alfke

From: spanchag@yahoo.com (spanchag)
Organization: http://groups.google.com
Newsgroups: comp.arch.fpga
Date: 2 Apr 2004 15:23:01 -0800
Subject: Logic required for multiplication

Hi

I would like to find out if there is some sort of an equation where we
give the size of the two inputs and it tells us how many flip flops it
is going to use to implement the multiplier function.

(It may be specific to the architecture of the chip but a rough
estimate would do)

Thanks,

 

[Larry Doolittle]

In article <80e4f9e8.0404050657.233e9164@posting.google.com>, spanchag wrote:

Thanks for your reply. I am working on something that will require
more multipliers than the dedicated ones in the Virtex II, where I may
have to implement some in logic and use the dedicated ones as well.

I was wondering if there is some sort of a computation method whereby
we know the widths of the multiplier and the multiplicand and using
the method we can compute the resources (like LUTs) the multiplication
operation would use.

Assuming Virtex1/Virtex2-type logic cells (4-input LUT plus carry
logic and Flip-Flop):

Generic combinatorial N x M multiplier takes ~ (N-1)*M cells.

Loadable KCM, also combinatorial, takes ~ (N/2-1)*(M+3) cells.

Scaling Accumulator multiplier, N clock cycles, takes M arithmetic
cells. Depending on your infrastructure, you may have to count
another N cells to serialize the multiplier, plus another N cells
to store the LSBs that shift out.

If you haven't read Ray Andraka's page on multiplication
http://www.fpga-guru.com/multipli.htm
yet, do so now.

I believe all of this also applies to Altera chips, except there
the KCM is not loadable.

- Larry

 

[Ray Andraka]

There are many ways to multiply, and where you have lots of multiplies to do it may make
sense to either time multiplex the existing multipliers or if it is for a sum of products
use distributed arithmetic. We really need more information about your specific application
in order to give you better guidance. Modern FPGAs can handle clock rates at 200+ MHz with
carefully executed designs. Use that capability to fold the multiplications into a smaller
area.

spanchag wrote:

Thanks for your reply. I am working on something that will require
more multipliers than the dedicated ones in the Virtex II, where I may
have to implement some in logic and use the dedicated ones as well.

I was wondering if there is some sort of a computation method whereby
we know the widths of the multiplier and the multiplicand and using
the method we can compute the resources (like LUTs) the multiplication
operation would use.

Pe

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759