Transcript Slide 1
Design and Implementation of VLSI Systems (EN1600) Lecture 25: Datapath Subsystems 1/4 Prof. Sherief Reda Division of Engineering, Brown University Spring 2008 [sources: Weste/Addison Wesley – Rabaey/Pearson] S. Reda EN1600 SP’08 Datapath Subsystems Adders Multipliers Comparators Counters Shifters S. Reda EN1600 SP’08 Adders Addition is the most commonly used arithmetic operation → could be speed limiting → optimization of the adder is of the utmost importance S. Reda EN1600 SP’08 A N-bit carry-ripple adder can be constructed by cascading 1-bit FA A0 B0 Ci,0 A1 B1 Co,0 FA A2 B2 Co,1 A3 B3 Co,2 Co,3 FA FA FA S1 S2 S3 (= Ci,1) S0 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 S. Reda EN1600 SP’08 Full adder Boolean equations A S A B C Cout MAJ ( A, B, C ) Cin B Full adder Cout Sum S = A B Ci = ABC i + ABC i + ABCi + ABCi C o = AB + BC i + ACi S can be factored to reuse the Co term S. Reda EN1600 SP’08 An implementation that requires 28 transistors VDD VDD A Ci A B B A B B Ci A X Ci VDD Ci S A Ci A B B VDD A Co S. Reda EN1600 SP’08 B Ci A B Problems with the design VDD VDD A Ci A B B A B B Ci A X Ci VDD Ci S A Ci A B B VDD A Co Problems: B Ci A B Note • Large area • Ci is connected to the transistor • Tall transistor stacks closest to the output • Large intrinsic capacitance for Co S. Reda EN1600 SP’08 Self-dual property of FAs A. A full adder receiving complementary inputs produce complementary outputs B. An inverting full adder receiving complementary inputs produce true outputs A Self duality enables two optimizations: A.PGK mirror FA B.Faster ripple carry adder Ci A B FA S Co Ci B FA S S A B C i = S A B Ci C A B C = C A B C o i o i S. Reda EN1600 SP’08 Co A. PGK mirror FA design • For a full adder, define what happens to carry – Generate: Cout = 1 independent of C • G=A•B – Propagate: Cout = C • P=AB – Kill: Cout = 0 independent of C • K = ~A • ~B S. Reda EN1600 SP’08 A. The mirror adder VDD VDD A B A VDD A B B Ci B Kill "0"-Propagate A Ci S Ci A "1"-Propagate Generate A B Still need two inverters to generate Co and S S. Reda EN1600 SP’08 Ci Co B A B Ci A B • Less area • Shorter stacks • Less intrinsic capacitance A. Mirror adder stick diagram VDD A B Ci B A Ci Co S GND S. Reda EN1600 SP’08 Co Ci A B B. Minimize critical path (carry) by reducing the number of inverters along the path Even cell A0 Ci,0 B0 , FA S0 A1 Co,0 B1 , FA S1 A2 Co,1 Odd cell B2 , FA S2 A3 Co,2 B3 , FA S3 • FA’ is a FA without the inverter in the carry path S. Reda EN1600 SP’08 Co,3