Introduction to CMOS VLSI Design Lecture 11: Adders

Introduction to CMOS VLSI Design Lecture 11: Adders

Introduction to CMOS VLSI Design Lecture 11: Adders David Harris Harvey Mudd College Spring 2004 Outline Single-bit Addition Carry-Ripple Adder Carry-Skip Adder Carry-Lookahead Adder Carry-Select Adder Carry-Increment Adder Tree Adder 11: Adders CMOS VLSI Design Slide 2 Single-Bit Addition A Half Adder S B 0 S S Cout C S B C 0 0

0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

CMOS VLSI Design B Cout A 11: Adders Cout A Full Adder S Cout Cout A B Cout S Slide 3 Single-Bit Addition A Half Adder S A B B Full Adder S A B C Cout Cout AB S A B Cout Cout MAJ ( A, B, C ) C S A B

Cout S A B C Cout S 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0

1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1

1 1 1 11: Adders CMOS VLSI Design Slide 4 PGK For a full adder, define what happens to carries Generate: Cout = 1 independent of C G= Propagate: Cout = C P= Kill: Cout = 0 independent of C K= 11: Adders CMOS VLSI Design Slide 5 PGK For a full adder, define what happens to carries Generate: Cout = 1 independent of C G=AB Propagate: Cout = C P=AB Kill: Cout = 0 independent of C K = ~A ~B 11: Adders CMOS VLSI Design Slide 6 Full Adder Design I Brute force implementation from eqns S A B C Cout MAJ ( A, B, C ) A A A S MAJ Cout

C A B C B C B C B A 11: Adders B A B A B C A B C B C S C B B A CMOS VLSI Design A B C A C A B Cout

B Slide 7 Full Adder Design II Factor S in terms of Cout S = ABC + (A + B + C)(~Cout) Critical path is usually C to Cout in ripple adder MINORITY A B C Cout S S Cout 11: Adders CMOS VLSI Design Slide 8 Layout Clever layout circumvents usual line of diffusion Use wide transistors on critical path Eliminate output inverters 11: Adders CMOS VLSI Design Slide 9 Full Adder Design III Complementary Pass Transistor Logic (CPL) Slightly faster, but more area B B A A B C B C B C

B C A S S A B C B C B C B C Cout Cout B B 11: Adders CMOS VLSI Design Slide 10 Full Adder Design IV Dual-rail domino Very fast, but large and power hungry Used in very fast multipliers C_h A_h B_h A_h C_l B_h A_l C_h B_h

A_h C_l B_l Cout _l A_l B_l B_l S_l 11: Adders Cout _h S_h C_h B_h A_l CMOS VLSI Design Slide 11 Carry Propagate Adders N-bit adder called CPA Each sum bit depends on all previous carries How do we compute all these carries quickly? AN...1 BN...1 Cout Cout + SN...1 11: Adders Cin Cin 00000 1111 +0000 1111 CMOS VLSI Design Cout 11111

1111 +0000 0000 Cin carries A4...1 B4...1 S4...1 Slide 12 Carry-Ripple Adder Simplest design: cascade full adders Critical path goes from Cin to Cout Design full adder to have fast carry delay A4 B4 Cout B3 C3 S4 11: Adders A3 A2 B2 C2 S3 A1 B1 Cin C1 S2 CMOS VLSI Design S1 Slide 13 Adder is Symmetric A Ci A B

FA Co Ci S B FA Co S S A B C i = S A B C i C o A B C i = Co A B Ci 11: Adders CMOS VLSI Design Slide 14 Inversions Critical path passes through majority gate Built from minority + inverter Eliminate inverter and use inverting full adder A4 B4 Cout B3 C3 S4 11: Adders A3 A2 B2 C2 S3 A1 B1 Cin C1 S2

CMOS VLSI Design S1 Slide 15 Generate / Propagate Define 3 new variable which ONLY depend on A, B Generate (G) = AB Propagate (P) = A B Kill = 16 CMOS VLSI Design AB Generate / Propagate Equations often factored into G and P Generate and propagate for groups spanning i:j Gi: j Pi: j 0 GCP 0:00:0 in Base case Gi:i Gi Pi:i Pi G0:0 G0 P0:0 P0 Sum: Si 11: Adders CMOS VLSI Design Slide 17 Generate / Propagate 11: Adders CMOS VLSI Design Slide 18 Generate / Propagate Equations often factored into G and P Generate and propagate for groups spanning i:j Gi: j Gi:k Pi:k Gk 1: j Pi: j Pi:k Pk 1: j 0 GCP

