Lower bounds for VLSI

ABSTRACT

Increased use of Very Large Scale Integration (VLSI) for the fabrication of digital circuits has led to increased interest in complexity results on the inherent VLSI difficulty of various problems. Lower bounds have been obtained for problems such as integer multiplication [1,2], matrix multiplication [7], sorting [8], and discrete Fourier transform [9], all within VLSI models similar to one originally developed by Thompson [8,9]. The lower bound results all pertain to a space-time trade-off measure that arises naturally within this model. In this paper, we extend the model and the class of functions for which non-trivial bounds can be proved. In Section 2, we give a more general model than has been proposed previously. In Section 3 we show how to reduce the derivation of lower bounds within the model to a problem in distributed computing In Section 4, we consider lower bounds for a number of predicates: n-input, l-output functions (as contrasted with the n-input, n-output functions which have been studied previously). In Section 5, we show that previous lower bound results (for n-input, n-output functions) also apply even when the model is extended to allow nondeterminism, randomness, and multiple arrivials. Finally, the full details of the results presented here will appear in the final version of this paper.

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 H. T. Kung, "The Area-Time Complexity of Binary Multiplication," Report No. CMU-CS-79-136, Dept. of Comp. Sci., Carnegie-Mellon U., Pittsburgh, Penn. (July, 1979).
• 3: P. Erdos and J. Spencer, Probabilistic Methods in Combinatorics Academic Press, 1974.
• 4: F. C. Hennie, "On-line Turing Machine Computations," IEEE Transactions on Electronic Computers EC-15 pp. 35-44 (1966).
• 5: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 6: R. J. Lipton and R. E. Tarjan, "Applications of a Planar Separator Theorem," SIAM J. of Computing August 1980, vol. 9 no. 3 pp. 615-627.
• 7: J. E. Savage, "Area-Time Tradeoffs for Matrix Multiplication and Related Problems in VLSI Models," Proc. 17th Allerton Conf. on Communication, Control, and Computing, pp. 670-676 (Oct. 10-12, 1979).
• 8: C. D. Thompson, "A Complexity Theory for VLSI," Report No. CMU-CS-, Dept. of Comp. Sci., Carnegie-Mellon U., Pittsburgh, Penn. (Sept. 16, 1979).
• 9: 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]
• 10: J. Vuillemin, "A Combinatorial Limit to the Computing Power of VLSI Circuits," Procs. 21st Ann. Symp. on Foundations of Comp. Sci., pp. 294-300 (Oct. 12-14. 1980).
• 11: 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:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

General Terms:
Algorithms, Design, Theory