High level hierarchical fault simulation techniques

ABSTRACT

This paper presents techniques for simulating directly from a hierarchical circuit description without flattening to the level of primitives. An overview of traditional fault simulation techniques is followed by details of the hierarchical techniques. The fault model is shown to be decoupled from the simulator programs through the use of a fault library. The fault library allows the user to mix both functional and technology-dependent fault models, which allows fault simulation and consequently test coverage estimation early in the design, with refinements in the fault model and test coverage as the design progresses. Thus testing problems can be detected early in the design process while they are much easier to correct. The circuit description language, SCALD, and the fault library language are described and illustrated with examples. The simulator initialization and execution phases are discussed in detail with emphasis on the unique data structures necessary for hierarchical simulation. The hierarchy provides a framework for an adaptive evaluation technique that speeds the evaluation of faulty machines. Initial performance measurements and experiences with the simulator indicate that hierarchical fault simulation is superior to traditional techniques.

REFERENCES

• 1: 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
• 2: T.W. Williams and K. P. Parker, "Design for Testability - A Survey," Proceedings of the 1EEE, voL 71, pp. 98-112, January 1983.
• 3: T W. Williams, VLSI testing, Computer, v.17 n.10, p.126-136, Oct. 1984 [doi>10.1109/MC.1984.1658965]
• 4: Richard D. Eldred, Test Routines Based on Symbolic Logical Statements, Journal of the ACM (JACM), v.6 n.1, p.33-37, Jan. 1959 [doi>10.1145/320954.320957]
• 5: V.D. Agrawal, "Sampling Techniques for Determining Fault Coverage in LSI Circuits," Journal of Digital Systems, vol. V, pp. 189-202, 1981.
• 6: J.P. Roth, W. G. Bouricus, and P. R. Schneider, "Programmed Algorithms to Compute Tests ~,o Detect and Distinguish Between Failures in Logic Circuits," IEEE Transactions on Computers, vol. EC-16, pp. 567-580, October 1967.
• 7: Prabhakar Goel , Barry C. Rosales, PODEM-X: An automatic test generation system for VLSI logic structures, Proceedings of the 18th conference on Design automation, p.260-268, June 29-July 01, 1981, Nashville, Tennessee, United States
• 8: O.H. Ibarra and S. K. Sahni, "Polynomiatly Complete Fault Detection Problems," 1EEE Transactions on Computers, vol. C-24, pp, 242-249, March 1975.
• 9: C.H. Sequin, "Managing VLSI Complexity: An Outlook," Proceedings of the 1EEE, vol. 71, pp. 14%166, January 1983.
• 10: B.T. Preas and C. V~. Gwyn, "General Hierarchical Automatic Layout of Custom VLSI Circuit Masks," Journal of Design Automation & Fault-Tolerant Computing, vol. 3, pp. 41-58, January 1979.
• 11: C. Niessen, "Hierarchical Design Methodologies and Tools for VLSI Chips," Proceedings of the 1EEE, vol. 71, pp. 66-75, January 1983.
• 12: M. R. Genesereth, "Diagnosis Using Hierarchical Design Models," HPP-81-20, Stanford University. Stanford, California, 1981.
• 13: H. Daseking, R. Gardner, and P. WeiI, "\qSTA: A VLSI CAD System," 1EEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. CAD-I, pp. 36-52, January 1982.
• 14: Robert I. Gardner , Paul B. Weil, Hierarchical modeling and simulation in VISTA, Proceedings of the 16th Conference on Design automation, p.403-405, June 25-27, 1979, San Diego, CA, United States
• 15: S. Seshu, "Oft an Improved Diagnosis Program," IEEE Transactions on Computers, vol. EC-14, pp. 76-79, February 1965.
• 16: Arthur D. Friedman, Logical Design of Digital Systems, W. H. Freeman & Co., New York, NY, 1975
• 17: E. W. Thompson and S. A. Szygenda, "Digital Logic Simulation in a Time-Based, Table-Driven Environment Part 2. Parallel Fault Simulation," Computer, vol. 8, pp. 38-49, March 1975.
• 18: D. Saab and I. Haj~ "Parallel and Concurrent Fault Simulation of MOS Circuits," in IEEE International Conference on Computer Design, Port Chester, N.Y~ pp. 752-756, October 1984.
• 19: D.B. Armstrong, "A Deductive Method for Simulating Faults in Logic Circuits," 1EEE Transactions on Computers, vol. C-21, pp. 464-471, May 1972.
• 20: P. N. Yianilos, "A Dedicated Comparator Matches Symbol Strings Fast and Intelligently," Electronics, vol. 56, pp. 113- 117, December 1983.
• 21: N. Giambiasi , A. Miara , D. Muriach, Methods for generalized deductive fault simulation, Proceedings of the 17th conference on Design automation, p.386-392, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804560]
• 22: Y.H. Levendet and P. R. Menon, "Fault-Simulation Methods - Extensions and Comparison," Bell System Technical Journal, vol. 60, pp. 2235-2259, November 1981.
• 23: E. G. Ulrich and T. Baker, "Concurren~ Simulation of Nearly Identical Digital Networks," Computer, vol. 7, pp. 39-44, April 1974.
• 24: E. Ulrich , D. Lacy , N. Phillips , J. Tellier , M. Kearney , T. Elkind , R. Beaven, High-speed concurrent fault simulation with vectors and scalars, Proceedings of the 17th conference on Design automation, p.374-380, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804558]
• 25: B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
• 26: M. E. Lesk and E. Schmidt, "Lex - A Lexical Analyzer Generator," in UNIX Programmer's Manual. Murray Hill, New Jersey: Bell Laboratories, 1979.
• 27: S. C. Johnson, "'Yacc: Yet Another Compiler-Compiler," in UNIX Programmer's Manual. Murray Hill, New Jerse~y: Bell Laboratories, 1979.
• 28: J.D. Lesser and J. J. Shedletsky, "An Experimental Delay Test Generator for LSI Logic," 1EEE Transactions on Computers, vol. C-29, pp. 235-248, March 1980.
• 29: V.V. Nickel, "VLSI - The Inadequacy of the Stuck-At Fault Model," in 1EEE Test Conference, Philadelphia, P~, pp. 378-381, November 1980.
• 30: C. Law, S. Y. Iq. Su, and Y. K. Malaiya, "Test Generation for Delay Faults Using Stuck-At-Fault Test Set," in 1EEE Test Conference, Philadelphia, Pa., pp. 167-175, November 1980.
• 31: D.R. Schertz and G. Metze, "A New Representation for Faults in Combinational Digital Circuits," 1EEE Transactions on Computers, vol. C-21, pp. 858-866, August 1972.
• 32: E.J. McCluskey and F. W. Clegg, "Fault Equivalence in Combinational Logic Networks," IEEE Transactions on Computers, vol. C-20, pp. 1286-1293, November 1971.
• 33: T. M. McWilliams, J. B. Rubin, L C. Widdoes, and S~ Correl, SCALD 11 User's Manual. Lawrence Livermore Laboratory, 1979 Annual Report, The S-1 Project.
• 34: J.M. Acken and J. D. Stauffer, "Part II: Logic Circuit Simulation," IEEE Circuits and Systems Magazine, vol. 1, pp. 3- 12, June 1979.
• 35: B. Salefski, "D," Masters Thesis. University of Illinois, Urbana-Champaign, 1981.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Theory