Prefix tree adder with efficient carry generation

Details Prefix tree adder with efficient carry generation Prefix tree adder with efficient carry generation

1999-04-14

2003-03-04

Mai, Tan V. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S710000

Reexamination Certificate

active

06529931

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to electronic circuits and more particularly to adder circuits for use in semiconductor integrated circuits and other electronic devices.
BACKGROUND OF THE INVENTION
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.
Step 1 (1 stage):
Calculate g
j
=a
j
b
j
and p
j
=a
j
⊕b
j
∀j 0≦j<n.
Step 2 (┌log
2
n┐ stages):
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.
Step 3 (1 stage)
Calculate c
j
=G
0
j
+P
0
j
c
−1
∀j 0≦j<n.
Step 4 (1 stage)
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

Affiliated with

Also associated with

Rating

Prefix tree adder with efficient carry generation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Prefix tree adder with efficient carry generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prefix tree adder with efficient carry generation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3075409