0:00:0 in Base case Gi:i Gi Ai Bi Pi:i Pi Ai Bi G0:0 G0 Cin P0:0 P0 0 Sum: Si Pi Gi 1:0 11: Adders CMOS VLSI Design Slide 19 PG Logic A4 B4 A3 B3 A2 B2 A1 B1 Cin 1: Bitwise PG logic G4 P4 G3 P3 G2 P2 G1 P1 G0 P0 2: Group PG logic

G3:0 G2:0 G1:0 G0:0 C3 C2 C1 C0 3: Sum logic C4 Cout 11: Adders S4 S3 S2 S1 CMOS VLSI Design Slide 20 Carry-Ripple Revisited Gi:0 Gi Pi Gi 1:0 A4 B4 G4 P4 A3 B3 G3 P3 A2 B2 G2

P2 A1 B1 G1 P1 Cin G0 G3:0 G2:0 G1:0 G0:0 C3 C2 C1 C0 P0 C4 Cout 11: Adders S4 S3 S2 S1 CMOS VLSI Design Slide 21 Carry-Ripple PG Diagram Bit Position 15 14 13 12

11 10 9 8 7 6 5 4 3 2 1 0 tripple Delay 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 11: Adders CMOS VLSI Design Slide 22 Carry-Ripple PG Diagram Bit Position 15 14 13 12 11 10 9 8 7 6 5

4 3 2 1 0 tripple t pg ( N 1)t AO txor Delay 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 11: Adders CMOS VLSI Design Slide 23 PG Diagram Notation Black cell i:k Gray cell k-1:j i:k i:j Gi:k Pi:k Gk-1:j Pk-1:j 11: Adders Buffer k-1:j i:j i:j i:j Gi:j Gi:k Pi:k Gk-1:j Pi:j CMOS VLSI Design

Gi:j Gi:j Gi:j Pi:j Pi:j Slide 24 Carry Chain Designs 11: Adders CMOS VLSI Design Slide 25 Manchester Carry Chain 11: Adders CMOS VLSI Design Slide 26 Carry-Skip Adder Carry-ripple is slow through all N stages Carry-skip allows carry to skip over groups of n bits Decision based on n-bit propagate signal Cout A16:13 B16:13 A12:9 B12:9 A8:5 B8:5 A4:1 P16:13 P12:9 P8:5 P4:1 1 0 C12 + S16:13

11: Adders 1 0 C8 + 1 0 S12:9 CMOS VLSI Design C4 + S8:5 B4:1 1 0 + Cin S4:1 Slide 27 Carry-Skip PG Diagram 16 15 14 13 12 11 10 9 8 7 6 5 4

3 2 1 0 16:0 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 For k n-bit groups (N = nk) tskip 11: Adders CMOS VLSI Design Slide 28 Carry-Skip PG Diagram 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 16:0 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 For k n-bit groups (N = nk) tskip t pg 2 n 1 (k 1) t AO txor 11: Adders

CMOS VLSI Design Slide 29 Variable Group Size 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 16:0 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 Delay grows as O(sqrt(N)) 11: Adders CMOS VLSI Design Slide 30 Carry-Lookahead Adder Carry-lookahead adder computes Gi:0 for many bits in parallel. Uses higher-valency cells with more than two inputs. A16:13 B16:13 Cout G16:13 P16:13 +

S16:13 11: Adders C12 A12:9 B12:9 G12:9 P12:9 A8:5 B8:5 C8 + S12:9 CMOS VLSI Design A4:1 C4 G8:5 P8:5 B4:1 G4:1 P4:1 + + S8:5 S4:1 Cin Slide 31 CLA PG Diagram 16 15 14 13 12 11 10 9 8

7 6 5 4 3 2 1 0 16:0 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 11: Adders CMOS VLSI Design Slide 32 Higher-Valency Cells i:k k-1:l l-1:m m-1:j i:j Gi:k Pi:k Gk-1:l Pk-1:l Gl-1:m Pl-1:m Gm-1:j Gi:j Pi:j Pm-1:j 11: Adders CMOS VLSI Design Slide 33 Carry-Select Adder Trick for critical paths dependent on late input X Precompute two possible outputs for X = 0, 1 Select proper output when X arrives Carry-select adder precomputes n-bit sums For both possible carries into n-bit group A16:13 B16:13 0

