Integrated power supply planning and floorplanning

ABSTRACT

One of the most challenging issues in today's high-performance VLSI design is to ensure high-quality power supply to each individual circuit blocks. Reduced power supply voltage can result in slower cell switching, or even circuit failure. Nevertheless, most floorplanning methodologies have ignored power supply considerations. Thus, the resulting floorplan may suffer from local hot spots and insufficient power supply for certain circuit blocks. In this paper, we present an optimal power supply planning algorithm based on network flow to shorten the current paths from power bumps to local power supply wirings. We have incorporated our algorithm into a floorplanning algorithm for integrated floorplanning and power supply planning. Experimental results are encouraging.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• 4: D. F. Wong , C. L. Liu, A new algorithm for floorplan design, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.101-107, July 1986, Las Vegas, Nevada, United States
• 5: Hiroshi Murata , Kunihiro Fujiyoshi , Shigetoshi Nakatake , Yoji Kajitani, Rectangle-packing-based module placement, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.472-479, November 05-09, 1995, San Jose, California, United States
• 6: Shigetoshi Nakatake , Kunihiro Fujiyoshi , Hiroshi Murata , Yoji Kajitani, Module placement on BSG-structure and IC layout applications, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.484-491, November 10-14, 1996, San Jose, California, United States
• 7: [7] H. Murata and E. S. Kuh, "Sequence-pair Based Placement Method for Hard/Soft/Preplaced Modules," Proc. Intl. Conf. on Computer-Aided Design, pp. 472-479, 1995.
• 8: F. Y. Young , D. F. Wong, Slicing floorplans with pre-placed modules, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.252-258, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288622]
• 9: F. Y. Young , D. F. Wong, Slicing floorplans with range constraint, Proceedings of the 1999 international symposium on Physical design, p.97-102, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300033]
• 10: Hung-Ming Chen , Hai Zhou , F. Y. YOung , D. F. Wong , Hannah H. Yang , Naveed Sherwani, Integrated floorplanning and interconnect planning, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.354-357, November 07-11, 1999, San Jose, California, United States
• 11: Pei-Ning Guo , Chung-Kuan Cheng , Takeshi Yoshimura, An O-tree representation of non-slicing floorplan and its applications, Proceedings of the 36th ACM/IEEE conference on Design automation, p.268-273, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309928]
• 12: Jason Cong , Tianming Kong , David Zhigang Pan, Buffer block planning for interconnect-driven floorplanning, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.358-363, November 07-11, 1999, San Jose, California, United States
• 13: Xiaoping Tang , D. F. Wong, Planning buffer locations by network flows, Proceedings of the 2000 international symposium on Physical design, p.180-185, May 2000, San Diego, California, United States [doi>10.1145/332357.332397]
• 14: Probir Sarkar , Vivek Sundararaman , Cheng-Kok Koh, Routability-driven repeater block planning for interconnect-centric floorplanning, Proceedings of the 2000 international symposium on Physical design, p.186-191, May 2000, San Diego, California, United States [doi>10.1145/332357.332398]
• 15: 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]
• 16: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 17: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 18: [18] A. B. Kahng, P. Tucker, and A. Zelikovsky, "Optimization of Linear Placements for Wirelength Minimization with Free Sites," Proc. Asia and South Pacific Design Automation Conf., pp. 241-244, 1999.
• 19: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 20: [20] S.-M. Liu, K.-R. Pan, M. Pedram, and A. M. Despain, "Alleviating Routing Congestion by Combining Logic Resynthesis and Linear Placement," Proc. European Conf. on Design Automation, pp. 578-582, 1993.
• 21: Jinan Lou , Amir H. Salek , Massoud Pedram, An exact solution to simultaneous technology mapping and linear placement problem, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.671-675, November 09-13, 1997, San Jose, California, United States
• 22: [22] D. Russell, Optimization Theory. W. A. Benjamin, 1970.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
  B.8 Performance and Reliability

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

General Terms:
Algorithms, Design, Experimentation, Performance, Theory