Linear constraint graph for floorplan optimization with soft blocks

ABSTRACT

In this paper, we propose the Linear Constraint Graph (LCG) as an efficient general floorplan representation. For n blocks, an LCG has at most 2n+3 vertices and at most 6n+2 edges. Operations with direct geometric meanings are developed to perturb the LCGs. We apply the LCGs to the floorplan optimization with soft blocks to leverage its advantage in terms of the sizes of the graphs, which will improve the efficiency of solving a complex mathematical program in the inner loop of the optimization that decide the block shapes without introducing overlaps to the non-slicing floorplans. Experimental results confirm that the LCGs are effective and efficient.

REFERENCES

• 1: F. Y. Young, C. C. N. Chu, W. S. Luk, and Y. C. Wong, "Handling soft modules in general non-slicing floorplan using Lagrangian relaxation," IEEE TCAD, vol. 20, no. 5, pp. 687--692, May 2001.
• 2: Evangeline F. Y. Young , Chris C. N. Chu , M. L. Ho, Placement constraints in floorplan design, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.7, p.735-745, July 2004 [doi>10.1109/TVLSI.2004.830915]
• 3: 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]
• 4: X. Tang, R. Tian, and M. D. F. Wong, "Minimizing wire length in floorplanning," IEEE TCAD, vol. 25, no. 9, pp. 1744--1753, Sept. 2006.
• 5: H.-C. Lee, Y.-W. Chang, and H. H. Yang, "MB*-Tree: A multilevel floorplanner for large-scale building-module design," IEEE TCAD, vol. 26, no. 8, pp. 1430--1444, Aug. 2007.
• 6: T. Ohtsuki, N. Sugiyama, and H. Kawanishi, "An optimization technique for integrated circuit layout design," in Proc. ICCST, Kyoto, Japan, 1970, pp. 67--68.
• 7: Ralph H. J. M. Otten, What is a floorplan?, Proceedings of the 2000 international symposium on Physical design, p.201-206, May 2000, San Diego, California, United States [doi>10.1145/332357.332400]
• 8: F. Y. Young, C. C. N. Chu, and Z. C. Shen, "Twin Binary Sequences: A non-redundant representation for general non-slicing floorplan," IEEE TCAD, vol. 22, no. 4, pp. 457--469, Apr. 2003.
• 9: 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]
• 10: 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
• 11: Jia Wang , Hai Zhou, Interconnect estimation without packing via ACG floorplans, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120928]
• 12: H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair," IEEE TCAD, vol. 15, no. 12, pp. 1518--1524, Dec. 1996.
• 13: C. Lin, "Incremental mixed-signal layout generation concepts," Ph.D. dissertation, Eindhoven University of Technology, Eindhoven, The Netherlands, 2002.
• 14: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 15: CS2 version 4.3, "Andrew Goldberg's network optimization library," http://www.avglab.com/andrew/soft.html.
• 16: S. N. Adya and I. L. Markov, "Fixed-outline floorplanning: Enabling hierarchical design," IEEE TVLSI, vol. 11, no. 6, pp. 1120--1135, Dec. 2003.