Linear programming for sizing, Vth and Vdd assignment

ABSTRACT

Most circuit sizing tools calculate the tradeoff between each gate's delay and power or area, and then greedily change the gate with the best tradeoff. We show this is suboptimal. Instead we use a linear program to minimize circuit power. The linear program provides a fast and simultaneous analysis of how each gate affects gates it has a path to. Our approach reduces power by up to 30% compared to commercial software, with a 0.13um library. The runtime for posing and solving the linear program scales linearly with circuit size

REFERENCES

• 1: Bai, M., and Sylvester, D., "Analysis and Design of Level-Converting Flip-Flops for Dual-Vdd/Vth Integrated Circuits," IEEE International Symposium on System-on-Chip, 2003, pp. 151--154.
• 2: Fishburn, J.P., and Dunlop, A.E., "TILOS: A Posynomial Programming Approach to Transistor Sizing," International Conference on Computer-Aided Design, 1985, pp. 326--328.
• 3: Forrest, J., Nuez, D., and Lougee-Heimer, R., CLP User Guide, http://www.coin-or.org/Clp/userguide/
• 4: K. Kasamsetty, M. Ketkar and S. S. Sapatnekar, "A New Class of Convex Functions for Delay Modeling and their Application to the Transistor Sizing Problem," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 19, No. 7, 2000, pp. 779--788.
• 5: Sarvesh H. Kulkarni , Dennis Sylvester, High performance level conversion for dual VDD design, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.9, p.926-936, September 2004 [doi>10.1109/TVLSI.2004.833667]
• 6: Sarvesh H. Kulkarni , Ashish N. Srivastava , Dennis Sylvester, A new algorithm for improved VDD assignment in low power dual VDD systems, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013287]
• 7: David Nguyen , Abhijit Davare , Michael Orshansky , David Chinnery , Brandon Thompson , Kurt Keutzer, Minimization of dynamic and static power through joint assignment of threshold voltages and sizing optimization, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871545]
• 8: Ashish Srivastava , Dennis Sylvester , David Blaauw, Concurrent Sizing, Vdd and Vth Assignment for Low-Power Design, Proceedings of the conference on Design, automation and test in Europe, p.10718, February 16-20, 2004
• 9: 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
          Subjects: Optimization

General Terms:
Algorithms, Design, Performance

Keywords:
delay, linear program, power, sizing