Complexity theory and design automation

ABSTRACT

Complexity Theory is discussed and its relationship to Physical Design (i.e. Placement/Wiring) and Test Pattern Generation is shown and developed.

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: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 3: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• 4: See, e.g., L. J. Stockmeyer, "The polynomial - Time Hierarchy", Theoretical Computer Science 3 (1977).
• 5: P. K. Wolff, Sr, A. E. Ruehli, B. J. Agile, J. D. Lesser and G. Goertzel, "Power Timing: Optimization and Layout Techniques for LSI chips", J. of Design Autom. and Fault Tolerant Computing 2 pp. 145-164 (1978).
• 6: M. Hanan, P. K. Wolff, Sr., and B. J. Agule "A Study of Placement Techniques", J. Design Autom. and Fault Tolerant Computing 1, pp. 28-61.
• 7: B. S. Ting, E. S. Kuh, and A. Sangiovanni - Vincentelli "Via Assignment Problem in Multilayer Printed Circuit Board", IEEE Trans. on Circuits and Systems CAS-26 pp. 261-272 (April 1979).
• 8: W. E. Donath, "Placement and Average Interconnection Lengths of Computer Logic", IEEE Trans. on Circuits and Systems CAS-26, pp 272-276 (April 1979).
• 9: W. R. Heller, W. F. Mikhail, and W. E. Donath, "Prediction of Wiring Space Requirements for LSI", J. of Design Automation and Fault Tolerant Computing 2 pp 117-144 (1978).
• 10: B. S. Landman and R. L. Russo, "On a Pin vs. Block Relationship for Partitions of Logic Graphs", IEEE Trans. Comput. C-20 pp 1469-1479 (Dec. 1971).
• 11: W. E. Donath, "Equivalence of Memory to Random Logic", IBM J. of Res. and Development 18 pp 401-407 (1974); see also "Stochastic Model of The Computer Logic Design Process", IBM T. J. Watson Res. Ctr. Yorktown Heights, N. Y., Report RC 3136 (Nov. 5, 1970).
• 12: M. Hanan and J. M. Kurtzberg, "Placement Techniques", chapter 5 of M. A. Brener "Design Automation of Digital Systems" (Prentice-Hall Inc. Englewood Cliffs, N. J. 1972) pp 213-282.
• 13: S.B. Akers "Routing", chapter 6 of M. A. Breuer (see ref 12) pp 283-334.
• 14: A. Chandra and L. J. Stockmeyer, pvt. communication.
• 15: R. J. Preiss, "Fault Test Generation", chapter 7 of M. A. Breuer (see ref 12) pp 336-410.
• 16: Akihiko Yamada , Nobuo Wakatsuki , Hideo Shibano , Osamu Itoh , Kyouji Tomita , Shigehiro Funatsu, Automatic test generation for large digital circuits, Proceedings of the 14th conference on Design automation, p.78-83, January 1977
• 17: Thomas J. Snethen, Simulator-oriented fault test generator, Proceedings of the 14th conference on Design automation, p.88-93, January 1977
• 18: E. B. Eichelberger , T. W. Williams, A logic design structure for LSI testability, Proceedings of the 14th conference on Design automation, p.462-468, January 1977
• 19: S. Fumatso, H. Shibano, and O. Itoh "Effectiveness of Scan Path in Automatic Test Generations," Proc. of IECFO Conf 1977 (March 1977).
• 20: J. P. Roth, W. G. Botiwin. and P. R. Schreider, "Programmed Algorithms to compute text, to detect and distinguish between, failures in logic circuits" IEEE Trans. on Comp. C-p 567-579, Oct. 1967.
• 21: C. Cha, W. E. Donath and F. Ozguner, "9-V Algorithm and Program for Text Pattern Generation of Combinational Digital Circuits".
• 22: O. H. Ibarra and S. K. Sahni, "Polynomially Complete; Fault Detection Problems", IEEE Trans. on Comp. C-24 pp 242-249, (March 1975).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Design, Theory