Transcript Introduction to VLSI Design

Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
Multipliers and Shifters
S. Sundar Kumar Iyer
1
IEP on Synthesis of Digital Design 2007
Multipliers and Shifters
Acknowledgement

Slides taken from
http://bwrc.eecs.berkeley.edu/IcBook/index.htm
which is the web-site of “Digital Integrated Circuit – A Design
Perspective” by Rabaey, Chandrakasan, Nicolic
2
IEP on Synthesis of Digital Design 2007
Multipliers and Shifters
Outline
 Multipliers




Basic Algorithm
Array Multiplier
Carry-Save Multiplier
Wallace-Tree Multiplier
 Shifter
 Binary Shifter
 Barrel Shifter
 Logrithmic Shifter
3
IEP on Synthesis of Digital Design 2007
Multipliers and Shifters
Multipliers
Expensive and slow operations
 Multiplication units in state of the art DSP and mP
 Complex adders – earlier discussion on adders relevant
 Partial products; accumulation; final summation

4
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
The Binary Multiplication
Z
=
··
X Y
M + N– 1
=

k=0
N – 1
i 
M – 1

= 
Xi 2   
 

 i=0
 j = 0
Zk 2

=

 Xi Yj 2
i =0 j= 0
j
Yj 2 
M – 1 N – 1




k
with M – 1
i
X =  Xi 2
i=0
N– 1



i + j



Y
=
 Y j2
j
j= 0
• Multiplication needs M cycles using N-bit adder
• In shift and add
-M partial product added
-Partial product is AND operation of multiplier bit
and multiplicand followed by a ‘shift’
5
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
The Binary Multiplication
1 0 1 0 1 0
x
1 0 1 1
Multiplicand
Multiplier
1 0 1 0 1 0
1 0 1 0 1 0
0 0 0 0 0 0
+
Partial products
1 0 1 0 1 0
1 1 1 0 0 1 1 1 0
Result
6
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
Partial Product Generation




Logical AND of multiplicand X and multiplier bit Yi
Adding zeros has no impact on results
Can reduce no. or partial products by half!!
Eg. 0111 1110 ≡ 1000 0010 where 1 = -1
 So only two partial products need be added!
(N-1)/2
 Multiplier word Y = S Yj 4j with Yj e {-2,-1, 0, 1, 2}
j=0

This transformation is Booth’s Recoding




Leads to less additions with area reduction and higher speed
Alternating 10101010 for eight bit is the worst case!
Multiplying with {-2,-1, 0, 1, 2} versus {1, 0}; needs encoding
Used modified Booth’s recoding for consistent operation size7
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
Modified Booth’s Recording
•Bunch bits from msb to lsb in
Partial Product Selection Table
Multiplier Bits
Recorded Bits
three with successive overlap
000
0
•Assign multiplier as per the table
001
+ Multiplicand
•Number of partial products is half
010
+ Multiplicand
011
+2 × Multiplicand
Eg. 01111111 is bunched into
100
-2 × multiplicand
101
- Multiplicand
110
- Multiplicand
111
0
 01(1), 11(1), 11(1), 11(0)
