Topology constrained rectilinear block packing for layout reuse

ABSTRACT

In this paper, we formulate the problem of top olo gy constrained rectiline ar blo ck packing in la yout reuse. A specific class of rectilinear shaped blocks, ordered convex r ectiline ar blo cks, is represen ted in bounded slicing grid (BSG) structure. The Non-overlapped pac king is guaranteed. Based on both sequence pair (SP) and BSG structures, w e propose an algorithm to compact the ordered con vexbloc ks under the topological constrain ts, in whic hthe x and y directions are independently compacted. By augumenting or further partitioning the arbitrary rectilinear blocks in to the ordered con vexshapes, this method can be extended to handle the topology constrained rectilinear block pac king. Furthermore, our recent theoretical progress is briefly reported at the end of this paper, in which arbitrarily rectilinear shaped blocks are represented in SP structure. Three necessary and sufficient constrain ts are deriv ed on the sequence pair, such that the non-overlapping compaction is guaranteed.

REFERENCES

• 1: S. Nakatake, H. Murata, K. Fujiyoshi, and Y. Kajitani, "Bounded-Slicing Structure for Module Placement," Tech. Rep. 313, Institute of Electronics, Information and Communication Engineers of Japan, 1994.
• 2: Hiroshi Murata , Kunihiro Fujiyoshi , Shigetoshi Nakatake , Yoji Kajitani, Rectangle-packing-based module placement, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.472-479, November 05-09, 1995, San Jose, California, United States
• 3: M. Kang and W. W.-M. Dai, "General Floorplanning with L- shaped, T-shaped and Soft Blocks Based on Bounded Slicing Grid Structure," in Proc. of Asia and South Pacific Design Automation Conf. 1997, (Chiba, Japan), pp. 265-270, Feburaxy 1997.
• 4: J. Dufour, tL McBride, P. Zhang, and C.-K. Cheng, "A Building Block Placement Tool," in Proc. 1997 Aisa and South Pacific Design Automation Conf., (Chiba, Japan), pp. 271- 276, January 1997.
• 5: Maggie Kang , Wayne W. Dai, TOPOLOGY CONSTRAINED RECTILINEAR BLOCK PACKING FOR LAYOUT REUSE, University of California at Santa Cruz, Santa Cruz, CA, 1997

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

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

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

General Terms:
Algorithms, Design