Recursive Cutting of Rectangular Partitions for VLSI Floorplanning

Rectangular partitionings form a mathematical base for many modern approaches to automation of VLSI design [1-3]. In particular, popular methodologies of hierarchical placement (by cell grouping / merging) as well as procedures of global routing and layout compression deal with partitions that can be hierarchically subdivided into components of bounded complexity.

The article shows that some tight placements cannot be generated by any pairwise merging procedure in the class of isotetically convex blocks.

 

Figure 1. Simplest blocks of bounded rank.

 

Isotetically convex blocks (here called blocks, for simplicity) are well described in [4,5]. A block P is a closed polygon whose boundary consists of line segments parallel to coordinate axes, and every horizontal or vertical segment connecting any two points of the polygon P belongs to P. Rank r of block P is the minimal number of rectangles R1, R2, ..., Rr which do not intersect block P and complete it to rectangle. In other words:

P (Ri, for i=1,2,...,r) is rectangle,

Ri Rj = for i,j=1,2,...,r, i != j.

Ri R = for i=1,2,...,r.

This definition of rank is equivalent to one introduced in [5]. Rank r of block P and number k of block vertices are related by equation

k = 2r + 4.

Figure 1 shows all possible blocks of rank 0, rank 1, and three blocks of rank 2 (excluding ones made by symmetry transformations).

Let us denote the interior of set A by int(A) and boundary of A by fr(A). A set of rectangles

R = {Ri}, i=1,2,...,n is partition of block P if

1. int(Ri) int(Rj) = , i != j, i,j=1,2,...,n

2. {Ri, i=1,2,...,n} = P.

There is an evident relation between the structure of block and its partition. So we will use same letter P to denote both the block itself and it partition. Rectangles Ri are called atoms of the partition. The rank of partition is the rank of the partitioned block.

Articles [6-7] propose an approach to find the "best" placement of isotetic blocks based on the sequence of their pairwise merging. This article is intended to show an existence of placements which cannot be constructed by any sequence of pairwise merge operations over isotetically convex blocks of limited rank.

Let us introduce the following notations:

- V is set of vertices of P atoms;

- F is aggregate of atom boundaries:

F = {fr(Ri), i=1,2,...n};

- L is partition of F:

L = {S=[V1,V2] | (S V) = {V1,V2}}.

Now we can introduce the notion of cutting. An ordered sequence C=(S1,S2,...,St) of segments of partition P cuts partition P if:

- Si L, i=1,2,...t;

- (Si Sj) = Vij, Vij V if

and only if i=j+1, or j=i+1; i,j=1,2,...t;

- (Si Sj) = 0 if and only if

i != j+1 and j != i+1, i,j = 1,2,...,t;

- (C fr(B)) = (Vb, Ve}, where

Vb = (S1 fr(B)),

