Fast decap allocation based on algebraic multigrid

ABSTRACT

Decap (decoupling capacitor) is an effective technique for suppressing power supply noise. Nevertheless, over-usage of decap usually causes excessive power dissipation. Therefore, the total decap area needs to be minimized subject to power supply noise constraints. This is a complicated nonlinear optimization problem that may have as many as millions of variables. We propose an algebraic multigrid (AMG) based method to handle the high complexity. An error compensation scheme is developed to compensate the accuracy loss during the AMG reduction. A charge based back-mapping method and a few other techniques are suggested to further improve the computation efficiency. Our method is flexible to use and can be easily integrated with other existing decap allocation works. When compared to several previous works, the results from our method are usually the closest to the optimum. Our method also runs fast and can solve circuits with up to 1 million nodes in about 11 minutes. In addition, it has better scalability than the previous works.

REFERENCES

• 1: Sudhakar Bobba , Tyler Thorp , Kathirgamar Aingaran , Dean Liu, IC power distribution challenges, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 2: Zhu, Power Distribution Network Design for VLSI, John Wiley & Sons, 2004
• 3: Howard H. Chen , David D. Ling, Power supply noise analysis methodology for deep-submicron VLSI chip design, Proceedings of the 34th annual conference on Design automation, p.638-643, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266307]
• 4: C. K. S. Zhao, C.-K. Koh, and K. Roy. Decoupling capacitance allocation and its application to power-supply noise-aware floorplanning. IEEE Trans. on Computer-Aided Design, 21(1):81--92, Jan. 2002.
• 5: H. Su, S. S. Sapatnekar, and S. R. Nassif. Optimal decoupling capacitor sizing and placement for standard cell layout designs. IEEE Trans. on Computer-Aided Design, 22(4):428--436, Apr. 2003.
• 6: Jingjing Fu , Zuying Luo , Xianlong Hong , Yici Cai , Sheldon X.-D. Tan , Zhu Pan, A fast decoupling capacitor budgeting algorithm for robust on-chip power delivery, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
• 7: Zhenyu Qi , Hang Li , Sheldon X. -D. Tan , Lifeng Wu , Yici Cai , Xianlong Hong, Fast Decap Allocation Algorithm For Robust On-Chip Power Delivery, Proceedings of the 6th International Symposium on Quality of Electronic Design, p.542-547, March 21-23, 2005 [doi>10.1109/ISQED.2005.57]
• 8: Hang Li , Zhenyu Qi , Sheldon X.-D. Tan , Lifeng Wu , Yici Cai , Xianlong Hong, Partitioning-based approach to fast on-chip decap budgeting and minimization, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065627]
• 9: K. Wang and M. Marek-Sadowask. On-chip power supply network optimization using multigrid-based technique. IEEE Trans. on Computer-Aided Design, 24(3):407--417, Mar. 2005.
• 10: W. Hackbusch. Multigrid Methods. Science Press, Beijing, China, 1988.
• 11: J. N. Kozhaya, S. R. Nassif, and F. N. Najm. A multigrid-like technique for power grid analysis. IEEE Trans. on Computer-Aided Design, 21(10):1148--1160, Oct. 2002.
• 12: Haihua Su , Emrah Acar , Sani R. Nassif, Power grid reduction based on algebraic multigrid principles, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775863]
• 13: Zhengyong Zhu , Bo Yao , Chung-Kuan Cheng, Power network analysis using an adaptive algebraic multigrid approach, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775862]
• 14: K. Stuben. Algebraic Multigrid (AMG): An Introduction with Applications, volume Guest appendix, in Multigrid Methods. Academic Press, New York, 2000, also available as GMD Report 70, Nov. 1999.
• 15: Cheng Zhuo , Jiang Hu , Kangsheng Chen, An Improved AMG-based Method for Fast Power Grid Analysis, Proceedings of the 7th International Symposium on Quality Electronic Design, p.290-295, March 27-29, 2006 [doi>10.1109/ISQED.2006.23]
• 16: H. H. Chen and J. S. Neely. Interconnect and circuit modeling techniques for full-chip power noise analysis. IEEE Trans. on Components Packaging II, 21, Issue 3:209--215, Aug. 1998.
• 17: http://aemdesign.com/downloadrfsqp.htm.
• 18: Y. Yuan and W. Sun. Optimization Theory and Method. Science Press, Beijing, China, 1997.
• 19: http://www.tau.ac.il/stoledo/taucs/.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids
  B.m MISCELLANEOUS
      Subjects: Design management

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
        G.1.10 Applications
      G.1.8 Partial Differential Equations
          Subjects: Multigrid and multilevel methods

General Terms:
Algorithms, Design, Performance