Conflict driven techniques for improving deterministic test pattern generation

ABSTRACT

This work presents several new techniques for enhancing the performance of deterministic test pattern generation for VLSI circuits. The techniques introduced are called dynamic decision ordering, conflict driven recursive learning and conflict learning. An important feature shared by all these techniques is that they are triggered by the occurrence of a conflict in the generation of tests. Hence, they are not active all the time nor for all the faults. This feature allows the ATPG system that uses these techniques to resolve hard-to-resolve faults with far fewer backtracks and leaves the system as efficient as before in the absence of conflicts. We have incorporated these techniques into a commercial D-algorithm based ATPG tool. The experimental results on full scan versions of ITC'99 benchmark circuits demonstrate an improvement of the ATPG system both in the number of aborted faults and in test generation time.

REFERENCES

• 1: J. P. Roth, "Diagnosis of Automata Failures: A Calculus & a Method," IBM J. Res. Develop., vol. 10, Jul 1966, pp. 278--291
• 2: Lawrence H. Goldstein , Evelyn L. Thigpen, SCOAP: Sandia controllability/observability analysis program, Proceedings of the 17th conference on Design automation, p.190-196, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804528]
• 3: P. Goel, "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits," IEEE Trans. on Computers, March 1981, pp. 215--222
• 4: H. Fujiwara and S. Toida, "The Complexity of Fault Detection Problems for Combinational Logic Circuits", IEEE Trans. on Computers, June 1982, pp. 555--560
• 5: H. Fujiwara and T. Shimono, "On the Acceleration of Test Generation Algorithms," IEEE Trans. on Computers, Dec. 1983, pp. 1137--1144
• 6: T. Kirkland , M. R. Mercer, A topological search algorithm for ATPG, Proceedings of the 24th ACM/IEEE conference on Design automation, p.502-508, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37963]
• 7: M. Schulz, E. Trischler, and T. Sarfert, "SOCRATES: A Highly Efficient Automatic Test Pattern Generation System," Proc. of ITC, 1987, pp. 1016--1026
• 8: A. Ivanov and V. K. Agarwal, "Dynamic Testability Measures for ATPG", IEEE Trans. on CAD, May 1988, pp. 598--608
• 9: M. Abramovici, M. A. Breuer and A. D. Friedman, "Digital Systems Testing and Testable Design", IEEE Press, 1990
• 10: Wolfgang Kunz , Dhiraj K. Pradhan, Recursive Learning: An Attractive Alternative to the Decision Tree for Test Genration in Digital Circuits, Proceedings of the IEEE International Test Conference on Discover the New World of Test and Design, p.816-825, September 20-24, 1992
• 11: T. Larrabee, "Test Pattern Generation Using Boolean Satisfiability," IEEE Trans. on CAD, Jan. 1992, pp. 4--15
• 12: W. Kunz and D. K. Pradhan, "Accelerated Dynamic Learning for Test Pattern Generation in Combinational Circuits," IEEE Tran on CAD, May 1993, pp. 684--693
• 13: H. K. Lee and D. S. Ha, "On the Generation of Test Patterns for Combinational Circuits", Technical Report No. 12_93, Dept of Electrical Eng., Virgina Polytechnic Institute and State Unviersity
• 14: M. Henftling , H. C. Wittmann , K. J. Antreich, A single-path-oriented fault-effect propagation in digital circuits considering multiple-path sensitization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.304-309, November 05-09, 1995, San Jose, California, United States
• 15: P. Stephan, R. K. Brayton and A.L. Sagiovanni-Vincentelli, "Combinational Test Generation Using Satisfiability", IEEE Trans. on CAD, September 1996, pp. 1167--1176
• 16: João P. Marques Silva , Karem A. Sakallah, GRASP—a new search algorithm for satisfiability, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.220-227, November 10-14, 1996, San Jose, California, United States
• 17: Joao P. Marques Silva , Karem A. Sakallah, Robust Search Algorithms for Test Pattern Generation, Proceedings of the 27th International Symposium on Fault-Tolerant Computing (FTCS '97), p.152, June 25-27, 1997
• 18: I. Hamzaoglu , J. H. Patel, 20.2 New Techniques for Deterministic Test Pattern Generation, Proceedings of the 16th IEEE VLSI Test Symposium, p.446, April 26-30, 1998
• 19: S. Davidson, "ITC'99 Benchmark Circuits -- Preliminary Results," Proc. of International Test Conference, 1999, pp. 1125 (Gate level description: http://www.cad.polito.it)
• 20: Emil Gizdarski , Hideo Fujiwara, SPIRIT: A Highly Robust Combinational Test Generation Algorithm, Proceedings of the 19th IEEE VLSI Test Symposium, p.346, March 29-April 03, 2001
• 21: Chen Wang , Irith Pomeranz , Sudhakar M. Reddy, REDI: an efficient fault oriented procedure to identify redundant faults in combinational logic circuits, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 22: Lintao Zhang , Conor F. Madigan , Matthew H. Moskewicz , Sharad Malik, Efficient conflict driven learning in a boolean satisfiability solver, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California

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:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Algorithms, Design, Experimentation, Theory