Area-time complexity for VLSI

ABSTRACT

The complexity of the Discrete Fourier Transform (DFT) is studied with respect to a new model of computation appropriate to VLSI technology. This model focuses on two key parameters, the amount of silicon area and time required to implement a DFT on a single chip. Lower bounds on area (A) and time (T) are related to the number of points (N) in the DFT: AT2≥ N2/16. This inequality holds for any chip design based on any algorithm, and is nearly tight when T &equil; &thgr;(N1/2) or T &equil; &thgr;(log N). A more general lower bound is also derived: ATx &equil; &Ohgr;(N1+x/2), for 0≤×≤2.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: R. J. Bonneau, A CLASS OF FINITE COMPUTATION STRUCTURES SUPPORTING THE FAST FOURIER TRANSFORM, Massachusetts Institute of Technology, Cambridge, MA, 1973
• 3: Cutler, M. and Shiloach, Y. Permutation layout. Networks 8:253-278, 1978.
• 4: M. R. Garey , D. S. Johnson , L. Stockmeyer, Some simplified NP-complete problems, Proceedings of the sixth annual ACM symposium on Theory of computing, p.47-63, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803884]
• 5: Grigoryev, Y. An application of separability and independence notions for proving lower bounds on circuit complexity. In Notes of Scientific Seminars, Vol. 60. Sleklov Mathematical Institute, Leningrad Dept., (translation courtesy of J. E. Savage, Brown University), 1976.
• 6: MacLane, Saunders and Birkhoff, Garrett, Algebra. The Macmillan Company, London, 1967.
• 7: Mead, Carver and Rom, Martin. Cost and Performance of VLSI Computing Structures. Technical Report 1584, California Institute of Technology Computer Science Department, 1978.
• 8: Moshell, Michael and Rothstein, Jerome. Parallel Recognition of Patterns: Insights from Formal Language Theory. International Conference on Parallel Processing, August, 1976.
• 9: Marshall C. Pease, An Adaptation of the Fast Fourier Transform for Parallel Processing, Journal of the ACM (JACM), v.15 n.2, p.252-264, April 1968 [doi>10.1145/321450.321457]
• 10: Savage, J. E. and Swami, Sowmitri. Space-Time Tradeoffs in the FFT Algorithm. Technical Report TRCS-31, Brown University, August 1977.
• 11: Sutherland, Ivan E. and Oestreicher, Donald. How big should a printed circuit board be?. IEEE Trans. Comput. C-22:537-542, May 1973.
• 12: Clark David Thompson, A complexity theory for vlsi, 1980
• 13: John Von Neumann , Arthur W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press, Champaign, IL, 1966
• 14: Winograd, S. On Computing the Discrete Fourier Transform. Technical Report RC 6291 (#27013), IBM T. J. Watson Research Center, November 1976.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures

General Terms:
Algorithms, Design, Measurement, Performance, Theory