EECS 150 - Components and Design Techniques for Digital Systems Lec 18 – Arithmetic II (Multiplication)ReviewComputer Number Systems2s Complement Overflow2s comp. Overflow Detection2s Complement Adder/SubtractorAdders on the Xilinx VirtexCarry Look-ahead AddersCarry Look-ahead Adders – in blocksSlide 10Parallel Prefix (generalizing CLA)Slide 12Time / Space (resource) Trade-offsBit-serial AdderAnnouncementsBasic concept of multiplicationCombinational Multiplier: accumulation of partial productsArray Multiplier“Shift and Add” MultiplierCarry-save AdditionCarry-save CircuitsArray Mult. using Carry-save AdditionAnother Representation (from book)Slide 24Signed MultiplierSigned multiplicationSigned Array Multiplier“Shift and Add” Signed MultiplierSummaryEECS 150 - Components and Design Techniques for Digital Systems Lec 18 – Arithmetic II (Multiplication)David CullerElectrical Engineering and Computer SciencesUniversity of California, Berkeleyhttp://www.eecs.berkeley.edu/~cullerhttp://www-inst.eecs.berkeley.edu/~cs150Review•Circuit design for unsigned addition–Full adder per bit slice–Delay limited by Carry Propagation»Ripple is algorithmically slow, but wires are short•Carry select–Simple, resource-intensive–Excellent layout•Carry look-ahead–Excellent asymptotic behavior–Great at the board level, but wire length effects are significant on chip•Digital number systems–How to represent negative numbers–Simple operations–Clean algorithmic properties•2s complement is most widely used–Circuit for unsigned arithmetic–Subtract by complement and carry in–Overflow when cin xor cout of sign-bit is 1Computer Number Systems•Positional notation–Dn-1 Dn-2 …D0 represents Dn-1Bn-1 + Dn-2Bn-2 + …+ D0 B0 where Di { 0, …, B-1 }•2s Complement–Dn-1 Dn-2 …D0 represents: - Dn-12n-1 + Dn-22n-2 + …+ D0 20–MSB has negative weight0000000100100011100001010110010010011010101111001101011111101111+0+1+2+3+4+5+6+7-8-7-6-5-4-3-2-1-8 + 52s Complement OverflowAdd two positive numbers to get a negative numberor two negative numbers to get a positive number5 + 3 = -8!-7 - 2 = +7!0000000100100011100001010110010010011010101111001101011111101111+0+1+2+3+4+5+6+7-8-7-6-5-4-3-2-10000000100100011100001010110010010011010101111001101011111101111+0+1+2+3+4+5+6+7-8-7-6-5-4-3-2-1How can you tell an overflow occurred?2s comp. Overflow Detection53-80 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0-7-271 0 0 0 1 0 0 1 1 1 0 01 0 1 1 15270 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1-3-5-81 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0OverflowOverflowNo overflowNo overflowOverflow occurs when carry in to sign does not equal carry out2s Complement Adder/SubtractorA - B = A + (-B) = A + B + 1A B CO S + CI A B CO S + CI A B CO S + CI A B CO S + CI 0 1 Add/Subtract A 3 B 3 B 3 0 1 A 2 B 2 B 2 0 1 A 1 B 1 B 1 0 1 A 0 B 0 B 0 Sel Sel Sel Sel S 3 S 2 S 1 S 0 OverflowAdders on the Xilinx Virtex•Dedicated carry logic provides fast arithmetic carry capability for high-speed arithmetic functions. The Virtex-E CLB supports two separate carry chains, one per Slice. The height of the carry chains is two bits per CLB.•The arithmetic logic includes an XOR gate and AND gate that allows a 2-bit full adder to be implemented within a slice. •Cin to Cout delay = 0.1ns, versus 0.4ns for F to X delay.How do we map a 2-bit adder to one slice?Carry Look-ahead Adders•In general, for n-bit addition best we can achieve is delay log(n)•How do we arrange this? (think trees)•First, reformulate basic adder stage:carry “kill” ki = ai’ bi’carry “propagate” pi = ai bicarry “generate” gi = ai bici+1 = gi + picisi = pi ci0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1a b ci ci+1 sCarry Look-ahead Adders – in blocks•“Group” propagate and generate signals:•P true if the group as a whole propagates a carry to cout•G true if the group as a whole generates a carry•Group P and G can be generated hierarchically.pigipi+1gi+1pi+kgi+kP = pi pi+1 … pi+kG = gi+k + pi+kgi+k-1 + … + (pi+1pi+2 … pi+k)gicincoutCout = G + PCinCarry Look-ahead Addersa0b0a1b1a2b2aa3b3a4b4a5b5bc3 = Ga + Pac0PaGaPbGba6b6a7b7a8b8cc6 = Gb + Pbc3PcGcP = PaPbPcG = Gc + PcGb + PbPcGac9 = G + Pc0c09-bit Example of hierarchically generated P and G signals:Parallel Prefix (generalizing CLA)•Compute all the prefixes Fi = Fi-1 op Fi-2 op … op F0•Assume associative and commutativeB ABABAxBAxAx0123456776543210101032325454767664207430307454 107030541074 64 30 20303070 60 50 40c0a0b0s0a1b1s1c1a2b2s2a3b3s3c3c2c0c0a4b4s4a5b5s5c5a6b6s6a7b7s7c7c6c0c4c0c8p,gP,GP,GcincoutP,GPa,GaPb,GbP = PaPbG = Gb + GaPbCout = G + cinPaibisip,gcici+1p = a bg = abs = p cici+1 = g + cip8-bit Carry Look-ahead AdderTime / Space (resource) Trade-offs•Carry select and CLA utilize more silicon to reduce time.•Can we use more time to reduce silicon?•How few FAs does it take to do addition?Bit-serial Adder•Addition of 2 n-bit numbers:–takes n clock cycles,–uses 1 FF, 1 FA cell, plus registers–the bit streams may come from or go to other circuits, therefore the registers may be optional.•Requires controller–What does the FSM look like? Implemented?•Final carry out?•A, B, and R held in shift-registers. Shift right once per clock cycle.•Reset is asserted by controller.n - b i t s h i f t r e g i s t e rn - b i t s h i f t r e g i s t e r sscr e s e tRF AF FBAlsbAnnouncements•Reading: 5.8•Regrades in with homework on Friday•Digital Design in the news – from UCB–Organic e-textiles (Prof. Vivek Subramanian)Basic concept of multiplicationmultiplicandmultiplier1101 (13)1011 (11)1101110100001101*10001111(143)Partial products•product of 2 n-bit numbers is an 2n-bit number–sum of n n-bit partial products•unsignedCombinational Multiplier: accumulation of partial productsA0B0A0 B0A1B1A1 B0A0 B1A2B2A2 B0A1 B1A0 B2A3B3A2 B0A2 B1A1 B2A0 B3A3 B1A2 B2A1 B3A3 B2A2 B3A3 B3S6S5S4S3 S2S1 S0S7Array Multiplierb3 0 b2 0 b1 0 b0 0P7 P6 P5 P4a00a10a20a30P0P1P2P3FAbjsum insum outcarryoutaicarryinEach row: n-bit adder with AND gatesWhat is the critical path?Generates all n
View Full Document
Unlocking...