A fast algorithm for power grid design

ABSTRACT

This paper presents an efficient heuristic algorithm to design a power distribution network of a chip by employing a successive partitioning and grid refinement scheme. In an iterative procedure, the chip area is recursively bipartitioned, and the wire pitches and the wire widths of the power grid in the partitions are repeatedly adjusted to meet the voltage drop and current density specifications. By using the macromodels of the power grid constructed in the previous levels of partitioning, the scheme ensures that a small global power grid system is simulated in each iteration. A post-processing step at the end of the optimization is employed to maximize the alignment of wires in adjacent partitions. The effectiveness of the scheme is demonstrated by designing various power grids with real circuit parameters and realistic input current values. The proposed algorithm is able to design power grids comprising thousands of wires and more than a million electrical nodes in about 7-16 minutes. The proposed design scheme as compared to a multigrid-based power grid design scheme saves about 7%-12% of wire area.

REFERENCES

• 1: X. D. S. Tan et al. Reliability-Constrained Area Optimization of VLSI Power/Ground Networks Via Sequence of Linear Programmings. In IEEE Trans. on CAD, volume 22, pages 1678--1684, Dec 2003.
• 2: X.-D. Sheldon Tan , C.-J. Richard Shi, Fast power/ground network optimization based on equivalent circuit modeling, Proceedings of the 38th conference on Design automation, p.550-554, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379021]
• 3: Xiaohai Wu , Xianlong Hong , Yici Cai , C. K. Cheng , Jun Gu , Wayne Dai, Area minimization of power distribution network using efficient nonlinear programming techniques, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 4: Optimization of the Power/Ground Network Wire-Sizing and Spacing Based on Sequential Network Simplex Algorithm, Proceedings of the 3rd International Symposium on Quality Electronic Design, p.157, March 18-21, 2002
• 5: K. Wang and M. M-Sadowska. On-chip Power Supply Network Optimization using Multigrid-based Technique. In Proc. ACM/IEEE DAC, pages 113--118, 2004.
• 6: Min Zhao , Yuhong Fu , Vladimir Zolotov , Savithri Sundareswaran , Rajendran Panda, Optimal placement of power supply pads and pins, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996615]
• 7: Jaskirat Singh , Sachin S. Sapatnekar, Topology optimization of structured power/ground networks, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981093]
• 8: T. Mitsuhashi , E. S. Kuh, Power and ground network topology optimization for cell based VLSIs, Proceedings of the 29th ACM/IEEE conference on Design automation, p.524-529, June 08-12, 1992, Anaheim, California, United States
• 9: H. Cai, Multi-pads, single layer power net routing in VLSI circuits, Proceedings of the 25th ACM/IEEE conference on Design automation, p.183-188, June 12-15, 1988, Atlantic City, New Jersey, United States
• 10: Jaewon Oh , Massoud Pedram, Multi-pad power/ground network design for uniform distribution of ground bounce, Proceedings of the 35th annual conference on Design automation, p.287-290, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277128]
• 11: Haihua Su , Kaushik Gala , Sachin S. Sapatnekar, Fast analysis and optimization of power/ground networks, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 12: 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]
• 13: E. Chiprout, Fast flip-chip power grid analysis via locality and grid shells, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.485-488, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382626]
• 14: Min Zhao , Rajendran V. Panda , Sachin S. Sapatnekar , Tim Edwards , Rajat Chaudhry , David Blaauw, Hierarchical analysis of power distribution networks, Proceedings of the 37th conference on Design automation, p.150-155, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337355]
• 15: H. Kriplani, F. Najm, and I. Hajj. Pattern Independent Maximum Current Estimation in Power and Ground Buses of CMOS VLSI Circuits : Algorithms, Signal Correlations, and Their Resolution. In Proc. IEEE/ACM ICCAD, pages 998--1012, 1995.
• 16: http://www.netlib.org/c/meschach.
• 17: Kevin Skadron , Mircea R. Stan , Wei Huang , Sivakumar Velusamy , Karthik Sankaranarayanan , David Tarjan, Temperature-aware microarchitecture, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 18: W. Liao, L. He, and K. Lepak. Temperature-Aware Performance and Power Modeling. In Technical Report UCLA Engr. 04-250.
• 19: Semiconductor Industry Association. International Technology Roadmap for Semiconductors, 2001. Available at http://public.itrs.net.
• 20: J. Cong. An Interconnect-Centric Design Flow for Nanometer Technologies. In Proc. IEEE, volume 89, pages 477--480, 2000.
• 21: C. Lawrence et al. User's gude for cfsqp version 2.4. Institute for Systems Research, University of Maryland, College Park, MD, Tech. Rep. TR-94-16rl, 1996.

INDEX TERMS

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

Keywords:
bipartitioning, locality, macromodel, optimization, power grid design, wire pitch