Risk aversion min-period retiming under process variations

ABSTRACT

Recent advances in statistical timing analysis (SSTA) achieve great success in computing arrival times under variations by extending sum and maximum operations to random variables. It remains a challenge problem to apply such results in order to address the variability in circuit optimizations. In this paper, we study the statistical retiming problem, where retiming is a powerful sequential transformation that relocates flip-flops in a circuit without changing its functionality. We formulate the risk aversion min-period retiming problem under process variations based on conventional two-stage stochastic program with fixed recourse and a risk aversion objective of the clock period. We prove that the proposed problem is an integer convex program, show that the subgradient of the objective function can be derived from the combinational paths with the maximum path delay, and present a heuristic incremental algorithm to solve the proposed problem. Our approach can handle arbitrary gate delay model under process variations through sampling from a black-box and the effectiveness is confirmed by the experimental results. Further more, we point out how the current state-of-the-art SSTA techniques could be improved for future optimization algorithms when analytical models are available.

REFERENCES

• 1: D. Blaauw, K. Chopra, A. Srivastava, and L. Scheffer. Statistical Timing Analysis: From Basic Principles to State of the Art. IEEE TCAD, 27(4):589--607, Apr. 2008.
• 2: 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]
• 3: 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
• 4: D. Sinha, N. Shenoy, and H. Zhou. Statistical Timing Yield Optimization by Gate Sizing. IEEE TVLSI, 14(10):1140--1146, Oct. 2006.
• 5: A. Srivastava, K. Chopra, S. Shah, D. Sylvester, and D. Blaauw. A Novel Approach to Perform Gate-Level Yield Analysis and Optimization Considering Correlated Variations in Power and Performance. IEEE TCAD, 27(2):272--285, Feb. 2008.
• 6: M. Mani, A. Devgan, M. Orshansky, and Y. Zhan. A Statistical Algorithm for Power- and Timing-Limited Parametric Yield Optimization of Large Integrated Circuits. IEEE TCAD, 26(10):1790--1802, Oct. 2007.
• 7: J. Singh, Z.-Q. Luo, S. Sapatnekar. A Geometric Programming-Based Worst-Case Gate Sizing Method Incorporating Spatial Correlation. IEEE TCAD, 27(2):295--308, Feb. 2008.
• 8: 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]
• 9: R. J. -B. Wets. Stochastic Programs with Fixed Recourse: The Equivalent Deterministic Program. SIAM Review, 16(3):309--339, Jul. 1974.
• 10: C. E. Leiserson and J. B. Saxe. Retiming Synchronous Circuitry. Algorithmica, 6(1):5--35, 1991.
• 11: Jia Wang , Hai Zhou, Minimal period retiming under process variations, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA [doi>10.1145/988952.988985]
• 12: Hai Zhou, Deriving a new efficient algorithm for min-period retiming, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120774]
• 13: R. T. Rockafellar. Coherent Approaches to Risk in Optimization under Uncertainty. INFORMS TutORials in Operations Research, pages 38--61, 2007.
• 14: Jia Wang , Hai Zhou, An efficient incremental algorithm for min-area retiming, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391603]
• 15: David B. Shmoys , Chaitanya Swamy, Stochastic Optimization is (Almost) as easy as Deterministic Optimization, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.228-237, October 17-19, 2004 [doi>10.1109/FOCS.2004.62]
• 16: Nicole Immorlica , David Karger , Maria Minkoff , Vahab S. Mirrokni, On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 17: A. M. -C. So, J. Zhang, and Y. Ye. Stochastic Combinatorial Optimization with Controllable Risk Aversion Level. Lecture Notes in Computer Science, vol. 4110, pages 224--235, Aug. 2006.
• 18: Tony F. Chan , Jason Cong , Joseph R Shinnerl , Kenton Sze , Min Xie, mPL6: enhanced multilevel mixed-size placement, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123055]