A novel approach for variation aware power minimization during gate sizing

ABSTRACT

Increasing dominance of process variations in the nanometer designs are posing significant challenges for circuit design and optimization. The variations in parameters such as channel length and the gate oxide thickness impacts circuit delay and power. In this paper, we propose a new gate sizing algorithm using fuzzy mathematical programming (FMP) in which the uncertainty due to process variations is modeled using fuzzy numbers. The variations in gate delay, which is a function of gate sizes and the fan-outs of the gate, are represented using triangular fuzzy numbers with linear membership functions. The variation aware gate sizing problem is formulated as a fuzzy mathematical program to perform a delay constrained power minimization in the presence of variations. Initially, a deterministic optimization is performed by fixing the fuzzy parameters to the worst and the average case values and the results are used to convert the fuzzy optimization problem into a crisp non-linear problem which is then solved using a non-linear optimization solver. The above model with delay and power as constraints, maximizes the robustness, i.e., the variation resistance of the circuit and thus the yield. The proposed approach was tested on ISCAS '85 benchmarks and the results were validated for timing yield using monte-carlo simulations. The fuzzy approach yields significantly better results compared to stochastic programming based gate sizing approach with a comparable runtime.

REFERENCES

• 1: Xiaoliang Bai, Chandu Visweswariah, N. Philip Strenski, and J. David Hathway. Uncertainty-Aware Circuit Optimization. Design Automation journal, pages 58--63, 2002.
• 2: R. E Bellman and L. A Zadeh. Decision Making in Fuzzy Environment. Management Science, pages 141--164, 1970.
• 3: 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
• 4: J. J. Buckley, Stochastic versus possibilistic programming, Fuzzy Sets and Systems, v.34 n.2, p.173-177, Jan. 30 1990 [doi>10.1016/0165-0114(90)90156-Z]
• 5: Srinivas Devadas, H. F Jyu, Kurt Keutzer, and Sharad Malik. Statistical Timing Analysis of Combinational Circuits. International journal on Computer Design, pages 38--43, 1992.
• 6: Anirudh Devgan and Chandramouli Kashyap. Block-based Static Timing Analysis with Uncertainty. International journal on Computer Aided Design, pages 607--614, 2003.
• 7: J. P Fishburn and A. E Dunlop. TILOS : A Posynomial Programming Approach to Transistor Sizing. IEEE Transactions on CAD, pages 326--336, 1985.
• 8: N. Rafail Gasimov and Kursat Yenilmez. Fuzzy Linear Programming Problems with Fuzzy Membership Functions. Mathematical Subject Classification, pages 375--396, 2000.
• 9: Masanori Hashimoto , Hidetoshi Onodera, A performance optimization method by gate sizing using statistical static timing analysis, Proceedings of the 2000 international symposium on Physical design, p.111-116, May 2000, San Diego, California, United States [doi>10.1145/332357.332385]
• 10: Ireneusz Karkowski. Architectural Synthesis with possibilistic programming. International journal on system sciences, pages 14--22, 1995.
• 11: M. Mani and M. Orshansky. A New Statistical Optimization Algorithm for Gate Sizing. International journal on Computer Design, pages 272--277, 2004.
• 12: Murari Mani, Anirudh Devgan, and Michael Orshansky. An Efficient Algorithm for Statistical Minimization of Total Power under Timing Yield Constraints. Design Automation journal, pages 309--314, 2005.
• 13: A. K Murugavel and N. Ranganathan. Gate Sizing and Buffer Insertion using Economic models for Power Optimization. International journal on VLSI Design, pages 195--200, 2004.
• 14: Masatoshi Sakawa, Genetic Algorithms and Fuzzy Multiobjective Optimization, Kluwer Academic Publishers, Norwell, MA, 2001
• 15: C. Schmidt and Grossmanm I.E. The exact overall time distribution of uncertain task durations. European journal of Operational Research, 2000.
• 16: Jaskirat Singh, Vidyasagar Nookala, Zhi-Quan Luo, and Sachin Sapatnekar. Robust Gate Sizing by Geometric Programming. Design Automation journal, pages 315--320, 2005.
• 17: J.F Tang, D.W Wang, Y.K Fung, and Yung K.L. Understanding of Fuzzy Optimization: Theories and Methods. journal of System Science and Complexity, pages 117--136, 2004.
• 18: Hiran Tennakoon , Carl Sechen, Gate sizing using Lagrangian relaxation combined with a fast gradient-based pre-processing step, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.395-402, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774631]

INDEX TERMS

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

General Terms:
Algorithms, Design