+ Cout 1 + B8:5 C8 B4:1 C4 + Cin 0 CMOS VLSI Design 1 + 1 S12:9 A4:1 0 + 0 1 0 1 S16:13 A8:5 0 + C12 1 + 11: Adders A12:9 B12:9

S8:5 S4:1 Slide 34 Carry-Increment Adder Factor initial PG and final XOR out of carry-select 15 14 13 12 11 10 13:12 8 7 6 9:8 14:12 15:12 9 4 3 2 1 0 5:4 10:8 11:8 5 6:4 7:4 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 tincrement 11: Adders

CMOS VLSI Design Slide 35 Carry-Increment Adder Factor initial PG and final XOR out of carry-select 15 14 13 12 11 10 13:12 8 7 6 9:8 14:12 15:12 9 4 3 2 1 0 5:4 10:8 11:8 5 6:4 7:4 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 tincrement t pg n 1 (k 1) t AO txor 11: Adders

CMOS VLSI Design Slide 36 Variable Group Size Also buffer noncritical signals 15 14 13 12 11 10 9 12:11 8 7 6 8:7 13:11 4 5:4 9:7 14:11 5 3 2 1 0 3:2 6:4 10:7

15:11 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 15 14 13 12 11 10 9 12:11 7 6 8:7 13:11 14:11 8 9:7 10:7 5 5:4 6:4 4 3 3:2 2 1 0 1:0 3:0 6:0 15:11 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0

11: Adders CMOS VLSI Design Slide 37 Tree Adder If lookahead is good, lookahead across lookahead! Recursive lookahead gives O(log N) delay Many variations on tree adders 11: Adders CMOS VLSI Design Slide 38 Brent-Kung 15 14 13 12 11 10 15:14 13:12 15:12 11:10 9 9:8 11:8 8 7 6 7:6 5 5:4 7:4 15:8 4 3 3:2 2

1 0 1:0 3:0 7:0 11:0 13:0 9:0 5:0 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 11: Adders CMOS VLSI Design Slide 39 Sklansky 15 14 13 12 11 10 15:14 13:12 11:10 15:12 14:12 15:8 14:8 11:8 10:8 13:8 9 9:8 8 7 6 7:6 7:4 5 5:4 6:4

4 3 2 3:2 3:0 1 0 1:0 2:0 12:8 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 11: Adders CMOS VLSI Design Slide 40 Kogge-Stone 15 14 13 12 11 10 9 8 7 6 5 4 3 2 15:14 14:13 13:12 12:11 11:10 10:9 9:8 8:7 7:6 6:5 5:4 4:3

3:2 2:1 15:12 14:11 13:10 3:0 2:0 15:8 14:7 13:6 12:9 11:8 10:7 9:6 8:5 7:4 6:3 5:2 4:1 12:5 11:4 10:3 9:2 8:1 7:0 6:0 5:0 4:0 1 0 1:0 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 11: Adders CMOS VLSI Design

Slide 41 Tree Adder Taxonomy Ideal N-bit tree adder would have L = log N logic levels Fanout never exceeding 2 No more than one wiring track between levels Describe adder with 3-D taxonomy (l, f, t) Logic levels: L+l Fanout: 2f + 1 Wiring tracks: 2t Known tree adders sit on plane defined by l + f + t = L-1 11: Adders CMOS VLSI Design Slide 42 Tree Adder Taxonomy l (Logic Levels) 3 (7) f (Fanout) 2 (6) 3 (9) 1 (5) 2 (5) 1 (3) 0 (2) 0 (4) 0 (1) 1 (2) 2 (4) 3 (8) t (Wire Tracks) 11: Adders CMOS VLSI Design Slide 43 Tree Adder Taxonomy l (Logic Levels) 3 (7)

f (Fanout) Brent-Kung 2 (6) Sklansky 3 (9) 1 (5) 2 (5) 1 (3) 0 (2) 0 (4) 0 (1) 1 (2) 2 (4) Kogge-Stone 3 (8) t (Wire Tracks) 11: Adders CMOS VLSI Design Slide 44 Han-Carlson 15 14 13 12 11 10 9 8 7 6 5 4 3 15:14 13:12 11:10 9:8 7:6

