Timing budgeting under arbitrary process variations

ABSTRACT

Timing budgeting under process variations is an important step in a statistical optimization flow. We propose a novel formulation of the problem where budgets are statistical instead of deterministic as in existing works. This new formulation considers the changes of both the means and variances of delays, and thus can reduce the timing violation introduced by ignoring the changes of variances. We transform the problem to a linear programming problem using a robust optimization technique. Our approach can be used in late-stage design where the detailed distribution information is known, and is most useful in early-stage design since our approach does not assume specific underlying distributions. In addition, with the help of block-level timing budgeting, our approach can reduce the timing pessimism. Our approach is applied to the leakage power minimization problem. The results demonstrate that our approach can reduce timing violation from 690ps to Ops, and the worst total leakage power by 17.50% on average.

REFERENCES

• 1: 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]
• 2: C. Visweswariah , K. Ravindran , K. Kalafala , S. G. Walker , S. Narayan, First-order incremental block-based statistical timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996663]
• 3: 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
• 4: 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
• 5: D. Sinha , N. V. Shenoy , Hai Zhou, Statistical gate sizing for timing yield optimization, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.1037-1041, November 06-10, 2005, San Jose, CA
• 6: 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, Anaheim, California, USA [doi>10.1145/1065579.1065661]
• 7: Azadeh Davoodi , Ankur Srivastava, Variability driven gate sizing for binning yield optimization, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147152]
• 8: Ruiming Chen , Hai Zhou, Fast min-cost buffer insertion under process variations, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278567]
• 9: V. Sundararajan, S. S. Sapatnekar, and K. K. Parhi. Fast and exact transistor sizing based on iterative relaxation. IEEE Transactions on Computer Aided Design, 21(5):568--581, 2002.
• 10: Ruiming Chen , Hai Zhou, Efficient algorithms for buffer insertion in general circuits based on network flow, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.322-326, November 06-10, 2005, San Jose, CA
• 11: S. Ghiasi, E. Bozorgzadeh, P.-K Huang, R. Jafari, and M. Sarrafzadeh. A unified theory of timing budget management. IEEE Transactions on Computer Aided Design, 25(11):2364--2375, November 2006.
• 12: J. D. Ma , C. F. Fang , R. A. Rutenbar , Xiaolin Xie , D. S. Boning, Interval-valued statistical modeling of oxide chemical-mechanical polishing, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.141-148, November 06-10, 2005, San Jose, CA
• 13: Amith Singhee , Claire F. Fang , James D. Ma , Rob A. Rutenbar, Probabilistic interval-valued computation: toward a practical surrogate for statistics inside CAD tools, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146955]
• 14: Wei-Shen Wang , Vladik Kreinovich , Michael Orshansky, Statistical timing based on incomplete probabilistic descriptions of parameter uncertainty, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146954]
• 15: Wei-Shen Wang , Michael Orshansky, Robust estimation of parametric yield under limited descriptions of uncertainty, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233686]
• 16: D. Bertsimas and M. Sim. Robust discrete optimization and network flows. Mathematical Programming B, 98:49--71, 2003.
• 17: 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
• 18: MOSEK. Mosek aps optimization software. http://www.mosek.com.