PRIMO

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

PRIMO: probability interpretation of moments for delay calculation

Full text

Pdf (254 KB)

Source

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

San Francisco, California, United States

Pages: 463 - 468

Year of Publication: 1998

ISBN:0-89791-964-5

Authors

Rony Kay	Department of Electrical and Computer Engineering, Carnegie Mellon University
Lawrence Pileggi	Department of Electrical and Computer Engineering, Carnegie Mellon University

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 12, Citation Count: 24

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

ABSTRACT

Moments of the impulse response are widely used for interconnect delay analysis, from the explicit Elmore delay (first moment of the impulse response) expression, to moment matching methods which create reduced order transimpedance and transfer function approximations. However, the Elmore delay is fast becoming ineffective for deep submicron technologies, and reduced order transfer function delays are impractical for use as early-phase design metrics or as design optimization cost functions. This paper describes an approach for fitting moments of the impulse response to probability density functions so that delays can be estimated from probability tables. For RC trees it is demonstrated that the incomplete gamma function provides a provably stable approximation. The step response delay is obtained from a one-dimensional table lookup.

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	C. Chu and M. Horowitz, Charge-Sharing Models fmSwitch- Level Simulation, Trans. on CAD, June, 1987.
	2	C. C. Craig, "A new Exposition and Chart for the Pearson system of Frequency Curves", Ann. Math. Statistics, vol. 7, 1936.
	3	W. C. Elmore, 'The Transient Response of Damped Linear Networks with Particular Regard toWideband Amplifiers", J. Applied Physics, vol. 19, no. 1, Jan. 1948.
	4	P. Feldman and R. W. Freund, "Efficient Linear Circuit Analysis by Padd Approximation Via the Lanczos Process", IEEE Tran. Computer-Aided Design, vol. 14, no. 5, May 1995.
	5	R. Gupta, B.Krauter and L. Pileggi, "Transmission Line Synthesis via Constrained Multivariable Optimization", IEEE Trans. Computer-Aided Design, Vol. 16, No. 1, Jan. 1997.
	6	R. Gupta, B. Tutuianu and L. Pileggi, 'TheElmore Delay as a Bound for RC Trees Generalized input Signals", IEEE Trans. Computer-Aided Design, vol. 16, no. 1, January 1997.
	7	M.A. Horowitz, Timing Models for MOS Circuits, Ph.D. thesis, Stanford University, January 1984.
	8	Andrew B. Kahng , Kei Masuko , Sudhakar Muddu, Analytical delay models for VLSI interconnects under ramp input, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.30-36, November 10-14, 1996, San Jose, California, United States
	9	M. G. Kendall and A. Stuart, 'The Advanced Theory of Statistics, vol. 1: Distribution Theory", New York: Hafner, 1969.
	10	Kevin J. Kerns , Ivan L. Wemple , Andrew T. Yang, Stable and efficient reduction of substrate model networks using congruence transforms, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.207-214, November 05-09, 1995, San Jose, California, United States
	11	H.J. Larson, "Introduction to Probability Theory and Statistical Inference", 3rd ed., John Wiley & Sons pub., 1982.
	12	Lin, E. Acar, and L. Pileggi, Camegie Mellon University, CMU Technical Report in Preparation.
	13	H. L MacGillivray, "The Mean, Median, Mode Inequality and Skewness for a Class of Densities", Australian J. of Statistics, vol. 23 no. 2, 1981.
	14	Altan Odabasioglu , Mustafa Celik , Lawrence T. Pileggi, PRIMA: passive reduced-order interconnect macromodeling algorithm, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.58-65, November 09-13, 1997, San Jose, California, United States
	15	L, T. Pillage and R. A. Rohrer, "Asymptotic Waveform Evaluation for Timing Analysis", Tran. on CAD, Apr. 1990.
	16	William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
	17	C. Ratzlaff and L.T. Pillage, "RICE: Rapid Interconnect Circuit Evaluator using Asymptotic Waveform Evaluation", IEEE Trans. Computer-Aided Design, Jun 1994.
	18	J. Rubenstein, P. Penfield and M. A. Horowitz, "Signal Delay in RC Tree Networks", Trans. on CAD, July 1983.
	19	L. Miguel Silveira , Mattan Kamon , Jacob White, Efficient reduced-order modeling of frequency-dependent coupling inductances associated with 3-D interconnect structures, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.376-380, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217558]
	20	S. M. Stigler, "The History of Statistics: The Measurement of Uncertainty before 1900", Belknap Press of Harvard University Press, 1986.
	21	Bogdan Tutuianu , Florentin Dartu , Lawrence Pileggi, An explicit RC-circuit delay approximation based on the first three moments of the impulse response, Proceedings of the 33rd annual conference on Design automation, p.611-616, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240634]

