Interconnect estimation without packing via ACG floorplans

ABSTRACT

ACG (Adjacent Constraint Graph) is a general floorplan representation. The refinement of constraint graphs gives not only an efficient representation but also a representation sharing the advantage of adjacency graphs. As most edges in an ACG are between modules that are close to each other, the physical distance of two modules can be measured without packing by the shortest path between them on the ACG. Experimental results verified this relationship and possible approaches for interconnect planning are discussed.

REFERENCES

• 1: Jayaram Bhasker , Sartaj Sahni, A linear algorithm to find a rectangular dual of a planar triangulated graph, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.108-114, July 1986, Las Vegas, Nevada, United States
• 2: 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]
• 3: J. Grason. A Dual Linear Graph Representation for Space-Filling Location Problems of the Floor-planning Type. MIT Press, Cambridge, MA, 1970.
• 4: 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]
• 5: 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
• 6: K. Kozminski and E. Kinnen. Rectangular dual of planar graphs. Networks, 15:145--157, 1985.
• 7: Y. T. Lai and S. M. Leinwand. Algorithms for floor-plan design via rectangular dualization. IEEE TCAD, 7(12):1278--1289, 1988.
• 8: 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]
• 9: 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
• 10: 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
• 11: 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]
• 12: G. Yeap and M. Sarrafzadeh. Floorplanning by graph dualization: 2-concave rectilinear modules. Manuscripts, 1993.
• 13: 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, 22(4):457--469, April 2003.
• 14: Hai Zhou , Jia Wang, ACG-Adjacent Constraint Graph for General Floorplans, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.572-575, October 11-13, 2004