Method for generating an optimized nested arrangement of constrained rectangles

The overall arrangement of a number of non-overlapping rectangles with constraints on their size and shape, may be generated with relation to a number of objective functions such as, size and shape of the enveloping rectangle, size of an interconnecting network, and distance between pairs of individual rectangles, by first embedding a distance space, reflecting the desired proximity structure, in the plane; next, by refining containment relations, fixing the relative positions of rectangles within such a containment in accordance with the corresponding positions in the embedding; and on the basis thereof estimating the space required for the local realization of the interconnecting network in a configuration satisfying the constraints on the individual rectangles, and optimal with respect to any quasi-concave objective function on the dimensions of the enveloping rectangle that is monotone in its arguments. The method can be implemented even on relatively small computers. Its major application is in the generation of mask patterns of complex semiconductor integrated circuits, especially when a given functional structure must be preserved by containment in rectangles.

TECHNICAL FIELD OF THE INVENTION 
The present invention relates to information handling systems and more 
particularly to automatic process control systems. 
The invention can be applied in production environments where rectangles 
are dissected into smaller rectangles and where the usefulness and the 
quality of the dissection depend on the position of the rectangles 
relative to each other and to the enveloping rectangle. Two environments, 
where such a dissection directly affects the costs and the quality of the 
products, will be described to illustrate the involvement. 
The first is a stock-cutting task, where a machine is capable of dissecting 
rectangular sheets up to a certain size by a cut parallel to one of the 
sides and all the way across that sheet. The properties of the material 
may vary over the sheet so that, depending on the requirements, the 
smaller rectangles are preferably taken from specific regions of the 
sheet. Also the amount of waste material must be kept small. The invention 
can be used to drive the cutting machine on the basis of quality 
measurements on the sheet. 
A second and probably more important application of the invention is in the 
production of mask patterns for circuit integration by semiconductor 
technologies. The complexity of these patterns, measured in the number of 
elementary patterns, such as rectangles, has increased enormously, and 
made it necessary to employ digital computers to assist in or take over 
the handling of the data to be processed during the design of mask 
patterns. But even with the help of a computer the size of the problems 
may still be unmanageable. Today's micro-electronics technology makes 
systems with millions of elementary patterns feasible. The design 
complexity of these so-called very large scale integrated (vlsi) circuits 
makes new functional design methodologies imperative. 
It has been conjectured that complex systems evolve far more quickly if 
they are of hierarchic nature (i.e. composed of interrelated subsystems, 
each being hierarchic in structure, until some lowest level of elementary 
subsystems is reached) than non-hierarchic systems of comparable size. 
Therefore, a hierarchical design methodology is probably the only feasible 
approach for developing new vlsi circuits from user-oriented 
specifications. 
Software systems for generating the mask patterns of today's integrated 
circuits have to accept a functional description, whether or not 
hierarchically specified, and must be capable of producing a layout 
satisfying rules depending on the fabrication technology and the required 
performance of the circuit. 
The invention disclosed in this application fits in such systems. 
PRIOR ART 
A rectangle dissection problem was formulated in 1940 by R. L. Brooks, C. 
A. B. Smith, A. H. Stone, and W. T. Tutte in their article The dissection 
of rectangles into squares in Duke Math. Journal, Volume 7, pages 312 up 
to 340. The topologies of the dissection they were after, are exactly 
those the present invention excludes. Consequently, their methods (and 
methods of the mathematicians solving the same problem) do not teach nor 
suggest the present invention. 
A reduction of complexity obtained by restricting the topology of the 
dissection to those generated by the present invention was recognized by 
P. C. Gilmore and R. E. Gomory when solving cutting stock problems. Their 
results were published in Operations Research, Volume 13, pages 94 up to 
120, in 1963. Their major concern was to minimize waste material when a 
number of fixed rectangular sheets of material had to be cut out of a big 
rectangular sheet. The position of each rectangle in relation with the 
positions of the other rectangles was not important. 
In 1979 U. Lauther presented a placement algorithm for rectangles with 
fixed shapes at the 16th Design Automation Conference. The method is 
described in Journal of Digital Systems, Volume 4, pages 21 up to 34 
issued in 1980. In the first part, however, the shapes do not affect the 
process, only the areas and the nets interconnecting the subsystems to be 
allocated in the rectangles are taken into account. The outcome of this 
first part is a topology, though somewhat more constrained, consistent 
with the rules for topologies generated by the method according to the 
present invention. The other parts of that system do not preserve the 
topology delivered by the first part, and allow more general building 
block configurations. 
Also in 1979, a layout design system called MIRAGE was announced at the 
16th Design Automation Conference in San Diego, as can be read at pages 
297 up to 304 of the Proceedings of the 16th Design Automation Conference. 
Although the example satisfies the topology constraints of the invention, 
no method for generation of these configurations is described or reported. 
The necessity of a layout system that accepts a functional hierarchy as 
useful information for a layout generating process, was published in 1978 
by B. T. Preas and C. W. Gwynn, Methods for hierarchical automatic layout 
of custom lsi circuit masks, Proceedings of the 15th Design Automation 
Conference, pages 206 up to 212. A complete embodiment is not described, 
but from what has come to the knowledge of the applicant it is clear 
that--if an embodiment of that idea exists--it uses building block 
formulations with rigid shapes for the rectangles. 
The genealogical approach to the layout problems, published by A. A. 
Szepieniec and the applicant of the present invention in Proceedings of 
the 17th Design Automation Conference, pages 535 up to 542, in 1980, has 
exactly the same topology restrictions as this invention. However, in the 
first part of the genealogical approach the generation of this topology 
does not follow a strictly top-down slicing process. It starts with the 
placement of some rectangle around which other rectangles are placed in 
accordance with the topological restrictions. Consequently, the 
interrelations are not taken into account in a global way as they are in 
the present invention where a two-dimensional point configuration is 
generated on the basis of the whole interrelations structure. The 
genealogical approach only considers nets connecting the subsystems in the 
already placed rectangles with those that are not yet placed. The second 
part does proceed in a top-down manner, but it uses a merging instead of a 
slicing process. The global interrelation structure does not have priority 
as it has in this invention. Therefore, the techniques employed in the 
genealogical approach to obtain the topology of the configuration cannot 
be used in the topology part of an embodiment of the present invention. 
In case all given rectangles have fixed shape and size, but free 
orientations, an algorithm described by L. Stockmeyer in IBM Research 
Report RJ 3731 can be used in the last part of an embodiment of this 
invention. The method according to the present invention is a 
generalization, and is capable of optimizing configurations of a mixture 
of fixed and flexible rectangles with or without free orientations, and 
with wiring areas of given width. 
Some of the subtasks arising in an embodiment have well-known sometimes 
even standard solutions. For the method according to the preset invention, 
they will be mentioned at the appropriate places. The more specific, but 
for the embodiment preferred, methods will be described and given in the 
form of implementations in the figures. 
The prior art discussed above does not teach nor suggest the present 
invention as disclosed and claimed herein.

