The chip complexity of binary arithmetic

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&agr;,for &agr; ≥ 0, is used as a complexity measure. A particular value of &agr;, which is chosen by the user, reflects the relative importance between A and T. This paper derives lower and upper 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.

REFERENCES

• 1: Harold Abelson , Peter Andreae, Information transfer and area-time tradeoffs for VLSI multiplication, Communications of the ACM, v.23 n.1, p.20-23, Jan. 1980 [doi>10.1145/358808.358814]
• 2: R. J. Bonneau, A CLASS OF FINITE COMPUTATION STRUCTURES SUPPORTING THE FAST FOURIER TRANSFORM, Massachusetts Institute of Technology, Cambridge, MA, 1973
• 3: Brent, R.P. and Kung, H.T. A Regular Layout for Parallel Adders. Technical Report, Carnegie-Mellon University, Department of Computer Science, June, 1979.
• 4: R. P. Brent , H. T. Kung, The Area-Time Complexity of Binary Multiplication, Journal of the ACM (JACM), v.28 n.3, p.521-534, July 1981 [doi>10.1145/322261.322269]
• 5: Brent, R.P. and Kung, H.T. On the Area of Binary Tree Layouts. Technical Report TR-CS-79-07, The Australian National University, Department of Computer Science, July, 1979.
• 6: Brent, R. P. On the addition of binary numbers. IEEE Transactions on. Computers C-19:758–579, 1970.
• 7: Brent, R.P. The Complexity of Multiple-precision Arithmetic. In Anderssen, R.S. and Brent, R.P., editors, The Complexity of Computational Problem Solving, pages 126–165. University of Queensland Press, Brisbane, Australia, 1976.
• 8: Garner, H.L. A Survey of Some Recent Contributions to Computer Arithmetic. IEEE Transactions on Computers C-15:1277–1282, 1976.
• 9: Jackson, L.B., Kaiser, S.F. and McDonald, H.S. An Approach to the Implementation of Digital Filters. IEEE Trans. Audio and Electroacoust. AU-16:413–421, September, 1968.
• 10: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 11: Kung, H.T. and Leiserson, C.E. Systolic Arrays (for VLSI). In Duff, I. S. and Stewart, G. W., editor, Sparse Matrix Proceedings 1978, pages 256–282. Society for Industrial and Applied Mathematics, 1979. A slightly different version appears in Introduction to VLSI Systems by C. A. Mead and L. A. Conway, Addison-Wesley, 1980, Section 8.3.
• 12: Ladner, R.E. and Fischer, M.J. Parallel Prefix Computation. In 1977 International Conference on Parallel Processing, pages 213–223. IEEE, 1977.
• 13: Leiserson, C.E. Area-Efficient Graph Layouts (for VLSI). Technical Report, Carnegie-Mellon University, Department of Computer Science, February, 1980.
• 14: Linnik, U.V. On the Least Prime in an Arithmetic Progression. I. The Basic Theorem. Rec. Math. 15:139–178, 1944.
• 15: Lyon, R.F. Two's Complement Pipeline Multipliers. IEEE Transactions on Communications COM-24(4):418–425, April, 1976.
• 16: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 17: Mead, C.A. and Rem, M. Cost and Performance of VLSI Computing Structures. IEEE Journal of Solid State Circuits SC-14(2):455–462, April, 1979.
• 18: Ofman, Y. On the Algorithmic Complexity of Discrete Functions. Dokl. Akad. Nauk SSSR 145:48–51, 1962. In Russian.
• 19: Rosser, J.B, and Schoenfeld, L. Approximate Formulas for Some Functions of Prime Numbers. Illinois J. Math. 6:64–94, 1962.
• 20: Savage, J.E. and Swamy, S. Space-Time Tradeoffs for Oblivious Sorting and Integer Multiplication. Technical Report 37, Brown University, Department of Computer Science, 1978.
• 21: John E. Savage, The Complexity of Computing, Krieger Publishing Co., Inc., Melbourne, FL, 1987
• 22: John E. Savage. Area-Time Tradeoffs for Matrix Multiplication and Related Problems in VLSI Models. Technical Report CS-50, Brown University, Department of Computer Science, August, 1979.
• 23: Schonhage A. and Strassen, V. Schnelle Multiplikation grosser Zahlen. Computing 7:281–292, 1971.
• 24: C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804401]
• 25: Tung, C. Arithmetic. In Cardenas, A.F., Press, L. and Marin, M.A., editors, Computer Science. Wiley-Interscience, New York, 1972.
• 26: Wagstaff, S.S., Jr. Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus. Math. Comp. 33:1073–1083, 1979.
• 27: Wallace, C.S. A Suggestion for a Fast Multiplier. IEEE Trans. Elec. Comp. EC-13:14–17, 1964.
• 28: S. Winograd, On the Time Required to Perform Addition, Journal of the ACM (JACM), v.12 n.2, p.277-285, April 1965 [doi>10.1145/321264.321279]
• 29: Yaglom, I.M. and Boltyanskii, V.G. Convex Figures. Holt, Rinehart and Winston, New York, 1961. Translated by P.J. Kelly and L.F. Walton.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Arithmetic and logic units

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Proof theory

General Terms:
Theory