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

  • Unit 1

    Unit 1

    in a variety of content area, grade-level texts. Incorporate plan & monitor reading strategies, as well as graphic organizers, in order to clarify and analyze the meaning of the text. in a variety of content area, grade-level texts. Unit Objectives
  • CABI TOURISM TEXTS 4th Edition Leisure, Sport and

    CABI TOURISM TEXTS 4th Edition Leisure, Sport and

    Leisure, Sport and Tourism, Politics, Policy and Planning, 4th edition, Veal, 2017, CABI Tourism Texts The nature of ideology Ideology: 'A system of ideas concerning phenomena, especially those of social life; the manner of thinking of a class or an...
  • Classifying Igneous Rocks Earth Science Standard 3c: Students

    Classifying Igneous Rocks Earth Science Standard 3c: Students

    Earth Science Standard 3c: Students know how to explain the properties of rocks based on the physical and chemical conditions in which they formed, including plate tectonic processes.. Classifying Igneous Rocks
  • P O L L U T I O N - Eagle Mountain-Saginaw Independent School ...

    P O L L U T I O N - Eagle Mountain-Saginaw Independent School ...

    Air Pollution. Atmosphere need to know: Air is more dense at sea level. 75-80% of air mass found in troposphere. Atmosphere contains 78% N, 21%O, and 1% trace gases like, methane, nitrous oxide, ozone, argon, water vapor, and carbon dioxide.
  • Active Academics

    Active Academics

    Frank mows lawns for extra money. If he mows 5 lawns in one hour and has 30 lawns to mow, how long will it take him to mow all of them? 6 hours
  • Antimicrobial Resistance

    Antimicrobial Resistance

    AMR is now considered one of the greatest threats to human health facing the world today. ... To receive this publication in an accessible format phone 90965007, using the National Relay Service 13 36 77 if required, or email [email protected]
  • How Stations Can Support Personalized Learning

    How Stations Can Support Personalized Learning

    Kahoot Demo. How Stations Can Support Personalized Learning. How Stations Can Support Personalized Learning. How to Start. 1. Create a list of what must be accomplished. 2. Ask yourself this question: Where in this list can I give students the...
  • Lecture 1- Introduction

    Lecture 1- Introduction

    testing room . is typically smaller and accommodates a small number of people . The . observation room, can see into the testing room typically via a one-way mirror. The observation room is larger and can hold the usability testing...