Computer Arithmetic Circuit Design
Chapter 11
Tree and Array Multipliers
Full-Tree Multipliers Alternative Reduction Trees Tree Multipliers for Signed Numbers Partial-Tree Multipliers Array Multipliers Pipelined Tree and Array Multipliers
Ch 11. Tree and Array Multipliers
Computer Arithmetic Circuit Design
Full-Tree Multipliers
Ch 11. Tree and Array Multipliers
Computer Arithmetic Circuit Design
Full-Tree Multipliers
1. All multiples of the multiplicand are produced in parallel. 2. k-input CSA tree is used to reduce them to two operands. 3. A CPA is used to reduce those two to the product. No feedback pipelining is feasible. Different multiplier arrays are distinguished by the designs of the above three elements.
Ch 11. Tree and Array Multipliers 3
Computer Arithmetic Circuit Design
General Structure of a Full-tree Multiplier
Ch 11. Tree and Array Multipliers
Computer Arithmetic Circuit Design
Radix Tradeoffs
The higher the radix .
The more complex the multiple-forming circuits, and The less complex the reduction tree.
Where is the optimal cost-effectiveness?
Depends on design Depends on technology
Ch 11. Tree and Array Multipliers 5
Computer Arithmetic Circuit Design
Tradeoffs in CSA Trees
Wallace Tree Multiplier
Combine partial product bits at the earliest opportunity. Leads to fastest possible design.
Dadda Tree Multiplier
Combine as late as possible, while keeping the critical path length (# levels) of the tree minimal. Leads to simpler CSA tree structure, but wider CPA at the end.
Hybrids
Some where in between.
Ch 11. Tree and Array Multipliers 6
Computer Arithmetic Circuit Design
Two Binary 4 4 Tree Multipliers
Ch 11. Tree and Array Multipliers
Computer Arithmetic Circuit Design
Reduction Tree
Results from chapter 8 apply to the design of partial product reduction trees.
General CSA Trees Generalized Parallel Counters
Ch 11. Tree and Array Multipliers
Computer Arithmetic Circuit Design
CSA for 7 7 Tree Multiplier
Ch 11. Tree and Array Multipliers
Computer Arithmetic Circuit Design
Structure of a CSA Tree
A logarithmic depth reduction trees based on CSAs (e.g. Wallace, Dadda. Etc.)
Have an irregular structure. Make design and layout difficult.
Connections and signal paths of various lengths
Lead to logic hazards and signal skew. Implication for both performance and power consumption.
Ch 11. Tree and Array Multipliers
10
Computer Arithmetic Circuit Design
Alternative Reduction Trees (n;2) Counters
(more suitable to VLSI)
Ch 11. Tree and Array Multipliers
11
Computer Arithmetic Circuit Design
A Balanced (11;2) Counter
1. Balanced: All outputs are produced after the same number of delays. 2. All carries produced at evel i enter FAs at level i+1. 3. Can be laid out to occupy a narrow vertical slice. 4. Can be easily expanded to a (18;2) counter.
Ch 11. Tree and Array Multipliers 12
Computer Arithmetic Circuit Design
Tree Multiplier Based on (4,2) Counters
Ch 11. Tree and Array Multipliers
13
Computer Arithmetic Circuit Design
Layout of Binary Reduction Tree
Ch 11. Tree and Array Multipliers
14
Computer Arithmetic Circuit Design
Sign Extension
Ch 11. Tree and Array Multipliers
15
Computer Arithmetic Circuit Design
Signed Addition
Ch 11. Tree and Array Multipliers
16
Computer Arithmetic Circuit Design
Baugh-Wooley Arrays
Ch 11. Tree and Array Multipliers
17
Computer Arithmetic Circuit Design
Partial Tree Multipliers
Ch 11. Tree and Array Multipliers
18
Computer Arithmetic Circuit Design
Basic Array Multiplier Using a One-Sided CSA Tree
Ch 11. Tree and Array Multipliers
19
Computer Arithmetic Circuit Design
Unsigned Array Multiplier1
Ch 11. Tree and Array Multipliers
20
Computer Arithmetic Circuit Design
Unsigned Array Multiplier2
Ch 11. Tree and Array Multipliers
21
Computer Arithmetic Circuit Design
Baugh-Wooley Signed Multiply
Ch 11. Tree and Array Multipliers
22
Computer Arithmetic Circuit Design
Signed Multiplier Array
Ch 11. Tree and Array Multipliers
23
Computer Arithmetic Circuit Design
Mixed Positive and Negative Binary
Ch 11. Tree and Array Multipliers
24
Computer Arithmetic Circuit Design
Mixed Binary Full Adders
Ch 11. Tree and Array Multipliers
25
Computer Arithmetic Circuit Design
5 5 Signed Multiplier Using Mixed +/ Numbers
Ch 11. Tree and Array Multipliers
26
Computer Arithmetic Circuit Design
Include AND Gates in Cells
Ch 11. Tree and Array Multipliers
27
Computer Arithmetic Circuit Design
Change the Terms of the Problem
Ch 11. Tree and Array Multipliers
28
Computer Arithmetic Circuit Design
Multiplier Without Final CPA
Ch 11. Tree and Array Multipliers
29
Computer Arithmetic Circuit Design
Conditional Carry-Save
Ch 11. Tree and Array Multipliers
30
Computer Arithmetic Circuit Design
Pipelined Partial-Tree Multiplier
Ch 11. Tree and Array Multipliers
31
Computer Arithmetic Circuit Design
Pipelined Array Multiplier
Ch 11. Tree and Array Multipliers
32
