An analytical approach to floorplan design and optimization

ABSTRACT

An analytical method for general floorplan design and optimization is proposed. This method is based on a mixed integer programming model and application of a standard mathematical software. The method allows arbitrary combinations of rigid and flexible modules. Various objective functions such as chip area, interconnection length, timing delays or any combinations of them are permitted. Routing space is estimated by the global router. Experimental data are provided.

REFERENCES

• BHA86: Jayaram Bhasker , Sartaj Sahni, A linear algorithm to find a rectangular dual of a planar triangulated graph, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.108-114, July 1986, Las Vegas, Nevada, United States
• HEL82: 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
• KAN83: Sungho Kang, Linear ordering and application to placement, Proceedings of the 20th conference on Design automation, p.457-464, June 27-29, 1983, Miami Beach, Florida, United States
• KOZ84: Krzysztof Kozminski , Edwin Kinnen, An algorithm for finding a rectangular dual of a planar graph for use in area planning for VLSI integrated circuits., Proceedings of the 21st conference on Design automation, p.655-656, June 25-27, 1984, Albuquerque, New Mexico, United States
• KOZ88: K.A. Kozminski, E. Kinnen, "Rectangular Dualization and Rectangular Dissections", IEEE Trans. on Circuits and Systems, Vol. 35, No. 9, pp. 1401-1416, Nov 1988.
• MAR84: Lev A. Markov , Jeffrey R. Fox , John H. Blank, Optimization techniques for two-dimensional placement, Proceedings of the 21st conference on Design automation, p.652-654, June 25-27, 1984, Albuquerque, New Mexico, United States
• MUE87: T. Mueller, D.F. Wont, C.L. Liu, "An Enhanced Bottom-Up Algorithm for Floorplan Design", Proc. 24th Design Automation Conference, pp. 524-527, 1987
• OTT82: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• OTT83: R.H.M. Otten, "Efficient Floorplan Optimization", Proc. International Conference on Computer Aided Design, pp. 499-502, 1983.
• SCH82: L. Schrage, "LINDO: Linear Interactive I)iscrete Optimizer", Copyright 1982.
• WIM88: Shmuel Wimer , Israel Koren , Israel Cederbaum, Optimal aspect ratios of building blocks in VLSI, Proceedings of the 25th ACM/IEEE conference on Design automation, p.66-72, June 12-15, 1988, Atlantic City, New Jersey, United States
• WON86: 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
• WON89: D. F. Wong , P. S. Sakhamuri, Efficient floorplan area optimization, Proceedings of the 26th ACM/IEEE conference on Design automation, p.586-589, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74481]
• YOU89: H. Youssef, E. Shragowitz, L.C. Bening, "Critical Path Issue in VLSI Designs", Proc. International Conference on Computer Aided Design, pp. 520-523, 1989.

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: Placement and routing; Layout

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

General Terms:
Algorithms, Design