Optimal Packing of Orthoblocks For ULSI Floorplanning

 

1. Introduction

Virtually all latest and prospective enhancements of Expert Layout processor (for example, semi-automatic floorplanning) are based on sophisticated geometrical models. In some cases some advanced mathematical research is necessary to develop efficient algorithms. This article is devoted to the problem of optimal packing of orthoblock which is originated from several areas of VLSI design automation.

Cutting, packing and placement problems appear under different names in literature and come from various fields of production, design, engineering, planning and operations research. In spite of their variety, these problems have essentially much in common. H. Dyckhoff [2] was probably the first to take an attempt to develop a comprehensive topology integrating the various kinds of cutting and packing problems. Note this topology has not list its significance until now and we refer the reader to the survey [2] for a unifying framework of cutting and packing problems as well as for an overview of methods for their solving. Different special aspects of the cutting and packing topic related to our packing problems are also concerned in [6,9]. Our paper is devoted to an extension of the hierarchical merging method which has been used so far for solving placement and layout problems [1,3,4,10] in the plane to a special packing problem in 3 dimensions. Informally speaking, the problems is to pack given items (material pieces) into a container with a minimum area base. Our problem has the following features.

1. Unlike the problems considered in [2], no container is given in advance, but it is to be constructed (designed) as a result of solving the problems. Container design must meet the following requirements: – container must be cylinder, with its bottom being a rectilinear polygon (so-called) orthogon, see below;

  • container’s geometric shape determined by the shape of its bottom should be “simple” enough in common sense;

  • material consumption to manufacture a container defined by its lateral area and, consequently, determined by the perimeter length of its bottom should be reduced;

  • the bottom area should be minimized to save the pallet space when loading containers on a pallet.

We define the container bottom to be an orthoconvex polygon (see below) to settle contradictions among the above container’s properties by a proper compromise.

2. The item in our problem are assumed to be “thin”, i.e. to be cylinders with rectilinear bases and “small” heights to provide the practical adequacy of our model. This implies that the items can be assumed to be planar objects, more precisely rectilinear polygons. Taking into consideration this circumstance and following Dyckhoff [2], we should speak about our problem as a 2.5-dimensional problems rather than 3-dimensional one.

Note at last we deal with arbitrary rectilinear items whereas a majority of papers published until now are concerned with rectangular items.

 

2. Packings With A Minimum Area Base

We will consider geometric objects that have axis parallel edges. A polygon with axis parallel edges is called an orthogon (Figure 1). An orthogon P can be given by its clockwise ordered vertex list VList(P) and the translation vector which determines its current position with respect to its initial one. An orthogon P is said to be orthoconvex (Figure 2) if the intersection P and a horizontal or vertical line is connected, i.e. is empty or is a segment.

Figure 1. An orthogon P, orthoconvex hull of orthogon P
(outlined with bold lines) and rectangular
hull of orthogon P (outlined with dotted lines).

 

Figure 2. General structure of orthoconvex.

 

Rank r of orthoconvex P is the minimal number of rectangles R1, R2, ...,Rr which do not intersect P and complete it to rectangle. In other words:

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

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

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

Articles[1,4] propose an approach to find the "best" placement of isotetic blocks based on the sequence of their pairwise merging.

The orthoconvex hull OH(P) of an orthogon P is defined to be the smallest orthoconvex orthogon containing P. The rectangular hull RH(P) is the smallest axis-oriented rectangular that contains P (Figure 1).

By a placement of a set S = {P1,...,Pm} of orthogons in the plane E we mean a mapping which determines an orthogon (Pi) is in E for Pi, 1 m with the help of translation Pi by a vector vi.

Remark 1. We emphasize that our definition of orthogons placement allows overlapping of orthogons (Pi), i=1,...,m.

We define an orthoblock B in Euclidean space E to be a point set B {(x , y, z)|(x, y)P is in OXY, a z b}, where P is an orthogon. The orthogon P is called the bottom and h = b - a the height of orthoblock B.

Let M = {B1,...,Bm} be a set of orthoblocks whose bottoms P1,...,Pm have n1,...,n1 vertices, respectively, =1 ni = n.

By a packing of the set M in E we mean a mapping which determines a orthoblock (Bi) for each Bi, 1,...,m with the help of translation by a vector vi, with int (Bi) int (Bi) 0,1 i,j m, i j, (int B denotes the interior of orthoblock B). Unless otherwise explicitly stated we assume that rotations of orthoblock are not allowable.

Let M = {B1,...,Bm} be a set of orthoblock in E. We define a container C(M) of orthogons set M to be an orthoblock which contains blocks B1,...,Bm, with its bottom being orthoconvex.

