Prefix tree adder with efficient carry generation

The present invention relates generally to electronic circuits and more particularly to adder circuits for use in semiconductor integrated circuits and other electronic devices.

As a result of ever-shrinking very large scale integration (VLSI) process geometries, it has become necessary to reexamine the tradeoffs that have been made in the existing design and implementation of computer arithmetic algorithms. Algorithms utilizing the so-called carry lookahead technique, as described in A. Weinberger and J. L. Smith, “A One-Microsecond Adder Using One-Megacycle Circuitry,” IRE Trans. on Electronic Computers, pp. 65-73, June 1956, speed up the addition process by unrolling a recursive carry equation. Both transistor count and interconnection complexity have typically limited the maximum unrolling to 4 bits. Larger adders have been built as block carry-lookahead adders, where the lookahead operation occurs within small blocks, as described in T.-F. Ngai et al., “Regular, Area-Time Efficient Carry-Lookahead Adders,” Journal of Parallel and Distributed Computing, Vol. 3, pp. 92-105, 1986.

The recursive carry computation can also be reduced to a prefix computation, as described in, e.g., P. M. Kogge and H. S. Stone, “A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations,” IEEE Trans. on Computers, Vol. C-22, No. 8, pp. 786-793, August 1973. As described in R. P. Brent and H. T. Kung, “A Regular Layout for Parallel Adders,” IEEE Trans. on Computers, Vol. C-31, No. 3, pp. 260-264, March 1982, a prefix tree can be used to compute the carry at the most-significant bit position, and an additional tree superimposed on the prefix tree can be used to compute the intermediate carries. Faster computation of all the carries can be achieved by using a separate prefix tree for each bit position, as described in D. Dozza et al., “A 3.5 NS, 64 Bit, Carry-Lookahead Adder,” in Proc. Intl. Symp. Circuits and Systems, pp. 297-300, 1996.

A problem associated with the above-noted full prefix tree adders, which are also known as Kogge-Stone adders, is the additional delay introduced as a result of exponentially growing interconnection complexity. Existing architecture tradeoffs have emphasized reduction of interconnection complexity at the expense of higher gate fanouts. Interconnection complexity can also be reduced by using hybrid carry lookahead/carry select architectures which eliminate the need to implement a full prefix tree for each bit position. The use of low resistance and low capacitance materials can reduce the negative effects of architectures that depend on large amounts of interconnect, as described in J. Silberman et al., “A 1.0 GHz Single-Issue 64b PowerPC Integer Processor,” IEEE Intl. Solid-State Circuits Conf., pp. 230-231, February 1998. Furthermore, with additional levels of interconnect, the area overhead required to implement such adders is alleviated through the use of extensive “over-the-cell” routing, which removes the routing channels and further minimizes the interconnect capacitance.

The operation of conventional prefix tree adders will be described in greater detail with reference to FIGS. 1 and 2. In a general n-bit prefix tree adder, the addition of two numbers A and B, A = - a n - 1  2 n - 1 + ∑ j = 0 n - 2  a j  2 j B = - b n - 1  2 n - 1 + ∑ j = 0 n - 2  b j  2 j ,

represented in two's complement binary form, can be accomplished by computing: g j = a j  b j p j = a j ⊕ b j c j = g j + p j  c j - 1 s j = p j ⊕ c j - 1 }     ∀ j , 0 ≤ j < n ,

where c −1 is the primary carry-input. The signals designated g j , p j and c j are referred to herein as generate, propagate and carry signals, respectively; The resulting sum of A and B is S = - s n - 1  2 n - 1 + ∑ j = 0 n - 2  s j  2 j .

An overflow occurs, and the resulting sum is invalid, if

c n−1 ⊕c n−2 =1.

The above-cited Dozza et al. reference defines (G j j , P j j )=(g j , p j ), and

( G i j ,P i j )=( g j ,p j ) o ( g j−1 ,p j−1 ) o . . . o ( g i ,p i ) if j>i,

where o is the fundamental carry operator described in the above-cited Brent and Kung reference and defined as

( g j ,p j ) o ( g i ,p i )=(( g j +p j g i ), p j p i )

The fundamental carry operator o is both associative and idempotent. At each bit position, the carry is given by

c j =G 0 j +P 0 j c −1   (1)

