Performance optimized floor planning by graph planarization

ABSTRACT

A new procedure for VLSI floor planning that minimizes routing parasitics is presented. The procedure, based on rectangular dualization, maximizes adjacency of modules that are heavily connected or connected by critical nets. Wiring macros are introduced to provide routing area for those modules that cannot be located adjacent to one another; these macros are located by planarizing the system interconnectivity graph using an edge crossing strategy that minimizes the cost of intersection. The rectangular dual is compacted using heuristics to approximate a quadratic area constraint by one or more linear constraints, thereby reducing the complexity of compaction from that of quadratic programming to linear programming.

REFERENCES

• 1: William R. Heller , G. Sorkin , Klim Maling, The planar package planner for system designers, Proceedings of the 19th conference on Design automation, p.253-260, January 1982
• 2: M.A. Jubri, "Automatic Building of Graphs Rectangularly Duulisable for use in IC Floorplansing," Proc. International Symposium on C='rcuits and Systems, pp. 1683-1686, 1988.
• 3: E.G. Coffman, M.R. Gaxey, D.S. Johnson, and R.E. Tarjan, "Performance Bounds for Level- Oriented Two-Dimensional Packing Algorithms," Siam J. Computing, vol. 9, no. 4, pp. 808-8,26, 1980.
• 4: S.L. Hakimi, "A Problem on Rectangulur Floorplans," Proe. International Symposium on Circuits and S~tsterr~, pp. 1533-1535, 1988.
• 5: M.R. Gaxey and D.S. Johnson, "Crossing Number is NP-Complete," Siam Z Aig. Disc. .~leth., vol. 4, no. 3, pp. 312-316, 1983.
• 6: B. Lokan~than and E. Kinnen, "Planarization of VLSI lnterconnectivity Graphs tor Floorplanning using Rectangular Duulizution," Proc. Seventh Biennial UGI)tt S$1mposium, pp. 115-119, 1987.
• 7: S. MucLane, "A Structural Characterization of Planar Combinatorial Graphs," Duke Math. J., vol. 3, pp. 460-472, 1937.
• 8: K. Kozminski and E. Kinnen, "Rectangular Duals of Plaaaar Graphs," Networks, vol. 15, pp. 145- 157, Jan. 1985.
• 9: K. Kozminski and E. Kinnen, "Rectangular Dualizution and Rectangular Dissections," IEEE Trans. Circuits and Systems, vol. 35, no. l l, pp. 1401-1416, 1988.
• 10: R.L. Brooks, C.A.B. Smith, A II. Stone, and W.T. Tutte, "The Dissection of Rectangles i~to Squares," Duke Mathematical Journal, pp. 312- 340j 1940.
• 11: James.P. Coene, "Detailed Routing for a VLSI Layout Bazed on Net Ordering," EL 88-07, Department of Elec~ical Eng, ineering, University of Rochester, 1988.

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.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout; Placement and routing

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Performance