Ve = (St fr(B), Vb,Ve V.

In other words, cutting is a simple path consisting of segments of L such that it first and last points belong to boundary of block P. C is "through" cutting if Vb and Ve belong parallel segments of boundary of P. Otherwise cutting is called as "sidelong".

Every cutting C splits the partition P into non-empty subsets P1 and P2. Herein we will consider only cuttings which intersections with any horizontal or vertical line are connected. In this case (P1) and (P2) are blocks.

Cutting C2 intersects cutting C1, if C1 cuts P into partitions P1 and P2, and C2 is cutting either P1 or P2, and just one of end points of C2 belongs to C1.

Let us define the direction of cutting:

We will say that block (partition) P can be recursively cut into blocks of rank r if partition P contains cutting which splits it into non-empty partitions P1 and P2, ranks of P1 and P2 do not exceed r, and both blocks P1 and P2 also can be recursively cut into blocks of rank r. It is supposed that a single atom can be cut into blocks of any rank. Figure 2 shows three first steps of cutting rectangle onto blocks of rank 2.

Figure 2. Recursive cutting onto blocks of rank 2.

 

A set of all partitions recursively cut only onto blocks of rank >= r is denoted via P**r.

Theorem. The set P**r is not empty for any positive integer r. In other words, for any positive integer r there exists partition which cannot be cut onto blocks of rank r.

To prove the theorem, we will show how to construct an example partition P of square which belongs to P**r for every pre-defined natural r. The construction will be made on 2-dimensional regular integer grid.

Partition P1 from P**1 can be pointed out directly. It is the first "snail" drawn on Figure 3. Any through cutting splits it into blocks of rank 1. Sidelong cutting splits the "snail" into blocks of ranks 0 and 1. So one-dimensional "snail" belongs to P**1.

 

Figure 3. Based "snail" and generated partitions Pr.

 

 

Partition Pr from P**r can be constructed as a square containing r rows and r columns. Cell Kij located at the intersection of row i and column j, i+j=0(mod2), i,j = 1,2,...r, contains "snail" P1. Cell Kij, i+j=1(mod2), i,j=1,2,...r, contains partition ~P1 which is mirroring of P1 with respect to horizontal or vertical axis. Figure 3. shows example partitions P1, P2, P3 and the structure of cells for example partition P3.

Partition Pr inherits main property of partition P1. Namely, a part of any cutting bounded by bottom (upper) side of cell Kij and bottom (upper) side of source square contains i-1 (r-i) steps. If this part is bounded by cell side and bottom (upper) side of the source square, then it contains i (r-i+1) steps.

Now we are ready to show, that any sequence C^ =(C1,C2,...,Cq) of cuttings Pr onto atoms will create blocks of rank >= r. Blocks created after every cutting from C^ can be considered as central (ones contain symmetry center of source square) and peripheral blocks. Peripheral blocks are out of our interest. We will estimate ranks of central blocks. So cuttings peripheral blocks can be instantly removed out of C^, and, after this operation, C^ can be considered as sequence of cutting details out of central point.

Pr consists of r rows and r columns. As it was noted, every through cutting contains r steps. It is true, because maximal available length of every segment in Pr is 3 units and every cutting started and finished on opposite sides of the initial rectangle contains r steps and, consequently, it creates blocks of rank r. So, let us assume C^ does not contain through cuttings.

The last assumption means that C^ contains at least one sidelong cutting for the original square and one additional cutting which intersects the first one. Otherwise it would be impossible to cut out central atom of source partition. Let denote this additional cutting by Cp:

p = min{k | (Ck Ck^) != }, where Ck^ =

{Cj, j=1,2,...,k-1}.

As it is noted in [4], after C1,C2...,Cp-1 cuttings the central block is bounded by at most 4 stairways. Its general view is shown at Figure 4. Segments F1=(B1,A2),...,F4=(B4,A1) are parts of boundary of the initial square. So, without loosing the correctness, we can assume that first p-1 cuttings in C^ can be replaced by 4 ones: C1', C2', C3', C4', where Cj'=(Aj,...,Bj), j=1,...,4.

Figure 4. General structure of isotetically convex block.

 

 

Now let us consider structure of blocks being created after all possible configurations of cutting Cp. Let Ap and Bp be its first and last vertices, Ap C1', Pp1 and Pp2 are central and peripheral blocks which are cut out by Cp. Taking into account the symmetry of configuration, we can consider only the following 6 different cuttings:

1. dir(Cp) = dir(C1'), BpF1;

2. dir(Cp) = dir(C1'), BpCk', k=2,3,4;

3. dir(Cp) != dir(C1'), BpC2';

4. dir(Cp) = dir(C1'), BpF2;

5. dir(Cp) != dir(C1'), BpF2;

6. dir(Cp) != dir(C1'), BpC3'.

In the first case the block Pp1 is bounded by (A1,...,Ap,...Bp). It is sidelong cutting. The structure of the block Pp1 remains the same as shown at Figure 4. We can assume it is built from the original square with the help of cuttings (A1,...,Ap,...,Bp), C2', C3', C4'. If we replace block Pp by block Pp1 and cuttings C1' and Cp in C^ by cutting (A1,...,Ap,...,Bp), then we can recursively consider sequence C^ again without loosing of correctness.

In the second case the block Pp1 is bounded either by cutting (A1,...,Ap,...Bp) or cutting (B1,...Ap,...Bp). We can reduce this configuration to configuration of the general case again. With this goal let us repair the central block Pp by gluing peripheral block split by C1' and replacing cuttings C1' and Cp in C^ by boundary of just created Pp1.

The third case can be reduced to the second case by re-orientations.

In accordance with assumption cutting cannot go through a boundary of the central atom. So reductions made during consideration of first three cases are correct and we will meet in C^ cutting made by one of rest cases.

In the fourth case the block Pp1 will be bounded by (A1,...,Ap,...,Bp). It is through cutting.

Now we consider case 5. Illustrations for it is shown at Figure 5. Let Ap cell Klm. All available intersections of cutting C1' and cutting Cp inside Klm are shown at Fig 7. Boundaries of the cell are drawn by thin lines. Parts of C1' and Cp bounded by l-th row are drawn by thick lines. Let us denote the contribution of the l-th row into the rank of block Pp1 by Sl. It can be easily seen that Sl = 1 (for intersections 1,3,5,6,7,9,10,11,12) or Sl = 2 (for intersections 2,4,8). Now we can estimate the number of steps of the left boundary of block Pp1: (l-1) + Sl + r-l) >= r.

 

   

 Figure 5. Case 5 of cutting.

 Figure 6. Case 6 of cutting.

The last case is illustrated at Figure 6. Let us assume that Ap Klm, BpKkn. Let us denote contributions of rows l and k into rank of the block Pp1 by Sl, Sk, and contributions of columns m and n into rank of the block Pp2 by Sm and Sn. From the properties of the initial "snail" it follows that:

Sl, Sm, Sk, Sn >= 1.

the following conditions are necessary for Pr to be recursively cut into blocks of rank < r:

(l - 1) + Sl + (k - l) + Sk + (r - n) < r;

(m - 1) + Sm + (n - m) + Sn + (r - k) < r.

Incompatibility of these conditions shows that there is no way to build sequence of cutting in class of isotetic blocks with apriory bounded number of vertices. It finishes the proof.

The author wishes to express his gratitude to N.Metelsky for formulation of the problem and kindly advices.

 

Figure 7. All possible intersections of cutting inside cell.

Summary

There exist a partition of the square into rectangles which cannot be synthesized by pairwise block merging procedure in the class of convex isotetic blocks with apropriory bounded number of vertices.

References

  1. Busnyuk N.N., Sarvanov V.I. // Vesci AN BSSR.
  2. Busnyuk N.N., Graphs of partition of rectangle into rectangles. Preprint (36(306)) of the Mathematical Institute, Belarussian Academy of Sciense, 1987.
  3. Klebanovich D.M., Metelskiy N.N. Grid of macro-blocks for channel model of VLSI. Preprint (6(316)) of the Mathematical Institute, Belarussian Academy of Sciense, 1988.
  4. Wood D. // Computational geometry, Toussaint G.T. (editor). North Holland): Elsevier Science Publishers, 1985, P.431-459.
  5. Metelskiy N.N., Krikun V.S. Isotetic boundaries of limited rank, type and kind. Preprint (10(410)) of the Mathematical Institute, Belarussian Academy of Sciense, 1990.
  6. Azarenok A.S., Klebanovich D.M., Krikun V.S. and others. Automation of VLSI design. Method of hierarchical generation VLSI layout on the base of fixed non-standard blocks. Preprint (16(316)) of the Mathematical Institute, Belarussian Academy of Science, 1990.
  7. Metelskiy N.N., Krikun V.S. The method of hierarchical placement of isotetic blocks. Preprint (27(427)) of the Mathematical Institute, Belarussian Academy of Sciense, 1990.