where c −1 is the primary carry input. If there is no primary carry input, then c j is simply G 0 j .

FIG. 1 shows a set of superimposed prefix trees 10 for a prefix tree adder in which the computation of (G 0 j , P 0 j )∀j can be accomplished in ┌log 2 n┐ stages. In the set of prefix trees 10 , n=16. A complete n-bit prefix tree adder with a set of prefix trees of the type shown in FIG. 1 can be constructed by implementing the following steps.

Calculate g j =a j b j and p j =a j ⊕b j ∀j 0≦j<n.

For k=1 . . . ┌log 2 n┐ calculate

( G 0 j ,P 0 j )=( G j−2 k−1 +1 j , P j−2 k−1 +1 j ) o ( G 0 j−2 k−1 ,P 0 j−2 k−1 )∀ j 2 k−1 ≦j <2 k −1

( G j−2 k +1 j ,P j−2 k +1 j )=( G j−2 k−1+1 j ,P j−2 k−1 +1 j ) o ( G j−2 k +1 j−2 k−1 ,P j−2 k +1 j−2 k−1 )∀ j 2 k −1 ≦j<n.

Calculate c j =G 0 j +P 0 j c −1 ∀j 0≦j<n.

Calculate s j =p j ⊕c j−1 ∀j 0≦j<n.

In the set of prefix trees 10 of FIG. 1, the open squares at the top compute propagate signals p j and generate signals g j for each bit position in accordance with Step 1, the empty circles apply the fundamental carry operator in accordance with Step 2, and the filled circles represent buffers. The last stage, shown as crossed circles in FIG. 1, applies equation (1) to every (G 0 j , P 0 j ) in accordance with Step 3. The output of this stage is the carry at each bit position. An additional sum generation stage (not shown) is needed to generate the sum at each bit position from the p j signal and the carry from the previous bit position in accordance with Step 4. A complete 16-bit adder includes the set of prefix trees 10 plus this sum generation stage for implementing Step 4. The logic depth of an n-bit adder of the type illustrated in FIG. 1 is 3+┌log 2 n┐. If there is no carry input, then the last stage of the set of prefix trees shown in FIG. 1 is not needed.

FIG. 2 illustrates an alternative set of superimposed prefix trees 20 , also for the case n=16. Again, it should be noted that a complete adder of this type would include the set of prefix trees as well as a sum generation stage. In the set of prefix trees 20 , the contribution due to the carry input is incorporated by redefining the first generate in the set of prefix trees as

g 0 =a 0 b 0 +( a 0 +b 0 ) c −1   (2)

Such a technique is described in the above-cited Dozza et al. reference. With this change,

G

0

j

=c

j

∀j.

The polygon in FIG. 2 implements equation (2). This replaces the hardware required to implement Step 3 above and reduces the fanout on the c −1 input from n to 1. However, the logic depth remains 3+┌log 2 n┐ and the overall delay of the adder is unchanged.

An additional speedup in the sets of superimposed prefix trees of FIGS. 1 and 2 can be achieved by using transmit signals t j instead of propagate signals p j to compute carries for each bit position. The final sum computation still requires the propagate signals p j to be generated from the primary inputs. The addition operation in this case is defined as g j = a j  b j t j = a j + b j c j = g j + t j  c j - 1 s j = ( a j ⊕ b j ) ⊕ c j - 1 }     ∀ j , 0 ≤ j < n ,

where (G j j , T j j )=(g j , t j ), and

( G i j ,T i j )=( g j ,t j ) o ( g j−1 ,t j−1 ) o . . . o ( g i ,t i ) if j>i,

where o is the fundamental carry operator. The computation of (G 0 j , T 0 j )∀j follows the same methodology as in Step 2 above for (G 0 j , P 0 j ). The carry c j for each bit position is then given by

c

j

=G

0

j

+T

0

j

c

−1

where c −1 is the primary carry input. If there is no primary carry input, then c j is simply G 0 i . The t j signals can be computed faster than the p j signals since an OR gate is typically faster than an XOR gate. Hence, the carry computation through the prefix trees can start slightly earlier if the transmit signals are used. Since the sum generation step still uses the propagate signals, the load on the transmit signals in this architecture is smaller than the load on the propagate signals in the FIGS. 1 and 2 architectures. However, the load on the input signals is now higher since both transmit and propagate signals need to be generated. For example, in the set of prefix trees 10 of FIG. 1, the open squares at the top would now need to compute the transmit signals in addition to the generate and propagate signals. The remaining circles will then operate on the transmit signals instead of the propagate signals.

