Constrained polygon transformations for incremental floorplanning

ABSTRACT

A productivity-driven methodology for incremental floorplanning is described and the constrained polygon transformation problem, a key step of this methodology, is formulated. The input to the problem consists of a floorplan computed using area estimates and the actual area required for each subcircuit of the floorplan. Informally, the objective is to change the areas of the modules without drastically changing their shapes or locations. We show that the constrained polygon transformation problem is NP-hard and present several fast algorithms that produce results within a few percent of a theoretical lower bound on several floorplans.

REFERENCES

• 1: 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
• 2: Maggie Zhi-Wei Kang , Wayne Wei-Ming Dai, Topology constrained rectilinear block packing for layout reuse, Proceedings of the 1998 international symposium on Physical design, p.179-186, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274562]
• 3: 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]
• 4: Dinesh P. Mehta , Naveed Sherwani, A Minimum-Area Floorplanning Algorithm for MBC Designs, Proceedings of the 6th Great Lakes Symposium on VLSI, p.56, March 22-23, 1996
• 5: MURATA, H., FUJIYOSHI, F., NAKATAKE,S.,AND KAJITANI, Y. 1996. VLSI module placement based on rectangle packing by the sequence-pair. IEEE Trans. Computer-Aided Design 15, 12 (Dec.), 1518-1524.
• 6: NAKATAKE, S., FUJIYOSHI, F., MURATA, H., AND KAJITANI, Y. 1998. Module packing based on the BSG-structure and IC layout applications. IEEE Trans. Computer-Aided Design 17, 6 (June), 519-530.
• 7: WANG,T.,AND WONG, D. 1992. Optimal floorplanning area minimization. IEEE Trans. Computer- Aided Design 11, 8 (Aug.), 992-1002.
• 8: WONG,D.F.,AND LIU, C. L. 1989. Floorplan design of VLSI circuits. Algorithmica 4, 263-291.
• 9: 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]
• 10: 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: Geometrical problems and computations; Routing and layout

General Terms:
Algorithms

Keywords:
floorplanning, incremental design, rectilinear polygons