EE141 1 © Digital Integrated Circuits 2nd Arithmetic Circuits Digital Integrated Digital Integrated Circuits Circuits A Design Perspective A Design Perspective Arithmetic Circuits Arithmetic Circuits Jan M. Rabaey Anantha Chandrakasan Borivoje Nikolic January, 2003 EE141 2 © Digital Integrated Circuits 2nd Arithmetic Circuits A Generic Digital Processor A Generic Digital Processor MEM ORY DATAPATH CONTROL INPUT-OUTPUT EE141 3 © Digital Integrated Circuits 2nd Arithmetic Circuits Building Blocks for Digital Architectures Building Blocks for Digital Architectures Arithmetic unit - Bit-sliced datapath (adder, multiplier, shifter, comparator, etc.) Memory - RAM, ROM, Buffers, Shift registers Control - Finite state machine (PLA, random logic.) - Counters Interconnect - Switches - Arbiters - Bus EE141 4 © Digital Integrated Circuits 2nd Arithmetic Circuits An Intel Microprocessor An Intel Microprocessor 9-1 Mux9-1 Mux 5-1 Mux2-1 Mux ck1 CARRYGEN SUMGEN + LU 1000um b s0 s1 g64 sum sumb LU : Logical Unit SUMSEL a to Cache node1 REG Itanium has 6 integer execution units like this EE141 5 © Digital Integrated Circuits 2nd Arithmetic Circuits Bit-Sliced Design Bit-Sliced Design Bit 3 Bit 2 Bit 1 Bit 0 Register Adder Shifter Multiplexer Control Data-In Data-Out Tile identical processing elements EE141 6 © Digital Integrated Circuits 2nd Arithmetic Circuits Bit-Sliced Datapath Bit-Sliced Datapath Adder stage 1 Wiring Adder stage 2 Wiring Adder stage 3 B i t s l i c e 0 B i t s l i c e 2 B i t s l i c e 1 B i t s l i c e 6 3 Sum Select Shifter Multiplexers L o o p b a c k B u s From register files / Cache / Bypass To register files / Cache L o o p b a c k B u s L o o p b a c k B u s EE141 7 © Digital Integrated Circuits 2nd Arithmetic Circuits Itanium Integer Datapath Itanium Integer Datapath Fetzer, Orton, ISSCC’02 EE141 8 © Digital Integrated Circuits 2nd Arithmetic Circuits Adders Adders EE141 9 © Digital Integrated Circuits 2nd Arithmetic Circuits Full-Adder Full-Adder A B Cout Sum Cin Full adder EE141 10 © Digital Integrated Circuits 2nd Arithmetic Circuits The Binary Adder The Binary Adder S A B C i ⊕ ⊕ = A= BC i ABC i ABC i ABC i + + + C o AB BC i AC i + += A B Cout Sum Cin Full adder [...]... Digital Integrated Circuits2 nd 15 Arithmetic Circuits A Better Structure: The Mirror Adder VDD VDD A B A B B Kill "0"-Propagate A VDD A Ci B Ci Co Ci S Ci A "1"-Propagate Generate A B B A B A Ci B 24 transistors EE141 © Digital Integrated Circuits2 nd 16 Arithmetic Circuits Mirror Adder Stick Diagram VDD A B Ci B A Ci Co Ci A B Co S GND EE141 © Digital Integrated Circuits2 nd 17 Arithmetic Circuits The Mirror... EE141 © Digital Integrated Circuits2 nd 18 Arithmetic Circuits Transmission Gate Full Adder P VDD A A P P B VDD Ci Ci A A P Ci VDD S Sum Generation Ci B P A P VDD Co Carry Generation Ci Setup EE141 © Digital Integrated Circuits2 nd A P 19 Arithmetic Circuits Manchester Carry Chain Pi VDD Pi φ Co Ci Gi Co Ci VDD Gi Di Pi EE141 © Digital Integrated Circuits2 nd φ 20 Arithmetic Circuits Manchester Carry Chain... Integrated Circuits2 nd F tp∼ log2(N) 33 Arithmetic Circuits Carry Lookahead Trees Co , 0 = G 0 + P 0 Ci , 0 C o, 1 = G1 + P1 G0 + P 1 P 0 Ci, 0 C o, 2 = G2 + P2 G1 + P 2 P1 G0 + P2 P 1 P 0 C i, 0 = ( G2 + P 2 G1) + ( P 2 P 1 ) ( G0 + P0 Ci , 0 ) = G 2:1 + P 2:1 C o, 0 Can continue building the tree hierarchically EE141 © Digital Integrated Circuits2 nd 34 Arithmetic Circuits S0 EE141 © Digital Integrated Circuits2 nd... B A B B Ci A X Ci VDD Ci A Ci A B B VDD A B Co Ci A B 28 Transistors EE141 © Digital Integrated Circuits2 nd 13 Arithmetic Circuits Inversion Property A Ci A B FA S Co Ci B FA Co S S ( A, B, C i ) = S ( A, B , C i ) C ( A, B, C ) = C ( A, B , C ) o i o i EE141 © Digital Integrated Circuits2 nd 14 Arithmetic Circuits Minimize Critical Path by Reducing Inverting Stages Even cell A0 Ci,0 B0 FA A1 Co,0 S0... Manchester Carry Chain VDD φ P0 P1 P2 P3 C3 Ci,0 G1 G0 G3 G2 φ C0 EE141 © Digital Integrated Circuits2 nd C1 C2 C3 21 Arithmetic Circuits Manchester Carry Chain Stick Diagram Propagate/Generate Row VDD Pi Ci - 1 Gi φ Pi + 1 Gi + 1 φ Ci Ci + 1 GND Inverter/Sum Row EE141 © Digital Integrated Circuits2 nd 22 Arithmetic Circuits Carry-Bypass Adder Ci,0 G1 FA P0 C o,0 P0 G1 Ci,0 FA FA P0 C o ,0 G1 P2 C o ,1 G1... EE141 © Digital Integrated Circuits2 nd 23 Arithmetic Circuits Carry-Bypass Adder (cont.) Bit 0–3 Bit 4–7 Setup tsetup Setup Bit 8–11 tbypass Bit 12–15 Setup Setup Carry propagation Carry propagation Carry propagation Carry propagation Sum Sum Sum tsum Sum M bits tadder = tsetup + Mtcarry + (N/M-1)tbypass + (M-1)tcarry + tsum EE141 © Digital Integrated Circuits2 nd 24 Arithmetic Circuits Carry Ripple versus... Carry Ripple versus Carry Bypass tp ripple adder bypass adder 4 8 EE141 © Digital Integrated Circuits2 nd N 25 Arithmetic Circuits Carry-Select Adder Setup P,G "0" "0" Carry Propagation "1" "1" Carry Propagation Co,k-1 Multiplexer Co,k+3 Carry Vector Sum Generation EE141 © Digital Integrated Circuits2 nd 26 Arithmetic Circuits Carry Select Adder: Critical Path Bit 0–3 Bit 4–7 Bit 8–11 Bit 12–15 Setup Setup... Generation Sum Generation Sum Generation S2-4 S5-8 S0-1 EE141 © Digital Integrated Circuits2 nd Sum Generation S9-13 29 Sum S14-19 (9) Arithmetic Circuits Adder Delays - Comparison 50 Ripple adder tp (in unit delays) 40 30 Linear select 20 10 0 Square root select 0 20 40 60 N EE141 © Digital Integrated Circuits2 nd 30 Arithmetic Circuits LookAhead - Basic Idea A A1, B1 Ci,0 P0 Ci,1 S0 ••• P1 S1 AN-1, BN-1... = Gk + P k Co , k – 1 EE141 © Digital Integrated Circuits2 nd 31 Arithmetic Circuits Look-Ahead: Topology Expanding Lookahead equations: VDD C o, k = Gk + Pk (Gk – 1 + Pk – 1 Co , k – 2 ) G2 G1 All the way: G0 C o, k = Gk + Pk ( Gk – 1 + P k – 1( … + P1 ( G0 + P0 Ci , 0 ) ) ) Ci,0 Co,3 P0 P1 P2 P3 EE141 © Digital Integrated Circuits2 nd 32 Arithmetic Circuits Logarithmic Look-Ahead Adder F A0 A1 A2 A3... (P) = A + B EE141 © Digital Integrated Circuits2 nd 11 Arithmetic Circuits The Ripple-Carry Adder A0 Ci,0 B0 FA A1 Co,0 (= Ci,1) S0 B1 FA A2 Co,1 S1 B2 FA A3 Co,2 S2 B3 FA S3 Worst case delay linear with the number of bits td = O(N) tadder = (N-1)tcarry + tsum Goal: Make the fastest possible carry path circuit EE141 © Digital Integrated Circuits2 nd 12 Arithmetic Circuits Complimentary Static CMOS Full . Integrated Circuits 2nd Arithmetic Circuits Digital Integrated Digital Integrated Circuits Circuits A Design Perspective A Design Perspective Arithmetic Circuits. Circuits Arithmetic Circuits Jan M. Rabaey Anantha Chandrakasan Borivoje Nikolic January, 2003 EE141 2 © Digital Integrated Circuits 2nd Arithmetic Circuits