The main problem is to find a packing of orthoblock set M = {B1,...,Bm} such that the area of containers bottom is minimal. We also refer to the main problem as POO (packing of orthoblocks into an orthoblock).

Notice that container height and, hence, the container volume is not assumed to be minimized in the main problem.

In general case optimal solution is very difficult to find and requires an algorithm based on exhaustive search approach. But in most practical cases an acceptable approximate solution can be obtained much faster and easier. There are number of purely heuristic algorithms designed to solve the packing problem which work very fast. There are also some heuristic modifications of exhaustive search algorithms, which substantially increase algorithm’s performance at cost of quality of result.

One of the popular approaches here is the pairwise merging technique. An algorithm based on this technique works in the following manner. Starting with initial blocks it generates new ones by merging them in pairwise manner. Blocks in each pair are attached to each other without overlapping at different relative positions thus creating a number of combined blocks. Such combined blocks are referred to as clusters. If cluster still fits in target area it is called feasible cluster and participates in subsequent mergers to form larger clusters and so on. Note that any feasible cluster as well as any initial block alone represents more or less satisfactory solution of the problem. When the algorithm is not able to generate any new cluster the best solution found so far is reported as final result.

The main obstacle in the way of practical implementation of this algorithm is merging operation . A number of problems complicate the implementation of this operation and the whole algorithm. The most interesting of them is the following.

Any two geometrical objects, even pair of rectangles, can be merged into a new one in an infinite number of ways. While initial blocks are rectangles and are relatively easy to deal with on first iterations of the algorithm, clusters that appear later can have very complex shapes. From the other side, it is easy to see that all initial blocks and intermediate clusters are orthoblocks. There are theoretical results which show that in order to find an optimal solution in this case we can limit ourselves to consideration of a finite number of relative positions of such objects -so called contact concurrent positions. However, the number of such positions can still be very large, which results in generation of large amounts of new feasible clusters. In practice the amount of intermediate data generated by the algorithm can easily overflow memory in any modern computer. Not to mention that algorithm’s iteration time grows at a very high rate.

A simple way to reduce the number of variants generated by merge function is the following.When some cluster s is generated at particular iteration of the algorithm, all previously built clusters t, such that cluster s dominates over cluster t, can be discarded without compromising the quality of final solution. In fact, in any placement that contains cluster t it can be naturally replaced with cluster s. Such replacement can only increase the quality of the solution. Note that according to definition of domination relation any cluster s dominates over itself. It means that by discarding dominated clusters the algorithm discards identical clusters as well. The discarding results in substantial decrease in number of clusters built by the algorithm thus reducing the number of variants to be checked and increasing the overall performance of the algorithm.

Amount of internal waste in cluster can be used in two simple heuristic criteria which significantly reduce number of variants processed by the algorithm. The main idea here is to detect and discard intermediate clusters that are unlikely to be part of optimal solution. The criterion is applied to clusters generated by merge operation. If a cluster meets the criterion it participates in subsequent mergers, otherwise the cluster is discarded because of high percentage of internal waste.

These criteria are heuristics, and on particular input data they can "cut off" optimal solution of the problem. But with algorithms described below they provide excellent results in terms of performance and quality of solution. There are also more complex and more precise criteria for discarding clusters that cannot be part of optimal solution . Branch-and-bound technique can be naturally used in pairwise merging algorithms.

Figure 3. Simplest blocks of bounded rank.

 

 

3. Special Cases of the Main Problem

Let us specify three cases of POO by means of the following conditions.

1. Both the container and orthoblocks B1,...,Bm are parallelepipeds (problem PPP).

2. The container is a parallelepiped (problem POP).

3. Orthoblocks B1,...,Bm are parallelepipeds (problem PPO).

It follows immediately from the setting of POO that its solution can be found if the following problem POO2 has been solved. Problem POO2 is to determine a placement * of the bottoms P1,...,Pm of orthoblocks B1,...,Bm such that the area of the orthoconvex hull covering the bottoms placed attains its minimum:

where Ar{P} is the area of orthogon P.

Let us consider the following three special cases of POO2 such that their solving provides solutions to PPP, POP, PPO.

  1. Both the container bottom and the orthoblocks bottoms P1,...,Pm are rectangle (problem PPP2).

  2. The container bottom is a rectangle (problem POP2).

  3. The orthoblock bottoms are rectangle R1,...,Rm (problem PPO2).

Figure 4. Placement t* is an exact solution of problems PPP2 and PPO2.

 

