Variability driven gate sizing for binning yield optimization

ABSTRACT

Process variations result in a considerable spread in the frequency of the fabricated chips. In high performance applications, those chips that fail to meet the nominal frequency after fabrication are either discarded or sold at a loss which is typically proportional to the degree of timing violation. The latter is called binning. In this paper we present a gate sizing-based algorithm that optimally minimizes the binning yield-loss. We make the following contributions: 1) prove the binning yield function to be convex, 2) do not make any assumptions about the sources of variability, and their distribution model, 3) we integrate our strategy with statistical timing analysis tools (STA), without making any assumptions about how STA is done, 4) if the objective is to optimize the traditional yield (and not binning yield) our approach can still optimize the same to a very large extent. Comparison of our approach with sensitivity-based approaches under fabrication variability shows an improvement of on average 72% in the binning yield-loss with an area overhead of an average 6%, while achieving a 2.69 times speedup under a stringent timing constraint. Moreover we show that a worst-case deterministic approach fails to generate a solution for certain delay constraints. We also show that optimizing the binning yield-loss minimizes the traditional yield-loss with a 61% improvement from a sensitivity-based approach.

REFERENCES

• 1: A. Agrawal, K. Chopra, D. Blaauw, and V. Zolotov. Circuit Optimization Using Statistical Static Timing Analysis. In DAC, pages 338--342, 2005.
• 2: A. Raychowdhury , S. Ghosh , K. Roy, A Novel On-Chip Delay Measurement Hardware for Efficient Speed-Binning, Proceedings of the 11th IEEE International On-Line Testing Symposium, p.287-292, July 06-08, 2005 [doi>10.1109/IOLTS.2005.10]
• 3: 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]
• 4: 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
• 5: 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, San Diego, California, USA [doi>10.1145/1065579.1065604]
• 6: http://www.mosek.com.
• 7: J. Fishburn and A. Dunlop. TILOS: A Posynomial Programming Approach to Transistor Sizing. In ICCAD, pages 326--328, 1985.
• 8: 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, San Diego, California, USA [doi>10.1145/1065579.1065662]
• 9: Jan M. Rabaey, Anantha Chandrakasan, and Borivoje Nikolić. Digital Integrated Circuits. Prentice Hall.
• 10: 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
• 11: 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, San Diego, California, USA [doi>10.1145/1065579.1065661]
• 12: 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
• 13: R. J-B Wets. Stochastic Programs with Fixed Recourse: The Equivalent Deterministic Program. In SIAM Review, pages 309--339, July 1974.
• 14: S. Bhardwaj, S. B.. K. Vrdhula. Leakage Minimization of Nano-scale Circuits in the Presence of Systematic and Random Variations. In ICCAD, Nov. 2005.
• 15: Shekhar Borkar , Tanay Karnik , Siva Narendra , Jim Tschanz , Ali Keshavarzi , Vivek De, Parameter variations and impact on circuits and microarchitecture, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775920]
• 16: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 17: 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 Transactions on CAD, pages 1621--1634, Nov. 1993.
• 18: Vishal Khandelwal , Ankur Srivastava, A general framework for accurate statistical timing analysis considering correlations, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065607]
• 19: Y. Cao, T. Sato, D. Sylvester, M. Orshansky, and C. Hu. New paradigm of predictive MOSFET and interconnect modeling for early circuit design. In Proc. of CICC, 2000.

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
gate sizing, process variations, speed binning