Efficient decomposition of polygons into L-shapes with application to VLSI layouts

ABSTRACT

We present two practical algorithms for partitioning circuit components represented by rectilinear polygons so that they can be stored using the L-shaped corner stitching data structure; that is, our algorithms decompose a simple polygon into a set of nonoverlapping L-shapes and rectangles by using horizontal cuts only. The more general of our algorithms computes and optimal configuration for a wide variety of optimization functions, whereas the other computes a minimum configuration of rectangles and L-shapes. Both algorithms run in O(n + h log h time, where n is the number of vertices in the polygon and h is the number of H-pairs. Because for VLSI data h is small, in practice these algorithms are linear in n. Experimental results on actual VLSI data compare our algorithms and demonstrate the gains in performance for corner stitching (as measured by different objective functions) obtained by using them instead of more traditional rectangular partitioning algorithms.

REFERENCES

• 1: BLUST, G. AND MEHTA, D.P. 1993. Corner stitching for L-shaped tiles. In Proceedings of the Third Great Lakes Symposium on VLSI (Kalamazoo, MI, March 5-6), 67-68.
• 2: CAI, Y. AND WONG, D. F. 1993. On minimizing the number of L-shaped channels in 93 building-block layout. IEEE Trans. Comput. Aided Des. 12, 6, 757-769.
• 3: Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
• 4: DAI, W. M., ASANO, T., AND KUH, E. 1985. Routing region definition and ordering scheme for building-block layout. IEEE Trans. Comput. Aided Des. 4, 189-197.
• 5: Du, D. AND ZHANG, Y. 1990. On heuristics for minimum length rectilinear partitions. Algorithmica, 5, 111-128.
• 6: EDELSBRuNNER, H., O'ROURKE, J., AND WELZL, E. 1984. Stationing guards in rectilinear art galleries. Comput. Vision, Graph. Image Process. 27, 167-176.
• 7: GONZALEZ, T. F. AND ZHENG, S.-Q. 1990. Approximation algorithms for partitioning rectilinear polygons. Algorithmica, 5, 11-42.
• 8: Teofilo Gonzalez , Si-quig Zheng, Improved bounds for rectangular and guillotine partitions, Journal of Symbolic Computation, v.7 n.6, p.591-610, June 1989 [doi>10.1016/S0747-7171(89)80042-2]
• 9: Teofilo F. Gonzalez , Mohammadreza Razzazi , Man-Tak Shing , Si-Qing Zheng, On optimal guillotine partitions approximating optimal d-box partitions, Computational Geometry: Theory and Applications, v.4 n.1, p.1-11, May 1994 [doi>10.1016/0925-7721(94)90013-2]
• 10: GONZALEZ, T. F., RAZZAZI, M., AND ZHENG, S.-Q. 1993. An efficient divide-and-conquer algorithm for partitioning into d-Boxes. Int. J. Comput. Geom. Appl. 3, 4, 417-428.
• 11: Ellis Horowitz , Sartaj Sahni, Fundamentals of data structures in PASCAL, Computer Science Press, Inc., New York, NY, 1984
• 12: Hiroshi Imai , Takao Asano, Efficient algorithms for geometric graph search problems, SIAM Journal on Computing, v.15 n.2, p.478-494, May 1986 [doi>10.1137/0215033]
• 13: Andrzej Lingas, Heuristics for minimum edge length rectangular partitions of rectilinear figures, Proceedings of the 6th GI-Conference on Theoretical Computer Science, p.199-210, January 05-07, 1983
• 14: LINGAS, A., PINTER, R., RIVEST, R., AND SHAMIR, A. 1982. Minimum edge length partitioning of rectilinear polygons. In Proceedings of the 20th Allerton Conference on Commun. Control Comput., 53-63.
• 15: W. T. Liou , J. J. Tan , R. C. Lee, Minimum partitioning simple rectilinear polygons in O(n log log n) - time, Proceedings of the fifth annual symposium on Computational geometry, p.344-353, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73871]
• 16: MARPLE, D., SMULDERS, M., AND HEGEN, H. 1990. Tailor: A layout system based on trapezoidal corner stitching. IEEE Trans. Comput. Aided Des. 9, 1, 66-90.
• 17: MEHTA, D. P., SHANBHAG, A., AND SHERWANI, N.A. 1995. A new approach for floorplanning in MBC designs. Tech. Rep. 95-02, Univ. of Tennessee Space Institute.
• 18: NAHAR, S. AND SAHNI, S. 1988. A fast algorithm for polygon decomposition. IEEE Trans. Comput. Aided Des. 7 (April), 478-483.
• 19: OHTSUKI, T. 1982. Minimum dissection of rectilinear regions. In Proceedings of the 1982 International Symposium on Circuits and Systems (ISCAS), 1210-1213.
• 20: Joseph O'Rourke, Computational geometry in C, Cambridge University Press, New York, NY, 1994
• 21: O'ROURKE, g.1983. An alternate proof of the rectilinear art gallery theorem. J. Geom. 21, 118-130.
• 22: OUSTERHOUT, J. K. 1984. Corner stitching: A data structuring technique for VLSI layout tools. IEEE Trans. Comput. Aided Des. 3, 1, 87-100.
• 23: John K. Ousterhout , Gordon T. Hamachi , Robert N. Mayo , Walter S. Scott , George S. Taylor, Magic: A VLSI layout system, Proceedings of the 21st conference on Design automation, p.152-159, June 25-27, 1984, Albuquerque, New Mexico, United States
• 24: SEQUIN, C. H. AND FA~ANHA, H. D.S. 1993. Corner stitched tiles with curved boundaries. IEEE Trans. Comput. Aided Des. 12, 1, 47-58.
• 25: SHANBHAG, A. G., DANDA, S. R., AND SHERWANI, N. 1994. Floorplanning for mixed macro block and standard cell designs. In Proceedings of the Fourth Great Lakes Symposium on VLSI (Notre Dame, IN, March 4-5), 26-29.
• 26: Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1995
• 27: Ting-chi Wang , D. F. Wong, An optimal algorithm for floorplan area optimization, Proceedings of the 27th ACM/IEEE conference on Design automation, p.180-186, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123253]
• 28: Wu, S. AND SAHNI, S. 1991. Fast algorithms to partition simple rectilinear polygons. Int. J. Comput. Aided VLSI Des. 3, 241-270.
• 29: Wu, S. AND SAHNI, S. 1990. Covering rectilinear polygons by rectangles. IEEE Trans. Comput. Aided Des. 9 (April), 377-388.
• 30: Kok-Hoo Yeap , Majid Sarrafzadeh, Floor-planning by graph dualization: 2-concave rectilinear modules, SIAM Journal on Computing, v.22 n.3, p.500-526, June 1993 [doi>10.1137/0222035]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

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

General Terms:
Algorithms

Keywords:
L-shapes, corner stitching, partition, rectangle, rectilinear polygons