On theoretical and practical considerations of path selection for delay fault testing

ABSTRACT

In current industrial practice, critical path selection is an indispensable step for AC delay test and timing validation. Traditionally, this step relies on the construction of a set of worse-case paths based upon discrete timing models. The assumption of discrete timing models can be invalidated by delay effects in the deep sub-micron domain, where timing defects and process variation are statistical in nature. In this paper, we study the problem of optimizing critical path selection, under both fixed delay and statistical delay assumptions. With a novel problem formulation and new theoretical results, we prove that the problem in both cases are computationally intractable. We then discuss practical heuristics and their theoretical performance bounds, and demonstrate that among all heuristics under consideration, only one is theoretically feasible. Finally, we provide consistent experimental results based upon defect-injected simulation using an efficient statistical timing analysis framework.

REFERENCES

• 1: Keith Baker , Guido Gronthoud , Maurice Lousberg , Ivo Schanstra , Charles Hawkins, Defect-Based Delay Testing of Resistive Vias-Contacts A Critical Evaluation, Proceedings of the 1999 IEEE International Test Conference, p.467, September 28-30, 1999
• 2: M. A. Breuer, C. Gleason, and S. Gupta. New Validation and Test Problems for High Performance Deep Sub-Micron VLSI Circuits. Tutorial Notes, IEEE VLSI Test Symposium, April 1997.
• 3: Robert C. Aiken, Nanometer Technology Effects on Fault Models for IC Testing, Computer, v.32 n.11, p.46-51, November 1999 [doi>10.1109/2.803640]
• 4: Kwang-Ting Chueng , Sujit Dey , Mike Rodgers , Kaushik Roy, Test challenges for deep sub-micron technologies, Proceedings of the 37th conference on Design automation, p.142-149, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337353]
• 5: W.-N. Li, S. M. Reddy, and S. K. Sahni. On Path Selection in Combinational Logic Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 8(1):56--63, January 1989.
• 6: S. Tani , M. Teramoto , T. Fukazawa , K. Matsuhiro, 9.1 Efficient Path Selection for Delay Testing Based on Partial Path Evaluation, Proceedings of the 16th IEEE VLSI Test Symposium, p.188, April 26-30, 1998
• 7: C. P. Ravikumar , Nitin Agrawal , Parul Agarwal, Hierarchical Delay Test Generation, Journal of Electronic Testing: Theory and Applications, v.10 n.3, p.231-244, June 1997 [doi>10.1023/A:1008267608838]
• 8: K. Antreich, A. Ganz, and P. Tafertshofer. Statistical Analysis of Delay Faults-Theory and Efficient Computation. AEU-International Journal of Electronics and Communications, 51(3):117--130, May 1997.
• 9: Rafi Levy , David Blaauw , Gabi Braca , Aurobindo Dasgupta , Amir Grinshpon , Chanlee Oh , Boaz Orshav , Supamas Sirichotiyakul , Vladimir Zolotov, ClariNet: a noise analysis tool for deep submicron design, Proceedings of the 37th conference on Design automation, p.233-238, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337400]
• 10: Jing-Jia Liou , Kwang-Ting Cheng , Deb Aditya Mukherjee, Path Selection for Delay Testing of Deep Sub-Micron Devices Using Statistical Performance Sensitivity Analysis, Proceedings of the 18th IEEE VLSI Test Symposium (VTS'00), p.97, April 30-May 04, 2000
• 11: Jing-Jia Liou , Angela Krstic , Li-C. Wang , Kwang-Ting Cheng, False-path-aware statistical timing analysis and efficient path selection for delay testing and timing validation, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514061]
• 12: C. H. Papadimitriou, and M. Yannakakis, "Optimization, Approximation, and Complexity Classes," Journal of Computer and System Sciences, 43, 1991, pp. 425--440.
• 13: Erez Petrank, The hardness of approximation: gap location, Computational Complexity, v.4 n.2, p.133-157, April 1994 [doi>10.1007/BF01202286]
• 14: G. Cornuejols, M. Fisher, and G. L. Nemhauser, "Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms," Management Science, Vol 23, No 8, April, 1977, pp. 789--810.
• 15: Alexander A. Ageev , Maxim Sviridenko, Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.17-30, June 09-11, 1999
• 16: Q. Han, Y. Ye, H. Zhang, and J. Zhang, "On Approximation of Max-Vertex-Cover," in European Journal of Operation Research, 2001.
• 17: M. Sivaraman and A. Strojwas. Path Delay Fault Diagnosis and Coverage A Metric and an Estimation Technique. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 20(3):440--457, March 2001.
• 18: Anacad. Eldo v4.4.x User's Manual. 1996.
• 19: Nandakumar N. Tendolkar, Analysis of timing failures due to random AC defects in VLSI modules, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.709-714, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317967]
• 20: Jose Pineda de Gyvez, Integrated Circuit Defect-Sensitivity: Theory and Computational Models, Kluwer Academic Publishers, Norwell, MA, 1992

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.9 Integral Equations
          Subjects: Delay equations

General Terms:
Experimentation, Measurement, Reliability, Theory