Efficient floorplan area optimization

ABSTRACT

The floorplan area optimization problem is to determine the shape and dimensions of all the modules when the topology of the floorplan is given. The objective is to minimize the area of the resulting floorplan. Existing methods only apply to slicing floorplans. We present in this paper an algorithm for general hierarchical floorplans. Our algorithm combines the curve-adding technique used in the case of slicing floorplans and a new technique that computes shape curves by iterative modification of the shape and dimensions of individual modules. We also present an optimal points selection algorithm using the technique of dynamic programming to further enhance the process of shape curves construction.

REFERENCES

• AhHU74: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• DaKu87: Dai, Wei-Ming and E. S. Kuh, "Simultaneous Floor Planning and Gtobal Routing for Hierarchical Building-Block Layout," {EEE Trans. on CAD, Vol. CAD.6. NO.5. (1987), 828-837.
• Laut80: Lauther, U., "A Min-Cut Placement Algorithm for General Cell Assemblies Based on a Graph Representation," Journal of Digital Systeme, Vol. IV, Issue 1, (1980), 21-34.
• Otte82: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• Otte84: Otten, R. H. M., "Efficient Floorplan Optimization," Proc. ICCD 83, (1983), 499-502.
• PrVa79: B. T. Preas , W. M. vanCleemput, Placement algorithms for arbitrarily shaped blocks, Proceedings of the 16th Conference on Design automation, p.474-480, June 25-27, 1979, San Diego, CA, United States
• Stoc85: 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]
• WoLi86: 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
• WoLi87: Wong, D. F. and C. L. Liu, "Floorplan Design for Rectangular and L-Shaped Modules", Proc. IEEE Intl. Conf. on CompuIer-Aided-Design, (1987), 520-523,

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

General Terms:
Algorithms, Design