The entropic limitations on VLSI computations(Extended Abstract)

ABSTRACT

In this paper we will explore the limitations imposed by entropic constraints, both in generality and for specific problems. We list below the main questions that we will address. (1) In the binary number system, addition is easy while multiplication is hard for VLSI. Is there an “ideal” number representation, in which all arithmetic operations have efficient VLSI implementations? (2) Can one build multipliers for binary numbers, which achieve both small area and fast average computation time? (3) Thompson's technique applies only to multiple output functions. How can one prove area-time bounds for single output functions? (4) What other ways are there for deriving entropic constraints from consideration of data movement? Answers to these questions will be discussed in the ensuing sections.

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. P. Brent and L. M. Goldschlager, "Some area-time tradeoffs for VLSI," August 1980, draft.
• 3: R. P. Brent , H. T. Kung, The chip complexity of binary arithmetic, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.190-200, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804666]
• 4: R. P. Brent and H. T. Kung, "On the area of binary tree layouts," Information Processing Letters 11 (1980), 46-48.
• 5: L.J. Guibas, H. T. Kung, and C. D. Thompson, "Direct VLSI implementation of combinatorial algorithms," Proc. Conf. on VLSI Architecture Design and Fabrication, 1979, CALTECH.
• 6: J. E. Hopcroft and R. M. Karp, "An n5/2 algorithm for maximum matchings in bipartite graphs," SIAM J. on Computing 2(1973), 225-231.
• 7: H. T. Kung and C. E. Leiserson, "Systolic arrays for VLSI," in the book by Mead and Conway (reference {8}), Section 8.3.
• 8: R. J. Lipton , S. C. Eisenstat , R. A. DeMillo, Space and Time Hierarchies for Classes of Control Structures and Data Structures, Journal of the ACM (JACM), v.23 n.4, p.720-732, Oct. 1976 [doi>10.1145/321978.321990]
• 9: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 10: A. L. Rosenberg, private communication, March 1980.
• 11: J. E. Savage, "Area-time tradeoffs for matrix multiplication and related problems in VLSI models," Proc. 17-th Ann. Allerton Conf. on Comm., Control and Computing, October 1979, Allerton, Illinois.
• 12: 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]
• 13: Clark David Thompson, A complexity theory for vlsi, 1980
• 14: J. Vuillemin, "A combinatorial limit to the computing power of VLSI circuits," Proc. 21-st Ann. IEEE Symp. on Foundations of Computer Science, October 1980, Syracuse, New York, 294-300.
• 15: S. Winograd, On the Time Required to Perform Multiplication, Journal of the ACM (JACM), v.14 n.4, p.793-802, Oct. 1967 [doi>10.1145/321420.321438]
• 16: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Theory