On bounding the delay of a critical path

ABSTRACT

Process variations cause different behavior of timing-dependent effects across different chips. In this work, we analyze one example of timing-dependent effects, cross-coupling capacitance, and the complex problem space created by considering coupling and process variations together. The delay of a critical path under these conditions is difficult to bound for design and test. We develop a methodology that analyzes this complex space by decomposing the problem space along three dimensions: the aggressor space, test space, and sample space. For design, we utilize an OBDD-based approach to prune the aggressor space based on logical constraints, which can be combined with a worst-case timing window simulator to prune based on both logical and timing constraints. After pruning, the reduced aggressor space can be used to derive a more accurate timing bound. Solving the problems in the test and sample spaces is postponed to the post-silicon stage, where we propose a test selection methodology for bounding the delay of every sample. This methodology is based on probability density estimation and has a tradeoff between the number of tests to apply and the tightness of the delay bound obtained. Experimental results based on benchmark examples are presented to show the effectiveness of the proposed methodology.

REFERENCES

• 1: Layout and parasitic information for ISCAS circuits. http://dropzone.tamu.edu/~xiang/iscas.html.
• 2: The R project for statistical computing. http://www.r-project.org/.
• 3: Aseem Agarwal , Florentin Dartu , David Blaauw, Statistical gate delay model considering multiple input switching, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996746]
• 4: Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, August 1986 [doi>10.1109/TC.1986.1676819]
• 5: V. Chandramouli , Karem A. Sakallah, Modeling the effects of temporal proximity of input transitions on gate propagation delay and transition time, Proceedings of the 33rd annual conference on Design automation, p.617-622, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240635]
• 6: Yi-Shing Chang , Sandeep Gupta , Melvin Breuer, Test Generation for Maximizing Ground Bounce for Internal Circuitry with Reconvergent Fan-outs, Proceedings of the 19th IEEE VLSI Test Symposium, p.358, March 29-April 03, 2001
• 7: Pinhong Chen , Desmond A. Kirkpatrick , Kurt Keutzer, Miller factor for gate-level coupling delay calculation, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 8: Weiyu Chen , Sandeep K. Gupta , Melvin A. Breuer, Test generation in VLSI circuits for crosstalk noise, Proceedings of the 1998 IEEE International Test Conference, p.641, October 18-22, 1998
• 9: Wei-Yu Chen , Sandeep K. Gupta , Melvin A. Breuer, Test Generation for Crosstalk-Induced Delay in Integrated Circuits, Proceedings of the 1999 IEEE International Test Conference, p.191, September 28-30, 1999
• 10: Florentin Dartu , Lawrence T. Pileggi, Calculating worst-case gate delays due to dominant capacitance coupling, Proceedings of the 34th annual conference on Design automation, p.46-51, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266033]
• 11: Yi-Min Jiang , Kwang-Ting Cheng, Vector generation for power supply noise estimation and verification of deep submicron designs, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.2, p.329-340, April 2001 [doi>10.1109/92.924055]
• 12: 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]
• 13: A. B. Kahng et al. Noise and delay uncertainty studies for coupled RC interconnects. In ASIC/SOC, 1999.
• 14: Angela Krstic , Yi-Min Jiang , Kwang-Ting (Tim) Cheng, Delay Testing Considering Power Supply Noise Effects, Proceedings of the 1999 IEEE International Test Conference, p.181, September 28-30, 1999
• 15: Angela Krstic , Jing-Jia Liou , Yi-Min Jiang , Kwang-Ting Cheng, Delay testing considering crosstalk-induced effects, Proceedings of the IEEE International Test Conference 2001, p.558-567, October 30-November 01, 2001
• 16: Leonard Lee , Sean Wu , Charles H-P Wen , Li-C. Wang, On Generating Tests to Cover Diverse Worst-Case Timing Corners, Proceedings of the 20th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT'05), p.415-426, October 03-05, 2005 [doi>10.1109/DFTVS.2005.50]
• 17: Leonard Lee , Li-C. Wang , Praveen Parvathala , T. M. Mak, On Silicon-Based Speed Path Identification, Proceedings of the 23rd IEEE VLSI Test Symposium (VTS'05), p.35-41, May 01-05, 2005 [doi>10.1109/VTS.2005.61]
• 18: Feng Lu , Li-C. Wang , Kwang-Ting Cheng , Ric C-Y Huang, A Circuit SAT Solver With Signal Correlation Guided Learning, Proceedings of the conference on Design, Automation and Test in Europe, p.10892, March 03-07, 2003
• 19: J. Qian et al. Modeling the effective capacitance for the RC interconnect of CMOS gates. IEEE Trans. Computer-Aided Design, 13(12):1526--1555, Dec. 1994.
• 20: T. Sakurai. Closed-form expressions for interconnection delay, coupling, and crosstalk in VLSI's. Trans. Elect. Dev., 40(1):118--124, Jan. 1993.
• 21: S. J. Sheather and M. C. Jones. A reliable data-based bandwidth selection method for kernel density estimation. J. Roy. Statist. Soc. B, 53:683--690, 1991.
• 22: B. W. Silverman. Density Estimation. Chapman and Hall, 1986.
• 23: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance
  B.m MISCELLANEOUS
      Subjects: Design management

General Terms:
Design, Theory, Verification