Although the above-described conventional prefix tree adders can provide acceptable performance in certain applications, further improvements are needed, particularly in terms of parameters such as logic depth, delay and circuit area.

The invention provides a prefix tree adder in which the contribution due to a primary carry input is incorporated into each of at least a subset of prefix trees without introducing any significant additional overall delay. In an illustrative embodiment, the adder includes a set of prefix trees, with a given one of the prefix trees corresponding to each bit position. An n-bit prefix tree adder therefore includes n prefix trees, each associated with a bit position of the adder and including a number of computation stages. The prefix trees are interconnected such that carry signals are computed at least partially in parallel. For example, a carry signal computed in an initial stage of a given prefix tree is used in subsequent stages of the given prefix tree without introducing substantial additional delay in computation of other carry signals in other prefix trees associated with higher bit positions. Carries computed for lower bit positions are thus used to compute carries for higher bit positions, but generate, propagate and/or transmit signals may be generated in an initial stage of each of the prefix trees without utilizing a primary carry input signal in the computation.

The adder architecture of the present invention provides a reduced logic depth, delay and circuit area relative to conventional architectures. The techniques of the invention are applicable to a wide variety of prefix tree adders, including both radix-2 adders and non-radix-2 adders. These and other features and advantages of the present invention will become more apparent from the accompanying drawings and the following detailed description.

FIGS. 1 and 2 show sets of prefix trees for conventional 16-bit prefix tree adders.

FIG. 3 shows a set of prefix trees for a prefix tree adder with carry incorporated into the trees, in accordance with a first illustrative embodiment of the present invention.

FIG. 4 illustrates a complete prefix tree adder including a set of prefix trees of the type shown in FIG. 3 and a sum generation stage.

FIG. 5 shows a set of prefix trees for a prefix tree adder with carry incorporated into the trees, in accordance with a second illustrative embodiment of the present invention.

FIGS. 6 through 9 show examples of circuits which incorporate a prefix tree adder in accordance with the invention.

The present invention will be illustrated below in conjunction with exemplary prefix tree adders. It should be understood, however, that the invention is not limited to use with any particular type of adder, but is instead more generally applicable to any carry-lookahead adder in which it is desirable to provide a significant reduction in critical path delay without unduly increasing the cost or complexity of the adder circuit. For example, although illustrated using radix-2 carry-lookahead prefix tree adders, it will be apparent to those skilled in the art that the disclosed techniques are readily applicable to other types of adders, including non-radix-2 adders.

In accordance with the invention, a primary carry input signal can be incorporated into a set of prefix trees of a prefix tree adder without introducing additional delay. In the illustrative embodiments to be described below, the carries in the prefix tree adder are computed by using a separate prefix tree for each bit position. The adder architecture of the present invention reduces the logic depth, delay and circuit area of an n-bit adder, compared to existing architectures such as those illustrated in FIGS. 1 and 2. For example, it will be shown below that a fully-static 32-bit radix-2 prefix tree adder configured in accordance with the invention has a delay on the order of 1.0 nsec in a 0.25 μm static CMOS implementation.

FIG. 3 shows a set of superimposed prefix trees 30 for a 16-bit prefix tree adder in accordance with a first illustrative embodiment of the invention. In the above-described conventional set of prefix trees 20 of FIG. 2, redefining the first generate in accordance with equation (2) affects the delay at every bit position. The set of prefix trees 30 overcomes this limitation of the prior art by: (i) allowing the first generate signal and propagate and/or transmit signals to be used unchanged in the first stage of each of the prefix trees, and (ii) computing the carries in parallel. For example, the carry c 0 computed by the prefix tree associated with the first bit position can then be used in subsequent stages of the prefix tree without affecting the delay of the carry computations for the higher bit positions. The general algorithm for an n-bit radix-2 prefix tree adder of this type is described below.

Calculate g j =a j b j and p j =a j ⊕b j ∀j 0≦j<n.

For k=1 . . . ┌log 2 n┐ calculate

