Correlation-preserved non-gaussian statistical timing analysis with quadratic timing model

ABSTRACT

Recent study shows that the existing first order canonical timing model is not sufficient to represent the dependency of the gate delay on the variation sources when processing and operational variations become more and more significant. Due to the nonlinearity of the mapping from variation sources to the gate/wire delay, the distribution of the delay is no longer Gaussian even if the variation sources are normally distributed. A novel quadratic timing model is proposed to capture the non-linearity of the dependency of gate/wire delays and arrival times on the variation sources. Systematic methodology is also developed to evaluate the correlation and distribution of the quadratic timing model. Based on these, a novel statistical timing analysis algorithm is propose which retains the complete correlation information during timing analysis and has the same computation complexity as the algorithm based on the canonical timing model. Tested on the ISCAS circuits, the proposed algorithm shows 10x accuracy improvement over the existing first order algorithm while no significant extra runtime is needed.

REFERENCES

• 1: 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]
• 2: M. Orshansky, "Fast computation of circuit delay probability distribution for timing graphs with arbitary node correlation," TAU'04, Feb 2004.
• 3: Michael Orshansky , Kurt Keutzer, A general probabilistic framework for worst case timing analysis, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514059]
• 4: Aseem Agarwal , David Blaauw , Vladimir Zolotov , Savithri Sundareswaran , Min Zhao , Kaushik Gala , Rajendran Panda, Statistical delay computation considering spatial correlations, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119825]
• 5: A. Agarwal, V. Zolotov, and D. Blaauw, "Statistical timing analysis using bounds and selective enumeration," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 9, pp. 1243--1260, Sept 2003.
• 6: C. Visweswariah , K. Ravindran , K. Kalafala , S. G. Walker , S. Narayan, First-order incremental block-based statistical timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996663]
• 7: Aseem Agarwal , David Blaauw , Vladimir Zolotov, Statistical Timing Analysis for Intra-Die Process Variations with Spatial Correlations, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.900, November 09-13, 2003 [doi>10.1109/ICCAD.2003.130]
• 8: Sarvesh Bhardwaj , Sarma B. K. Vrudhula , David Blaauw, "AU: Timing Analysis Under Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.615, November 09-13, 2003 [doi>10.1109/ICCAD.2003.1]
• 9: Anirudh Devgan , Chandramouli Kashyap, Block-based Static Timing Analysis with Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.607, November 09-13, 2003 [doi>10.1109/ICCAD.2003.41]
• 10: Hongliang Chang , Sachin S. Sapatnekar, Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-Like Traversal, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.621, November 09-13, 2003 [doi>10.1109/ICCAD.2003.129]
• 11: Shuji Tsukiyama , Masakazu Tanaka , Masahiro Fukui, A statistical static timing analysis considering correlations between delays, Proceedings of the 2001 conference on Asia South Pacific design automation, p.353-358, January 2001, Yokohama, Japan [doi>10.1145/370155.370390]
• 12: S. R. Nassif, "Modeling and analysis of manufacturing variations," CICC, pp. 223--228, 2001.
• 13: S. Nassif, "Within-chip variability analysis," Electron Devices Meeting, 1998. IEDM '98 Technical Digest., International, pp. 283--286, Dec 1998.
• 14: Xin Li , Jiayong Le , P. Gopalakrishnan , L. T. Pileggi, Asymptotic probability extraction for non-normal distributions of circuit performance, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.2-9, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382533]
• 15: B. V. Gnedenko, Theory of Probability, 6th ed. Gordon and Breach Science Publishers, 1997, translated from Russian by Igor A. Ushakov.
• 16: C. Clark, "The greatest of a finite set of random variables," Operations Research, pp. 145--162, March 1961.

INDEX TERMS

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

General Terms:
Algorithms, Performance, Verification