Congestion-driven codesign of power and signal networks

ABSTRACT

We present a global wire design methodology that simultaneously considers the performance needs for both signal lines and power grids under congestion considerations. An iterative procedure is employed in which the global routing is performed according to a congestion map that includes the resource utilization of the power grid, followed by a step in which the power grid is adjusted to relax the congestion in crowded regions. This adjustment is in the form of wire removal in noncritical regions, followed by a wire sizing step that overcomes the effects of wire removal. Experimental results show that the overall routability can be significantly improved while the power grid noise is maintained within the voltage droop constraint.

REFERENCES

• 1: Charles J. Alpert , Jiang Hu , Sachin S. Sapatnekar , Paul Villarrubia, A practical methodology for early buffer and wire resource allocation, Proceedings of the 38th conference on Design automation, p.189-194, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378461]
• 2: C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, and D. Karger. Prim Dijkstra Tradeoffs for Improved Performance-Drrive Routing Tree Design. IEEE Transactions on Computer-Aided Design of ICs and Systems, 14(7):890--896, July 1995.
• 3: P. T. Boggs and J. W. Tolle. Sequential Quadratic Programming. Cambridge Univ. Press, Cambridge, 1995.
• 4: 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]
• 5: H. H. Chen and J. S. Neely. Interconnect and Circuit Modeling Techniques for Full-Chip Power Supply Noise Analysis. IEEE Transactions on Components, Packaging, and Manufacturing Technology, Part B, 21(3):209--215, August 1998.
• 6: C. Chiang and M. Sarrafzadeh. Global Routing Based on Steiner Min-max Tree. IEEE Transactions on Computer-Aided Design, 9(12):1318--1325, December 1990.
• 7: Andrew R. Conn , Ruud A. Haring , Chandu Visweswariah, Noise considerations in circuit optimization, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.220-227, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288617]
• 8: S. W. Director and R. A. Rohrer. The Generalized Adjoint Network and Network Sensitivities. IEEE Transactions on Circuit Theory, 16(3):318--323, August 1969.
• 9: P. Feldmann, T. V. Nguyen, S. W. Director, and R. A. Rohrer. Sensitivity Computation in Piecewise Approximation Circuit Simulation. IEEE Transactions on Computer-Aided Design of ICs and Systems, 10(2):171--183, February 1991.
• 10: P. E. Gill, W. Murray, M. A. Saunders, and M. H. Wright. User's Guide for SOL/QPSOL: A Fortran Package for Quadratic Programming. Department of Operations Research, Stanford University, July, 1983.
• 11: Jiang Hu , Sachin S. Sapatnekar, A timing-constrained algorithm for simultaneous global routing of multiple nets, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 12: James D. Z. Ma , Lei He, Simultaneous signal and power routing under K model, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.175-182, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368841]
• 13: R. Nair. A Simple Yet Effective Technique for Global Wiring. IEEE Transactions on Computer-Aided Design, 6(2):165--172, March 1987.
• 14: Sani R. Nassif , Joseph N. Kozhaya, Fast power grid simulation, Proceedings of the 37th conference on Design automation, p.156-161, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337359]
• 15: L. T. Pillage, R. A. Rohrer, and C. Visweswariah. Electronic and System Simulation Methods. McGraw-Hill, New York, NY, 1995.
• 16: E. Shragowitz , S. Keel, A global router based on a multicommodity flow model, Integration, the VLSI Journal, v.5 n.1, p.3-16, March 1987 [doi>10.1016/S0167-9260(87)80003-2]
• 17: 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
• 18: Haihua Su , Sachin S. Sapatnekar , Sani R. Nassif, An algorithm for optimal decoupling capacitor sizing and placement for standard cell layouts, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505405]
• 19: 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]
• 20: B. S. Ting and B. N. Tien. Routing and Techniques for Gate Array. IEEE Transactions on Computer-Aided Design, 2(4):301--312, October 1983.
• 21: 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
• 22: 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]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Algorithms

Keywords:
codesign, power grid noise, signal routing, wire congestion