Optimizing wirelength and routability by searching alternative packings in floorplanning

ABSTRACT

Recent advances in VLSI technology have made optimization of the interconnect delay and routability of a circuit more important. We should consider interconnect planning as early as possible. We propose a postfloorplanning step to reduce the interconnect cost of a floorplan by searching alternative packings. If a packing contains a rectangular bounding box of a group of modules, we can rearrange the blocks in the bounding box to obtain a new floorplan with the same area, but possibly with a smaller interconnect cost. Experimental results show that we can reduce the interconnect cost of a packing without any penalty in area.

REFERENCES

• 1: Adya, S. N. and Markov, I. L. 2001. Fixed-outline floorplanning through better local search. IEEE Trans. VLSI Syst., 328--333.
• 2: Saurabh N. Adya , Igor L. Markov, Consistent placement of macro-blocks using floorplanning and standard-cell placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505392]
• 3: Adya, S. N. and Markov, I. L. 2003. Fixed-Outline floorplanning: Enabling hierarchical design. In Proceedings of the International Conference on Computer Design, 1120--1135.
• 4: Chang, C. C., Cong, J., Pan, D. Z., and Yuan, X. 2000. Interconnect-Driven floorplanning with fast global wiring planning and optimization. In Proceedings of the SRC Techcon Conference, 21.
• 5: 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
• 6: Kastner, R., Bozorgzadeh, E., and Sarrafzadeh, M. 2002. Pattern routing: Use and theory for increasing predictability and avoiding coupling. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst., 777--780.
• 7: Steve T. W. Lai , Evangeline F. Y. Young , Chris C. N. Chu, A New and Efficient Congestion Evaluation Model in Floorplanning: Wire Density Control with Twin Binary Trees, Proceedings of the conference on Design, Automation and Test in Europe, p.10856, March 03-07, 2003
• 8: Jinan Lou , Shankar Krishnamoorthy , Henry S. Sheng, Estimating routing congestion using probabilistic analysis, Proceedings of the 2001 international symposium on Physical design, p.112-117, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369749]
• 9: M. C. Jeske, B. Y. W. and Greenwood, G. 2003. Floorplanning with performance-based clustering. In Proceedings of the IEEE International Symposium on Circuits and Systems, 724--727.
• 10: Yuchun Ma , Xianlong Hong , Sheqin Dong , Song Chen , Yici Cai , C. K. Cheng , Jun Gu, Dynamic global buffer planning optimization based on detail block locating and congestion analysis, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776036]
• 11: 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
• 12: Murata, H., Fujiyoshi, K., Nakatake, S., and Kajitani, Y. 1996. VLSI module placement based on rectangle-packing by the sequence-pair. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst., 1518--1524.
• 13: Hiroshi Murata , Ernest S. Kuh, Sequence-pair based placement method for hard/soft/pre-placed modules, Proceedings of the 1998 international symposium on Physical design, p.167-172, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274560]
• 14: Sham, C. W. and Young, E. F. Y. 2003. Routability-Driven floorplanning with buffer planning. IEEE Trans. Comput. Aided Des. Integ. Circ. Syst., 470--480.
• 15: Maogang Wang , Majid Sarrafzadeh, Modeling and minimization of routing congestion, Proceedings of the 2000 conference on Asia South Pacific design automation, p.185-190, January 2000, Yokohama, Japan [doi>10.1145/368434.368601]

INDEX TERMS

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

General Terms:
Performance

Keywords:
Floorplanning, wirelength reduction