How to generate a CSA tree?

S

Sleep Mode

Guest
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
Click to expand...
 
Peter Alfke <peter@xilinx.com> wrote in message news:<4002D411.A6AA3B10@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
Click to expand...
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 <karagiozhs@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 bon@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,
Click to expand...
Yes I agree. Chris, try it and see.

except I don't
think many synthesis tools support booth 3 architectures.
Click to expand...
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
Click to expand...
--
--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
 
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 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
Click to expand...
--
--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
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top