Hi all,

I am trying to design a 16-bit integer multiplier in VHDL and I want to use
a Carry-Save-Adder (CSA) tree for generating the interim subproducts
and -then- with an additional CPA (or other) adder to add them to the final
32-bit product; i.e. I want to build a full-tree multiplier.

My question is whether there is some automatic (core) generator for the
CSA-tree interconnections since it is rather complicated to do it by hand...
If not, is there any fast method of drawing it manually (pen-and-paper) so
that I can translate it to VHDL later on?


Thanks in advance guys,
Chris

The most automatic way to design a fast
multiplier is to just use the
one that exists as a hard macro ( i.e. dedicated logic) in the newer FPGAs.
I bet you cannot beat its speed...
Peter Alfke
==================
Sleep Mode wrote:
> 
> Hi all,
> 
> I am trying to design a 16-bit integer multiplier in VHDL and I want to use
> a Carry-Save-Adder (CSA) tree for generating the interim subproducts
> and -then- with an additional CPA (or other) adder to add them to the final
> 32-bit product; i.e. I want to build a full-tree multiplier.
> 
> My question is whether there is some automatic (core) generator for the
> CSA-tree interconnections since it is rather complicated to do it by hand...
> If not, is there any fast method of drawing it manually (pen-and-paper) so
> that I can translate it to VHDL later on?
> 
> Thanks in advance guys,
> Chris

Peter Alfke <p...@xilinx.com> wrote in
message news:<4...@xilinx.com>...
> The most automatic way to design a fast multiplier is to just use the
> one that exists as a hard macro ( i.e. dedicated logic) in the newer FPGAs.
> I bet you cannot beat its speed...
> Peter Alfke
> ==================
> Sleep Mode wrote:
> > 
> > Hi all,
> > 
> > I am trying to design a 16-bit integer multiplier in VHDL and I want to use
> > a Carry-Save-Adder (CSA) tree for generating the interim subproducts
> > and -then- with an additional CPA (or other) adder to add them to the final
> > 32-bit product; i.e. I want to build a full-tree multiplier.
> > 
> > My question is whether there is some automatic (core) generator for the
> > CSA-tree interconnections since it is rather complicated to do it by hand...
> > If not, is there any fast method of drawing it manually (pen-and-paper) so
> > that I can translate it to VHDL later on?
> > 
> > Thanks in advance guys,
> > Chris

Depending on your requirements (area/speed), I would
build a booth 2 or booth 3 multiplier and just use '+'
for addition. That would allow the synthesis tool to
choose the best adder for your requirement.
Of course a '*' should do almost the same, except I don't
think many synthesis tools support booth 3 architectures.

Regards,
rudi
========================================================
   ASICS.ws   ::: Solutions for your ASIC/FPGA needs :::
..............::: FPGAs * Full Custom ICs * IP Cores :::
FREE IP Cores -> http://www.asics.ws/  <- FREE EDA Tools

Sleep Mode <k...@hotmail.com> wrote:
: Hi all,

: I am trying to design a 16-bit integer multiplier in VHDL and I want to use
: a Carry-Save-Adder (CSA) tree for generating the interim subproducts
: and -then- with an additional CPA (or other) adder to add them to the final
: 32-bit product; i.e. I want to build a full-tree multiplier.

: My question is whether there is some automatic (core) generator for the
: CSA-tree interconnections since it is rather complicated to do it by hand...
: If not, is there any fast method of drawing it manually (pen-and-paper) so
: that I can translate it to VHDL later on?


For example, XST infers a quite fast multiplier for the verilog statement

assign ab = a*b;

when no hardware multipliers are available or LUT style is choosen.
So you don't need to care for the inner workings.

Regarding Peter's proposal about using parts with hardware multipliers: They
either give headaches for the Test boards, as the parts only come as fine
pitch BGAs (VirtexII) or they will give you headache with getting them, as
they are not yet released (Spartan III). And both Virtex II and Spatan III
are no longer 5 Volt tolerant, often giving additional headache with
interfacing other parts.

Bye
-- 
Uwe Bonnes                b...@elektron.ikp.physik.tu-darmstadt.de

Institut fuer Kernphysik  Schlossgartenstrasse 9  64289 Darmstadt
--------- Tel. 06151 162516 -------- Fax. 06151 164321 ----------

Rudolf Usselmann wrote:

> Of course a '*' should do almost the same, 

