Fast power/ground network optimization based on equivalent circuit modeling

ABSTRACT

This paper presents an efficient algorithm for optimizing the area of power or ground networks in integrated circuits subject to the reliability constraints. Instead of solving the original power/ground networks extracted from circuit layouts as previous methods did, the new method first builds the equivalent models for many series resistors in the original networks, then the sequence of linear programming method [9] is used to solve the simplified networks. The solutions of the original networks then are back solved from the optimized, simplified networks. The new algorithm simply exploits the regularities in the power/ground networks. Experimental results show that the complexities of simplified networks are typically significantly smaller than that of the original circuits, which renders the new algorithm extremely fast. For instance, power/ground networks with more than one million branches can be sized in a few minutes on modern SUN workstations.

REFERENCES

• 1: J. R. Black, "Electromigration failure modes in aluminum metalization for semiconductor devices," in Proc. of IEEE, vol. 57, pp.1587-1597, Sept. 1996.
• 2: S. Chowdhury and M. A. Breuer, "Minimal area design of power/ground nets having graph topologies," IEEE Trans. Circuits and Systems, vol. CAS-34, no. 12, pp. 1441-1451, Dec. 1987.
• 3: S. Chowdhury and M. A. Breuer, "Optimum design of IC power/ground networks subject to reliability constraints," IEEE Trans. Computer-Aided Design, vol. 7, no. 7, pp. 787-796, July 1988.
• 4: S. Chowdhury, Optimum design of reliable IC power networks having general graph topologies, Proceedings of the 26th ACM/IEEE conference on Design automation, p.787-790, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74530]
• 5: R. Dutta , M. Marek-Sadowska, Automatic sizing of power/ground (P/G) networks in VLSI, Proceedings of the 26th ACM/IEEE conference on Design automation, p.783-786, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74529]
• 6: R. E. Griffith and R. A. Stewart, "A nonlinear programming technique for the optimization of continuous process systems," Management Science, no. 7, pp. 379-392, 1961.
• 7: D. Stark and M. Horowitz, "Techniques for Calculating Currents and Voltages in VLSI Power Supply Networks," IEEE Trans. on Computer-Aided Design, vol. 9, no. 2, pp. 126-132, February 1990.
• 8: 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
• 9: Xiang-Dong Tan , C.-J. Richard Shi , Dragos Lungeanu , Jyh-Chwen Lee , Li-Pen Yuan, Reliability-constrained area optimization of VLSI power/ground networks via sequence of linear programmings, Proceedings of the 36th ACM/IEEE conference on Design automation, p.78-83, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309880]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization
  B.7 INTEGRATED CIRCUITS
  B.8 Performance and Reliability

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Design, Performance, Theory