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.
KeywordsRobust Gate SizingSecond Order ConeGeometric ProgrammingBudget of UncertaintyParameter Variations
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.
Roy, S. and Asenov, A. (2005) Where Do the Dopants Go? Science, 309, 388-390.
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
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.
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.
Wang, J., Das, D. and Zhou, H. (2007) Gate Sizing by Lagrangian Relaxation Revisited. Proceedings of ICCAD, 111-118.
Ketkar, M., Kasamsetty, K. and Saptnekar, S. (2000) Convex Delay Models for Transistor Sizing. Proceedings of DAC, 655-660.
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
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
Cong, J., Lee, J. and Vandenberghe, L. (2008) Gate Sizing by Lagrangian Relaxation Revisited. Proceedings of International Symposium on Physical Design (ISPD), 10-14.
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.
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
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
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
Bertsimas, D., Brown, D.B. and Caramanis, C. (2008) Theory and Applications of Robust Optimization. SIAM Review, 27, 295-308.
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
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.
Boyd, S. and Vandenberghe, L. (2004) Convex Optimization. Cambridge University Press, New York.
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
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.
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.
Stein, M.L. (1999) Interpolation of Spatial Data. Springer, New York. http://dx.doi.org/10.1007/978-1-4612-1494-6
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.
Chiang, M. (2005) Geometric Programming for Communication Systems. Now Publishers, Hanover.
Nanoscale Integration and Modeling (NIMO) Group (2011) Predictive Technology Model (ptm). http://ptm.asu.edu
Boyd, S.P. (2011) Stephen p. Boyd—Software. Website, August. http://stanford.edu/~boyd/software.html