Accelerated test pattern generation by cone-oriented circuit partitioning

ABSTRACT

In this paper an efficient cone oriented circuit partitioning method is presented, which significantly speeds up automatic test pattern generation for combinational circuits. The advantages gained by the proposed partitioning method are based on the increase in the number of dominators in the circuit graph. In contrast to conventional ATPG working on the unpartitioned circuit test generation is less time consuming now and redundancies can often be identified without any backtracks. Experimental results illustrate the superiority of the cone oriented partitioning approach. Independent of the underlying ATPG algorithm the cone oriented partitioning results on average in a performance increase by more than a factor of 2.

REFERENCES

• 1: Williams, M. J. Y., Angell, J. B.: "Enhancing Testability of Large Scale Integrated Circuits via Test Points and Additional Logic", IEEE Trans., Comput., C-22 (1), pp. 46--60, 1973
• 2: Kobayashi, T., Matsue, T., Shiba, H.: "Flip-flop Circuit with FLT Capability", Proc. IECEO, p. 692, 1968
• 3: 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
• 4: Goel, P.: "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic", IEEE Trans. Comput., Vol. C-30 (3), pp. 215--222, 1981
• 5: Fujiwara, H., Shimono, T.: "On the Acceleration of Test Generation Algorithms", Proc. 13th Int. Symp. Fault-Tolerant Computing, pp. 98--105, 1983
• 6: Schulz, M. H., Auth, E.: "Advanced Automatic Test Pattern Generation and Redundancy Identification Techniques", Proc. 18th Int. Symp. Fault-Tolerant Computing, pp. 30--35, 1988
• 7: 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]
• 8: Roth, J. P.: "Diagnosis of Automata Failures: A calculus and a method", IBM Journal Res. Dev. 10, pp. 278--281, 1966
• 9: Mc Cluskey, E. J.: "Verification Testing", Proc. Intern. Test Conf. 1982, pp. 183--190, October 1982
• 10: Tarjan, R.: "Finding Dominators in Directed Graphs", SIAM Journal of Computing, Vol. 3, pp. 62--89, 1974
• 11: Muth, P.: "A Nine-Valued Logic Model for Test Generation", IEEE Trans. Comput., Vol. C-25, pp. 630--636, 1976
• 12: Brglez, F., Fujiwara, H.: "A Neutral Netlist of 10 Combinational Benchmark Circuits and a Target Translator in Fortran", special session on ATPG and fault Simulation, Proc. 1985 IEEE Int. Symp. on Circuits and Systems, Kyoto (Japan), 1985