A novel fixed-outline floorplanner with zero deadspace for hierarchical design

ABSTRACT

Fixed-outline floorplanning, which enables hierarchical design, is considered more and more important nowadays. In this paper, a novel SA-based Fixed-outline Floorplanner with the Optimal Area utilization named SAFFOA is introduced to improve the total wirelength. The basic idea is to build and solve a group of four quadratic equations in four variables iteratively, which can handle the fixed-outline constraint of any aspect ratio. A new topological representation called Ordered Quadtree is then custom-made for this basic idea to facilitate its integration into SA iterations. After the fixed-outline constraint with 100% area utilization is achieved, we will solve the tradeoff between the chip area and wirelength and thus concentrate on the latter in SA process. Experimental results show that the chip wirelength is decreased by about 16.8% and 8.6% on average, compared with two previous fixed-outline floorplanners on soft modules, which are both proved to be better than Parquet. Besides, our method is still competitive on the wirelength, even if compared with some leading-edge outline-free floorplanners. At last, Local Refinement is also adopted to guide the SA process and reshape soft modules to meet the constraint on their aspect ratios (ARs). With its help, SAFFOA can still generate feasible floorplans with no deadspace under a strict AR constraint such as [0.5,2].

REFERENCES

• 1: S. N. Adya and I. L. Markov. Fixed-outline foorplanning: Enabling hierarchical design. IEEE Trans. on VLSI Systems, 11(6):1120--1135, 2003.
• 2: 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]
• 3: 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
• 4: Tung-Chieh Chen , Yao-Wen Chang, Modern floorplanning based on fast simulated annealing, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055161]
• 5: T. Chen and Y. W. Chang. Modern foorplanning based on b*-tree and fast simulated annealing. IEEE Trans. on CAD, 25(4): 637--650, 2006.
• 6: Song Chen , Takeshi Yoshimura, A stable fixed-outline floorplanning method, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA [doi>10.1145/1231996.1232021]
• 7: 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, January 27-30, 2004, Yokohama, Japan
• 8: R. Liu, S. Dong, X. Hong and Y. Kajitani. Fixed-outline foorplanning with constraints through instance augmentation. In Proc. IEEE ISCAS, pages 1883--1886, 2005.
• 9: T. S. Moh, T. S. Chang, and S. L. Hakimi. Globally optimal foorplanning for a layout problem. IEEE Trans. on Circuit and Systems, 43(9):713--720, 1996.
• 10: Pinhong Chen , Ernest S. Kuh, Floorplan sizing by linear programming approximation, Proceedings of the 37th conference on Design automation, p.468-471, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337547]
• 11: J. G. Kim and Y. D. Kim. A Linear Programming-Based Algorithm for Floorplanning in VLSI Design. IEEE Trans. on CAD, 22(5):584--592, 2003
• 12: Chuan Lin , Hai Zhou , Chris Chu, A revisit to floorplan optimization by Lagrangian relaxation, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233535]
• 13: F. Y. Young, C. C. N. Chu, W. S. Luk and Y. C. Wong. Handling soft modules in general non-slicing foorplan using lagrangian relaxation. IEEE Trans. on CAD, 20(5):687--692, May 2001.
• 14: Hiroaki Itoga , Chikaaki Kodama , Kunihiro Fujiyoshi, A Graph Based Soft Module Handling in Floorplan, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E88-A n.12, p.3390-3397, December 2005 [doi>10.1093/ietfec/e88-a.12.3390]
• 15: Yong Zhan , Yan Feng , Sachin S. Sapatnekar, A fixed-die floorplanning algorithm using an analytical approach, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118477]
• 16: Jason Cong , Gabriele Nataneli , Michail Romesis , Joseph R. Shinnerl, An area-optimality study of floorplanning, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981083]
• 17: J. Cong, M. Romesis, and J. Shinnerl. Fast Floorplanning by Look-Ahead Enabled Recursive Bipartitioning. IEEE Trans. on CAD, 25(9): 1719--1732, September, 2006.
• 18: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• 19: 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
• 20: Jai-Ming Lin , Yao-Wen Chang, TCG: a transitive closure graph-based representation for non-slicing floorplans, Proceedings of the 38th conference on Design automation, p.764-769, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379062]
• 21: Hai Zhou , Jia Wang, ACG-Adjacent Constraint Graph for General Floorplans, Proceedings of the IEEE International Conference on Computer Design, p.572-575, October 11-13, 2004
• 22: 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
• 23: 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
• 24: X. Hong, S. Dong, G. Huang, Y. Cai, C. K. Cheng, J. Gu, "Corner Block List Representation and Its Application to Flooplan Optimization", IEEE Trans. on Circuits and Systems, 51(5), 228--233, May 2004.
• 25: K. Sakanushi and Y. Kajitani. The quarter-state sequence (qsequence) to represent the foorplan and applications to layout optimization. In IEEE APCCAS, pages 829--832, 2000.

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design

Keywords:
fixed-outline, floorplanner, soft modules, zero deadspace