Efficient Boolean characteristic function for fast timed ATPG

ABSTRACT

Circuit timing analysis is important in various aspects of circuit optimization. The problem of finding input vectors achieving functional and temporal requirements is known as timed Automatic Test Pattern Generation (timed ATPG). A timed ATPG algorithm will return an input vector that satisfies functional and temporal requirements simultaneously when evaluated. Several previous works use timed ATPG as a core engine for solving problems related to timing analysis, such as crosstalk and maximum instantaneous current analysis. Despite the usefulness of timed ATPG, traditional timed ATPG is slow and unscalable for large circuits. In this paper, we present a very efficient way for timed ATPG. On average, our results are 8 times faster than the most recent work, and in some cases, up to 32 times faster.

REFERENCES

• 1: P. Ashar, and S. Malik, "Functional Timing Analysis Using ATPG," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, no. 8, pp. 1025--1030, Aug. 1995.
• 2: R. I. Bahar, H. Cho, G. D. Hachtel, E. Macii, and F. Somenzi, "Timing Analysis of Combinational Circuits using ADD's," in Proc. of IEEE European Design Test Conference, pp. 625--629, 1994.
• 3: H.-C. Chen, and D. Du, "Path Sensitization in Critical Path Problem," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 2, pp. 196--207, Feb. 1993.
• 4: S. Devadas, K. Keutzer, and S. Malik, "Computation of Floating Mode Delay in Combinational Circuits: Theory and Algorithms," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 12, pp. 1913--1923, Dec. 1993.
• 5: J. L. Güntzel, A. C. M. Pinto, and R. Reis "A Timed Calculus for ATG-Based Timing Analysis of Circuits with Complex Gates," in Proc. IEEE Latin American Test Workshop, pp. 234--239, 2001.
• 6: H. Kriplani, F. Najm, and I. N. Hajj, "Pattern Independent Maximum Current Estimation in Power and Ground Buses of CMOS VLSI Circuits: Algorithms, Signal Correlations, and Their Resolution," IEEE Trans. on Computer-Aided Design, vol. 14, no. 8, pp. 998--1012, Aug. 1995.
• 7: Yi-Min Jiang , Angela Krstic , Kwang-Ting Cheng, Estimation for maximum instantaneous current through supply lines for CMOS circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.1, p.61-73, Feb. 2000 [doi>10.1109/92.820762 ]
• 8: Y.-M. Jiang, K.-T. Cheng, and A. Krstic, "Estimation of Maximum Power and Instantaneous Current Using a Genetic Algorithm," in Proc. of IEEE Custom Integrated Circuits Conference, pp. 135--138, 1997.
• 9: Rahul Kundu , R. D. (Shawn) Blanton, Timed Test Generation Crosstalk Switch Failures in Domino CMOS Circuits, Proceedings of the 20th IEEE VLSI Test Symposium, p.379, April 28-May 02, 2002
• 10: Rahul Kundu , R. D. (Shawn) Blanton, ATPG for Noise-Induced Switch Failures in Domino Logic, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.765, November 09-13, 2003 [doi>10.1109/ICCAD.2003.37]
• 11: P. C. McGeer, A. Saldanha, P. R. Stephan, R. K. Brayton, and A. L. Sangiovanni-Vicentelli, "Timing Analysis and Delay-Fault Test Generation using Path-Recursive Functions," in Proc. of the ICCAD, pp. 180--183, 1991.
• 12: Matthew W. Moskewicz , Conor F. Madigan , Ying Zhao , Lintao Zhang , Sharad Malik, Chaff: engineering an efficient SAT solver, Proceedings of the 38th conference on Design automation, p.530-535, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379017]
• 13: A. Nadel, "Backtrack Search Algorithms for Propositional Satisfiability: Review and Innovations," Master's Thesis, the Hebrew University of Jerusalem, 2002.
• 14: J. P. M. Silva, and K. A. Sakallah, "Efficient and Robust Test Generation-Based Timing Analysis," in Proc. of the International Symposium on Circuits and Systems, pp. 303--306, 1994.
• 15: João P. Marques-Silva , Karem A. Sakallah, GRASP: A Search Algorithm for Propositional Satisfiability, IEEE Transactions on Computers, v.48 n.5, p.506-521, May 1999 [doi>10.1109/12.769433 ]
• 16: Luís Guerra e Silva , João Marques-Silva , L. Miguel Silveira , Karem A. Sakallah, Satisfiability models and algorithms for circuit delay computation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.137-158, January 2002 [doi>10.1145/504914.504920]
• 17: Hakan Yalcin , John P. Hayes, Hierarchical timing analysis using conditional delays, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.371-377, November 05-09, 1995, San Jose, California, United States
• 18: Hantao Zhang, SATO: An Efficient Propositional Prover, Proceedings of the 14th International Conference on Automated Deduction, p.272-275, July 13-17, 1997

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance
      B.8.2 Performance Analysis and Design Aids
  B.m MISCELLANEOUS
      Subjects: Design management

General Terms:
Design, Performance, Verification