Yes I agree. Chris, try it and see.

> except I don't
> think many synthesis tools support booth 3 architectures.

True, but that may be a "Home Related Requirement" (HRR).

     -- Mike Treseler

What is your target?  If it is an FPGA with fast
carry chains, then it generally

doesn't make sense to use a CSA architecture unless it is for an educational
exercise.  In most technologies, fast adders are more resource intensive than
the simplest adder (a ripple carry adder).  A CSA adder tree postpones the
carry so that only one of the more expensive adders is needed; all the other
adds are just half adders.  This provides the speed of a multiplier implemented
using fast adders throughout without the attendant expense.  In the case of an
FPGA with a fast carry chain, the lowest cost adder (a ripple carry adder using
the fast carry chain) also happens to be the fastest, in fact with the Xilinx
architecture
the fast carry chain adders use HALF the resources one without the fast carry
chain uses because the carry half of the half adders is in dedicated logic that
is
there whether you use it or not.  Since the cheapest adder in the FPGA is also
the
fastest, there is no need to resort to schemes such as a CSA (a wallace tree is
a CSA
adder tree arranged as a tree structure).  The one place a CSA architecture
makes sense
with the FPGA is if you are really out there on the speed such that you are
pipelining the
carry in the adder in order to achieve the speed.

In answer to your question, the CSA connections can be generated algorithmically
and I am
sure there is something out there to do it, but I am not aware of it.

Sleep Mode wrote:

> Hi all,
>
> I am trying to design a 16-bit integer multiplier in VHDL and I want to use
> a Carry-Save-Adder (CSA) tree for generating the interim subproducts
> and -then- with an additional CPA (or other) adder to add them to the final
> 32-bit product; i.e. I want to build a full-tree multiplier.
>
> My question is whether there is some automatic (core) generator for the
> CSA-tree interconnections since it is rather complicated to do it by hand...
> If not, is there any fast method of drawing it manually (pen-and-paper) so
> that I can translate it to VHDL later on?
>
> Thanks in advance guys,
> Chris

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950
email r...@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

The CSA tree combines like weighted bits, and
produces one bit of the same weight
and
one with weight * 2.  Basically, just keep combining like weighted bits until there
is just
two bits of each weight,  then add those with a conventional adder.

Ray Andraka wrote:

> What is your target?  If it is an FPGA with fast carry chains, then it generally
>
> doesn't make sense to use a CSA architecture unless it is for an educational
> exercise.  In most technologies, fast adders are more resource intensive than
> the simplest adder (a ripple carry adder).  A CSA adder tree postpones the
> carry so that only one of the more expensive adders is needed; all the other
> adds are just half adders.  This provides the speed of a multiplier implemented
> using fast adders throughout without the attendant expense.  In the case of an
> FPGA with a fast carry chain, the lowest cost adder (a ripple carry adder using
> the fast carry chain) also happens to be the fastest, in fact with the Xilinx
> architecture
> the fast carry chain adders use HALF the resources one without the fast carry
> chain uses because the carry half of the half adders is in dedicated logic that
> is
> there whether you use it or not.  Since the cheapest adder in the FPGA is also
> the
> fastest, there is no need to resort to schemes such as a CSA (a wallace tree is
> a CSA
> adder tree arranged as a tree structure).  The one place a CSA architecture
> makes sense
> with the FPGA is if you are really out there on the speed such that you are
> pipelining the
> carry in the adder in order to achieve the speed.
>
> In answer to your question, the CSA connections can be generated algorithmically
> and I am
> sure there is something out there to do it, but I am not aware of it.
>
> Sleep Mode wrote:
>
> > Hi all,
> >
> > I am trying to design a 16-bit integer multiplier in VHDL and I want to use
> > a Carry-Save-Adder (CSA) tree for generating the interim subproducts
> > and -then- with an additional CPA (or other) adder to add them to the final
> > 32-bit product; i.e. I want to build a full-tree multiplier.
> >
> > My question is whether there is some automatic (core) generator for the
> > CSA-tree interconnections since it is rather complicated to do it by hand...
> > If not, is there any fast method of drawing it manually (pen-and-paper) so
> > that I can translate it to VHDL later on?
> >
> > Thanks in advance guys,
> > Chris
>
> --
> --Ray Andraka, P.E.
> President, the Andraka Consulting Group, Inc.
> 401/884-7930     Fax 401/884-7950
> email r...@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

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950
email r...@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