Practical slicing and non-slicing block-packing without simulated annealing

ABSTRACT

We propose a new floorplanner BloBB based on multi-level branch-and-bound. It is competitive with annealers in terms of runtime and solution quality. We empirically quantify the gap between optimal slicing and non-slicing floorplans by comparing optimal packings and best seen results. Optimal slicing and non-slicing packings for apte, xerox and hp are reported. We also discover that the soft versions of all MCNC benchmarks, except for apte, and all GSRC benchmarks can be packed with zero dead-space.Additionally, realistic floorplans often have blocks with similar dimensions, if design blocks, such as memories, are reused. We show that this greatly reduces the complexity of black-packing.

REFERENCES

• 1: S.N. Adya, I.L. Markov, "Fixed-outline Floorplanning: Enabling Hierarchical Design," IEEE Trans. on VLSI 11(6), pp. 1120-1135, 2003. http://vlsicad.eecs.umich.edu/BK/parquet/
• 2: A.E. Caldwell, A.B. Kahng, and I.L. Markov, "Optimal Partitioners and End-case Placers for Standard-cell Layout," IEEE Trans. on CAD, 19(11), pp. 1304--1314, 2000.
• 3: H.H. Chan and I.L. Markov, "Practical Slicing and Non-slicing Block-Packing without Simulated Annealing," CSE-TR-487-04, The University of Michigan, 2004.
• 4: 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]
• 5: 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]
• 6: 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]
• 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: 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
• 9: 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]
• 10: 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]
• 11: I. Mandoiu, "Multi-Project Reticle Floorplanning and Wafer Dicing," to appear in ISPD 2004.
• 12: H. Murata et al., "VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair," IEEE Trans on CAD 15(12), pp. 1518--1524, 1996.
• 13: 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
• 14: Hidetoshi Onodera , Yo Taniguchi , Keikichi Tamaru, Branch-and-bound placement for building block layout, Proceedings of the 28th conference on ACM/IEEE design automation, p.433-439, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127708]
• 15: 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
• 16: Jin Xu , Pei-Ning Guo , Chung-Kuan Cheng, Cluster refinement for block placement, Proceedings of the 34th annual conference on Design automation, p.762-765, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266366]
• 17: 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]
• 18: http://cc.ee.ntu.edu.tw/~ywchang/research.html
• 19: http://vlsicad.eecs.umich.edu/BK/BloBB/
• 20: http://vlsicad.eecs.umich.edu/BK/CompaSS/

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:
block-packing, branch-and-bound, evaluation, floorplanning, hierarchical, large-scale, optimal, slicing, soft blocks