A regular layout for parallel adders
60. R. P. Brent and
H. T. Kung,
A regular layout for parallel adders,
IEEE Transactions on Computers C-31 (1982), 260-264.
MR 83b:68002.
Retyped 2000.
Abstract:
dvi (3K),
pdf (78K),
ps (27K).
Paper:
dvi (23K),
pdf (177K),
ps (70K).
Abstract
With VLSI architectures, the chip area and design regularity represent a
better measure of cost than the conventional gate count. We show that addition
of n-bit binary numbers can be performed on a chip with a regular
layout in time proportional to log n.
Errata
In Figure 5 of the original paper,
the processors at coordinates (4,5) and (2,6) should be
white rather than black. This is corrected in the retyped version.
(Note that the origin is at the bottom right of the Figure, and
the first coordinate increases from right to left.
Each black processor should have two inputs and two outputs.)
Comments
At the time of publication the use of carry-lookahead in VLSI designs
was unpopular, but more recently the
design technique proposed here has been applied widely in VLSI
implementations of adders.
For a prototype design, see [71].
A similar adder was suggested independently, at about the same time,
by A. Bilgory and D. D. Gajski,
"Automatic Generation of Cells for Recurrence Structures",
Proc. 18th Design Automation Conference, Nashville, Tennessee, 1981.
Related papers are Brent and Kung
[53,
56];
P. M. Kogge and H. S. Stone,
"A parallel algorithm for the efficient solution of a general class of
recurrence equations", IEEE Transactions on Computers C-22 (1973),
786-793;
and R. E. Ladner and M. J. Fischer,
"Parallel prefix computation", J. ACM 27 (1980), 831-838.
A survey of various adders suitable for VLSI implementation is
given in:
Reto Zimmermann,
Binary Adder Architectures for Cell-Based VLSI,
Ph.D thesis, ETH, Zurich, 1997;
also
Series in Microelectronics, Volume 73, Hartung-Gorre, Konstanz, 1998.
Go to next publication
Return to Richard Brent's index page