B*-Trees: a new representation for non-slicing floorplans

ABSTRACT

We present in this paper an efficient, flexible, and effective data structure, B*-trees for non-slicing floorplans. B*-trees are based on ordered binary trees and the admissible placement presented in [1]. Inheriting from the nice properties of ordered binary trees, B*-trees are very easy for implementation and can perform the respective primitive tree, operations search, insertion, and deletion in only O(1), O(1), and O(n) times while existing representations for non-slicing floorplans need at least O(n) time for each of these operations, where n is the number of modules. The correspondence between an admissible placement and its induced B*-tree is 1-to-1 (i.e., no redundancy); further, the transformation between them takes only linear time. Unlike other representations for non-slicing floorplans that need to construct constraint graphs for cost evaluation, in particular, the evaluation can be performed on B*-trees and their corresponding placements directly and incrementally. We further show the flexibility of B*-trees by exploring how to handle rotated, pre-placed, soft, and rectilinear modules. Experimental results on MCNC benchmarks show that the B*-tree representation runs about 4.5 times faster, consumes about 60% less memory, and results in smaller silicon area than the O-tree one [1]. We also develop a B*-tree based simulated annealing scheme for floorplan design; the scheme achieves near optimum area utilization even for rectilinear modules.

REFERENCES

• 1: 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]
• 2: M. Kang and W. Dai., "General Floorplanning with L-shaped, T-shaped and Soft Blocks Based on Bounded Slicing Grid Structure," Proc. ASP-DAC, 1997.
• 3: Maggie Zhiwei Kang , Wayne Wei-Mingi Dai, Arbitrary rectilinear block packing based on sequence pair, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.259-266, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288623]
• 4: S. Kirkpatrick, C. D. Gelatt, and M. R Vecchi, "Optimization by Simulated Annealing," Science, vol. 220, no. 4598, May 13, 1983, pp.671-680.
• 5: Tsu-chang Lee, A bounded 2D contour searching algorithm for floorplan design with arbitrarily shaped rectilinear and soft modules, Proceedings of the 30th international conference on Design automation, p.525-530, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165014]
• 6: 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
• 7: H. Murata , K. Fujiyoshi , M. Kaneko, VLSI/PCB placement with obstacles based on sequence-pair, Proceedings of the 1997 international symposium on Physical design, p.26-31, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267675]
• 8: 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]
• 9: 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
• 10: S. Nakatake, M. Furuya, and Y. Kajitani, "Module Placement on BSG-Structure with Pre-Placed Modules and Rectilinear Modules," P1vc. ASP-DAC, pp. 571-576, 1998.
• 11: 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]
• 12: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• 13: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 14: Ting-chi Wang , D. F. Wong, An optimal algorithm for floorplan area optimization, Proceedings of the 27th ACM/IEEE conference on Design automation, p.180-186, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123253]
• 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: Jin Xu , Pei-ning Guo , Chung-Kuan Cheng, Rectilinear block placement using sequence-pair, Proceedings of the 1998 international symposium on Physical design, p.173-178, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274561]

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout
  B.8 Performance and Reliability

  C. Computer Systems Organization

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Design, Experimentation, Measurement, Performance, Theory