Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper describes a new floorplanning approach called Constrained Adjacency Graph (CAG) that helps exploring adjacency in floorplans. CAG extends the previous adjacency graph approaches by adding explicit adjacency constraints to the graph edges. After sufficient and necessary conditions of CAG are developed based on dissected floorplans, CAG is extended to handle general floorplans in order to improve area without changing the adjacency relations dramatically. These characteristics are currently utilized in a randomized greedy improvement heuristic for wire length optimization. The results show that better floorplans are found with much less running time for problems with 100 to 300 modules in comparison to a simulated annealing floorplanner based on sequence pairs.

REFERENCES

• 1: 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]
• 2: J. Garson. A Dual Linear Graph Representation for Space-Filling Location Problems of the Floor-planning Type. G. T. Moore (ed.) Emerging Methods in Environmental Design and Planning, MIT Press, 1970.
• 3: Krzysztof Kozminski , Edwin Kinnen, An algorithm for finding a rectangular dual of a planar graph for use in area planning for VLSI integrated circuits., Proceedings of the 21st conference on Design automation, p.655-656, June 25-27, 1984, Albuquerque, New Mexico, United States
• 4: J. Bhasker and S. Sahni. A Linear Algorithm to Find a Rectangular Dual of a Planar Triangulated Graph. Algorithmica, 3:247--278, 1988.
• 5: Y. T. Lai and S. M. Leinwand. Algorithms for Floorplan Design via Rectangular Dualization. IEEE Trans. on Computer-Aided Design, 7(12):1278--1289, December 1988.
• 6: 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]
• 7: Xianlong Hong , Gang Huang , Yici Cai , Jiangchun Gu , Sheqin Dong , Chung Kuan Cheng , Jun Gu, Corner block list: an effective and efficient topological representation of non-slicing floorplan, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 8: F. Y. Young, C. C. Chu, and Z. C. Shen. Twin Binary Sequences: A Non-redundant Representation for General Non-Slicing Floorplan. IEEE Trans. on Computer-Aided Design, 22(4):457--469, April 2003.
• 9: 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
• 10: Jia Wang , Hai Zhou, Linear constraint graph for floorplan optimization with soft blocks, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
• 11: S. N. Adya and I. L. Markov. Fixed-outline Floorplanning: Enabling Hierarchical Design. IEEE Trans. On VLSI Systems, 11(6):1120--1135, December 2003.
• 12: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 13: 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]
• 14: Natarajan Viswanathan , Chris Chong-Nuen Chu, FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981072]
• 15: Hayward H. Chan , Saurabh N. Adya , Igor L. Markov, Are floorplan representations important in digital design?, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055164]
• 16: Jackey Z. Yan , Chris Chu, DeFer: deferred decision making enabled fixed-outline floorplanner, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391512]