A parallel and randomized algorithm for large-scale discrete dual-Vt assignment and continuous gate sizing

ABSTRACT

We propose a parallel and randomized algorithm to solve the problem of discrete dual-Vt assignment combined with continuous gate sizing which is an important low power design technique in high performance domains. This combinatorial optimization problem is particularly difficult to solve on large-sized circuits. We first introduce a hybrid algorithm which combines the existing heuristics and convex formulations for this problem to achieve a better tradeoff between the runtime of the algorithm and the quality of generated solution. We then extend our algorithm to include parallelism and randomization. We introduce a unique utilization of parallelism to better identify the optimization direction. Consequently, we can reduce both the number of iterations in optimization as well as improve the quality of solution. We further use random sampling to avoid being trapped in local minima and to focus the optimization effort on the more "promising" regions of the solution space. Our algorithm improves the average power by 37% compared to an approach which is based on solving a continuous convex program and applying discretization. Power improvement is over 50% for larger benchmarks for an implementation on a grid of 9 computers.

REFERENCES

• 1: Chung-Ping Chen , Chris C. N. Chu , D. F. Wong, Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.617-624, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289097]
• 2: H. Chou, Y.-H. Wang, and C. C.-P. Chen. Fast and effective gate-sizing with multiple-vt assignment using generalized lagrangian relaxation. 2005.
• 3: iscas benchmarks available at:. http://www.fm.vslib.cz/~kes/asic/iscas/.
• 4: Tanay Karnik , Yibin Ye , James Tschanz , Liqiong Wei , Steven Burns , Venkatesh Govindarajulu , Vivek De , Shekhar Borkar, Total power optimization by simultaneous dual-Vt allocation and device sizing in high performance microprocessors, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514042]
• 5: mosek optimization. available at: http://www.mosek.com.
• 6: Jeegar Tilak Shah , Marius Evers , Jeff Trull , Alper Halbutogullari, Circuit optimization for leakage power reduction using multi-threshold voltages for high performance microprocessors, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA [doi>10.1145/1231996.1232010]
• 7: S. Shah , A. Srivastava , D. Sharma , D. Sylvester , D. Blaauw , V. Zolotov, Discrete Vt assignment and gate sizing using a self-snapping continuous formulation, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.705-712, November 06-10, 2005, San Jose, CA
• 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: Vijay Sundararajan , Keshab K. Parhi, Low power synthesis of dual threshold voltage CMOS VLSI circuits, Proceedings of the 1999 international symposium on Low power electronics and design, p.139-144, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313900]
• 10: T. Tannenbaum, D. Wright, K. Miller, and M. Livny. Condor -- A Distributed Job Scheduler. MIT Press, October 2001.
• 11: H. Tennakoon and C. Sechen. Gate sizing using lagrangian relaxation combined with a fast gradient-based pre-processing step. Proc. Des. Autom. Conference, 2007.
• 12: N. R. Tool. available at: http://www.nlreg.com.
• 13: Andreas Wächter , Chandu Visweswariah , Andrew R. Conn, Large-scale nonlinear optimization in circuit tuning, Future Generation Computer Systems, v.21 n.8, p.1251-1262, October 2005 [doi>10.1016/j.future.2005.04.002]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Reliability

Keywords:
large-scale mixed-mode optimization, power optimization