An optimal algorithm for floorplan area optimization

ABSTRACT

In this paper we present an optimal algorithm for the floorplan area optimization problem. Our algorithm is based on an extension of the technique in [5]. Experimental results indicate that our algorithm is efficient and capable of successfully handling large floorplans. We compare our algorithm with the branch-and-bound optimal algorithm in [6]. The running time of our algorithm is substantially less than that of [6]. For several examples where the algorithm in [6] ran for days and did not terminate, our algorithm produced optimal solutions in a few seconds.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Arvindam, S., V. Kum~r and V.N. Rao "Floorplan Optimization on Multiprocessors," ICC19.89.
• 3: Lauther, U., "A Min-Cut Placement Algorithm for General Cell Assemblies Based on a Graph Representation," Journal of Digital Systems, Vol. IV, I,~sue 1 (1980), ~1- 34.
• 4: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• 5: 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]
• 6: Wimer, S., I. Koren and I. Cederbaum, "Optimal Aspect Ratios of Building Blocks in VLSI," IEEE Trans. on CAD, Vol. CAD-8, No. 2 (1989), 139-145.
• 7: 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
• 8: 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]
• 9: Wong, D.F. and K.S. The, "An Algorithm for Hierarchical Floorplan Design," Proc. IEEE b~ternational Conf. on Computer-Aided Design (1989), 4~4-487.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Performance