5:4 3:2 15:12 13:10 11:8 9:6 7:4 5:2 3:0 15:8 13:6 11:4 9:2 7:0 5:0 2 1 0 1:0 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 11: Adders CMOS VLSI Design Slide 45 Knowles [2, 1, 1, 1] 15 14 13 12 11 10 9 8 7 6 5 4

3 2 15:14 14:13 13:12 12:11 11:10 10:9 9:8 8:7 7:6 6:5 5:4 4:3 3:2 2:1 15:12 14:11 13:10 3:0 2:0 15:8 14:7 13:6 12:9 11:8 10:7 9:6 8:5 7:4 6:3 5:2 4:1 12:5 11:4 10:3 9:2 8:1

7:0 6:0 5:0 4:0 1 0 1:0 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 11: Adders CMOS VLSI Design Slide 46 Ladner-Fischer 15 14 13 12 11 10 15:14 13:12 15:12 11:10 9 9:8 11:8 15:8 13:8 15:8 13:0 8 7 6 7:6 5:4 7:4

7:0 11:0 5 4 3 3:2 2 1 0 1:0 3:0 5:0 9:0 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 11: Adders CMOS VLSI Design Slide 47 Taxonomy Revisited (f)Ladner-Fischer (b) Sklansky 15 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

14 15:14 15:14 13:12 11:10 15:12 14:12 15:8 14:8 9:8 7:6 11:8 10:8 13:8 7:4 5:4 3:2 6:4 3:0 l (Logic Levels) 2:0 15:0 14:0 13:0 12:0 11:010:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 4 3 2 15:14 14:13 13:12 12:11 11:10 10:9 9:8 8:7 7:6 6:5 5:4 4:3 3:2

2:1 15:12 14:11 13:10 9:6 8:5 7:4 6:3 5:2 4:1 3:0 2:0 15:8 14:7 13:6 12:9 12:5 11:8 10:7 11:4 10:3 9:2 8:1 7:0 6:0 5:0 15:14 1 0 (2) 0 5 4 3

2 9:8 7:6 5:4 3:2 13:0 7:4 1 0 1:0 0:0 1:0 3:0 7:0 11:0 5:0 9:0 9:0 8:0 7:0 6:0 5:0 4:0 7 6 5 4 3 2 3:0

2:0 9 8 1 0 13:12 11:10 9:8 7:6 11:8 5:4 3:2 7:4 15:8 1:0 3:0 7:0 9:0 5:0 1 (2) 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 HanCarlson (d) Han-Carlson 15 14 13 12 11 10 15 14 13 12 11 10 9 8 7 6 5

4 3 2 9:8 8:7 7:6 6:5 5:4 4:3 3:2 2:1 12:9 11:8 10:7 9:6 8:5 7:4 6:3 5:2 4:1 3:0 2:0 12:5 11:4 10:3 9:2 8:1 7:0 6:0 5:0 4:0 1

0 1:0 Kogge3 (8) Stone 9 8 7 6 5 4 3 15:14 13:12 11:10 9:8 7:6 5:4 3:2 15:12 13:10 11:8 9:6 7:4 5:2 3:0 15:8 13:6 11:4 9:2 7:0

5:0 2 1 0 1:0 t (Wire Tracks) 15:0 14:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 15:0 14:0 13:0 12:0 11:010:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 11: Adders 6 11:0 (c) Kogge-Stone 13:6 13:8 15:8 15:12 HanCarlson 2 (4) 14:7 15:8 13:0 Knowles [2,1,1,1] 15:8 7 11:8 New (1,1,1) Knowles [4,2,1,1] 1:0

0 (4) 0 (1) 15:014:0 13:0 12:0 11:0 10:0 9:0 8:0 7:0 6:0 5:0 4:0 3:0 2:0 1:0 0:0 15:12 14:11 13:10 11:10 15 14 13 12 11 10 4:0 15:14 14:13 13:12 12:11 11:10 10:9 8 1 (5) 1 (3) 5 9 15:0 14:0 13:0 12:0 11:0 10:0 2 (5) 6 10 (a) Brent-Kung 2 (6) (e) Knowles [2,1,1,1] 7 11 3 (7) Sklansky 3 (9) 8 13:12 15:12 BrentKung LadnerFischer LadnerFischer f (Fanout)

