Robust gate sizing via mean excess delay minimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Robust gate sizing via mean excess delay minimization

Full text

Pdf (245 KB)

Source

International Symposium on Physical Design archive
Proceedings of the 2008 international symposium on Physical design table of contents

Portland, Oregon, USA

SESSION: Physical optimization techniques with buffering and gate sizing table of contents

Pages 10-14

Year of Publication: 2008

ISBN:978-1-60558-048-7

Authors

Jason Cong	University of California at Los Angeles, Los Angeles, CA, USA
John Lee	University of California at Los Angeles, Los Angeles, CA, USA
Lieven Vandenberghe	University of California at Los Angeles, Los Angeles, CA, USA

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 41, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	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/1353629.1353634 What is a DOI?

ABSTRACT

We introduce mean excess delay as a statistical measure of circuit delay in the presence of parameter variations. The β-mean excess delay is defined as the expected delay of the circuits that exceed the β-quantile of the delay, so it is always an upper bound on the β-quantile. However, in contrast to the β-quantile, it preserves the convexity properties of the underlying delay distribution. We apply the β-mean excess delay to the circuit sizing problem, and use it to minimize the delay quantile over the gate sizes. We use the Analytic Centering Cutting Plane Method to perform the minimization and apply this sizing to the ISCAS '85 benchmarks. Depending on the structure of the circuit, it can make significant improvements on the 95% quantile

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	David S. Atkinson , Pravin M. Vaidya, A cutting plane algorithm for convex programming that uses analytic centers, Mathematical Programming: Series A and B, v.69 n.1, p.1-43, July 25, 1995 [doi>10.1007/BF01585551]
	2	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 [doi>10.1287/opre.1050.0254]
	3	Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
	4	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, Anaheim, California, USA [doi>10.1145/1065579.1065604]
	5	C. Chen, C. Chu, and D. Wong. Fast and exact simultaneous gate and wire sizing by lagrangian relaxation. IEEE Trans. on Computer-Aided Design, 18(7):1014--1025, 1999.
	6	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 [doi>10.1145/1146909.1147152]
	7	L. He, A. Kahng, K. Tam, and J. Xiong. Simultaneous buffer insertion and wire sizing considering systemic CMP variation and random L_eff variation. IEEE Trans. on Computer-Aided Design, 26(5):845--857, 2007.
	8	S. Joshi and S. Boyd. An efficient method for large-scale gate sizing. Submitted for publication, available at http://www.stanford.edu/~boyd/gatesizing.html.
	9	Murari Mani , Michael Orshansky, A New Statistical Optimization Algorithm for Gate Sizing, Proceedings of the IEEE International Conference on Computer Design, p.272-277, October 11-13, 2004
	10	MOSEK ApS. The MOSEK Optimization Tools Version 5.0. Available from http://www.mosek.com.
	11	Dinesh Patil , Sunghee Yun , Seung-Jean Kim , Alvin Cheung , Mark Horowitz , Stephen Boyd, A New Method for Design of Robust Digital Circuits, Proceedings of the 6th International Symposium on Quality of Electronic Design, p.676-681, March 21-23, 2005 [doi>10.1109/ISQED.2005.11]
	12	M. Pelgrom, A. Duinmaijer, and A. Welbers. Matching properties of MOS transistors. In IEEE Journal of Solid-State Circuits, 24(5):1433--1439, 1989.
	13	R. Rockafellar and S. Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 2(3):21--41, 2000.
	14	Jaskirat Singh , Vidyasagar Nookala , Zhi-Quan Luo , Sachin Sapatnekar, Robust gate sizing by geometric programming, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065662]
	15	D. Sinha , N. V. Shenoy , Hai Zhou, Statistical gate sizing for timing yield optimization, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.1037-1041, November 06-10, 2005, San Jose, CA
	16	Chandu Visweswariah, Death, taxes and failing chips, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775921]
	17	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]
	18	V. Wang, K. Agarwal, S. Nassif, K. Nowka, and D. Markovic. A design model for random process variability. To appear in ISQED '08.
	19	Wei-Shen Wang , Vladik Kreinovich , Michael Orshansky, Statistical timing based on incomplete probabilistic descriptions of parameter uncertainty, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146954]
	20	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, Anaheim, California, USA [doi>10.1145/1065579.1065605]