Robust Optimization for Gate Sizing Considering Non-Gaussian Local Variations

Jin Sun Janet M. Roveda

Department of Electrical and Computer Engineering, The University of Arizona, Tucson, USA.

DOI: 10.4236/am.2014.516245                

Abstract

This paper employs a new second-order cone (SOC) model as the uncertainty set to capture non-Gaussian local variations. Then using robust gate sizing as an example, we describe the detailed procedures of robust design with a budget of uncertainty. For a pre-selected probability level of yield protection, this robust method translates uncertainty budgeting problems into regular robust optimization problems. More importantly, under the assumption of non-Gaussian distributions, we show that within-die variations will lead to varying sizes of uncertainty sets at different nominal values. By using this new model of uncertainty estimation, the robust gate sizing problem can be formulated as a Geometric Program (GP) and therefore efficiently solved.

Keywords

Robust Gate Sizing, Second Order Cone, Geometric Programming, Budget of Uncertainty, Parameter Variations

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Boning, D. and Nassif, S. (2001) Models of Process Variations in Device and Interconnect. In Chandrakasan, A., Bowhill, W.J. and Cox, F., Eds., Design of High-Performance Microprocessor Circuits, Chapter 6, IEEE Press, 98-115.
[2]	Roy, S. and Asenov, A. (2005) Where Do the Dopants Go? Science, 309, 388-390.
[3]	Orshansky, M., Milor, L. and Hu, C. (2004) Characterization of Spatial Intrafield Gate CD Variability, Its Impact on Circuit Performance, and Spatial Mask-Level Correction. IEEE Transactions on Semicondictor Manufacturing, 17, 2-11. http://dx.doi.org/10.1109/TSM.2003.822735
[4]	Hargreaves, B., Hult, H. and Reda, S. (2008) Within-Die Process Variations: How Accurately Can They Be Statistically Modeled? Proceedings of ASPDAC, Seoul, 21-24 March 2008, 524-530.
[5]	Veetil, V., Sylvester, D., Blaauw, D., Shah, S. and Rochel, S. (2009) Efficient Smart Sampling Based Full-Chip Leakage Analysis for Intra-Die Variation Considering State Dependence. Proceedings of DAC, San Francisco, 26-31 July 2009, 154-159.
[6]	Wang, J., Das, D. and Zhou, H. (2007) Gate Sizing by Lagrangian Relaxation Revisited. Proceedings of ICCAD, 111-118.
[7]	Ketkar, M., Kasamsetty, K. and Saptnekar, S. (2000) Convex Delay Models for Transistor Sizing. Proceedings of DAC, 655-660.
[8]	Kasamsetty, K., Ketkar, M. and Saptnekar, S. (2000) A New Class of Convex Functions for Delay Modeling and Its Application to the Transistor Sizing Problem. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 19, 779-788. http://dx.doi.org/10.1109/43.851993
[9]	Shyu, J.M., Sangiovanni-Vincentelli, A., Fishburn, J.P. and Dunlop, A.E. (1988) Optimization-Based Transistor Sizing. IEEE Journal of Solid-State Circuits, 23, 400-409. http://dx.doi.org/10.1109/4.1000
[10]	Cong, J., Lee, J. and Vandenberghe, L. (2008) Gate Sizing by Lagrangian Relaxation Revisited. Proceedings of International Symposium on Physical Design (ISPD), 10-14.
[11]	Singh, J., Nookala, V., Luo, Z. and Sapatnekar, S. (2011) A Geometric Programming-Based Worst Case Gate Sizing Method Incorporating Spatial Correlation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 53, 464-501.
[12]	Li, X., Gopalakrishnan, P., Xu, Y. and Pileggi, L. (2007) Robust Analog/RF Circuit Design with Projection-Based Performance Modeling. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 26, 2-15. http://dx.doi.org/10.1109/TCAD.2006.882513
[13]	Hsiung, K.L., Kim, S.J. and Boyd, S. (2008) Tractable Approximate Robust Geometric Programming. Optimization and Engineering, 9, 95-118. http://dx.doi.org/10.1007/s11081-007-9025-z
[14]	Xu, Y., Hsiung, K.L., Li, X., Pileggi, L.T. and Boyd, S.P. (2009) Regular Analog/RF Integrated Circuits Design Using Optimization with Recourse Including Ellipsoidal Uncertainty. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 28, 623-637. http://dx.doi.org/10.1109/TCAD.2009.2013996
[15]	Bertsimas, D., Brown, D.B. and Caramanis, C. (2008) Theory and Applications of Robust Optimization. SIAM Review, 27, 295-308.
[16]	Dyer, M. and Stougie, L. (2006) Computational Complexity of Stochastic Programming Problems. Mathematical Programming: Series A and B, 106, 423-432. http://dx.doi.org/10.1007/s10107-005-0597-0
[17]	Xu, Y., Hsiung, K.L. and Li, X. (2005) Opera: Optimization with Ellipsoidal Uncertainty for Robust Analog IC Design. Proceedings of Design Automation Conference, Anaheim, 13-17 June 2005, 632-637.
[18]	Johnson, R.A. and Wichern, D.W. (2002) Applied Multivariate Statistical Analysis. Prentice Hall, Upper Saddle River.
[19]	Boyd, S. and Vandenberghe, L. (2004) Convex Optimization. Cambridge University Press, New York.
[20]	Lobo, M., Vandenberghe, L., Boyd, S. and Lebret, H. (1998) Applications of Second-Order Cone Programming. Linear Algebra and Its Applications, 284, 193-228. http://dx.doi.org/10.1016/S0024-3795(98)10032-0
[21]	Xiong, J., Zolotov, V. and He, L. (2006) Robust Extraction of Spatial Correlation. Proceedings of International Symposium on Physical Design, San Jose, 9-12 April 2006, 2-9.
[22]	Chang, H. and Sapatnekar, S. (2003) Statistical Timing Analysis Considering Spatial Correlation Using a Single Pert- Like Traversal. International Conference on Computer Aided Design, ICCAD-2003, 9-13 November 2003, 621-625.
[23]	Stein, M.L. (1999) Interpolation of Spatial Data. Springer, New York. http://dx.doi.org/10.1007/978-1-4612-1494-6
[24]	Ben-Tal, A. and Nemirovski, A. (2000) Robust Solutions of Linear Programming Problems Contaminated with Uncertain Data. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 88, 411-424.
[25]	Chiang, M. (2005) Geometric Programming for Communication Systems. Now Publishers, Hanover.
[26]	Nanoscale Integration and Modeling (NIMO) Group (2011) Predictive Technology Model (ptm). http://ptm.asu.edu
[27]	Boyd, S.P. (2011) Stephen p. Boyd—Software. Website, August. http://stanford.edu/~boyd/software.html