The chip complexity of binary arithmetic
53. R. P. Brent and
H. T. Kung,
The chip complexity of binary arithmetic,
Proceedings of the Twelfth Annual ACM Symposium
on the Theory of Computing,
ACM, New York, 1980, 190-200.
Abstract:
dvi (3K),
pdf (80K).
Paper:
pdf (675K).
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 ATalpha,
for non-negative alpha, is used as a complexity measure.
A particular value of alpha can be chosen to
reflect the relative importance of A and T.
We give both upper and lower bounds on the area-time 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
Similar results for the AT2 measure
were obtained independently by
Abelson and Andreae
[Communications of the ACM 23 (1980), 20-23],
using a more restrictive model than ours.
Bounds for binary multiplication are also considered
in Brent and Kung [55].
The upper bound for binary addition
is considered in more detail
in Brent and Kung [60].
For an extension of the results to problems with only a 1-bit output,
see Brent and Goldschlager [64].
Go to next publication
Return to Richard Brent's index page