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).


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.


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.)


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