UNIVERSITY OF MASSACHUSETTS Dept of Electrical Computer Engineering Digital Computer Arithmetic CE666 Koren Part 5b 1 ECE 666 Part 5b Fast Addition II Israel Koren Spring 2008 Copyright 2008 Koren Carry Look Ahead Addition Revisited Generalizing equations for fast adders carry look ahead carry select and carry skip Notation Pi j propagated carry Gi j group generated carry group for group of bit positions i i 1 j i j Pi j 1 when incoming carry into least significant position j cj is allowed to propagate through all i j 1 positions Gi j 1 when carry is generated in at least one of positions j to i and propagates to i 1 ci 1 1 Generalization of previous equations Special case single bit position functions Pi and Gi CE666 Koren Part 5b 2 Copyright 2008 Koren Group Carry Functions Boolean equations Pi i Pi Gi i Gi Recursive equations can be generalized i m j 1 Same generalization used for deriving section carry propagate and generate functions P and G Proof induction on m CE666 Koren Part 5b 3 Copyright 2008 Koren Fundamental Carry Operator Boolean operator fundamental carry operator Using the operator Pi j Gi j Pi m Gi m Pm 1 j Gm 1 j i m j 1 Operation is associative Operation is idempotent Therefore Pi j Gi j Pi m Gi m Pv j Gv j v m 1 CE666 Koren Part 5b 4 i m v j Copyright 2008 Koren Individual Bit Carry Sum Group carries Pi j and Gi j calculated from subgroup carries subgroups are of arbitrary size and may even overlap Group and subgroup carries used to calculate individual bit carries ci 1 ci cj 1 and sum outputs si si 1 sj Must take into account external carry cj For the mth bit position i m j rewritten as If Pm xm ym then sm cm Pm If Pm xm ym then sm cm xm ym CE666 Koren Part 5b 5 Copyright 2008 Koren Various Adder Implementations Equations can be used to derive various implementations of adders ripple carry carry look ahead carry select carry skip etc 5 bit ripple carry adder All subgroups consist of a single bit position computation starts at position 0 proceeds to position 1 and so on 16 bit carry look ahead adder 4 groups of size 4 ripple carry among groups CE666 Koren Part 5b 6 Copyright 2008 Koren Brent Kung Adder Variant of carry look ahead adder blocking factor of 2 very regular layout tree with log2n levels total area n log2n Consider c16 incoming carry at stage 16 in a 17bit or more adder and suppose G0 x0 y0 P0 c0 The part that generates P7 0 G7 0 corresponds to Each line except c0 represents two signals either xm ym or Pv m Gv m CE666 Koren Part 5b 7 Copyright 2008 Koren Tree Structure for Calculating C16 CE666 Koren Part 5b 8 Copyright 2008 Koren Carry Calculation Circuits in levels 2 to implement op c16 G15 0 Pm xm ym s16 c16 P16 5 fundamental carry sum Tree structure also generates carries c2 c4 and c8 Carry bits for remaining positions can be calculated through extra subtrees that can be added Once all carries are known corresponding sum bits can be computed Above blocking factor 2 Different factors for different levels may lead to more efficient use of space and or shorter interconnections CE666 Koren Part 5b 9 Copyright 2008 Koren Prefix Adders The BK adder is a parallel prefix circuit a combinational circuit with n inputs x1 x2 xn producing outputs x1 x2 x1 xn xn 1 x1 is an associative binary operation First stage of adder generates individual Pi and Gi Remaining stages constitute the parallel prefix circuit with fundamental carry operation serving as the associative binary operation This part of tree can be designed in different ways CE666 Koren Part 5b 10 Copyright 2008 Koren Implementation of the 16 bit BrentKung Adder CE666 Koren Part 5b 11 Copyright 2008 Koren Brent Kung Parallel Prefix Graph Bullets implement the fundamental carry operation empty circles generate individual Pi and Gi Number of stages and total delay can be reduced by modifying structure of parallel prefix graph Min of stages log2n 4 for n 16 For BK parallel prefix graph 1 CE666 Koren Part 5b 12 2log2n Copyright 2008 Koren Ladner Fischer Parallel Prefix Adder Implementing a 4 stage parallel prefix graph Unlike BK LF adder employs fundamental carry operators with a fan out 2 blocking factor varies from 2 to n 2 Fan out n 2 requiring buffers adding to overall delay CE666 Koren Part 5b 13 Copyright 2008 Koren Kogge Stone Parallel Prefix Adder log2n stages but lower fan out More lateral wires with long span than BK requires buffering causing additional delay CE666 Koren Part 5b 14 Copyright 2008 Koren Han Carlson Parallel Prefix Adder Other variants small delay in exchange for high overall area and or power Compromises between wiring simplicity and overall delay A hybrid design combining stages from BK and KS 5 stages middle 3 resembling KS wires with shorter span than KS CE666 Koren Part 5b 15 Copyright 2008 Koren Ling Adders Variation of carry look ahead simpler version of group generated carry signal reduced delay Example A carry look ahead adder groups of size 2 produces signals G1 0 P1 0 G3 2 P3 2 Outgoing carry for position 3 c4 G3 0 G3 2 P3 2 G1 0 where G3 2 G3 P3 G2 G1 0 G1 P1 G0 P3 2 P3 P2 Either assume c0 0 or set G0 x0 y0 P0 c0 Also Pi Xi Yi G3 0 G3 P3 G2 P3 P2 G1 P1 G0 since G3 G3 P3 G3 0 P3 H3 0 where H3 0 H3 2 P2 1 H1 0 H3 2 G3 G2 H1 0 G1 G0 Note P2 1 used instead of P3 2 before CE666 Koren Part 5b 16 Copyright 2008 Koren Ling Adders Cont H alternative to carry generate G Similar recursive calculation No simple interpretation like G Simpler to calculate Example H3 0 G3 G2 P2P1 G1 G0 Simplified H3 0 G3 G2 P2G1 P2P1G0 While G3 0 G3 P3G2 P3P2G1 P3P2P1G0 Smaller maximum fan in simpler faster circuits Variations of G have corresponding variations for H G3 0 G3 P3G2 0 H 3 0 G3 T2H2 0 where T2 x2 y2 General expression for H Hi 0 Gi Ti 1Hi 1 0 where Ti 1 xi 1 yi 1 CE666 Koren Part 5b 17 Copyright 2008 Koren Calculation of Sum Bits in Ling Adder Slightly more involved than for carry lookahead Example Calculation of H2 0 faster than c3 delay reduced Other variations of carry look ahead and implementations of Ling adders appear in literature CE666 Koren Part 5b 18 Copyright 2008 Koren Carry Select Adders n bits divided into non overlapping groups of possibly different lengths similar to adder conditional sum Each group generates two sets of sum and carry one assumes incoming carry into group is 0 the other 1 the l th group consists of k bit positions starting with j and ending with i j …