Turn to problem PPP2 which is to find a placement * of rectangles R1,...,Rm such that the area of the rectangular hull containing the rectangle is minimum and compute Ar{RH( *(Ri))}. The problem is NP-hard under additional condition int (Ri) int (Rj) = 0, 1 i, j m, i j [5] which is a mandatory requirement in two-dimensional cutting stock problems. In our case, where overlappings are allowable, the problem PPP2 can be easily solved int he following way.

Let li and hi denote horizontal and vertical size of rectangle Ri, 1 i m. Obviously, the smallest rectangle hull has the sizes L = maxi li and H = maxi li. Placement * can be realized by placing the corresponding, for example south-western vertices, at the same point (Figure 2.)

The size of the hull can be computed in O(m) time by comparing all values li, hi, 1 i m. That leads us to the following statement.

Theorem 1. Problem PPP2 and consequently PPP can be solved in O(m) time.

Theorem 2. Problem POP2 and consequently POP can be solved in O(m+n) time.

Proof. Solving problem PPO2 falls into two stages: computing the rectangular fulls for orthogons P1,...,Pm in O(n) time and then solving problem PPP2 for these hulls in O(n) time.

Turn to problem PPO2. Observe that, for placement * shown in Figure 2 the area of union Ri is minimal. Since the is union is an orthoconvex orthogon, placement * is an exact solution of problem PPO2. The vertex list VList for this orthogon can be computed n O(m log m) time by means of the sweep line method [7,8]. The area of the hull can be determined in O(m) time by using the vertex list. Hence, the following statement is true.

Theorem 3. Problem PP02 and consequently PPO can be solved in ) (m log m) time.

Generally, problem POO2 seems to be much more difficult than its special cases considered above. In this situation, one has to engage decomposition approaches. One of them, so-called hierarchical merging method [4], reduces a large-size problem of simultaneous placing orthogons to iterative placements of orthogon paris. At every iteration, a placement of two orthogons to minimize the area of their common hull is determined. This hull is an orthogon which represents the pair of block in later iterations. Selection of orthogons to be merged into a new orthogon (their common hull) is realized with the help of estimating the area waste when merging. These considerations motivates the study undertaken in the next section.

 

4. An Algorithm of Exact Solving Problems POO for Two Orthoblocks

Our idea is to take an attempt to distinguish from an infinite set of all placements a finite set (we call them concurrent) which contains at least one optimal solution.

A placement of orthogons Pi and Pj is, by definition, concurrent if x-coordinates of some vertical edges of different orthogons concur and the same holds for y-coordinates of some horizontal edges of Pi and Pj.

Note once more that we consider placements that allow overlappings of orthogons placed.

Theorem 4. There exists a concurrent placement * of orthogons Pi and Pj such that

Theorem 4 serves as the basis of the following algorithmic result.

Theorem 5. Problem POO2 for two orthogons Pi and Pj with ni and nj vertices and consequently POO for two orthoblocks can be solved in O(n n (ni+nj)) time and O(ni+nj) space.

 

References

  1. Azarionok A.S., Klebanovich D.M., Krikun V.S., Miatselski M.M., and others. Computer-aided design of VLSI circuits: a method for hierarchical generating a layout pattern on the base of arbitrarily sized blocks, Preprint N 16(326), Institute of Mathematics, AS BSSR, Minsk, 1988 (in Russian).
  2. Dyckhoff H. A topology of cutting and packing problems, Europ.J. OR, v 44, 1990. pp. 145-160.
  3. Martyuchik V.M., Miatselski M.M., Proth J.M. Computing placements of a pair of geometric objects under the criterion of intersection area minimization, Computational Mathematics and Mathematical Physics, N 5, 2000.
  4. Miatselski M.M., Krikun V.S. A method for allocation isothetic blocks, Preprint N 27(427), Institute of Mathematics, Minsk, 1990 (in Russian).
  5. Murata H., Fujiyoshi K., Nakatake S., Kajitani Y. Rectangle-packing-based module placement, Proc of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD’95), 1995.
  6. Nelissen J. New approach to the pallet loading problem, Reports RWTH, Aachen, 1994.
  7. Ottman T., Soisalon-Soininen E., Wood D. Partitioning and separating sets of orthogonal polygons, Information Sciences, v. 42, 1987, pp 31-49.
  8. Preparata F.P.,Shamos M.I. Computational geometry. An introduction, Springer-Verlag, New York, 1985.
  9. Scheithauer G., Terno J. the C4-heuristic for the pallet loading problem, Preprint Math-NM-06-1995, TU Dresden, 1995.
  10. Martynchik V., Miatselski M., Proth J.M. Three-dimensional packings of orthoblocks // Proceedings of the International Workshop “Discrete optimization methods n scheduling and computer-aided design”. Minsk, Republic of Belarus, September 5-6, 2000, p.147-150.