A general framework for accurate statistical timing analysis considering correlations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A general framework for accurate statistical timing analysis considering correlations

Full text

Pdf (1.28 MB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 42nd annual Design Automation Conference table of contents

Anaheim, California, USA

SESSION: Statistical timing analysis table of contents

Pages: 89 - 94

Year of Publication: 2005

ISBN:1-59593-058-2

Authors

Vishal Khandelwal	University of Maryland-College Park
Ankur Srivastava	University of Maryland-College Park

Sponsors

ACM: Association for Computing Machinery
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 46, Citation Count: 22

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1065579.1065607 What is a DOI?

ABSTRACT

The impact of parameter variations on timing due to process and environmental variations has become significant in recent years. With each new technology node this variability is becoming more prominent. In this work, we present a general Statistical Timing Analysis (STA) framework that captures spatial correlations between gate delays. Our technique does not make any assumption about the distributions of the parameter variations, gate delay and arrival times. We propose a Taylor-series expansion based polynomial representation of gate delays and arrival times which is able to effectively capture the non-linear dependencies that arise due to increasing parameter variations. In order to reduce the computational complexity introduced due to polynomial modeling during STA, we propose an efficient linear-modeling driven polynomial STA scheme. On an average the degree-2 polynomial scheme had a 7.3x speedup as compared to Monte Carlo with 0.049 units of rms error w.r.t Monte Carlo. Our technique is generic and can be applied to arbitrary variations in the underlying parameters.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	Aseem Agarwal , David Blaauw , Vladimir Zolotov , Sarma Vrudhula, Computation and Refinement of Statistical Bounds on Circuit Delay, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775922]
	3	A. Agarwal, V. Zolotov and D. Blaauw. "Statistical Timing Analysis Using Bounds and Selective Enumeration". In IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.22, Sept. 2003.
	4	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337549]
	5	C. E. Clark. "The Greates of a Finite Set of Random Variables". In Operations Research, pages 145--162, 1961.
	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	E.M. Sentovich, K.J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P.R. Stephan, R.K. Brayton, A.L. Sangiovanni-Vincentelli. SIS: A System for Sequential Circuit Synthesis. Memorandum No. UCB/ERL M92/41, Dept of EECS. UC Berkeley, May 1992.
	8	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]
	9	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]
	10	M. Cain. "The Moment Generating Function of the Minimum of Bivariate Normal Random Variables". In The American Statistician, pages 124--125, May 1994.
	11	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]

CITED BY 22

	Azadeh Davoodi , Ankur Srivastava, Probabilistic evaluation of solutions in variability-driven optimization, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Andrew B. Kahng , Bao Liu , Xu Xu, Statistical crosstalk aggressor alignment aware interconnect delay calculation, Proceedings of the international workshop on System-level interconnect prediction, March 04-05, 2006, Munich, Germany
	Jinjun Xiong , Lei He, Fast buffer insertion considering process variations, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Azadeh Davoodi , Ankur Srivastava, Variability driven gate sizing for binning yield optimization, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Andrew B. Kahng , Bao Liu , Xu Xu, Statistical gate delay calculation with crosstalk alignment consideration, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA
	Jaskirat Singh , Sachin Sapatnekar, Statistical timing analysis with correlated non-gaussian parameters using independent component analysis, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Benjamin N. Lee , Li-C. Wang , Magdy S. Abadir, Refined statistical static timing analysis through, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Vishal Khandelwal , Ankur Srivastava, Variability-driven formulation for simultaneous gate sizing and post-silicon tunability allocation, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Anand Ramalingam , Gi-Joon Nam , Ashish Kumar Singh , Michael Orshansky , Sani R. Nassif , David Z. Pan, An accurate sparse matrix based framework for statistical static timing analysis, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Vishal Khandelwal , Ankur Srivastava, A quadratic modeling-based framework for accurate statistical timing analysis considering correlations, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.15 n.2, p.206-215, February 2007
	Kaviraj Chopra , Bo Zhai , David Blaauw , Dennis Sylvester, A new statistical max operation for propagating skewness in statistical timing analysis, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Vikram Iyengar , Jinjun Xiong , Subbayyan Venkatesan , Vladimir Zolotov , David Lackey , Peter Habitz , Chandu Visweswariah, Variation-aware performance verification using at-speed structural test and statistical timing, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Rasit Onur Topaloglu, Monte Carlo-Alternative Probabilistic Simulations for Analog Systems, Proceedings of the 7th International Symposium on Quality Electronic Design, p.249-253, March 27-29, 2006
	Khaled R. Heloue , Farid N. Najm, Parameterized timing analysis with general delay models and arbitrary variation sources, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	Vishal Khandelwal , Ankur Srivastava, Monte-Carlo driven stochastic optimization framework for handling fabrication variability, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Lerong Cheng , Jinjun Xiong , Lei He, Non-linear statistical static timing analysis for non-Gaussian variation sources, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	Amith Singhee , Sonia Singhal , Rob A. Rutenbar, Exploiting correlation kernels for efficient handling of intra-die spatial correlation, with application to statistical timing, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany
	Lin Xie , Azadeh Davoodi , Jun Zhang , Tai-Hsuan Wu, Adjustment-based modeling for statistical static timing analysis with high dimension of variability, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Kelageri Nagaraj , Sandip Kundu, Process variation mitigation via post silicon clock tuning, Proceedings of the 19th ACM Great Lakes symposium on VLSI, May 10-12, 2009, Boston Area, MA, USA
	Cristiano Forzan , Davide Pandini, Statistical static timing analysis: A survey, Integration, the VLSI Journal, v.42 n.3, p.409-435, June, 2009
	Sudeep Pasricha , Young-Hwan Park , Nikil Dutt , Fadi J. Kurdahi, System-level PVT variation-aware power exploration of on-chip communication architectures, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.2, p.1-25, March 2009
	Seyed-Abdollah Aftabjahani , Linda Milor, Timing analysis with compact variation-aware standard cell models, Integration, the VLSI Journal, v.42 n.3, p.312-320, June, 2009