A topological search algorithm for ATPG

ABSTRACT

The automatic generation of tests for combinational digital circuits is examined from the standpoint of a guided search through a search space. The limitations of this process, namely the size of the search space and the overall strategy, are identified and methods are presented to reduce the size of the search space as well as produce a more optimal ordering of node assignments. A new algorithm is proposed that uses the smaller search space and the improved ordering for node assignments based on a topological analysis of the circuit. Results are presented indicating that this new algorithm, termed TOPological Search (TOPS), is faster than existing algorithms and also rapidly identifies many redundant faults without search.

REFERENCES

• Aho 79: A. A.ho and J. Ullman, Chapter 13 of PRIN- CIPLES O17 COMPILER DESIGN, Addison- Wesley 19qv9.
• Brglez 85: F. Brglez, P. Pownall and R. Hum, "Accelerated ATPG and Fault Grading Via Testability Analysis," Proc. of ISCAS 85, June, 1985, pp. 695-698.
• Fujiwara 83: H. Fujiwara and T. Shimono, "On the Acceleration of Test Generation Algorithms," IEEE Trans. on Computers, Vol. C-32, December 1983, pp. 1.137-1144.
• Fujiwara 85: H. Fujiwara, "FAN: A Fanout-Oriented Test Pattern Generation Algorithm," Proc. of ISCAS 85, June 1985, pp. 671-674.
• Goel 81: P. Goel, "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits", }~EEE Trans. on Computers, Vol. C-30, Mar. 1981, pp. 215-222.
• Kirkland 86: Tom Kirkland , M. Ray Mercer, A two-level guidance heuristic for ATPG, Proceedings of 1986 ACM Fall joint computer conference, p.841-847, November 1986, Dallas, Texas, United States
• Kirkland 87: Tom Kirkland , M. Ray Mercer, Algorithms for Automatic Test-Pattern Generation, IEEE Design & Test, v.5 n.3, p.43-55, May 1988 [doi>10.1109/54.7962]
• Lengauer 79: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• Muth 76: P. Muth, "A Nine Valued Circuit Model for Test Generation," IEEE Trans. on Computers, VOL C-25, No. 6, June 1976.
• Tarjan 74: 1~.. Tarjan, "Finding Dominators in Directed Graphs," SIAM Journal of Computing, Vol. 3, pp. 62-89, 1974.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.3 Reliability and Testing**
          Subjects: Test generation**

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

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