Statistical timing analysis with correlated non-gaussian parameters using independent component analysis

ABSTRACT

We propose a scalable and efficient parameterized block-based statistical static timing analysis algorithm incorporating both Gaussian and non-Gaussian parameter distributions, capturing spatial correlations using a grid-based model. As a preprocessing step, we employ independent component analysis to transform the set of correlated non-Gaussian parameters to a basis set of parameters that are statistically independent, and principal components analysis to orthogonalize the Gaussian parameters. The procedure requires minimal input information: given the moments of the variational parameters, we use a Padé approximation-based moment matching scheme to generate the distributions of the random variables representing the signal arrival times, and preserve correlation information by propagating arrival times in a canonical form. For the ISCAS89 benchmark circuits, as compared to Monte Carlo simulations, we obtain average errors of 0.99% and 2.05%, respectively, in the mean and standard deviation of the circuit delay. For a circuit with G gates and a layout with g spatial correlation grids,the complexity of our approach is O(g G).

REFERENCES

• 1: 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]
• 2: 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]
• 3: Hongliang Chang , Vladimir Zolotov , Sambasivan Narayan , Chandu Visweswariah, Parameterized block-based statistical timing analysis with non-gaussian parameters, nonlinear delay functions, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065604]
• 4: 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]
• 5: Chirayu S. Amin , Noel Menezes , Kip Killpack , Florentin Dartu , Umakanta Choudhury , Nagib Hakim , Yehea I. Ismail, Statistical static timing analysis: how simple can we get?, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065751]
• 6: Michael Orshansky , Arnab Bandyopadhyay, Fast statistical timing analysis handling arbitrary delay correlations, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996664]
• 7: Vishal Khandelwal , Ankur Srivastava, A general framework for accurate statistical timing analysis considering correlations, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065607]
• 8: Yaping Zhan , Andrzej J. Strojwas , Xin Li , Lawrence T. Pileggi , David Newmark , Mahesh Sharma, Correlation-aware statistical timing analysis with non-gaussian delay distributions, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065605]
• 9: Lizheng Zhang , Weijen Chen , Yuhen Hu , John A. Gubner , Charlie Chung-Ping Chen, Correlation-preserved non-gaussian statistical timing analysis with quadratic timing model, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065606]
• 10: Jiayong Le , Xin Li , Lawrence T. Pileggi, STAC: statistical timing analysis with correlation, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996665]
• 11: H. Damerdji, A. Dasdan, and S. Kolay. On the Assumption of Normality in Statistical Static Timing Analysis. In Proc. TAU, pages 2--7, 2005.
• 12: H. Chang and S. S. Sapatnekar. Statistical Timing Analysis Considering Spatial Correlations. In IEEE Trans. on CAD, volume 24, pages 1467--1482, Sep 2005.
• 13: Tony Bell. An ICA page - papers, code, demos, links. http://www.cnl.salk.edu/tony/ica.html.
• 14: A. Hyvärinen and E. Oja. Independent Component Analysis: A Tutorial. http://www.cis.hut.fi/aapo/papers/IJCNN99 tutorialweb/.
• 15: A. Hyvärinen , E. Oja, Independent component analysis: algorithms and applications, Neural Networks, v.13 n.4-5, p.411-430, May-June 2000 [doi>10.1016/S0893-6080(00)00026-5]
• 16: Roberto Manduchi , Javier Portilla, Independent Component Analysis of Textures, Proceedings of the International Conference on Computer Vision-Volume 2, p.1054, September 20-25, 1999
• 17: 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]
• 18: Available at http://www.cis.hut.fi/projects/ica/fastica/.
• 19: Available at http://www.cis.hut.fi/projects/ica/icasso/.
• 20: Simulating Dependent Random Variables Using Copulas. http://www.mathworks.com/products/statistics/.
• 21: S. Nassif. Delay Variability: Sources, Impact and Trends. In Proc. ISSCC, pages 368--369, 2000.

INDEX TERMS

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

General Terms:
Performance

Keywords:
independent component analysis, moment matching, non-Gaussian, statistical timing