A general probabilistic framework for worst case timing analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A general probabilistic framework for worst case timing analysis

Full text

Pdf (268 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 39th annual Design Automation Conference table of contents

New Orleans, Louisiana, USA

SESSION: Advances in timing and simulation table of contents

Pages: 556 - 561

Year of Publication: 2002

ISBN ~ ISSN:0738-100X , 1-58113-461-4

Authors

Michael Orshansky	University of California, Berkeley
Kurt Keutzer	University of California, Berkeley

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 48, Citation Count: 64

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/513918.514059 What is a DOI?

ABSTRACT

The traditional approach to worst-case static-timing analysis is becoming unacceptably conservative due to an ever-increasing number of circuit and process effects. We propose a fundamentally different framework that aims to significantly improve the accuracy of timing predictions through fully probabilistic analysis of gate and path delays. We describe a bottom-up approach for the construction of joint probability density function of path delays, and present novel analytical and algorithmic methods for finding the full distribution of the maximum of a random path delay space with arbitrary path correlations.

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	Boning, D., and Nassif, S., "Models of Process Variations in Device and Interconnect", in Design of High-Performance Microprocessor Circuits, A. Chandrakasan (ed.), 2000
	2	M. Orshansky, "Increasing Circuit Performance through Statistical Design Techniques," in Closing the Gap Between ASIC and Custom, Kluwer, D. Chinnery, K. Keutzer (ed.), 2002
	3	D. G. Chinnery , K. Keutzer, Closing the gap between ASIC and custom: an ASIC perspective, Proceedings of the 37th conference on Design automation, p.637-642, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337602]
	4	Semiconductor Industry Association, International Technology Roadmap for Semiconductors, 2001
	5	S. Nassif, "Statistical worst-case analysis for integrated circuits," Statistical Approaches to VLSI, Elsevier Science, 1994
	6	Robert B. Hitchcock, Sr., Timing Verification and the Timing Analysis program, Proceedings of the 19th conference on Design automation, p.594-604, January 1982
	7	H.-F. Jyu, S. Malik, S. Devadas, K. Keutzer, "Statistical timing analysis of combinational logic circuits," IEEE Trans. on VLSI Systems, vol.1, (no.2), June 1993. p.126--37
	8	M. Berkelaar, "Statistical Delay Calculation", International Workshop on Logic Synthesis, 1997
	9	S. Zanella et al, "Statistical Timing Macromodeling of Digital IP Libraries", Workshop on Statistical Metrology, 2000
	10	R. Adler, An Introduction to Continuity, Extrema, and Related Topics for General Gaussian Processes, 1990, p. 49
	11	M. Orshansky, DAC 2002 Technical Materials, www-device.eecs.berkeley.edu/~omisha/dac2002.htm
	12	D. Pollard, A User's Guide to Measure Theoretic Probability, Cambridge University Press, 2001