c j =G j−2 k−1 +1 j +P j−2 k−1 +1 j c j−2 k−1 ∀j 2 k−1 −1 ≦j <2 k −1  (3)

( G j−2 k +1 j ,P j−2 k +1 j )=( G j−2 k−1 +1 j ,P j−2 k−1 +1 j ) o ( G j−2 k +1 j−2 k−1 ,P j−2 k +1 j−2 k−1 )∀ j 2 k −1 ≦j<n.   (4)

Calculate

s j =p j ⊕c j−1 ∀j 0 ≦j<n   (5)

and

c n−1 =G 0 n−1 +P 0 n−1 c −1 .  (6)

In the set of prefix trees of FIG. 3, the open squares at the top compute p j and g j for each bit position in accordance with Step 1. The crossed circles implement equation (3) in Step 2 and equation (6) in Step 3 above. The empty circles apply the fundamental carry operator in accordance with equation (4) in Step 2, and the filled circles are buffers. A complete prefix tree adder will generally include an additional stage (not shown in FIG. 3) to generate the sum at each bit position from the p j signal and the carry from the previous bit position in accordance with equations (5) and (6), respectively, of Step 3. The sum computation of equation (5) occurs in parallel with the computation of the final carry output c n−1 . FIG. 4 shows a complete prefix tree adder 30 ′ which includes the set of superimposed prefix trees 30 of FIG. 3 as well as the additional stage for generating the sum at each bit position.

The logic depth of an n-bit prefix tree adder configured as shown in FIG. 3 is 2+┌log 2 n┐, and the fanout of the carry input c −1 is 1+┌log 2 n┐. By way of comparison, a conventional n-bit prefix tree adder configured as shown in FIG. 1 has a logic depth of 3+┌log 2 n┐, and the fanout of its carry input c −1 is n. It should be noted that the above-described algorithm can also be extended in a straightforward manner to higher radix prefix trees.

As will be described in greater detail below in conjunction with FIG. 5, c n−1 in Step 3 above can also be calculated as, for example, c n−1 =g n−1 +p n−1 c n−2 . This does not affect the overall delay of the adder, but reduces area by eliminating the need to compute G 0 n−1 and P 0 n−1 in the prefix tree.

An alternative embodiment of the invention uses the transmit signals t j instead of the propagate signals p j . The corresponding algorithm for a radix-2 prefix tree adder is described below.

Calculate g j =a j b j , t j =a j +b j , and p j =a j ⊕b j ∀j 0≦j<n.

For k=1 . . . ┌log 2 n┐ calculate

c j =G j−2 k−1 +1 j +T j−2 k−1 +1 j c j−2 k−1 ∀j 2 k−1 −1 ≦j <2 k −1

( G j−2 k +1 j ,T j−2 k +1 j )=( G j−2 k−1 +1 j ,T j−2 k−1 +1 j ) o ( G j−2 k +1 j−2 k−1 ,T j−2 k +1 j−2 k−1 )∀ j 2 k −1 ≦j<n.

Calculate

s j =p j ⊕c j−1 ∀j 0 ≦j<n,

and

c n−1 =G 0 n−1 +T 0 n−1 c −1 .

In implementing the above algorithm using the set of prefix trees 30 of FIG. 3, the open squares at the top now need to compute the transmit signal in addition to the generate and propagate signals. The remaining circles operate on the transmit signals instead of the propagate signals.

In the adder architecture of FIG. 3, the previous stage carries, i.e., lower bit position carries, are used to produce the high order carries. The interconnect lines to the last stage of the carry generation need to run over a distance of n/2 bits. Also, to generate the block carry out c n−1 , the block carry in c −1 needs to run from bit position 0 to bit position n. The block carry out c n−1 in the FIG. 3 architecture with n=16 is computed as follows

c n−1 =G 0 15 +T 0 15 c −1 ,

and therefore requires an extra column of carry operators for calculating (G 0 n , T 0 n ). FIG. 5 shows an alternative set of superimposed prefix trees 50 in accordance with the invention for the n=16 embodiment. The set of prefix trees 50 implements the following computation

c 15 =G 15 +T 15 c 14 ,

thereby eliminating a number of long interconnection wires. This compensates for the increased capacitive load on c 14 .

