Are floorplan representations important in digital design?

ABSTRACT

Research in floorplanning and block-packing has generated a variety of data structures to represent spatial configurations of circuit modules. Much of this work focuses on the geometry of module shapes and seeks tighter packing, as well as improvements in the asymptotic worst-case complexity of algorithms for standard tasks. In this work we consider the implications of interconnect optimization on the value of floorplan representations and establish a framework for comparing different representations. By analyzing performance bottlenecks in block packing and properties of floorplan representations, we show that many of the mathematical results in floorplanning do not translate into better VLSI layouts. This is confirmed by extensive empirical data for stand-alone floor-planners and integrated applications.

REFERENCES

• 1: S.N. Adya and I.L. Markov, "Fixed-outline Floorplanning: Enabling Hierarchical Design," IEEE Trans. on VLSI 11(6), pp.1120--35, 2003. http://vlsicad.eecs.umich.edu/BK/parquet/
• 2: S. N. Adya , S. Chaturvedi , J. A. Roy , D. A. Papa , I. L. Markov, Unification of partitioning, placement and floorplanning, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.550-557, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382639]
• 3: A. E. Caldwell, A. B. Kahng, I. L. Markov, "Optimal Partitioners and End-case Placers for Standard-cell Layout," IEEE Trans. on CAD 19(11), pp. 1304--1314, 2000.
• 4: Hayward H. Chan , Igor L. Markov, Practical slicing and non-slicing block-packing without simulated annealing, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA [doi>10.1145/988952.989020]
• 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: Kunihiro Fujiyoshi , Hiroshi Murata, Arbitrary convex and concave rectilinear block packing using sequence-pair, Proceedings of the 1999 international symposium on Physical design, p.103-110, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300034]
• 7: 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]
• 8: 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
• 9: 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]
• 10: R. E. Korf, "Optimal Rectangle Packing: New Results," ICAPS 2004, pp. 142--149.
• 11: M. Lai , D. Wong, Slicing tree is a complete floorplan representation, Proceedings of the conference on Design, automation and test in Europe, p.228-232, March 2001, Munich, Germany
• 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: 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]
• 14: Jai-Ming Lin , Yao-Wen Chang, TCG-S: orthogonal coupling of P*-admissible representations for general floorplans, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514127]
• 15: P. H. Madden, "Reporting of Standard Cell Placement Results," IEEE Trans. on CAD 21(2), Feb. 2002, pp. 240--247.
• 16: H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, "MVLSI Module Placement Based on Rectangle-Packing by the Sequence Pair," IEEE Trans. on CAD 15(12), pp. 1518--1524, 1996.
• 17: Hiroshi Murata , Ernest S. Kuh, Sequence-pair based placement method for hard/soft/pre-placed modules, Proceedings of the 1998 international symposium on Physical design, p.167-172, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274560]
• 18: Yingxin Pang , Chung-Kuan Cheng , Takeshi Yoshimura, An enhanced perturbing algorithm for floorplan design using the O-tree representation, Proceedings of the 2000 international symposium on Physical design, p.168-173, May 2000, San Diego, California, United States [doi>10.1145/332357.332395]
• 19: S. Prestwich, "Supersymmetric Modelling for Local Search," SymCon '02, September 2002. http://user.it.uu.se/~pierref/astra/SymCon02/
• 20: Z. C. Shen and C.C.N. Chu, "Bounds on the Number of Slicing, Mosaic, and General Floorplans," IEEE Trans. on CAD 22(10), pp. 1354--1361.
• 21: Xiaoping Tang , Ruiqi Tian , D. F. Wong, Fast evaluation of sequence pair in block placement by longest common subsequence computation, Proceedings of the conference on Design, automation and test in Europe, p.106-111, March 27-30, 2000, Paris, France [doi>10.1145/343647.343713]
• 22: Xiaoping Tang , D. F. Wong, FAST-SP: a fast algorithm for block placement based on sequence pair, Proceedings of the 2001 conference on Asia South Pacific design automation, p.521-526, January 2001, Yokohama, Japan [doi>10.1145/370155.370523]
• 23: 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
• 24: Guang-Ming Wu , Yun-Chih Chang , Yao-Wen Chang, Rectilinear block placement using B*-trees, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.2, p.188-202, April 2003 [doi>10.1145/762488.762490]
• 25: Bo Yao , Hongyu Chen , Chung-Kuan Cheng , Ronald Graham, Floorplan representations: Complexity and connections, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.1, p.55-80, January 2003 [doi>10.1145/606603.606607]
• 26: E.F.Y. Young, C.C.N. Chu and Z.C. Shen, "Twin Binary Sequences: A Nonredundant Representation for General Nonslicing Floorplan," IEEE Trans. on CAD 22(4), pp. 457--469, 2003.
• 27: Shuo Zhou , Sheqin Dong , Chung-Kuan Cheng , Jun Gu, ECBL: an extended corner block list with solution space including optimum placement, Proceedings of the 2001 international symposium on Physical design, p.150-155, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369756]
• 28: 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
• 29: C. Zhuang , Y. Kajitani , K. Sakanushi , L. Jin, An Enhanced Q-Sequence Augmented with Empty-Room-Insertion and Parenthesis Trees, Proceedings of the conference on Design, automation and test in Europe, p.61, March 04-08, 2002

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Experimentation

Keywords:
B*-tree, circuit layout, floorplanning, sequence pair