CITED BY 64

	Kurt Keutzer , Michael Orshansky, From blind certainty to informed uncertainty, Proceedings of the 8th ACM/IEEE international workshop on Timing issues in the specification and synthesis of digital systems, December 02-03, 2002, Monterey, California, USA
	Aseem Agarwal , David Blaauw , Vladimir Zolotov , Sarma Vrudhula, Statistical timing analysis using bounds and selective enumeration, Proceedings of the 8th ACM/IEEE international workshop on Timing issues in the specification and synthesis of digital systems, December 02-03, 2002, Monterey, California, USA
	Chandu Visweswariah, Death, taxes and failing chips, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	J. A. G. Jess , K. Kalafala , S. R. Naidu , R. H. J. M. Otten , C. Visweswariah, Statistical timing for parametric yield prediction of digital integrated circuits, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	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
	Aseem Agarwal , David Blaauw , Vladimir Zolotov , Sarma Vrudhula, Statistical timing analysis using bounds and selective enumeration, Proceedings of the 8th ACM/IEEE international workshop on Timing issues in the specification and synthesis of digital systems, December 02-03, 2002, Monterey, California, USA
	J. Dambre , D. Stroobandt , J. Van Campenhout, A probabilistic approach to clock cycle prediction, Proceedings of the 8th ACM/IEEE international workshop on Timing issues in the specification and synthesis of digital systems, December 02-03, 2002, Monterey, California, USA
	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
	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
	Li-C. Wang , T. M. Mak , Kwang-Ting Cheng , Magdy S. Abadir, On path-based learning and its applications in delay test and diagnosis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Puneet Gupta , Fook-Luen Heng, Toward a systematic-variation aware timing methodology, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	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
	Ashish Srivastava , Dennis Sylvester , David Blaauw, Statistical optimization of leakage power considering process variations using dual-Vth and sizing, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Frederic Worm , Paolo Ienne , Patrick Thiran , Giovanni De Micheli, On-Chip Self-Calibrating Communication Techniques Robust to Electrical Parameter Variations, IEEE Design & Test, v.21 n.6, p.524-535, November 2004
	Shuji Tsukiyama, Toward stochastic design for digital circuits: statistical static timing analysis, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.762-767, January 27-30, 2004, Yokohama, Japan
	Frédéric Worm , Paolo Ienne , Patrick Thiran , Giovanni De Micheli, A robust self-calibrating transmission scheme for on-chip networks, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.13 n.1, p.126-139, January 2005
	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
	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
	Hailin Jiang , Kai Wang , Malgorzata Marek-Sadowska, Clock skew bounds estimation under power supply and process variations, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, 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
	Jie Yang , Luigi Capodieci , Dennis Sylvester, Advanced timing analysis based on post-OPC extraction of critical dimensions, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	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
	Yu Cao , Lawrence T. Clark, Mapping statistical process variations toward circuit performance variability: an analytical modeling approach, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	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
	Lizheng Zhang , Yuhen Hu , Charlie Chung-Ping Chen, Block based statistical timing analysis with extended canonical timing model, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Liang Deng , Martin D. F. Wong, An exact algorithm for the statistical shortest path problem, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Fang Liu , Sule Ozev, Hierarchical analysis of process variation for mixed-signal systems, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	B. Lasbouygues , R. Wilson , N. Azemard , P. Maurine, Timing analysis in presence of supply voltage and temperature variations, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Michael Orshansky , Wei-Shen Wang , Martine Ceberio , Gang Xiang, Interval-based robust statistical techniques for non-negative convex functions, with application to timing analysis of computer chips, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Jie Yang , Ethan Cohen , Cyrus Tabery , Norma Rodriguez , Mark Craig, An up-stream design auto-fix flow for manufacturability enhancement, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Y. Satish Kumar , Jun Li , Claudio Talarico , Janet Wang, A Probabilistic Collocation Method Based Statistical Gate Delay Model Considering Process Variations and Multiple Input Switching, Proceedings of the conference on Design, Automation and Test in Europe, p.770-775, March 07-11, 2005
	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
	Lizheng Zhang , Yuhen Hu , Charlie Chung-Ping Chen, Statistical timing analysis with path reconvergence and spatial correlations, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
	Siddharth Garg , Diana Marculescu, Interactive presentation: System-level process variation driven throughput analysis for single and multiple voltage-frequency island designs, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Min Chen , Wei Zhao , Frank Liu , Yu Cao, Fast statistical circuit analysis with finite-point based transistor model, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Jamil Kawa , Charles Chiang, DFM issues for 65nm and beyond, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
	Stephen P. Boyd , Seung-Jean Kim , Dinesh D. Patil , Mark A. Horowitz, Digital Circuit Optimization via Geometric Programming, Operations Research, v.53 n.6, p.899-932, November-December 2005
	Xin Li , Jiayong Le , Lawrence T. Pileggi, Statistical performance modeling and optimization, Foundations and Trends® in Electronic Design Automation, v.1 n.4, p.331-480, April 2006
	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
	Feng Wang , Yuan Xie , Hai Ju, A novel criticality computation method in statistical timing analysis, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Sarvesh Bhardwaj , Praveen Ghanta , Sarma Vrudhula, A framework for statistical timing analysis using non-linear delay and slew models, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	B. Lasbouygues , R. Wilson , N. Azemard , P. Maurine, Temperature and voltage aware timing analysis: application to voltage drops, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	L. Lee , Li-C Wang , T. M. Mak , Kwang-Ting Cheng, A path-based methodology for post-silicon timing validation, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.713-720, November 07-11, 2004
	Yaping Zhan , A. J. Strojwas , M. Sharma , D. Newmark, Statistical critical path analysis considering correlations, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.699-704, November 06-10, 2005, San Jose, CA
	Xin Li , Jiayong Le , Mustafa Celik , L. T. Pileggi, Defining statistical sensitivity for timing optimization of logic circuits with large-scale process and environmental variations, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.844-851, November 06-10, 2005, San Jose, CA
	S. Tirumala , Y. Mahotin , X. Lin , V. Moroz , L. Smith , S. Krishnamurthy , L. Bomholt , D. Pramanik, Bringing Manufacturing into Design via Process-Dependent SPICE Models, Proceedings of the 7th International Symposium on Quality Electronic Design, p.801-806, March 27-29, 2006
	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
	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
	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
	Cristinel Ababei , Kia Bazargan, Placement Method Targeting Predictability Robustness and Performance, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.81, November 09-13, 2003
	Anand Rajaram , Bing Lu , Wei Guo , Rabi Mahapatra , Jiang Hu, Analytical Bound for Unwanted Clock Skew due to Wire Width Variation, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.401, November 09-13, 2003
	Puneet Gupta , Andrew B. Kahng, Manufacturing-Aware Physical Design, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.681, November 09-13, 2003
	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
	Aseem Agarwal , David Blaauw , Vladimir Zolotov, Statistical Clock Skew Analysis Considering Intra-Die Process Variations, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.914, November 09-13, 2003
	Aseem Agarwal , David Blaauw , Vladimir Zolotov , Sarma Vrudhula, Statistical Timing Analysis Using Bounds, Proceedings of the conference on Design, Automation and Test in Europe, p.10062, March 03-07, 2003
	Fang Liu , Jacob J. Flomenberg , Devaka V. Yasaratne , Sule Ozev, Hierarchical Variance Analysis for Analog Circuits Based on Graph Modelling and Correlation Loop Tracing, Proceedings of the conference on Design, Automation and Test in Europe, p.126-131, March 07-11, 2005
	Hratch Mangassarian , Mohab Anis, On Statistical Timing Analysis with Inter- and Intra-Die Variations, Proceedings of the conference on Design, Automation and Test in Europe, p.132-137, March 07-11, 2005
	Lizheng Zhang , Weijen Chen , Yuhen Hu , Charlie Chung-Ping Chen, Statistical Timing Analysis with Extended Pseudo-Canonical Timing Model, Proceedings of the conference on Design, Automation and Test in Europe, p.952-957, March 07-11, 2005
	Bao Liu, Signal probability based statistical timing analysis, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany
	Ravikishore Gandikota , David Blaauw , Dennis Sylvester, Modeling crosstalk in statistical static timing analysis, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	Fang Liu , Sule Ozev , Plamen K. Nikolov, Parametric variability analysis for multistage analog circuits using analytical sensitivity modeling, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.2, p.1-28, April 2008
	Lara Dolecek , Masood Qazi , Devavrat Shah , Anantha Chandrakasan, Breaking the simulation barrier: SRAM evaluation through norm minimization, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Cristiano Forzan , Davide Pandini, Statistical static timing analysis: A survey, Integration, the VLSI Journal, v.42 n.3, p.409-435, June, 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