CITED BY 24

	Frank Liu , Chandramouli Kashyap , Charles J. Alpert, A delay metric for RC circuits based on the Weibull distribution, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.620-624, November 10-14, 2002, San Jose, California
	Tao Lin , Emrah Acar , Lawrence Pileggi, h-gamma: an RC delay metric based on a gamma distribution approximation of the homogeneous response, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.19-25, November 08-12, 1998, San Jose, California, United States
	Naofumi Tsujii , Katsutoshi Baba , Shuji Tsukiyama, An interconnect topology optimization by a tree transformation, Proceedings of the 2000 conference on Asia South Pacific design automation, p.93-98, January 2000, Yokohama, Japan
	Charles J. Alpert , Anirudh Devgan , Chandramouli Kashyap, A two moment RC delay metric for performance optimization, Proceedings of the 2000 international symposium on Physical design, p.69-74, May 2000, San Diego, California, United States
	Lawrence Pileggi, Timing metrics for physical design of deep submicron technologies, Proceedings of the 1998 international symposium on Physical design, p.28-33, April 06-08, 1998, Monterey, California, United States
	Shuji Tsukiyama , Masakazu Tanaka , Masahiro Fukui, A statistical static timing analysis considering correlations between delays, Proceedings of the 2001 conference on Asia South Pacific design automation, p.353-358, January 2001, Yokohama, Japan
	Youngsoo Shin , Takayasu Sakurai, Estimation of power distribution in VLSI interconnects, Proceedings of the 2001 international symposium on Low power electronics and design, p.370-375, August 2001, Huntington Beach, California, United States
	Xiaodong Yang , Walter H. Ku , Chung-Kuan Cheng, RLC interconnect delay estimation via moments of amplitude and phase response, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.208-213, November 07-11, 1999, San Jose, California, United States
	Kanak Agarwal , Dennis Sylvester , David Blaauw, Simple metrics for slew rate of RC circuits based on two circuit moments, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Bernard N. Sheehan, Predicting coupled noise in RC circuits by matching 1, 2, and 3 moments, Proceedings of the 37th conference on Design automation, p.532-535, June 05-09, 2000, Los Angeles, California, United States
	Chandramouli V. Kashyap , Charles J. Alpert , Frank Liu , Anirudh Devgan, PERI: a technique for extending delay and slew metrics to ramp inputs, 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
	Chandramouli V. Kashyap , Charles J. Alpert , Anirudh Devgan, An "effective" capacitance based delay metric for RC interconnect, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Charles J. Alpert , Frank Liu , Chandramouli Kashyap , Anirudh Devgan, Delay and slew metrics using the lognormal distribution, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Ruchir Puri , David S. Kung , Anthony D. Drumm, Fast and accurate wire delay estimation for physical synthesis of large ASICs, Proceedings of the 12th ACM Great Lakes symposium on VLSI, April 18-19, 2002, New York, New York, USA
	S. Abbaspour , A. H. Ajami , M. Pedram , E. Tuncer, TFA: a threshold-based filtering algorithm for propagation delay and slew calculation of high-speed VLSI interconnects, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
	Soroush Abbaspour , Hanif Fatemi , Massoud Pedram, VITA: variation-aware interconnect timing analysis for symmetric and skewed sources of variation considering variational ramp input, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
	Arif Ishaq Abou-Seido , Brian Nowak , Chris Chu, Fitted Elmore delay: a simple and accurate interconnect delay model, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.7, p.691-696, July 2004
	Chandramouli V. Kashyap , Charles J. Alpert , Frank Liu , Anirudh Devgan, Closed form expressions for extending step delay and slew metrics to ramp inputs, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Anand Ramalingam , Sreekumar V. Kodakara , Anirudh Devgan , David Z. Pan, Robust analytical gate delay modeling for low voltage circuits, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Xiao-Dong Yang , Chung-Kuan Cheng , Walter H. Ku , Robert Carragher, Reduced Order Modeling for RLC Interconnect Tree Using Hurwitz Polynomial, Analog Integrated Circuits and Signal Processing, v.31 n.3, p.193-208, June 2002
	J. Wang , P. Ghanta , S. Vrudhula, Stochastic analysis of interconnect performance in the presence of process variations, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.880-886, November 07-11, 2004
	Praveen Ghanta , Sarma Vrudhula, Variational Interconnect Delay Metrics for Statistical Timing Analysis, Proceedings of the 7th International Symposium on Quality Electronic Design, p.19-24, March 27-29, 2006
	Dinesh Pamunuwa , Shauki Elassaad , Hannu Tenhunen, Analytic Modeling of Interconnects for Deep Sub-Micron Circuits, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.835, November 09-13, 2003
	Rajib Kar , Ashish K. Mal , Anup K. Bhattacharjee, An accurate slew metric for on-chip VLSI interconnect using Weibull distribution function, Proceedings of the International Conference on Advances in Computing, Communication and Control, January 23-24, 2009, Mumbai, India