Incremental buffer insertion and module resizing algorithm using geometric programming

ABSTRACT

This paper presents an efficient algorithm for incremental buffer insertion and module resizing for a full-placed floorplan. Our algorithm offers a method to use the white space in a given floorplan to resize modules and insert buffers, and at the same time keep the resultant floorplan as close to the original one as possible. Both the buffer insertion and module resizing are modelled as geometric programming problems, and can be solved extremely efficiently using new developed solution methods. The experimental results suggest that the the wirelength difference between the initial floorplan and result is quite small (less than 5%), and the global structure of the initial floorplan is preserved very well.

REFERENCES

• 1: http://www.mosek.com/.
• 2: S. Boyd, S.-J. Kim, L. Vandenberghe, and A. Hassibi. A tutorial on geometric programming. Optimization and Engineering, (1):67--127, 2007.
• 3: Song Chen , Xianlong Hong , Sheqin Dong , Yuchun Mal , Yici Cai , Chung-Kuan Cheng , Jun Gu, A buffer planning algorithm based on dead space redistribution, Proceedings of the 2003 Asia and South Pacific Design Automation Conference, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119859]
• 4: W. Chen, C. T. Hsieh, and M. Pedram. Simultaneous gate sizing and placement. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 19(2):206--214, 2000.
• 5: Yi-Hui Cheng , Yao-Wen Chang, Integrating buffer planning with floorplanning for simultaneous multi-objective optimization, Proceedings of the 2004 Asia and South Pacific Design Automation Conference, January 27-30, 2004, Yokohama, Japan
• 6: 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
• 7: Olivier Coudert , Jason Cong , Sharad Malik , Majid Sarrafzadeh, Incremental CAD, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 8: Jim Crenshaw , Majid Sarrafzadeh , Prithviraj Banerjee , Pradeep Prabhakaran, An Incremental Floorplanner, Proceedings of the Ninth Great Lakes Symposium on VLSI, p.248, March 04-06, 1999
• 9: Iris Hui-Ru Jiang , Yao-Wen Chang , Jing-Yang Jou , Kai-Yuan Chao, Simultaneous floorplanning and buffer block planning, Proceedings of the 2003 Asia and South Pacific Design Automation Conference, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119858]
• 10: Chen Li , Cheng-Kok Koh , Patrick H. Madden, Floorplan management: incremental placement for gate sizing and buffer insertion, Proceedings of the 2005 Asia and South Pacific Design Automation Conference, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120867]
• 11: Jim Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, Journal of Algorithms, v.18 n.3, p.548-585, May 1995
• 12: W. Wong , C. Sham , F. Young, Congestion Estimation with Buffer Planning in Floorplan Design, Proceedings of the conference on Design, automation and test in Europe, p.696, March 04-08, 2002

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
buffer insertion, floorplan, geometric programming, module resizing