skip to main content
10.1145/800076.802483acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article
Free Access

The entropic limitations on VLSI computations(Extended Abstract)

Published:11 May 1981Publication History

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. 1.H. Abelson and P. Andreae, "Information transfer and area-time tradeoffs for VLSI multiplications," Comm. ACM 23 (1980), 20-23. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. 2.R. P. Brent and L. M. Goldschlager, "Some area-time tradeoffs for VLSI," August 1980, draft.Google ScholarGoogle Scholar
  3. 3.R. P. Brent and H. T. Kung, "The chip complexity of binary arithmetics," Proc. 12-th Ann. ACM Symp. on Theory of Computing, April 1980, Los Angeles, California, 190-200. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. 4.R. P. Brent and H. T. Kung, "On the area of binary tree layouts," Information Processing Letters 11 (1980), 46-48.Google ScholarGoogle ScholarCross RefCross Ref
  5. 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.Google ScholarGoogle Scholar
  6. 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.Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. 7.H. T. Kung and C. E. Leiserson, "Systolic arrays for VLSI," in the book by Mead and Conway (reference {8}), Section 8.3.Google ScholarGoogle Scholar
  8. 8.R. J. Lipton, S. C. Eisenstat, and R. A. DeMillo, "Space and time hierarchies for classes of control structure and data structures," Journal ACM 23(1976), 720-732. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. 9.C. Mead and L. Conway, Introduction to VLSI Systems, Addison-Wesley, Reading, Mass., 1980. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. 10.A. L. Rosenberg, private communication, March 1980.Google ScholarGoogle Scholar
  11. 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.Google ScholarGoogle Scholar
  12. 12.C. D. Thompson, "Area-time complexity for VLSI," Proc. 11-th Ann. ACM Symp. on Theory of Computing, April 1979, Atlanta, Gerogia, 81-88. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. 13.C. D. Thompson, A Complexity Theory for VLSI, Ph.D. thesis, Carnegie-Mellon University, August 1980. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. 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.Google ScholarGoogle Scholar
  15. 15.S. Winograd, "On the time required to perform multiplication," Journal ACM 14(1967), 793-802. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. 16.A. C. Yao, "Some complexity questions related to distributive computing," Proc. 11-th Ann. ACM Symp. on Theory of Computing, April 1979, Atlanta, Georgia, 209-213. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. The entropic limitations on VLSI computations(Extended Abstract)

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in
        • Published in

          cover image ACM Conferences
          STOC '81: Proceedings of the thirteenth annual ACM symposium on Theory of computing
          May 1981
          390 pages
          ISBN:9781450373920
          DOI:10.1145/800076

          Copyright © 1981 ACM

          Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 11 May 1981

          Permissions

          Request permissions about this article.

          Request Permissions

          Check for updates

          Qualifiers

          • Article

          Acceptance Rates

          Overall Acceptance Rate1,469of4,586submissions,32%

          Upcoming Conference

          STOC '24
          56th Annual ACM Symposium on Theory of Computing (STOC 2024)
          June 24 - 28, 2024
          Vancouver , BC , Canada

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader