Computation and Refinement of Statistical Bounds on Circuit Delay

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computation and Refinement of Statistical Bounds on Circuit Delay

Full text

Pdf (176 KB)

Source

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

Anaheim, CA, USA

SESSION: Coping with variability: the end of deterministic design table of contents

Pages: 348 - 353

Year of Publication: 2003

ISBN:1-58113-688-9

Authors

Aseem Agarwal	University of Michigan, Ann Arbor, MI
David Blaauw	University of Michigan, Ann Arbor, MI
Vladimir Zolotov	Motorola, Inc., Austin, TX
Sarma Vrudhula	University of Arizona, Tucson, AZ

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 30, Citation Count: 27

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

ABSTRACT

The growing impact of within-die process variation has created the need for statistical timing analysis, where gate delays are modeled as random variables. Statistical timing analysis has traditionally suffered from exponential run time complexity with circuit size, due to arrival time dependencies created by reconverging paths in the circuit. In this paper, we propose a new approach to statistical timing analysis that is based on statistical bounds of the circuit delay. Since these bounds have linear run time complexity with circuit size, they can be computed efficiently for large circuits. Since both a lower and upper bound on the true statistical delay is available, the quality of the bounds can be determined. If the computed bounds are not sufficiently close to each other, we propose a heuristic to iteratively improve the bounds using selective enumeration of the sample space with additional run time. We demonstrate that the proposed bounds have only a small error and that by carefully selecting an small set of nodes for enumeration, this error can be further improved.

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	Vikas Mehrotra , Shiou Lin Sam , Duane Boning , Anantha Chandrakasan , Rakesh Vallishayee , Sani Nassif, A methodology for modeling the effects of systematic within-die interconnect and device variation on circuit performance, Proceedings of the 37th conference on Design automation, p.172-175, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337370]
	2	Srinivas Devadas , Horng-Fei Jyu , Kurt Keutzer , Sharad Malik, Statistical Timing Analysis of Combinational Circuits, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.38-43, October 11-14, 1992
	3	M. Berkelaar, "Statistical Delay Calculation, a Linear Time Method," Proc. TAU 1997
	4	Jing-Jia Liou , Kwang-Ting Cheng , Sandip Kundu , Angela Krstic, Fast statistical timing analysis by probabilistic event propagation, Proceedings of the 38th conference on Design automation, p.661-666, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379043]
	5	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]
	6	Timing Yield Estimation from Static Timing Analysis, Proceedings of the 2nd International Symposium on Quality Electronic Design, p.437, March 26-28, 2001
	7	Xiaoliang Bai , Chandu Visweswariah , Philip N. Strenski, Uncertainty-aware circuit optimization, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513935]
	8	F. Najm, R. Burch, P. Yang, I. Hajj, "Probabilistic simulation for reliability analysis of CMOS VLSI circuits" IEEE Trans. on CAD, 1990
	9	Feller, W., P. "An Introduction to Probability Theory and its Applications", Vol. 1,2 John Wiley & Sons, New York, 1970.
	10	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
	11	F. Brglez, H.Fujiwara, "A Neutral Netlist of 10 Combinatorial Benchmark Circuits", Proc. ISCAS, 1985, pp.695--698

CITED BY 27

	Farid N. Najm , Noel Menezes, Statistical timing analysis based on a timing yield model, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Chandu Visweswariah, Death, taxes and failing chips, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Seung Hoon Choi , Bipul C. Paul , Kaushik Roy, Novel sizing algorithm for yield improvement under process variation in nanometer technology, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Rajeev R. Rao , Anirudh Devgan , David Blaauw , Dennis Sylvester, Parametric yield estimation considering leakage variability, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	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
	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
	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
	Lei He , Andrew Kahng , King Ho Tam , Jinjun Xiong, Simultaneous buffer insertion and wire sizing considering systematic CMP variation and random leff variation, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Azadeh Davoodi , Vishal Khandelwal , Ankur Srivastava, Empirical models for net-length probability distribution and applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.10, p.1066-1075, October 2004
	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
	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
	Aseem Agarwal , Kaviraj Chopra , David Blaauw , Vladimir Zolotov, Circuit optimization using statistical static timing analysis, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Wai-Ching Douglas Lam , Cheng-Kok Koh, Process variation robust clock tree routing, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	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
	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
	Sari Onaissi , Farid N. Najm, A linear-time approach for static timing analysis covering all process corners, 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
	V. Khandelwal , A. Davoodi , A. Srivastava, Efficient statistical timing analysis through error budgeting, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.473-477, November 07-11, 2004
	K. R. Heloue , F. N. Najm, Statistical timing analysis with two-sided constraints, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.829-836, November 06-10, 2005, San Jose, CA
	Vishal Khandelwal , Azadeh Davoodi , Akash Nanavati , Ankur Srivastava, A Probabilistic Approach to Buffer Insertion, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.560, 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
	Kunhyuk Kang , Bipul C. Paul , Kaushik Roy, Statistical Timing Analysis using Levelized Covariance Propagation, Proceedings of the conference on Design, Automation and Test in Europe, p.764-769, 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
	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
	Jinjun Xiong , Kingho Tam , Lei He, Buffer Insertion Considering Process Variation, Proceedings of the conference on Design, Automation and Test in Europe, p.970-975, March 07-11, 2005