Robust gate sizing via mean excess delay minimization

ABSTRACT

We introduce mean excess delay as a statistical measure of circuit delay in the presence of parameter variations. The β-mean excess delay is defined as the expected delay of the circuits that exceed the β-quantile of the delay, so it is always an upper bound on the β-quantile. However, in contrast to the β-quantile, it preserves the convexity properties of the underlying delay distribution. We apply the β-mean excess delay to the circuit sizing problem, and use it to minimize the delay quantile over the gate sizes. We use the Analytic Centering Cutting Plane Method to perform the minimization and apply this sizing to the ISCAS '85 benchmarks. Depending on the structure of the circuit, it can make significant improvements on the 95% quantile

REFERENCES

• 1: David S. Atkinson , Pravin M. Vaidya, A cutting plane algorithm for convex programming that uses analytic centers, Mathematical Programming: Series A and B, v.69 n.1, p.1-43, July 25, 1995 [doi>10.1007/BF01585551]
• 2: Stephen P. Boyd , Seung-Jean Kim , Dinesh D. Patil , Mark A. Horowitz, Digital Circuit Optimization via Geometric Programming, Operations Research, v.53 n.6, p.899-932, November-December 2005 [doi>10.1287/opre.1050.0254]
• 3: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 4: 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]
• 5: C. Chen, C. Chu, and D. Wong. Fast and exact simultaneous gate and wire sizing by lagrangian relaxation. IEEE Trans. on Computer-Aided Design, 18(7):1014--1025, 1999.
• 6: 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]
• 7: L. He, A. Kahng, K. Tam, and J. Xiong. Simultaneous buffer insertion and wire sizing considering systemic CMP variation and random L_eff variation. IEEE Trans. on Computer-Aided Design, 26(5):845--857, 2007.
• 8: S. Joshi and S. Boyd. An efficient method for large-scale gate sizing. Submitted for publication, available at http://www.stanford.edu/~boyd/gatesizing.html.
• 9: 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
• 10: MOSEK ApS. The MOSEK Optimization Tools Version 5.0. Available from http://www.mosek.com.
• 11: Dinesh Patil , Sunghee Yun , Seung-Jean Kim , Alvin Cheung , Mark Horowitz , Stephen Boyd, A New Method for Design of Robust Digital Circuits, Proceedings of the 6th International Symposium on Quality of Electronic Design, p.676-681, March 21-23, 2005 [doi>10.1109/ISQED.2005.11]
• 12: M. Pelgrom, A. Duinmaijer, and A. Welbers. Matching properties of MOS transistors. In IEEE Journal of Solid-State Circuits, 24(5):1433--1439, 1989.
• 13: R. Rockafellar and S. Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 2(3):21--41, 2000.
• 14: Jaskirat Singh , Vidyasagar Nookala , Zhi-Quan Luo , Sachin Sapatnekar, Robust gate sizing by geometric programming, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065662]
• 15: 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
• 16: Chandu Visweswariah, Death, taxes and failing chips, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775921]
• 17: 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]
• 18: V. Wang, K. Agarwal, S. Nassif, K. Nowka, and D. Markovic. A design model for random process variability. To appear in ISQED '08.
• 19: 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]
• 20: Yaping Zhan , Andrzej J. Strojwas , Xin Li , Lawrence T. Pileggi , David Newmark , Mahesh Sharma, Correlation-aware statistical timing analysis with non-gaussian delay distributions, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065605]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.0 General

General Terms:
Algorithms, Design

Keywords:
conditional value-at-risk, geometric programming, process variation, robust gate sizing