Fast statistical timing analysis by probabilistic event propagation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast statistical timing analysis by probabilistic event propagation

Full text

Pdf (98 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 661 - 666

Year of Publication: 2001

ISBN:1-58113-297-2

Authors

Jing-Jia Liou	Electrical and Computer Engineering Department, University of California, Santa Barbara
Kwang-Ting Cheng	Electrical and Computer Engineering Department, University of California, Santa Barbara
Sandip Kundu	Intel Corporation, Austin
Angela Krstic	Electrical and Computer Engineering Department, University of California, Santa Barbara

Sponsors

EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 46, Citation Count: 39

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

ABSTRACT

We propose a new statistical timing analysis algorithm, which produces arrival-time random variables for all internal signals and primary outputs for cell-based designs with all cell delays modeled as random variables. Our algorithm propagates probabilistic timing events through the circuit and obtains final probabilistic events (distributions) at all nodes. The new algorithm is deterministic and flexible in controlling run time and accuracy. However, the algorithm has exponential time complexity for circuits with reconvergent fanouts. In order to solve this problem, we further propose a fast approximate algorithm. Experiments show that this approximate algorithm speeds up the statistical timing analysis by at least an order of magnitude and produces results with small errors when compared with Monte Carlo methods.

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	Fred M. Armstrong , Mark R. Reiter , David R. Tryon, Statistical failure analysis of system timing, IBM Journal of Research and Development, v.28 n.4, p.340-355, July 1984
	2	H.-F. Jyu, S. Malik, S. Devadas, and K. Keutzer. Statistical Timing Analysis of Combinational Logic Circuits. IEEE Transactions on VLSI Systems, 1(2):126-137, June 1993.
	3	Horng-Fei Jyu , Sharad Malik, Statistical delay modeling in logic design and synthesis, Proceedings of the 31st annual conference on Design automation, p.126-130, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196304]
	4	Jing-Jia Liou , Angela Krstic , Kwang-Ting Cheng , Deb Aditya Mukherjee , Sandip Kundu, Performance sensitivity analysis using statistical method and its applications to delay, Proceedings of the 2000 conference on Asia South Pacific design automation, p.587-592, January 2000, Yokohama, Japan [doi>10.1145/368434.368817]
	5	Sharad C. Seth , Vishwani D. Agrawal, A new model for computation of probabilistic testability in combinational circuits, Integration, the VLSI Journal, v.7 n.1, p.49-75, April 1989 [doi>10.1016/0167-9260(89)90059-X]
	6	David Ihsin Cheng , Kwang-Ting Cheng , Deborah C. Wang , Malgorzata Marek-Sadowska, A new hybrid methodology for power estimation, Proceedings of the 33rd annual conference on Design automation, p.439-444, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240602]
	7	Synopsys. Design Compiler Reference Manual. May, 2000.
	8	Athanasios Papoulis, Probability and statistics, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990

CITED BY 39

	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
	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
	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
	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
	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
	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
	Lizheng Zhang , Yuhen Hu , Charlie, Chungping Chen, Statistical timing analysis in sequential circuit for on-chip global interconnect pipelining, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, 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
	Vineet Agarwal , Janet Wang, Yield-area optimizations of digital circuits using non-dominated sorting genetic algorithm (YOGA), Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	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
	Luis Guerra e Silva , L. Miguel Silveira , Joel R. Phillips, Efficient computation of the worst-delay corner, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Rajeshwary G. Tayade , Vijay Kiran Kalyanam , Sani Nassif , Michael Orshansky , Jacob Abraham, Estimating path delay distribution considering coupling noise, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
	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
	Brian Cline , Kaviraj Chopra , David Blaauw , Yu Cao, Analysis and modeling of CD variation for statistical static timing, 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
	W.-L. Hung , Xiaoxia Wu , Yuan Xie, Guaranteeing performance yield in high-level synthesis, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	R. A. Rutenbar , Li-C Wang , Kwang-Ting Cheng , S. Kundu, Static statistical timing analysis for latch-based pipeline designs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.468-472, November 07-11, 2004
	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
	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
	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
	Srinath R. Naidu, Timing Yield Calculation Using an Impulse-train Approach, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.219, January 07-11, 2002
	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
	Osama Neiroukh , Xiaoyu Song, Improving the Process-Variation Tolerance of Digital Circuits Using Gate Sizing and Statistical Techniques, Proceedings of the conference on Design, Automation and Test in Europe, p.294-299, March 07-11, 2005
	Aseem Agarwal , Kaviraj Chopra , David Blaauw, Statistical Timing Based Optimization using Gate Sizing, Proceedings of the conference on Design, Automation and Test in Europe, p.400-405, March 07-11, 2005
	Mango , C.-T. Chao , Li-C. Wang , Kwang-Ting Cheng, Pattern Selection for Testing of Deep Sub-Micron Timing Defects, Proceedings of the conference on Design, automation and test in Europe, p.2160, February 16-20, 2004
	Jinseob Jeong , Seungwhun Paik , Youngsoo Shin, Statistical mixed V_t allocation of body-biased circuits for reduced leakage variation, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
	Jongyoon Jung , Taewhan Kim, Timing variation-aware high-level synthesis, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Kanupriya Gulati , Sunil P. Khatri, Accelerating statistical static timing analysis using graphics processing units, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Chen Dong , Scott Chilstedt , Deming Chen, FPCNA: a field programmable carbon nanotube array, Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays, February 22-24, 2009, Monterey, California, USA
	HaNeul Chon , Taewhan Kim, Timing variation-aware task scheduling and binding for MPSoC, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	P. Marques Morgado , Paulo F. Flores , L. Miguel Silveira, Generating realistic stimuli for accurate power grid analysis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.3, p.1-26, May 2009