An expected-utility based approach to variation aware VLSI optimization under scarce information

ABSTRACT

In this research, we propose a novel approach for simultaneous optimization of power, crosstalk noise and delay via gate sizing, in the presence of scarce information about the distribution of the variations. The methodology uses the concepts of utility theory and risk minimization to identify a deterministic equivalent model of the stochastic problem, ensuring high levels of expected utilities of constraints, and significant speedup in the optimization process for large circuits. A comparative study with an existing gate sizing methodology shows that our method is multi-fold faster as well as comparable in terms of the optimization.

REFERENCES

• 1: 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]
• 2: Kanak Agarwal , Dennis Sylvester , David Blaauw , Frank Liu , Sani Nassif , Sarma Vrudhula, Variational delay metrics for interconnect timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996675]
• 3: E. Ballestero. Stochastic linear programming with scarce information: an approach from expected utility and bounded rationality applied to the textile industry. Engineering Optimization, 38(4):425--440, 2006.
• 4: Michel R. C. M. Berkelaar , Jochen A. G. Jess, Gate sizing in MOS digital circuits with linear programming, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
• 5: R. Byrd, J. Nocedal, and R. Waltz. KNITRO: An integrated package for nonlinear optimization. Large-Scale Nonlinear Optimization, pages 35--59.
• 6: H. Chang and S. Sapatnekar. Statistical timing analysis under spatial correlations. CAD , IEEE Transactions on, 24(9):1467--1482, 2005.
• 7: 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]
• 8: Feng Gao , John P. Hayes, Total power reduction in CMOS circuits via gate sizing and multiple threshold voltages, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065593]
• 9: Narender Hanchate , Nagarajan Ranganathan, Statistical Gate Sizing for Yield Enhancement at Post Layout Level, Proceedings of the IEEE Computer Society Annual Symposium on VLSI, p.245-252, March 09-11, 2007 [doi>10.1109/ISVLSI.2007.92]
• 10: 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]
• 11: O. Kwon. Perspective of the Future Semiconductor Industry: Challenges and Solutions. DAC'07, 2007.
• 12: V. Mahalingam, N. Ranganathan, and J. Harlow III. A fuzzy optimization approach for variation aware power minimization during gate sizing. IEEE Tran. on VLSI Systems, 2007, to appear.
• 13: 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
• 14: 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]
• 15: D. Sinha , Hai Zhou, Gate sizing for crosstalk reduction under timing constraints by Lagrangian relaxation, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.14-19, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382535]
• 16: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior.
• 17: T. Xiao and M. Marek-Sadowska. Crosstalk reduction by transistor sizing. Proc. ASP-DAC, pages 137--140, 1999.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

General Terms:
Design, Performance, Reliability

Keywords:
crosstalk noise, delay, gate sizing, power minimization, process variations, utility theory