The same approach can be applied to an intermediate carry out, i.e., carry out C 7 . In the FIG. 3 implementation, this carry out is generated by (G 0 7 , T 0 7 ) and c −1 as

c 7 =G 0 7 +T 0 7 c −1 .

Eliminating the cell which generates (G 0 7 , T 0 7 ) and using (G 4 7 , T 4 7 ) and c 3 to generate c 7 as

c

7

=G

4

7

+T

4

7

c

3

reduces the number total gates needed to implement the adder architecture. Since the fanout of the cell which generates (G 3 7 , T 3 7 ) is reduced from 2 to 1, and the fanout of c 3 is increased from 1 to 2, this approach balances the overall delay for c 3 generation.

The implementations described above in conjunction with FIG. 5 can be generalized for an n-bit prefix tree adder with carry input incorporated into the tree. The block carry out in this case would be generated as

c n−1 =G n−1 n−1 +T n−1 n−1 c n−2 .

The first (from the right) intermediate carry for every carry generation starting with c 7 would be generated as follows

c j−1 =G j/2 j−1 +T j/2 j−1 c j/2−1 ,

where j=8, 16, 32, 64, etc.

For purposes of illustrating the advantages of the invention, 32-bit versions of the prefix tree adder architectures shown in FIGS. 1 and 3 were implemented using a 0.25 μm CMOS process, with fully static circuits. The layout area of the 32-bit adder using the conventional FIG. 1 architecture was approximately 350 μm×115 μm (˜0.04 mm 2 ), while the layout area of the 32-bit adder using the FIG. 3 architecture of the present invention was significantly smaller, i.e., 350 μm×80 μm (˜0.03 mm 2 ). The delay of the 32-bit adder using the conventional FIG. 1 architecture was determined to be on the order of 1.1 ns, while the delay of the 32-bit adder using the FIG. 3 architecture was determined to be approximately 10% less, i.e., 1.0 ns. The power consumption of the 32-bit adders for the FIG. 1 and FIG. 3 architectures was approximately the same, on the order of 32 mW at 400 MHZ and a Vdd supply voltage of 2.5 volts.

Although static circuits were used in the above-described 32-bit implementations, it should be noted that the invention may be implemented using either static circuits, dynamic circuits or combinations of both static and dynamic circuits. Static circuits are often preferred to dynamic circuits because of their ease of design. In addition, static circuits generally consume less area and power because they do not need clocks to precharge internal nodes.

FIGS. 6 through 9 illustrate a number of circuits, each of which incorporate one or more prefix tree adders in accordance with the invention. In each of these example circuits, the vertical arrows indicate the bit flow between the various circuit elements.

FIG. 6 shows an exemplary embodiment of a data arithmetic unit (DAU) 100 which includes a bit manipulation unit (BMU) 102 , an arithmetic logic unit (ALU)/add-compare-subtract (ACS) 104 , an adder 106 , a multiplexer 108 and saturate logic 110 . Prefix tree adders in accordance with the invention may be used for the adder 106 and/or incorporated into the ALU/ACS 104 . FIG. 7 shows the ALU/ACS 104 of FIG. 6 in greater detail. The ALU/ACS 104 includes a flag generator 122 and a prefix tree adder 124 . FIG. 8 shows an exemplary multiply-add unit 125 which includes a Y register 126 , an X register 127 , a partial product generation element 128 , an adder 130 and a P register 132 . FIG. 9 shows a comparator 140 which includes a register 142 , a subtractor 144 and a result evaluation element 146 . The adder 130 of FIG. 8 and the subtractor 144 of FIG. 9 are implemented as one or more prefix tree adders in accordance with the invention. It should be emphasized that FIGS. 6 through 9 are illustrative only, and therefore should not be construed as limiting the invention to use in certain types of circuits.

The above-described illustrative embodiments of the invention may be configured to meet the requirements of a variety of different circuit applications, using any desired value of n. As noted above, adders in accordance with the invention may be.used to implement circuits such as, e.g., ALUs, multiply-add units, and comparators. The invention can be incorporated in integrated circuits used in numerous applications, including microprocessors, memory circuits and telecommunications hardware. Moreover, as previously noted, a variety of other types of adders, including non-radix-2 adders, may also make use of the techniques of the present invention. These and numerous other alternative embodiments may be devised by those skilled in the art without departing from the scope of the following claims.