Multipliers & Pipelining - Massachusetts Institute of Technology
Multipliers & Pipelining
? Combinational multiplier ? Two's complement multiplier ? Smaller multipliers, faster multipliers ? Latency & Throughput ? Pipelining to increase throughput ? Retiming
Lab #3 due tonight, report next Tuesday, no LPSets this week
6.111 Fall 2008
Lecture 9
1
Unsigned Multiplication
A3 A2 A1 A0 x B3 B2 B1 B0
ABi called a "partial product"
A3B0 A2B0 A1B0 A0B0
A3B1 A2B1 A1B1 A0B1
A3B2 A2B2 A1B2 A0B2
+ A3B3 A2B3 A1B3 A0B3
Multiplying N-bit number by M-bit number gives (N+M)-bit result
Easy part: forming partial products (just an AND gate since BI is either 0 or 1)
Hard part: adding M N-bit partial products
6.111 Fall 2008
Lecture 9
2
Combinational Multiplier (unsigned)
X3 X2 X1 X0
* Y3 Y2 Y1 Y0
--------------------
X3Y0 X2Y0 X1Y0 X0Y0
+
X3Y1 X2Y1 X1Y1 X0Y1
+
X3Y2 X2Y2 X1Y2 X0Y2
+
X3Y3 X2Y3 X1Y3 X0Y3
-----------------------------------------
Z7 Z6 Z5 Z4 Z3 Z2 Z1 Z0
x3
multiplicand multiplier
Partial products, one for each bit in multiplier (each bit needs just one
AND gate)
x3
x2
x1
x0 y0
x2
x1
x0 y1
z0
HA
FA
FA
HA
Propagation delay ~2N
x3
x2
x1
x0 y2
z1
FA
FA
FA
HA
x3
x2
x1
x0 y3
z2
FA
FA
FA
HA
z7
z6
z5
z4
z3
6.111 Fall 2008
Lecture 9
3
Combinational Multiplier (signed!)
X3 X2 X1 X0 * Y3 Y2 Y1 Y0 -------------------X3Y0 X3Y0 X3Y0 X3Y0 X3Y0 X2Y0 X1Y0 X0Y0 + X3Y1 X3Y1 X3Y1 X3Y1 X2Y1 X1Y1 X0Y1 + X3Y2 X3Y2 X3Y2 X2Y2 X1Y2 X0Y2 - X3Y3 X3Y3 X2Y3 X1Y3 X0Y3 ----------------------------------------Z7 Z6 Z5 Z4 Z3 Z2 Z1 Z0
x3
x3 x2
x2 x1
x1
x0 y0
x0 y1 z0
FA
FA
FA
FA
FA
FA
HA
x3
x2
x1
x0 y2
z1
FA
FA
FA
FA
FA
HA
x3
x2
x1
x0 y3
z2
FA
FA
z7
z6
6.111 Fall 2008
FA
FA
z5
z4
Lecture 9
FA
1 NB: There are tricks we
can use to eliminate the
extra circuitry we
z3
added...
4
2's Complement Multiplication
(Baugh-Wooley)
Step 1: two's complement operands so high order bit is ?2N-1. Must sign extend partial products and subtract the last one
Step 3: add the ones to the partial products and propagate the carries. All the sign extension bits go away!
X3 X2 X1 X0 * Y3 Y2 Y1 Y0 -------------------X3Y0 X3Y0 X3Y0 X3Y0 X3Y0 X2Y0 X1Y0 X0Y0 + X3Y1 X3Y1 X3Y1 X3Y1 X2Y1 X1Y1 X0Y1 + X3Y2 X3Y2 X3Y2 X2Y2 X1Y2 X0Y2 - X3Y3 X3Y3 X2Y3 X1Y3 X0Y3 ----------------------------------------Z7 Z6 Z5 Z4 Z3 Z2 Z1 Z0
X3Y0 X2Y0 X1Y0 X0Y0
+
X3Y1 X2Y1 X1Y1 X0Y1
+
X2Y2 X1Y2 X0Y2
+
X3Y3 X2Y3 X1Y3 X0Y3
+
1
-
1 1 1 1
Step 2: don't want all those extra additions, so
Step 4: finish computing the constants...
add a carefully chosen constant, remembering
to subtract it at the end. Convert subtraction into add of (complement + 1).
X3Y0 X2Y0 X1Y0 X0Y0
X3Y0 X3Y0 X3Y0 X3Y0 X3Y0 X2Y0 X1Y0 X0Y0
+
1
+ X3Y1 X3Y1 X3Y1 X3Y1 X2Y1 X1Y1 X0Y1
+
1
+
X3Y1 X2Y1 X1Y1 X0Y1
+
X2Y2 X1Y2 X0Y2
+
X3Y3 X2Y3 X1Y3 X0Y3
+ 1
1
+ X3Y2 X3Y2 X3Y2 X2Y2 X1Y2 X0Y2
+
1
+ X3Y3 X3Y3 X2Y3 X1Y3 X0Y3
+
1
+
1
-
1 1 1 1
?B = ~B + 1
Result: multiplying 2's complement operands takes just about same amount of hardware as multiplying unsigned operands!
6.111 Fall 2008
Lecture 9
5
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- lecture 8 binary multiplication division university of utah
- 2 s complement and floating point university of washington
- l08 arithmetic multipliers mit massachusetts institute of
- two s complement rochester institute of technology
- binary arithmetic university of pittsburgh
- multipliers pipelining massachusetts institute of technology
Related searches
- seton institute of reconstructive surgery
- michigan institute of real estate classes
- sports institute of tucson
- institute of physics iop
- institute of physics uk
- american institute of physics
- american institute of physics citation
- american institute of physics inc
- chicago institute of plastic surgery
- indian institute of public health
- nigerian institute of international affairs
- eric institute of education science