Modern floorplanning based on fast simulated annealing

ABSTRACT

Unlike classical floorplanning that usually handles only block packing to minimize silicon area, modern VLSI floorplanning typically needs to pack blocks within a fixed die (outline) and additionally considers the packing with block positions and interconnect constraints. Floorplanning with bus planning is one of the most challenging modern floorplanning problems because it needs to consider the constraints with interconnect and block positions simultaneously. We study in this paper two types of modern floorplanning problems: (1) fixed-outline floorplanning and (2) bus-driven floorplanning. Our floorplanner uses the B*-tree floorplan representation and is based on a fast three-stage simulated annealing scheme, called Fast-SA. For fixed-outline floorplanning, we present an adaptive Fast-SA that can dynamically change the weights in the cost function to optimize wirelength under the outline constraint. Experimental results show that our floorplanner can achieve almost 100% success rates efficiently for fixed-outline floorplanning with various aspect ratios, compared to 10%--90% success rates obtained by the most recent works. For the bus-driven floorplanning, we explore the feasibility conditions of the B*-tree with the bus constraints and develop a bus-driven floorplanning algorithm based on the conditions and Fast-SA. Experimental results show that our floorplanner on the average reduces 20% (55%) dead space for the floorplanning with hard (soft) macro blocks, compared with the most recent work. In particular, our floorplanner is more efficient than the previous works.

REFERENCES

• 1: E.H.L. Aarts and P.J.M. van Laarhoven, "A new polynomial time cooling schedule," Proceedings of IEEE/ACM International Conference on Computer-Aided Design, 1985.
• 2: Fixed-Outline Floorplanning through Better Local Search, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.328, September 23-26, 2001
• 3: 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]
• 4: S. N. Adya and I. L. Markov, "Fixed-outline Floorplanning: Enabling Hierarchical Design," IEEE Trans. on VLSI Systems, vol 11(6), pp. 1120--1135, December 2003.
• 5: Yun-Chih Chang , Yao-Wen Chang , Guang-Ming Wu , Shu-Wei Wu, B*-Trees: a new representation for non-slicing floorplans, Proceedings of the 37th conference on Design automation, p.458-463, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337541]
• 6: J.-C. Chi and M. C. Chi, "A block placement algorithm for VLSI circuits," Chung Yuan Journal, Vol. 31, No. 1, March 2003, pp. 69--75.
• 7: GSRC Floorplan Benchmark Suite, http://www.cse.ucsc.edu/research/surf/GSRC/GSRCbench.html
• 8: C. Sechen and A. Sangiovanni-Vincentelli, "The TimberWolf placement and routing package," IEEE Journal of Solid-State Circuits, pp. 510--522, Volume 20, 1985.
• 9: 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]
• 10: Andrew B. Kahng, Classical floorplanning harmful?, Proceedings of the 2000 international symposium on Physical design, p.207-213, May 2000, San Diego, California, United States [doi>10.1145/332357.332401]
• 11: S. Kirpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing," Science, pp.671--680, 1983.
• 12: Hsun-Cheng Lee , Yao-Wen Chang , Jer-Ming Hsu , Hannah H. Yang, Multilevel floorplanning/placement for large-scale modules using B*-trees, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776037]
• 13: Chang-Tzu Lin , De-Sheng Chen , Yi-Wen Wang, Robust fixed-outline floorplanning through evolutionary search, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.42-44, January 27-30, 2004, Yokohama, Japan
• 14: 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
• 15: Parquet: Fixed-Outline Floorplanner, http://vlsicad.eecs.umich.edu/BK/parquet/
• 16: F. Rafiq, M. Chrzanowska-Jeske, H. H. Yang, and N. Sherwani, "Bus-based integrated floorplanning," Proceedings of IEEE International Synposium on Circuits and Systems, pp. 875--878, 2002.
• 17: Faran Rafiq , Malgorzata Chrzanowska-Jeske , Hannah Honghua Yang , Naveed Sherwani, Integrated floorplanning with buffer/channel insertion for bus-based microprocessor designs, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505403]
• 18: Sadiq M. Sait , Habib Youssef, VISI Physical Design Automation: Theory and Practice, McGraw-Hill, Inc., New York, NY, 1994
• 19: Xiaoping Tang , D. F. Wong, Floorplanning with alignment and performance constraints, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514128]
• 20: D. F. Wong , H. W. Leong , C. L. Liu, Simulated annealing for VLSI design, Kluwer Academic Publishers, Norwell, MA, 1988
• 21: Meng-Chen Wu , Yao-Wen Chang, Placement with Alignment and Performance Constraints Using the B*-Tree Representation, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.568-571, October 11-13, 2004
• 22: Hua Xiang , Xiaoping Tang , Martin D. F. Wong, Bus-Driven Floorplanning, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.66, November 09-13, 2003 [doi>10.1109/ICCAD.2003.43]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
floorplanning, simulated annealing