A unified approach to topology generation and area optimization of general floorplans

ABSTRACT

In this paper, it is shown that for any rectangularly dualizable graph, a feasible topology can be obtained by using only either straight or Z-cutlines recursively within a bounding rectangle. Given an adjacency graph, a potential topology, which may be nonslicible and is likely to yield an optimally sized floorplan, is produced first in a top-down fashion using heuristic search in AND-OR graphs. The advantage of this technique is fourfold : (i) accelerates top-down search phase, (ii) generates a floorplan with minimal number of nonslice cores, (iii) ensures safe routing order without addition of pseudo-modules, and (iv) solves the bottom-up algorithm efficiently for optimal sizing of general floorplans in the second phase.

REFERENCES

• 1: A. Bagchi and A. Mahanti, Admissible Heuristic Search in AND/OR Graphs, Theoretical Computer Science, 24, 1983, 207-219.
• 2: P.S. Dasgupta, S. Sur-Kolay and B.B. Bhattacharya, manuscript, 1995.
• 3: P. S. Dasgupta , S. Sur-Kolay , B. B. Bhattacharya, VLSI floorplan generation and area optimization using AND-OR graph search, Proceedings of the 8th International Conference on VLSI Design, p.370, January 04-07, 1995
• 4: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 5: P. Pan and C.L. Liu, Area Minimization for Floorplans, IEEE TCAD, Vol. 14, No. 1, 1995, 123-132.
• 6: Peichen Pan , Weiping Shi , C. L. Liu, Area minimization for hierarchical floorplans, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.436-440, November 06-10, 1994, San Jose, California, United States
• 7: Susmita Sur-Kolay , Bhargab B. Bhattacharya, The Cycle Structure of Channel Graphs in Nonslicible Floorplans and A Unified Algorithm for Feasible Routing Order, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.524-527, October 14-16, 1991
• 8: ----, On the family of Inherently Nonslicible Floorplans in VLSI Layout Design, Proc. ISCAS, June 1991, Singapore, 2850-2853.
• 9: S. Sur-Kolay , B. B. Bhattacharya, Canonical embedding of rectangular duals with applications to VLSI floorplanning, Proceedings of the 29th ACM/IEEE conference on Design automation, p.69-74, June 08-12, 1992, Anaheim, California, United States
• 10: T.C. Wang and D.F. Wong, Optimal Floorplan Area Optimization, IEEE TCAD, Vol. 11, No. 8, 1992, 992- 1002.
• 11: Gary K. H. Yeap , Majid Sarrafzadeh, Sliceable Floorplanning by Graph Dualization, SIAM Journal on Discrete Mathematics, v.8 n.2, p.258-280, May 1995 [doi>10.1137/S0895480191266700]
• 12: ----, A Unified Approach to Floorplan Sizing and Enumeration, IEEE TCAD, Vol. 12, No. 12, 1993, pp. 1858-67.

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

General Terms:
Measurement, Performance, Theory

Keywords:
VLSI floorplanning, placement, AND-OR graphs, heuristic search