THE CHIP COMPLEXITY OF BINARY ARITHMETIC

R. P. BRENT AND H. T. KUNG

Abstract

The chip complexity of a computation is concerned with the chip area, A, and the time, T, required to perform the computation when implemented on a chip. An area-time product AT^{α}, for α ≥ 0, is used as a complexity measure. A particular value of α, which is chosen by the user, reflects the relative importance of A and T. We give both upper and lower bounds on the areatime complexity for chips that implement binary arithmetic, assuming a model of computation which is intended to approximate current and anticipated LSI or VLSI technology.

Comments

Only the Abstract is given here. The full paper appeared as [2]. The case α = 1 was considered independently (using a more restrictive model than ours) by Abelson and Andreae [1]. Bounds for binary multiplication are also considered in [3], and the upper bound for binary addition is considered in more detail in [4]. For an extension of the lower bounds to problems with only a 1-bit output, see [5].

References

1. H. Abelson and P. Andreae, “Information transfer and area-time trade-offs for VLSI multiplication”, Communications of the ACM 23 (1980), 20–23.

2. R. P. Brent and H. T. Kung, “The chip complexity of binary arithmetic” Proc. Twelfth Annual ACM Symposium on the Theory of Computing, ACM, New York, 1980, 190–200. rpb053.

3. R. P. Brent and H. T. Kung, “The area-time complexity of binary multiplication”, Journal of the ACM 28 (1981), 521–534. CR 22#38242, MR 82i:68027. Corrigendum: ibid 29 (1982), 904. MR 83j:68046. rpb055.

4. 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. rpb060.

1991 Mathematics Subject Classification. Primary 68Q35; Secondary 65Y05, 68M07, 68Q25.

Key words and phrases. Area-time complexity, binary addition, binary multiplication, chip design, chip layout, circuit design, combinational logic, chip complexity, lower bounds, VLSI.

CR Categories. 5.25, 6.1, 6.32.

Received August 1979; revised March 1980; accepted April 1980.

This research was supported in part by the National Science Foundation under Grant MCS 78-236-76 and the Office of Naval Research under Contracts N00014-76-C-0370 and N00014-80-C-0236. Most of this work was carried out at the Australian National University while H. T. Kung was there as a Visiting Fellow during May 1979.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1980, ACM. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb053a typeset using AMS-L^{A}TEX 2 RPB053A, BRENT AND KUNG

5. R. P. Brent and L. M. Goldschlager, “Some area-time tradeoffs for VLSI”, SIAM J. on Computing 11 (1982), 737–747. MR 83k:68024. rpb064. (Brent) Department of Computer Science, Australian National University, Canberra (Kung) Department of Computer Science, Carnegie-Mellon University, Pittsburgh