DISCLOSURE OF THE INVENTION 
For uniformity of terminology the following definitions of a number of 
terms have been employed. 
A rectangle dissection is a geometrical configuration consisting of 
non-overlapping rectangles that together completely cover an enveloping 
rectangle. 
A slice is either an undissected rectangle or a rectangle dissected into 
slices by cutting lines parallel to one of the sides of the rectangle. 
A slicing structure is a rectangle dissection that can be obtained by 
recursively dividing rectangles into smaller rectangles by parallel lines. 
The slices obtained by dissecting a slice over all its parallel cutting 
lines are called the children or child slices of the dissected slice and 
siblings or sibling slices of each other. By maintaining a consistent 
ordering among sibling slices (e.g. left to right, and top to bottom) each 
of the sibling slices except one has a unique next sibling separated from 
it by exactly one cutting line. The dissected slice is called the parent 
or parent slice of the obtained slices. An undissected rectangle in a 
slicing structure is called a cell. 
The topology of a slicing structure is a tree with each slice represented 
by a node, and arcs from each node representing a parent to each node 
representing one of its children, leaving the parent's node in accordance 
with the ordering of the children. 
The longitudinal dimension of a slice is the dimension it inherits from its 
parent slice. The other dimension is its latitudinal dimension. The 
lattitudinal dimension of the common ancestor slice is the length of the 
side it transmits to its child slices. The other dimension is its 
longitudinal dimension. 
A bounding function is a right continuous, non-increasing, positive 
function of one variable defined for all real values not smaller than a 
given positive constant. 
The bounded area of a bounding function f is the set of pairs of real 
numbers (x,y) such that f(x) is defined and y.gtoreq.f(x). 
The inverse f.sup.-1 of a bounding function f is a bounding function 
defining a bounded area with exactly those (y,x) for which (x,y) is in the 
bounded area of f. 
The shape constraint of a rectangle is a bounding function of its 
longitudinal dimension. The bounded area of that function is the set of 
all permissible pairs of longitudinal and latitudinal dimensions. 
A contour score is a function of two variables, defined for all pairs of 
positive real numbers, and which is quasi-concave and monotone in its two 
arguments. 
In assembling a number of rectangles, each limited by a shape constraint, 
within one enveloping rectangle of which the dimensions are the arguments 
of a contour score to be minimized, and where the positions of the 
rectangles are related to the usefulness of the final configuration, a 
generation in accordance with this invention can be achieved by a sequence 
of procedures 
that accepts 
the description of the rectangles in the form of their shape constraints, 
and their interrelations in the form of 
an incidence structure, 
a distance function, 
a weight function, 
a combination thereof or 
other data from which mutual proximities (or distances) can be derived, 
which are transformed into a point configuration in the plane, 
or a configuration of points in the plane, each point representing a 
rectangle, 
from which a slicing structure is derived, 
or relative positions in a slicing structure, and that on the basis of that 
slicing structure estimates the space 
required for the realization of the interrelations, finally yielding a 
configuration of rectangles within an enveloping 
rectangle, satisfying the given shape constraints on these rectangles, 
leaving the estimated space for the realization of the interrelations and 
optimal under these constraints with respect to the given contour score. 
In accordance with this invention three procedures are required. The first 
procedure, TOPOLOGY, must deliver a topology for the slicing structure, on 
the basis of the available data. The second procedure, JUNCTOR, estimates 
the space required for realizing the interrelations between the rectangles 
with relative positions in accordance with the obtained slicing structure. 
The third procedure, GEOMETRY, determines the dimensions and positions of 
the rectangles such that the value of the contour score is optimized over 
all possible longitudinal and latitudinal dimensions of the enveloping 
rectangle. 
Also needed, of course, are structures for storing the intermediate data 
such as the topology, the space estimations, the bounding functions, etc. 
DESCRIPTION OF A PREFERRED EMBODIMENT 
The embodiment to be described with reference to FIGS. 5 through 26j, is 
the invention as applied to mask pattern generation for large scale 
integration. The preferred environment is a hierarchical functional design 
system. A hierarchic system or a hierarchy is either a system composed of 
interrelated subsystems, each of the latter being hierarchic in structure, 
or an elementary system. The systems in a hierarchy are called modules. A 
hierarchy can be represented by a tree. Each vertex in such a tree 
represents a module. An arrow from a vertex points to the subsystems 
(submodules) of the module it represents. The incoming arrow refers to its 
(unique) supermodule. The one module without an incoming arrow, the root, 
represents the whole system. The elementary subsystems are represented by 
the leaves, vertices without outgoing arrows. 
In such an environment a program calls for each of the nonelementary 
modules the procedure FLOORPLAN which is a particular embodiment of the 
invention. The sequence in which the modules are treated is strictly 
top-down. This means that a module is never treated by FLOORPLAN before 
its supermodule is. After completion of FLOORPLAN for all modules composed 
of more than one submodule, the program calls the appropriate procedures 
for the elementary modules. Then, in bottom-up sequence (i.e. child slices 
have to be treated before their parent slice is treated), the program 
realizes the interconnections in the reversed spaces called junction 
cells, and puts everything together by assigning absolute coordinates to 
all patterns. 
The direct environment of the embodiment to be described can be best given 
in a pseudo-pascal text 
module list:=(root); 
while module list is not empty do 
begin select M from the module list; 
delete M from module list; 
FLOORPLAN (M); 
add {non-elementary submodules of M} to module list end; 
After completing the above loop the elementary modules get a complete 
layout assigned to them, either by calling technology and style dependent 
layout generation routines, or by assigning an orientation to some stored 
layout image. Then, in a bottom-up manner, the modules are combined by 
completing the wiring spaces between them. (Bottom-up means that all child 
slices must be completed before their parent slice can be treated.) The 
process is finished when the common ancestor has been treated. 
The input available to FLOORPLAN contains the modules, their shape 
constraints, and proximity relations between the modules. Sometimes more 
information is available, such as the distribution of pins over the sides 
of a module, or even the exact location of the pins relative to the 
module. The latter is the case, for example, for inset cells. These are 
cells of which the complete layout is stored in some library. For the 
embodiment these cells are rectangles with fixed dimensions. The pin 
information can be used to give the cell an orientation in an early stage 
of the FLOORPLAN, if an orientation is not prescribed. The shape 
constraint of an inset cell with fixed orientation relative to its slice 
is like the one in FIG. 4a. The shaded areas indicate the bounding area. 
FIG. 4b gives a shape constraint of a non-square inset cell with free 
orientation. Another extreme example of a module is a flexible cell. 
Mostly, only a lower bound on the area is given for such a module, though 
a square shape generally is preferred. Its shape constraint looks like the 
one in FIG. 4c. The distribution of its pins over the sides is not known 
when FLOORPLAN is called. 
Several kinds of proximity data are possible, such as a distance matrix, a 
weight matrix, and a net list. Sometimes more specific information about 
the interrelations is available, such that parts of the embodiment can be 
bypassed. For example, when an acceptable point configuration is 
available, EMBED does not have to be called. When a topology is available, 
the whole TOPOLOGY part can be skipped. 
Commonly, the relations between the modules are given in the form of a net 
list. This is an incidence structure where the modules are considered as 
sets of pins. The nets are also considered to be sets of pins. The net 
list indicates whether a module and a net share a pin. 
Modules and nets are identified in FLOORPLAN by positive integers. The 
embodiment uses the fact that the position of a module or a net in certain 
data structures corresponds with the identifying number. 
With m modules and n nets the net list can be represented by a (0-1) matrix 
P.sub.mn. There are one-to-one correspondences between the rows and the 
modules, between the columns and the nets, and between the pins and the 
nonzero entries of P. An entry p.sub.ij equals 1 if the corresponding 
module and net share a pin. Otherwise p.sub.ij =0. Certain nets are 
critical, which means that it is important to keep them small. The 
criticality sometimes can be measured by a weight. Adopting the same order 
for the nets as in P the weights assigned to the nets can be represented 
by a positive vector w.sub.n. The higher the weight of a net, the closer 
the modules connected by this net should be together. 
Unless the topology of the required configuration is already among the 
available data, an embodiment in accordance with the invention first 
processes the available data in a procedure called TOPOLOGY, as indicated 
in FIG. 5. This procedure has to generate the topology of the slicing 
structure. It does so in the three stages given in FIG. 6, of which the 
first can be bypassed if a suitable point configuration in two dimensions 
is given in the available data. Every module to be accommodated in the 
enveloping rectangle must be represented in this configuration by a point, 
and the distances between two points must reflect the interrelation of the 
corresponding modules. If not available such a point configuration has to 
be generated in EMBED, the first stage of TOPOLOGY. The second stage, 
SLICING, produces a topology of a slicing structure in which the relative 
positions of the points are mainly preserved, and points close to each 
other are contained in many slices, if other requirements do not prevent 
that. 
The two-dimensional point configuration can be stored in two vectors, x and 
y, where x.sub.i and y.sub.i are the coordinates of the point representing 
module i. 
There are many ways described in literature to obtain a point configuration 
from data exhibiting the interrelation of objects. Three of them, 
mentioned in FIG. 7, will be described. One method frequently used in the 
context of circuit integration was described by Kenneth M. Hall in 1970 in 
his article `An r-dimensional quadratic placement algorithm`that appeared 
in Management Science, volume 17, pages 219 up to 229. It can be used in 
an embodiment of the invention if the interrelations can be measured by a 
weight function. Given a symmetrical matrix W, where element w.sub.ij 
quantifies the desirability of having the modules i and j close to each 
other, the method described by Hall minimizes .SIGMA..SIGMA. w.sub.ij 
d.sub.ij, where d.sub.ij is the euclidean distance between the points i 
and j, under certain conditions that guarantee a certain spread in the 
configuration, but are mainly chosen for convenience. 
The function CONFIG of FIG. 8 needs a distance matrix. This matrix can be 
input, or has to be generated before SCHOENBERG (see Equation (2)) is 
called. If the interrelations between the modules are given as a netlist, 
possibly with a weight vector for the nets, it can be transformed into a 
distance space. Among the many possible transformations the dutch metric 
appeared to be the most satisfactory. Its mathematical definition is given 
in equation 1. 
EQU D.sup.2 =J.sub.mm -(PI(w)P.sup.T)/((w.sup.T j.sub.n)J.sub.mm -FI(w)F.sup.T) 
(1) 
where F has a one where P has a zero and the other way around. An 
implementation yielding the distance matrix according to this formula is 
in FIG. 9, the function DUTCH. 
A bar over a matrix or vector operation indicates that the operation is to 
be performed elementwise. I(v) is a diagonal matrix with the elements of 
the vector v on its diagonal. J.sub.mn is an m.times.n matrix of all ones. 
j.sub.n is a vector of length n with all ones. 
Having obtained a distance space for the set of modules by whatever method, 
SCHOENBERG with the functions called by SCHOENBERG can be used to obtain a 
point configuration. The coordinates of the points in such a configuration 
are the components of eigenvectors associated with the two largest 
eigenvalues of the Schoenberg matrix of the distance space, where a 
Schoenberg matrix is defined as 
EQU -1/2ZD.sup.2 Z (2) 
Here D is the distance matrix of the distance space and Z.sub.mm 
=I(j.sub.m)-J.sub.mm. 
The resulting point configuration in the euclidean plane always is optimal 
in the following sense: 
In general, with an arbitrary distance matrix, applying SCHOENBERG results 
in a two-dimensional configuration of which the Schoenberg matrix S' is 
the best approximation of the Schoenberg matrix S derived from the 
original distance space, in the sense that 
EQU .psi.=j.sub.m.sup.T (S-S').sup.2 j.sub.m (3) 
is minimal, i.e. the sum of the squares of the differences between 
corresponding entries of S and S' is minimal. 
If, however, the given distance space is embeddable in some (r-dimensional) 
Euclidean space (i.e its Schoenberg matrix is positive semidefinite and of 
rank r or less), the obtained configuration also minimizes 
##EQU1## 
where d'.sub.ij are realized instead of d.sub.ij. 
An implementation of the functions is given in FIGS. 10a-10c. 
Another way of deriving a point configuration from net list data that is 
useful in the context of mask pattern generation is by making use of the 
principle of simulated annealing, described by Gelatt and Kirkpatrick in 
U.S. Pat. No. 4,495,559, entitled Optimization of an Organization of Many 
Discrete Elements. As stated there four elements have to be specified. The 
first element is a means for describing the configuration. Here, the 
sequence of the points in two perpendicular directions is chosen. The 
second element, a means for introducing local changes, is an elementary 
change in one or both of the sequences, for example the interchange of two 
arbitrary points. The third element is an objective function defined for 
all possible configurations and to be minimized by the procedure. 
Minimization of the expected length of the interconnections often is a 
suitable objective. If the distances between the points realistically 
represent the distances between the centers of the rectangles the ensuing 
interconnection length can be estimated quite accurately. To obtain this 
situation the points in each sequence are displaced such that the 
interspaces are proportional to the sum of the iso-oriented sides of the 
corresponding rectangles. Thus, the vectors x and y are formed. To avoid 
trivial solutions also the correlation between the two vectors defined in 
equation (5) has to be small. 
##EQU2## 
The objective function calculated by OBJECTF in FIG. 11f is 
EQU constant.times.(1+weight.times.correlation).times.(wirelength-plateau) 
where correlation is defined in equation (5) and wirelength is the sum over 
all interspaces of the product of the number of interconnections crossing 
a line in this interspace and the length of the interspace. The 
interconnections that have pins in the environment of which the location 
is known, can be taken into account by entering them at the appropriate 
extremes of the sequences. Constant, weight, and plateau are positive 
constants by which the relative influence on the individual contributions 
can be controlled. The fourth element is a heating and annealing schedule 
that has to be set on the basis of experiments. In the functions of FIG. 
11 this schedule can be controlled by setting ACCRATE, NR1, NR2, and NR3. 
Better is to have the program setting them dynamically on the basis of the 
available data. 
If there are inset cells with quite oblong shapes, it is better to have the 
orientations fixed before entering the second stage of TOPOLOGY. For inset 
cells the distribution of the pins over the sides is known. In case 
SCHOENBERG was used to obtain the point configuration a suitable 
orientation can be determined in the following way. For each such a module 
side a characteristic vector v.sub.n can be derived, indicating by a 
component 1 whether it has a pin connected to the corresponding net, and 
by a component 0 the absence of such a pin. Also the dutch distance of v 
to all rows of P can be calculated. Now, when a point is added to the 
r-dimensional Schoenberg configuration having exactly those distances to 
the corresponding module points (at most one extra dimension is needed for 
this addition), the position of its projected point in the two-dimensional 
configuration will be 
##EQU3## 
where s.sub.ii is the i-th diagonal element of the Schoenberg matrix S, 
.lambda..sub.1 and .lambda..sub.2 the largest eigenvalues of S, and 
d.sub.i is the dutch distance of v to p.sub.i.. Thus, two simple 
calculations give the position at which the module side `would like to be` 
if it were separable from its module. The vector obtained by substracting 
the module point coordinates from the result of (6), can be interpreted as 
a force vector. Such a vector can be determined for each side. Thinking of 
the module as a rectangle with minimum area, fixed position of its center, 
and the four `forces` applied to the centers of the respective sides, an 
amount of potential energy is associated with each of the eight possible 
orientations. The one with minimum energy is selected. 
A slight modification in the elements of the simulated annealing method 
will give orientatons to the inset cells while generating the two 
dimensional point configuration. When other methods of obtaining the point 
configuration in the plane are chosen, force methods similar to the one in 
the SCHOENBERG case can be used on the basis of the point positions 
derived. 
The second stage of TOPOLOGY is to derive a slicing structure from the 
point configuration obtained as a result of the functions in the first 
stage, or from another source. This function, called SLICING, has to 
preserve the relative positions in the slices for the modules as given by 
the point positions. To obtain information about which modules should be 
kept together in slices and which should be in different slices after a 
certain level, a shrinking process can be used. Suppose a given slice L 
with s.gtoreq.2 modules is to be sliced in a number of child slices. 
Slicing must be tried in the direction perpendicular to the lines 
separating P from its sibling slices. FIGS. 12a-12c are a visualization of 
a process determining the shrink factor of every possible slicing line. 
Then that factor will be defined more precisely and more faithful to the 
computational process implemented in DETSHR of FIG. 13e. 
Think of a module as a rectangle around the point representing it and with 
its sides parallel to the x- and y-axis in accordance with the orientation 
determined in EMBED. The sizes of these rectangles are such that each pair 
of rectangles has overlap and the ratio of their areas is equal to the 
ratio of the area estimates given to the corresponding modules. The 
rectangles are simultaneously shrunk leaving their centers fixed and 
preserving the area ratios. At some point during this shrinking process 
there will be a line that divides the modules in two blocks without 
intersecting any of the rectangles. The amount of shrinking necessary to 
reach that point is the shrink factor to be assigned to the corresponding 
line. Shrinking is continued and another line perpendicular to the 
longitudinal axis and separating other blocks will be intersection free. 
Again, the corresponding factor will be assigned to that line. The process 
is continued until all s-1 factors are assigned. The lines with the 
highest shrink factors are candidates to be accepted as slicing lines. 
However, since a preliminary geometry for each of the new slices can be 
calculated simultaneous with the slicing process, other information can be 
derived before deciding which of the slicing lines are acceptable, such as 
area distribution over the new slices, aspect ratios of the new slices, 
and the deformation (if suitably defined) the modules between consecutive 
slicing lines certainly will incur. To illustrate this point an embodiment 
of the last possibility will be described after completion of the precise 
implementation of shrink factor calculation. Once the set of accepted 
slicing lines has been determined, the resulting blocks will form the 
child slices, each of which will be treated in the same way if it contains 
more than 1 module. 
In the small example of FIG. 12a the rectangles--in this case 
squares--around the module centers are drawn in their position before the 
shrinking process. The amounts of shrinking necessary to have the vertical 
dashed lines intersection free are given for each line. After accepting 
/.sub.3 the three modules at the left are shown in FIG. 12b, and treated 
in the same way. The consequences for the shorthand tree are given for 
each step. The final tree and configuration are in FIG. 12c. 
More precisely: 
The modules in L are ordered according to their longitudinal coordinate. 
Let .pi.(M) be the rank number of M.epsilon.L in that order. x.sub..pi.(M) 
be its longitudinal coordinate and .xi.(M) be the iso-oriented dimension. 
There are in general s-1 possible slicing lines (the only exception occurs 
when modules have the same coordinate; a slicing line separating those 
modules gets shrink factor 0). Slicing line /.sub.i will separate the 
modules in L.sub.i.sup.- ={.pi..sup.-1 (j).vertline.j.ltoreq.i} from those 
in L.sub.i.sup.+ ={.pi..sup.-1 (j).vertline.j&gt;i}. The shrink factor 
assigned to /.sub.i is 
##EQU4## 
The computation of F.sub.i is quite simple. The initial f, f.sup.O, must 
be large enough such that 
##EQU5## 
is an interval. At each iteration step h.sub.p and k.sub.p are determined 
by solving 
##EQU6## 
by iteration. 
The value of f.sup.p is set to 
##EQU7## 
The process is continued until f.sup.p =1. Then 
##EQU8## 
By accepting only the lines with the highest shrink factors the embodiment 
achieves that modules that have points at a relatively short distance will 
be separated in a relatively late stage of the process. This means that 
they will be together in many nested slices. Modules with points 
relatively far from each other will be separated after a few slicings. The 
relative positions of the modules in the final result will be quite 
accurately the same as the relative positions of the corresponding points 
in the point configuration. 
As an illustration of the fact that an assessment of the shape of the child 
slices for a proposed set of slicing lines can be used for deriving 
additional figures of merit for that set beside the shrink factors a 
deformation calculation for flexible cells will be described as 
implemented in FLEXDEF, given in FIG. 13j. 
The preferred shape for flexible modules is a square. It is, however, in 
general not possible to accommodate the modules of a set B as squares or 
other fixed shapes with area .alpha.(M) in a slice with area 
##EQU9## 
to say nothing of such a slice with given dimensions, l.sub.1 and l.sub.2. 
To assess the deviation from square form of the modules in B FLEXDEF uses 
the following definition: 
##EQU10## 
where A={M.epsilon.B .vertline..alpha.(M)&gt;(MIN{l.sub.1,l.sub.2 }).sup.2 }. 
When A=.phi. the deformation will be zero. This does not mean that all 
modules of B fit into an l.sub.1 .times.l.sub.2 slice as non-overlapping 
squares. It only is an indication that the modules are small in comparison 
with that slice, and a reasonable packing can be expected. 
To use this definition of deformation it must be possible to calculate the 
dimensions of the slices in a partial structure tree. With the areas for 
the leaves given, this is possible if, for example, the aspect ratio of 
the chip or the ancestor module is known. For the latter this will have 
been predicted by a previous call of floorplan. 
The calculation of the dimensions of all slices starts with deriving the 
outer dimensions from the total area and the aspect ratio. One of these 
dimensions, the shortest, is inherited by the child slices of the 
ancestor. The other dimensions of these child slices are obtained by 
dividing the sum of the areas of the modules in each of them by the 
inherited dimension. Proceeding in this way, each slice inheriting the 
dimension calculated for its parent slice, will yield the dimensions of 
all slices. 
Since the computation is performed in a top-down fashion, it can also be 
applied to partial structure trees. So, after the shrinking process the 
dimensions l.sub.1.sup.s and l.sub.2.sup.s of the slice accommodating the 
modules in L are known and so are the shrink factors of all possible 
slicing lines. Accepting the lines with the c-1 highest shrink factors 
would yield c child slices C.sub.1, C.sub.2, . . . , C.sub.c. So, for the 
embodiment described here, the deformation associated with this selection 
of lines will be 
##EQU11## 
when l.sub.1.sup.s is the dimension to be inherited. 
The procedure DEFPREV of FIG. 13f used the deformation to derive threshold 
for shrink factors of lines to be accepted. This threshold is here 0 which 
corresponds with a very cautious slicing process. Whether the resulting 
deformation equals 0, can be determined without performing the 
calculations of (11) and (12). However, when even for c=2 there is nonzero 
deformation, the deformation of such a binary slicing must be calculated 
in order to be used in the comparison with other binary slicings in the 
same and in the perpendicular direction. In that case the line with the 
highest ratio of the shrinking factor over the deformation plus a positive 
real number is accepted either in the current stage, or in the next 
depending on its slicing direction, in spite of the deformation caused. 
The greater the positive number, the more determinative the shrinking 
factor will be. When this number is big enough, the procedure will simply 
take the line with the highest shrink factor. Of course, there are many 
variations possible on how to use shrink factors, deformation, and other 
measures in order to decide which lines to accept. 
The program uses a special data structure for storing partial stucture 
trees. It is a one-dimensional array with 2m-1 integers. The modules are 
represented as positive integers. After completion of the slicing 
structure these positive integers will be separated from each other by m-1 
nonpositive integers representing the slicing lines. The values of these 
nonpositive integers indicate the level of slicing. 
Initially all m-1 positions for the slicing indicators are filled with 
zeros. The positive integers are ordered according to the components of x. 
The procedures such as described in the preceding paragraphs, determine 
the first set of slicing lines to be accepted. At the corresponding 
positions in the array the zeros are replaced by a -2 (0 and -1 are 
reserved for separating interconnection regions around the total 
configuration). 
In each of the subsequent steps the groups of (two or more) positive 
integers separated by negative integers are treated in a similar way. They 
are ordered according to the coordinates not used in the preceding step, 
and the positions corresponding to the accepted slicing lines are filled 
with an integer 1 lower than the indicator of the preceding step. 
In the particular embodiment described here TOPOLOGY ends with the 
translation of the shorthandtree into a triply linked structure. The 
algorithm LINK of FIG. 13k does that in a straightforward way. 
SLICING and the functions called by SLICING for generating a slicing 
structure for flexible modules, and LINK are given in FIG. 13. The point 
configuration and the area of the modules, all flexible, are the arguments 
of SLICING. It further accepts the outer dimensions and the first slicing 
direction to be tried in the form of global variables. 
Thus, when entering the second part of FLOORPLAN, all slices containing the 
functional modules are known and organized in a data structure where every 
slice has pointers to its parent slice, its primogenitive, and to its next 
sibling. A pointer nil indicates that the corresponding slice does not 
exist. This second part, called JUNCTOR, essentially gathers the 
information necessary for estimating the space required by the realization 
of the interrelations. 
For the embodiment at hand nets are assigned to junction cells in a net by 
net sequence. Junction cells are slices that separate the sibling slices. 
In the topology of the slicing structure they form leaves that occur 
between the child slices that are not junction cells. The function given 
in FIG. 14, ADJC, adds these cells to the linked structure formed by LINK. 
In order to understand the procedures of the described embodiment that 
follow, the datastructures holding the configuration data have to be 
known. This information is mainly stored in two structures, FLPL and NETL, 
which are to be explained with reference to FIGS. 15 and 16, respectively. 
FLPL is a two-dimensional array, with 18 columns and as many rows as the 
number of slices. Four extra rows may be added for the external junction 
cells surrounding the whole configuration. The first four columns (FIG. 
15b) contain the linked slicing structure. The fifth column has the type 
number of the respective slice. The sixth column indicates for modules 
their orientation, and for compound slices the level in which they are 
contained. In the rows of the junction cells this field contains a 
negative integer, of which the absolute value indicates the level in which 
the corresponding junction cell occurs. 
The modules of the input are surrounded by four junction cells. Each 
junction cell--except two of the cells framing the configuration--is 
between two other junction cells. This information is stored in the FLPL 
structure in columns 7 up to 10. The junction cell rows have in column 9 
and 10 pointers to the array INJC. These pointers indicate the first and 
the last of a set of consecutive columns in INJC that give the nets 
occurring in this junction cell together with their entry and exit points. 
These entry and exit points are given by the respective intersecting 
junction cells. If a net has several pieces in the junction cell it is 
mentioned as many times. 
Columns 11 and 12 give the preliminary dimensions of the respective slice. 
Columns 13 and 14 contain the coordinates of the lower left corner of the 
slice, calculated under certain assumptions, such as zero or non-zero 
channel width, full flexibility or constraints on the shape of the 
modules, and given or free aspect ratio. 
Columns 15 and 16 have pointers indicating where in BREAKPTS the 
breakpoints of the shape constraints of the slice are stored. Except for 
those of the modules they still have to be derived. Finally, columns 17 
and 18 have pointers to positions in the NETPOS array indicating the pin 
positions of each module, and later possibly those of the other slices. 
The first two column positions specify how these are distributed over the 
sides. 
The other major data structure contains net based information. The first 
four columns (FIG. 16b) contain net information that is input to the 
procedures of FLOORPLAN. The fifth column contains the size, the length or 
some other measure which relates to the usefulness of a realization. The 
sixth column has the number of the smallest slice containing all the 
modules having a pin to be connected to that net. 
Columns 7 and 8 have pointers referring to positions in the NTOMOD array. 
If the whole net has no pins outside the configuration, i.e. the net is 
local with respect to the configuration under construction, these pointers 
mark the range in which the modules connected by this net are given. If 
the net is global with respect to this configuration, and information 
concerning its entry point is available, that information is given in the 
first poistions of the range, while the other positions are used to list 
the modules connected by this net. 
The last two columns of NETL point to the list of junction cells in which 
the net occurs. 
The interrelations between the procedures of JUNCTOR are in the flow 
diagram of FIG. 17. INCIDE, FIG. 18, fills the columns 7 up to 10 FLPL 
(FIG. 15b) for the rows associated with the modules and the compound 
slices, and the columns 7 and 8 for the junction cells. It also fills a 
matrix which has rows representing one set of iso-oriented junction cells, 
and columns to represent the other set of iso-oriented junction cells. The 
non-zeros in the matrix represent intersections of corresponding junction 
cells. An example of such a matrix is shown in FIG. 19a. Here the rows and 
columns are ordered according to the coordinates of the junction cells in 
the configuration of FIG. 19c, calculated for the shorthand tree of FIG. 
19b under the assumption of zero latitudinal dimension for the junction 
cells. 
Two functions used by the functions of FIG. 18, and elsewhere are K and 
UNK, given in FIG. 20. 
The actual task of JUNCTOR is to assign nets to sets of junction cells. In 
this embodiment a method of doing this is described, where the expected 
total net length is as small as possible. The problem can be formulated as 
a Steiner tree problem on a graph, a problem well known in literature. The 
graph has as nodes the intersections of the junction cell. The edges 
represent the pair of intersections that can be reached over a junction 
cell without passing another intersection. The length of each edge is the 
distance (again under zero width assumption for the junction cells) 
between the two associated intersections. 
In the traditional formulation of the Steiner problem the task is to find a 
minimum length subtree of the graph that contains all the nodes of a given 
subset. The nodes in this subset are called targets. There is, however, 
one difference with the traditional formulation of the Steiner problem. 
Instead of a set of targets there is set of target sets, and a minimum 
length tree is required that connects each given target set to at least 
one node. A target set consists, for example, of all nodes representing an 
intersection of junction cells at the periphery of a module that has to 
have a pin on the actual net. Or, if the side of the module on which the 
pin is to occur, is known, the junction cell intersections on that side 
induce a target set for the net at hand. In case the net is global, i.e. 
having connections outside the configuration, the node of the junction 
cell intersection closest to its entry point forms a target set. If the 
entry point is not known all or some of the junction cell intersections 
may be used for forming a target set. 
An efficient solution to the general Steiner tree problem is not known. 
Therefore, there has been much interest in approximation algorithms with 
performance guarantees. For example, generating the minimum spanning tree 
has a fast algorithm, yielding a tree less than fifty percent longer than 
the Steiner tree. A slightly slower algorithm allowing for so called 
Steiner points, guarantees a tree length less than 2.times.(1-1/k) the 
optimum. However, the slicing restraint offers several speed-ups for an 
algorithm searching for the optimum tree. For example, only the smallest 
slice containing all modules to be connected by the actual net has to be 
considered. Therefore, this slice is searched for by the function ANCSLICE 
(FIG. 23a) and is stored at the proper entry in NETL (column 6). An upper 
bound for the length of the optimum tree can be found in relatively short 
time by constructing a small spanning tree. The length of that tree is 
certainly not shorter than the Steiner tree. That length and the 
corresponding tree are returned by the procedure GREEDY of FIG. 23b. 
STEINER, as outlined in FIG. 23c, is a recursive program that returns the 
optimum tree for a given set of target sets and for a given set of 
consecutive sibling slices. If there are only two target sets the problem 
is reduced to finding the shortest path between one node from the first 
and one node from the second set. Therefore, the lengths of the shortest 
paths between each pair of nodes and their first intermediate nodes are 
determined by the function of FIG. 22, SHORTEST, before calling GREEDY and 
STEINER for each net. If the given set of consecutive siblings contains 
only one slice then STEINER is called for the same set of target sets and 
the smallest set of consecutive child slices that contains all targets in 
the target sets. If the set of consecutive siblings has more than one 
slice, then the junction cell intersections of the junction cell between 
the first sibling and the second sibling in that set are determined. For 
each such intersection STEINER is called twice. First for the first 
sibling and the target sets contained in that slice extended with a 
one-element target set consisting of that intersection. If this 
one-element set is contained in one of the target sets in that slice the 
latter target set is removed. Then STEINER is called for the group of 
other siblings and the set of target sets in that group are also extended 
by the one-element target set of the actual intersection, and its eventual 
supersets are removed. The sequence of recursive STEINER-calls is stopped 
as soon as it is clear that it cannot lead to an optimum tree. 
After JUNCTOR it is known which nets occur in which junction cells, and a 
fairly accurate estimate of the latitudinal dimension of the junction 
cells can be made. To realize this dimension for its junction cells, the 
estimate is translated into a shape constraint like the one in FIG. 4d. 
Since the shape constraints of the modules are supposed to be contained in 
the input data, all slices represented by leaves in the structure tree 
have shape constraints. 
If all shape-constraints are convex, linear programming and related 
techniques can be used to find a near-optimum geometrical configuration. 
For each compound slice a set of linear equations can be written (FIG. 
24): 
##EQU12## 
Each vertex gives rise to as many equations as its degree in the tree. The 
inner vertices, representing the compound slices, lead to the linear 
equations of (13). The constraints for the junction cells are incorporated 
in these equations. For each leaf, representing a module, a piece-wise 
linear approximation of its shape constraint, enters the set. Together 
these equations and inequalities are the constraints the final geometrical 
structure has to satisfy. To find a solution that is optimal in some 
sense, for example the smallest total area, a suitable objective function 
to be optimized under these constraints, has to be defined. The dimensions 
resulting from the simple area distribution procedure with zero channel 
widths, described before, can be used as a starting point. It is the 
solution of the system with one extra constraint, e.g. the aspect ratio, 
where the compound equations have a zero right hand side. The left hand 
side is unchanged. 
Mostly shape constraints will be convex in practice, when all inset cells 
have a fixed orientation. If the orientation still has to be chosen with 
regard to a contour score to be optimized, non-convex shape constraints 
will arise. The method to be described in the next paragraph can handle 
both cases, convex and non-convex shape constraints. 
So, all leaves in the tree representing the topology of the slicing 
structure have a shape constraint at this stage of the process. Addition 
of the shape constraints of the child slices in the region in which they 
are all defined, yields the inverse of the shape constraint of the parent 
slice. In this way GEOMETRY will construct shape constraints for all 
slices including the common ancestor of all slices. Knowing all feasible 
dimension pairs for this enveloping rectangle, it selects the one that is 
optimal with respect to the contour score. Because each slice inherits its 
longitudinal dimension from its parent the other can be determined by 
evaluating its bounding function for the inherited value. The functions of 
FIG. 26 handle the most common case, where the orientation of the inset 
cells, and other rotation-sensitive cells have been fixed, either by 
specification in the input, or by using the procedures described in the 
TOPOLOGY part. 
DGEOM must have all breakpoint information of the shape constraints of the 
leaves in packed form. Thus, 
EQU ((,0) KFLPL[;1 15 16 ]) K BREAKPTS. 
With CGEOM one out of four objective functions can be selected. 
Thus, while the invention has been described with reference to a preferred 
embodiment thereof, it will be understood by those skilled in the art that 
various changes in form and details may be made without departing from the 
scope of the invention.