On the use of flexible, rectilinear blocks to obtain minimum-area floorplans in mixed block and cell designs

ABSTRACT

This paper presents three minimum-area floorplanning algorithms that use flexible arbitrary rectilinear shapes for the standard cell regions in MBC design. The first algorithm (pure HCST) introduces a grid traversal technique which guarantees a minimum-area floorplan. The second algorithm (Hybrid-BF) uses a combination of HCST and Breadth First (BF) traversals to give a practical solution that approximately places flexible blocks at specified locations called seeds. The third algorithm (Hybrid-MBF) improves on the shapes of the flexible blocks generated by Hybrid-BF by using a combination of HCST and a Modified Breadth First (MBF) traversal. All three algorithms are polynomial in the number of grid squares. Optimized implementations of Hybrid-BF and Hybrid-MBF required less than two seconds on a SUN SPARCstation 10.

REFERENCES

• 1: Jitendra Apte , Gershon Kedem, Heuristic algorithms for combined standard cell and macro block layouts, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.367-385, March 1990, Boston, Massachusetts, United States
• 2: CHONG,K.AND SAHNI, S. 1993. Optimal realizations of floorplans. IEEE Trans. Comput.-Aided Des. 12 (June 1993), 793-801.
• 3: DAI, W., ESCHERMANN, B., KUH, E., AND PEDRAM, M. 1989. Hierarchical placement and floorplanning in BEAR. IEEE Trans. Comput.-Aided Des. 8, 1335-1349.
• 4: Partha S. Dasgupta , Susmita Sur-Kolay , Bhargab B. Bhattacharya, A unified approach to topology generation and area optimization of general floorplans, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.712-715, November 05-09, 1995, San Jose, California, United States
• 5: KOZMINSKI,K.A.AND KINNEN, E. 1988. Rectangular dualization and rectangular dissections. IEEE Trans. Circ. Syst. 35 (Nov. 1988), 1401-1416.
• 6: 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]
• 7: MEHTA,D.P.,SHANBHAG, A., AND SHERWANI, N. A. 1995. A new approach for floorplanning in MBC designs. Technical Report No. 95-02. Space Institute, Univ. Tennessee, Knoxville, TN.
• 8: 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
• 9: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• 10: OTTEN, R. 1983. Efficient floorplan optimization. In Proceedings of the International Conference on Computer Aided Design 499-503.
• 11: PAN,P.AND LIU, C. L. 1995. Area minimization for floorplans. IEEE Trans. Comput.-Aided Des. 14 (Jan.), 123-132.
• 12: Peichen Pan , Weiping Shi , C. L. Liu, Area minimization for hierarchical floorplans, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.436-440, November 06-10, 1994, San Jose, California, United States
• 13: PUTATUNDA, R., SMITH, D., STEBNISKY, M., PUSCHAK, C., AND PATENT, P. 1988. VITAL: Fully automatic placement strategies for very large semicustom designs. In Proceedings of the International Conference on Computer Design (ICCD '88) 434-439.
• 14: Majid Sarrafzadeh , M. Sarrafzadeh , C. K. Wong, An Introduction to VLSI Physical Design, McGraw-Hill Higher Education, 1996
• 15: Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1995
• 16: Larry Stockmeyer, Optimal orientations of cells in slicing floorplan designs, Information and Control, v.57 n.2-3, p.91-101, May/June 1983 [doi>10.1016/S0019-9958(83)80038-2]
• 17: SUTHANTAVIBUL, S., SHRAGOWITZ, E., AND ROSEN, J. B. 1991. An analytic approach to floorplan design and optimization. IEEE Trans. Comput.-Aided Des. 10 (June 1991), 761-769.
• 18: Michael Upton , Khosrow Samii , Stephen Sugiyama, Integrated placement for mixed macro cell and standard cell designs, Proceedings of the 27th ACM/IEEE conference on Design automation, p.32-35, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123219]
• 19: VIJAYAN,G.AND TSAY, R. 1991. A new method for floorplanning using topological constraint reduction. IEEE Trans. Comput.-Aided Des. 10 (Dec. 1991), 1494-1501.
• 20: WANG,T.AND WONG, D. 1988. Optimal floorplanning area minimization. IEEE Trans. Comput.-Aided Des. CAD-7, 11 (Nov.), 992-1002.
• 21: Kok-Hoo Yeap , Majid Sarrafzadeh, Floor-planning by graph dualization: 2-concave rectilinear modules, SIAM Journal on Computing, v.22 n.3, p.500-526, June 1993 [doi>10.1137/0222035]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

Additional Classification:
  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: Graph algorithms

General Terms:
Algorithms

Keywords:
floorplanning, mixed block and cell designs, rectilinear polygons