Robust gate sizing by geometric programming

ABSTRACT

We present an efficient optimization scheme for gate sizing in the presence of process variations. Using a posynomial delay model, the delay constraints are modified to incorporate uncertainty in the transistor widths and effective channel lengths due to the process variations. An uncertainty ellipsoid method is used to model the random parameter variations. Spatial correlations of intra-die width and channel length variations are incorporated in the optimization procedure. The resulting optimization problem is relaxed to be a Geometric Program and is efficiently solved using convex optimization tools. The effectiveness of our robust gate sizing scheme is demonstrated by applying the optimization on the ISCAS '85 benchmark circuits and testing the optimized circuits by performing Monte Carlo simulations to model the process variations. By varying the size of the uncertainty ellipsoids, a trade-off between area and robustness is explored. Experimental results show that the timing yield of the robustly optimized circuits improves manifold over the traditional deterministically sized circuits. As compared to the worst-case design, the robust gate sizing solution having the same area, has fewer timing violations.

REFERENCES

• 1: J. Fishburn and A. Dunlop, "TILOS: A Posynomial Programming Approach to Transistor Sizing," in Proc. IEEE/ACM ICCAD, pp. 326--328, 1985.
• 2: S. Sapatnekar, V. B. Rao, P. M. Vaidya, and S. M. Kang, "An Exact Solution to the Transistor Sizing Problem for CMOS Circuits Using Convex Optimization," in IEEE Trans. on CAD, vol. 12, pp. 1621--1634, Nov 1993.
• 3: K. Kasamsetty, M. Ketkar, and S. S. Sapatnekar, "A New Class of Convex Functions for Delay Modeling and their Application to the Transistor Sizing Problem," in IEEE Trans. on CAD, vol. 19, pp. 779--788, Jul 1998.
• 4: Xiaoliang Bai , Chandu Visweswariah , Philip N. Strenski, Uncertainty-aware circuit optimization, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513935]
• 5: Sreeja Raj , Sarma B. K. Vrudhula , Janet Wang, A methodology to improve timing yield in the presence of process variations, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996694]
• 6: Seung Hoon Choi , Bipul C. Paul , Kaushik Roy, Novel sizing algorithm for yield improvement under process variation in nanometer technology, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996695]
• 7: E. T. A. F. Jacobs , M. R. C. M. Berkelaar, Gate sizing using a statistical delay model, Proceedings of the conference on Design, automation and test in Europe, p.283-291, March 27-30, 2000, Paris, France [doi>10.1145/343647.343782]
• 8: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 9: R. A. Johnson , D. W. Wichern, Applied multivariate statistical analysis, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 10: K. L. Hsiung, S. J. Kim and S. Boyd, "Robust Geometric Programming via Piecewise Linear Approximation," 2003. Submitted to Mathematical Programming, available at http://www.stanford.edu/~boyd/rgp.html.
• 11: H. L. A-Malek and A.-K. S. O. Hassan, "The Ellipsoidal Technique for Design centering and Region Approximation," in IEEE Trans. on CAD, vol. 10, pp. 1006--1014, Aug 1991.
• 12: S. Sapatnekar, P. M. Vaidya, and S. M. Kang, "Convexity-based Algorithms for Design Centering," in IEEE Trans. on CAD, vol. 13, pp. 1536--1549, Dec 1994.
• 13: Hongliang Chang , Sachin S. Sapatnekar, Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-Like Traversal, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.621, November 09-13, 2003 [doi>10.1109/ICCAD.2003.129]
• 14: 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 [doi>10.1109/ICCAD.2003.130]
• 15: S. Nassif, "Delay Variability: Sources, Impact and Trends," in Proc. ISSCC, pp. 368--369, 2000.
• 16: Available at http://www.mosek.com.
• 17: "TSMC: 180nm Test Data." Available at http://www.mosis.org/Technical/Testdata/tsmc-018-prm.html.
• 18: A. Caldwell, A. B. Kahng and I. Markov, "Capo: a largescale fixed-die placer." available at http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/Placement.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Design

Keywords:
gate sizing, geometric program, optimization, posynomial, uncertainty ellipsoid