Hierarchical analysis of power distribution networks

ABSTRACT

Careful design and verification of the power distribution network of a chip are of critical importance to ensure its reliable performance. With the increasing number of transistors on a chip, the size of the power network has grown so large as to make the verification task very challenging. The available computational power and memory resources impose limitations on the size of networks that can be analyzed using currently known techniques. Many of today's designs have power networks that are too large to be analyzed in the traditional way as flat networks. In this paper, we propose a hierarchical analysis technique to overcome the aforesaid capacity limitation. We present a new technique for analyzing a power grid using macromodels that are created for a set of partitions of the grid. Efficient numerical techniques for the computation and sparsification of the port admittance matrices of the macromodels are presented. A novel sparsification technique using a 0-1 integer linear programming formulation is proposed to achieve superior sparsification for a specified error. The run-time and memory efficiency of the proposed method are illustrated through the analysis of case studies of several multi-million node power grids, extracted from real microprocessor and DSP designs.

REFERENCES

• 1: Abhijit Dharchoudhury , Rajendran Panda , David Blaauw , Ravi Vaidyanathan , Bogdan Tutuianu , David Bearden, Design and analysis of power distribution networks in PowerPC microprocessors, Proceedings of the 35th annual conference on Design automation, p.738-743, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277229]
• 2: Gregory Steele , David Overhauser , Steffen Rochel , Syed Zakir Hussain, Full-chip verification methods for DSM power distribution systems, Proceedings of the 35th annual conference on Design automation, p.744-749, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277231]
• 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: S. Taylor, "The challenge of designing global signals in UDSM CMOS," in CICC, pp. 429-435, 1999.
• 5: H. Kriplani, F. Najm, and I. Hajj, "Pattern independent minimum current estimation in power and ground buses of CMOS VLS! circuits," TCAD, vol. 14, no. 8, pp. 998-1012, 1995.
• 6: Angela Krstić , Kwang-Ting Cheng, Vector generation for maximum instantaneous current through supply lines for CMOS circuits, Proceedings of the 34th annual conference on Design automation, p.383-388, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266176]
• 7: Yi-Min Jiang , Tak K. Young , Kwang-Ting Cheng, VIP—an input pattern generator for indentifying critical voltage drop for deep sub-micron designs, Proceedings of the 1999 international symposium on Low power electronics and design, p.156-161, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313905]
• 8: G. H. Golub and C. F. V. Loan, Matrix Computations. Baltimore: The Johns Hopkins University Press, 1984.
• 9: C. Ho, A. Ruehli, and R Brennan, "The modified nodal approach to network analysis," IEEE Trans. Circuits and Systems, vol. CAS-22, no. 6, pp. 504-509, 1975.
• 10: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 11: Katta G. Murty, Operations research: deterministic optimization models, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 12: M. R. C. M. Berkelaar, "LP SOLVE 2.3 Users' Manual," 1998.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
  B.8 Performance and Reliability

  C. Computer Systems Organization

General Terms:
Design, Experimentation, Measurement, Performance, Theory, Verification