Uncertainty-aware circuit optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Uncertainty-aware circuit optimization

Full text

Pdf (131 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: New perspectives in physical design table of contents

Pages: 58 - 63

Year of Publication: 2002

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

Authors

Xiaoliang Bai	UC San Diego, La Jolla, CA
Chandu Visweswariah	IBM T. J. Watson Research Center, Yorktown Heights, NY
Philip N. Strenski	IBM T. J. Watson Research Center, Yorktown Heights, NY

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

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

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.513935 What is a DOI?

ABSTRACT

Almost by definition, well-tuned digital circuits have a large number of equally critical paths, which form a so-called "wall" in the slack histogram. However, by the time the design has been through manufacturing, many uncertainties cause these carefully aligned delays to spread out. Inaccuracies in parasitic predictions, clock slew, model-to-hardware correlation, static timing assumptions and manufacturing variations all cause the performance to vary from prediction. Simple statistical principles tell us that the variation of the limiting slack is larger when the height of the wall is greater.Although the wall may be the optimum solution if the static timing predictions were perfect, in the presence of uncertainty in timing and manufacturing, it may no longer be the best choice. The application of formal mathematical optimization in transistor sizing increases the height of the wall, thus exacerbating the problem. There is also a practical matter that schematic restructuring downstream in the design methodology is easier to conceive when there are fewer equally critical paths. This paper describes a method that gives formal mathematical optimizers the incentive to avoid the wall of equally critical paths, while giving up as little as possible in nominal performance. Surprisingly, such a formulation reduces the degeneracy of the optimization problem and can render the optimizer more effective. This "uncertainty-aware" mode has been implemented and applied to several high-performance microprocessor macros. Numerical results are included.

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	R. K. Brayton, G. D. Hachtel, and A. L. Sangiovanni-Vincentelli. A survey of optimization techniques for integrated-circuit design. Proceedings of the IEEE, 69(10):1334--1362, October 1981.
	2	Robert King Brayton , R. Brayton, Sensitivity and Optimization, Elsevier Science Inc., New York, NY, 1980
	3	C.-P. Chen, C. N. Chu, and D. F. Wong, Fast and exact simultaneous gate and wire sizing by Lagrangian Relaxation. IEEE Transactions on Computer-Aided Design of ICs and Systems, 18(7), July 1999.
	4	A. R. Conn , I. M. Elfadel , W. W. Molzen, Jr. , P. R. O'Brien , P. N. Strenski , C. Visweswariah , C. B. Whan, Gradient-based optimization of custom circuits using a static-timing formulation, Proceedings of the 36th ACM/IEEE conference on Design automation, p.452-459, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309979]
	5	A. R. Conn , I. M. Gould , Ph. L. Toint, Global convergence of a class of trust region algorithms for optimization with simple bounds, SIAM Journal on Numerical Analysis, v.25 n.2, p.433-460, April 1988 [doi>10.1137/0725029]
	6	Andrew R. Conn , Nicholas I. M. Gould , Philippe L. Toint, A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds, SIAM Journal on Numerical Analysis, v.28 n.2, p.545-572, April 1991 [doi>10.1137/0728030]
	7	A. R. Conn , N. I. M. Gould , Ph L. Toint, Lancelot: A FORTRAN Package for Large-Scale Nonlinear Optimization (Release A), Springer-Verlag New York, Inc., Secaucus, NJ, 1992
	8	Andrew R. Conn , Luís N. Vicente , Chandu Visweswariah, Two-Step Algorithms for Nonlinear Optimization with Structured Applications, SIAM Journal on Optimization, v.9 n.4, p.924-947, 1999 [doi>10.1137/S1052623498334396]
	9	P. Feldmann, T. V. Nguyen, S. W. Director, and R. A. Rohrer. Sensitivity computation in piecewise approximate circuit simulation. IEEE Transactions on Computer-Aided Design of ICs and Systems, 10(2):171--183, February 1991.
	10	J. P. Fishburn and A. E. Dunlop. TILOSL: A posynomial programming approach to transistor sizing. IEEE International Conference on Computer-Aided Design, pages 326--328. November 1985.
	11	M. Hashimoto and H. Onodera. Increase in delay uncertainty by performance optimization. Proc. IEEE International Symposium on Circuits and Systems (ISCAS), pages 379--382, 2001.
	12	W. Nye, D. C. Riley, A. Sangiovanni-Vincentelli, and A. L. Tits. DELIGHT.SPICE: An optimization-based system for the design of integrated circuits. IEEE Transactions on Computer-Aided Design of ICs and Systems, CAD-7(4):501--519, April 1988.
	13	V. B. Rao, J. P. Soreff, T. B. Brodnax, and R. E. Mains. EinsTLT: transistor-level timing with EinsTimer. Proc. TAU, December 1999.
	14	Stephen E. Rich , Matthew J. Parker , Jim Schwartz, Reducing the frequency gap between ASIC and custom designs: a custom perspective, Proceedings of the 38th conference on Design automation, p.432-437, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378548]
	15	Chandu Visweswariah , Andrew R. Conn, Formulation of static circuit optimization with reduced size, degeneracy and redundancy by timing graph manipulation, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.244-252, November 07-11, 1999, San Jose, California, United States
	16	C. Visweswariah and R. A. Rohrer. Piecewise approximate circuit simulation. IEEE Transactions on Computer-Aided Design of ICs and Systems, 10(7):861--870, July 1991.çß