Multiplier ≡ 10 00 00 01
(see table)
Four partial products
developed instead of eight
8
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
The Array Multiplier
X3
Z7
X2
X1
X0
Y1 Z0
X3
X2
X1
X0
HA
FA
FA
HA
X3
X2
X1
X0
FA
FA
FA
HA
X3
X2
X1
X0
FA
FA
FA
HA
Z6
Z5
Z4
Y3
Y2
Y0
Z1
Z2
Z3
• N partial products of M bit size each
• N×M two bit AND; N-1 M-bit adders
• Layout need not be straggled, but routing will take care of shift
9
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
The MxN Array Multiplier - Critical Path
FA
HA
FA
FA
FA
FA
HA
HA
Critical Path 1
Critical Path 2
FA
FA
FA
HA
Critical Path 1 & 2
Many critical paths!! Critical timing determination non-trivial
10
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
Transmission Gate Full Adder
P
VDD
Ci
A
P
A
A
P
B
VDD
Ci
A
P
Ci
VDD
S Sum Generation
Ci
P
B
VDD
A
P
Co Carry Generation
Ci
A
Setup
P
• Similar circuits for sum and carry generation
• tsum = tcarry in this case
11
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
Carry-Save Multiplier
HA
HA
HA
HA
HA
FA
FA
FA
HA
FA
FA
FA
FA
FA
HA
HA
Extra set of adders
Usually fast carry look ahead adder
Vector Merging Adder
•Carry passed diagonally downward
•Assumes tadd = tcarry
12
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
Multiplier Floorplan
X3
X2
X1
X0
Y0
Y1
C S
C S
C S
C S
HA Multiplier Cell
Z0
FA Multiplier Cell
Y2
Y3
Z7
C S
C S
C S
C S
C S
C S
C S
C S
C
C
C
C
S
Z6
S
Z5
S
Z4
S
Z3
Z1
Vector Merging Cell
Z2
X and Y signals are broadcasted
through the complete array.
(
)
•Can make layout rectangular
•Regular shape and layout
•Amenable to automation
13
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
Wallace-Tree Multiplier
Partial products
6
5
4
3
First stage
2
1
0
6
5
4
(a)
5
4
2
1
0 Bit position
2
1
0
(b)
Second stage
6
3
Final adder
3
2
1
0
6
5
4
3
•Substantial Hardware Savings
FA
•Higher Speeds
HA
(c)
(d)
•Propagation delay O(log3/2N)
•Irregular; inefficient for layout
14
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
Wallace-Tree Multiplier
HA
15
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
Wallace-Tree Multiplier
y0 y1
y2
y0 y1 y2
Ci-1
FA
y3
Ci
y3 y4 y5
FA
Ci-1
FA
FA
Ci
Ci-1
Ci
Ci-1
y4
FA
Ci
Ci-1
FA
Ci
Ci-1
y5
FA
Ci
FA
C
C
S
S
• 3 to 2 compression  4 to 2 and higher order compression proposed
16
• Today’s high performance multipliers do just that!
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
Wallace-Tree Multiplier
HA
•Final adder choice critical; depends on structure of accumulator array
•Carry look ahead might be good if data arrives simultaneously
•Place pipeline stage before final addition
17
•In non-pipelined, other adders  similar performance w/ less hardware
IEP on Synthesis of Digital Design 2007
Multipliers and Shifters
Multipliers —Summary
• Optimization Goals Different Vs Binary Adder
• Once Again: Identify Critical Path
• Other possible techniques
- Logarithmic versus Linear (Wallace Tree Mult)
- Data encoding (Booth)
- Pipelining
FIRST GLIMPSE AT SYSTEM LEVEL OPTIMIZATION
• 54 × 54 multiplier achieved propagation delay of 4.4 ns
• Combined Booth encoding and Wallace tree using 4-2 compression
• With pass transistors; mixed carry-select and carry look ahead topology
18
IEP on Synthesis of Digital Design 2007
Multipliers and Shifters
Shifters
Needs
extensive hardware support
Used for floating point units; scalers and multiplication by constants
Programmable shifter more complex
an intricate multiplexer circuitry
19
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
The Binary Shifter
Right
nop
Left
Ai
Bi
Ai-1
Bi-1
Bit-Slice i
...
• Too slow for large shift values
20
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
The Barrel Shifter
•# rows = # data word length
•Control wire routed diagonally
A3
•Signal goes through only one
transmission gate (theoretically
delay is constant for shift value
and shifter size)
B3
Sh1
A2
B2
: Data Wire
Sh2
A1
B1
Sh3
A0
B0
Sh0
Sh1
Sh2
Sh3
: Control Wire
•Reality – delay depends on
shift widths due to parasitic
capacitance
•Layout and area dominated by
wiring and not active elements
•Need decoder to interpret shift
data to route signal to
appropriate wire
21
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
4x4 barrel shifter
A3
A2
A1
A0
Sh0
Sh1
Sh2
Sh3
Buffer
Widthbarrel ~ 2 pm M
22
Multipliers and Shifters
IEP on Synthesis of Digital Design 2007
Logarithmic Shifter
Sh1 Sh1
A3
Sh2 Sh2
Sh4 Sh4
B3
•Total shift decomposed into
powers of two
•Max shift width of M has log2M
stages
•ith stage shifts 2i or passes data
unchanged
A2
B2
A1
B1
A0
B0
•Speed depends on shift length
•Series connection of pass
transistor slows shifter down for
larger shift values (need
intermediate buffers)
•Appropriate for larger shifts (in
terms of area and speed)
•Structure is regular  Can be
parameterised / auto- generated
23
IEP on Synthesis of Digital Design 2007
Multipliers and Shifters
0-7 bit Logarithmic Shifter
A
A
A
A
3
Out3
2
Out2
1
Out1
0
Out0
24