9 12 1:0 12:8 15 14 13 12 11 10 13 0 CMOS VLSI Design Slide 48 Summary Adder architectures offer area / power / delay tradeoffs. Choose the best one for your application. Architecture Classification Logic Levels Max Tracks Fanout Cells Carry-Ripple N-1 1 1 N Carry-Skip n=4 N/4 + 5 2 1 1.25N Carry-Inc. n=4 N/4 + 2 4

1 2N Brent-Kung (L-1, 0, 0) 2log2N 1 2 1 2N Sklansky (0, L-1, 0) log2N N/2 + 1 1 0.5 Nlog2N Kogge-Stone (0, 0, L-1) log2N 2 N/2 Nlog2N 11: Adders CMOS VLSI Design Slide 49 LookAhead - Basic Idea A A1, B1 Ci,0 P0 Ci,1 S0

P1 S1 AN-1, BN-1 Ci, N-1 SN-1 C o k = f A k B k Co k 1 = Gk + P k Co k 1 50 CMOS VLSI Design PN-1

Recently Viewed Presentations

  • Critical Thinking - Metropolitan Community College

    Critical Thinking - Metropolitan Community College

    Circulation, fluid resuscitation for the hypovolemia and check for any other points of blood loss.Your pt in the case study should be on a spinal precautions until cleared. He will need a full body x-ray, trauma centers are set up...
  • COMPANY TRAINING By CTO - Lt (SCC) Paul

    COMPANY TRAINING By CTO - Lt (SCC) Paul

    COMPANY TRAINING By CTO - Lt (SCC) Paul Edwards CGGI MInstLM RMR CORE MODULES LOOK OUT ON WWW.ACOY.CO.UK FOR UPDATES RMC Core Drill RMC Core Fieldcraft RMC Core Map Reading 27th May 2011 21st October 2011 8th April 2011 15th...
  • Service Facility Design and Layout - WIU

    Service Facility Design and Layout - WIU

    8-* Discuss the impact of the "servicescape" on the behavior of customers and employees. Describe the critical facility design features. Draw a process flow diagram. Identify the bottleneck operation in a product layout and rebalance for increased capacity. Use operations...
  • Jefferson and David - henry.k12.ky.us

    Jefferson and David - henry.k12.ky.us

    Neo-classic Era Basics. Neo=new "Age of Reason" - intellectual movement - ideas of Greece and Rome were inspiration. Marked by rationality, ethics, aesthetics, and knowledge. Get away from superstition (magic), irrationality, and tyranny of dark ages. Enlightenment - framework for...
  • Hurwitz Group of Order 504 - people.eecs.berkeley.edu

    Hurwitz Group of Order 504 - people.eecs.berkeley.edu

    A Möbius Band Transfromation Widen the bottom of the band by pulling upwards its two sides, get a Möbius basket, and then a Sudanese Möbius band. Many Different Möbius Shapes Topologically, these are all equivalent: They all are single-sided, They...
  • SOLAR DYNAMICS OBSERVATORY Camera Electronics Box Dr N

    SOLAR DYNAMICS OBSERVATORY Camera Electronics Box Dr N

    Camera Electronics Box Dr N R Waltham CEB Lead Engineer [email protected] Contents Overview Team and Responsibilities Top-Level Requirements CCD Architectural Design CCD Readout Modes CCD Electronics Design Requirements CEB Architectural Design Card-Level Architectural Design Overview of Box Design Contents DC-DC...
  • Hydraulics of Semi Circular Weirs - Home | NRCS

    Hydraulics of Semi Circular Weirs - Home | NRCS

    Hydraulics of Semi Circular Weirs. The use of a weir coefficient of 2.72 has nothing to do with a semi circular weir layout. It is just the traditional coefficient of 3.1 modified to provide freeboard.
  • Ecocomposites Reinforced with Cellulose Nanoparticles: An Alternative to

    Ecocomposites Reinforced with Cellulose Nanoparticles: An Alternative to

    Funding Eastman Chemical Co XEROX Foundation USDA NRI and McIntire Stennis and the EPA which is enabling continuation of this work Time, Effort, Ideas Dr. Deepanjan Bhattacharya, Prof. Avik Chatterjee, Mr. Chad Denton, Mr. Jake Goodrich, Ms. Hoa Nguyen Prof....