CITED BY 28

	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
	Murari Mani , Anirudh Devgan , Michael Orshansky, An efficient algorithm for statistical minimization of total power under timing yield constraints, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, 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
	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
	Matthew R. Guthaus , Natesan Venkateswaran , Vladimir Zolotov , Dennis Sylvester , Richard B. Brown, Optimization objectives and models of variation for statistical gate sizing, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
	Ashish Srivastava , Saumil Shah , Kanak Agarwal , Dennis Sylvester , David Blaauw , Stephen Director, Accurate and efficient gate-level parametric yield estimation considering correlated variations in leakage power and performance, 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
	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, San Diego, California, USA
	Animesh Datta , Swarup Bhunia , Jung Hwan Choi , Saibal Mukhopadhyay , Kaushik Roy, Speed binning aware design methodology to improve profit under parameter variations, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	N. Ranganathan , U. Gupta , V. Mahalingam, Simultaneous optimization of total power, crosstalk noise, and delay under uncertainty, Proceedings of the 18th ACM Great Lakes symposium on VLSI, May 04-06, 2008, Orlando, Florida, USA
	Yehia Massoud , Arthur Nieuwoudt, Modeling and design challenges and solutions for carbon nanotube-based interconnect in future high performance integrated circuits, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.2 n.3, p.155-196, July 2006
	Joonsoo Kim , Michael Orshansky, Towards formal probabilistic power-performance design space exploration, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA
	Matthew R. Guthaus , Dennis Sylvester , Richard B. Brown, Clock buffer and wire sizing using sequential programming, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Yan Lin , Lei He, Interactive presentation: Statistical dual-Vdd assignment for FPGA interconnect power reduction, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Swaroop Ghosh , Swarup Bhunia , Kaushik Roy, A new paradigm for low-power, variation-tolerant circuit synthesis using critical path isolation, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	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
	K. Chopra , S. Shah , A. Srivastava , D. Blaauw , D. Sylvester, Parametric yield maximization using gate sizing based on efficient statistical power and delay gradient computation, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.1023-1028, November 06-10, 2005, San Jose, CA
	M. R. Guthaus , N. Venkateswarant , C. Visweswariaht , V. Zolotov, Gate sizing using incremental parameterized statistical timing analysis, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.1029-1036, 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
	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
	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
	Jurjen Westra , Dirk-Jan Jongeneel , Ralph H. J. M. Otten , Chandu Visweswariah, Time Budgeting in a Wireplanning Context, Proceedings of the conference on Design, Automation and Test in Europe, p.10436, March 03-07, 2003
	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
	Shrirang K. Karandikar , Sachin S. Sapatnekar, Fast Comparisons of Circuit Implementations, Proceedings of the conference on Design, automation and test in Europe, p.20910, February 16-20, 2004
	Jaehyun Kim , Youngsoo Shin, Minimizing leakage power in sequential circuits by using mixed V_t flip-flops, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	V. Mahalingam , Nagarajan Ranganathan , Justin E. Harlow, A fuzzy optimization approach for variation aware power minimization during gate sizing, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.8, p.975-984, August 2008