Efficient list-approximation techniques for floorplan area minimization

ABSTRACT

As the sizes of many IC design problems become increasingly larger, approximation has become a valuable approach for arriving at satisfactory results without incurring exorbitant computational cost. In this paper, we present several approximation techniques for solving floorplan area minimization problems. These new techniques enable us to reduce both the time and space complexities of the previously best known approximation algorithms by more than a factor of n and n2 for rectangular and L-shaped subfloorplans, respectively (where n is the number of given implementions). The improvements in the time and space complexities of such approximation techniques is critical to their applicability in floorplan area minimization algorithms. The techniques are quite general, and may be applicable to other classes of approximation problems.

REFERENCES

• 1: AGGARWAL, A., KLAWE, M. M., MORAN, S., SHOR,P.,AND WILBER, R. 1987. Geometric applications of a matrix-searching algorithm. Algorithmica 2, 195-208.
• 2: Alok Aggarwal , Baruch Schieber , Takashi Tokuyama, Finding a minimum weight K-link path in graphs with Monge property and applications, Proceedings of the ninth annual symposium on Computational geometry, p.189-197, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161135]
• 3: Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
• 4: Zvi Galil , Kunsoo Park, Dynamic programming with convexity, concavity and sparsity, Theoretical Computer Science, v.92 n.1, p.49-76, Jan. 6, 1992 [doi>10.1016/0304-3975(92)90135-3]
• 5: LAWLER, E. L. 1979. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston.
• 6: LENGAUER,T.,AND MULLER, R. 1990. A robust framework for hierarchical floorplanning with integrated global wiring. In Proceedings of the IEEE International Conference on Computer-Aided Design. IEEE Computer Society Press, Los Alamitos, Calif., pp. 148-151.
• 7: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• 8: Vinod Narayananan , David LaPotin , Rajesh Gupta , Gopal Vijayan, PEPPER-a timing driven early floorplanner, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.230-235, October 02-04, 1995
• 9: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• 10: PAN,P.,AND LIU, C. L. 1995. Area minimization for floorplans. IEEE Trans. Comput.-Aided Des. Integ. Circ. Syst. 14, 1, 123-132.
• 11: PAN, P., SHI,W.,AND LIU, C. L. 1996. Area minimization for hierarchical floorplans. Algorithmica 15, 6, 550-571.
• 12: PEDRAM, M., AND PREAS, B. 1990. A hierarchical floorplanning approach. In Proceedings of the IEEE International Conference on Computer Design. IEEE Computer Society Press, Los Alamitos, Calif., pp. 332-338.
• 13: Baruch Schieber, Computing a minimum-weight k-link path in graphs with the concave Monge property, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.405-411, January 22-24, 1995, San Francisco, California, United States
• 14: 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]
• 15: WANG, T.-C., AND WONG, D. F. 1992. Optimal floorplan area optimization. IEEE Trans. Computer- Aided Design 11, 8, 992-1002.
• 16: Ting-Chi Wang , D. F. Wong, Graph-based techniques to speed up floorplan area optimization, Integration, the VLSI Journal, v.15 n.2, p.179-199, Oct. 1993 [doi>10.1016/0167-9260(93)90051-D]
• 17: Gerhard Zimmerman, A new area and shape function estimation technique for VLSI layouts, Proceedings of the 25th ACM/IEEE conference on Design automation, p.60-65, June 12-15, 1988, Atlantic City, New Jersey, United States

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: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design, Theory

Keywords:
area minimization, floorplanning, k-link shortest paths, list approximation