US4554625A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for generating an optimized nested arrangement of constrained rectangles
Assignee: International Business Machines Corp
•
Filing: 1983-06-14
•
Granted: 1985-11-19
•
Expires: 2003-06-14
Abstract
Abstract 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.
Inventors
- 👤 Ralph H. J. M. Otten
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 19:10
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392; B; B23; B23D; B23D15/00; B23D15/06; G06T; G06T17/00; Y; Y10; Y10S; Y10S706/00; Y10S706/902; Y10S706/903; Y10S706/908
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
101 words
A method for allocating rectangular areas for given elements on a rectangular surface of a product such as an integrated circuit, each element being limited by a shape constraint and related to the other elements by proximity information, comprising the steps of: deriving a distance space to position a center of each said element on said product surface in a configuration of points in a plane; constructing a slicing structure from said point configuration of said element centers; determining from the result of the above steps the dimensions, position, and orientation of said elements; and dividing up said product surface accordingly.
Claim 2
Independent Claim
101 words
A method for allocating rectangular areas for given elements on a rectangular surface of a product such as an integrated circuit, each element being limited by a shape constraint and related to the other elements by proximity information, comprising the steps of: deriving a distance space to position a center of each said element on said product surface in a configuration of points in a plane; constructing a slicing structure from said point configuration of said element centers; determining from the result of the above steps the dimensions, position, and orientation of said elements; and dividing up said product surface accordingly.
Claim 3
Dependent Claim
14 words
A method according to claim 1, wherein said proximity information comprises: an interconnection count.
Claim 4
Dependent Claim
14 words
A method according to claim 1, wherein said proximity information comprises: a distance matrix.
Claim 5
Dependent Claim
14 words
A method according to claim 1, wherein said proximity information comprises: a weights matrix.
Claim 6
Dependent Claim
15 words
A method according to claim 1, wherein said proximity information comprises: a wiring net list.
Claim 7
Dependent Claim
19 words
A method according to claim 5, wherein individual weights are assigned to the nets in said wiring net list.
Claim 8
Dependent Claim
19 words
A method according to claim 1, wherein said proximity information comprises: an incidence structure over said elements and interrelations.
Claim 9
Dependent Claim
18 words
A method according to claim 7, wherein individual weights are assigned to the interrelations of said incidence structure.
Claim 10
Dependent Claim
25 words
A method according to claim 1, wherein said proximity information leads to a configuration of points in the plane, where the points represent said elements.
Claim 11
Dependent Claim
17 words
A method according to claim 1, wherein said proximity information is a point configuration in the plane.
Claim 12
Dependent Claim
45 words
A method according to claim 1, wherein said construction of the slicing structure from the configuration of element centers is based on shrink factors for lines dividing a set of rectangles into disjunct subsets of rectangles without changing their relative position in the perpendicular direction.
Claim 13
Dependent Claim
42 words
A method according to claim 1, wherein said construction of the slicing structure from the configuration of element centers is based on the deformation the elements will incur if a set of lines is accepted as the next set of slicing lines.
Claim 14
Dependent Claim
43 words
A method according to claim 1, wherein said construction of the slicing structure from the configuration of element centers is based on the distribution of area over the ensuing slices after accepting a set of lines as the next set of slicing lines.
Claim 15
Dependent Claim
38 words
A method according to claim 1, wherein said construction of the slicing structure is based on determining the geometry of the partial slicing structure with all elements considered to be flexible and all interspaces assumed to be zero.
Claim 16
Dependent Claim
45 words
A method according to claim 1, wherein said construction of the slicing structure is based on a combination of at least two of the following indicators: shrink factors, deformation, area distribution, and geometrical top-down calculations under the assumption of only flexible elements and no interspaces.
Claim 17
Dependent Claim
26 words
A method according to claim 1, comprising the further step of: determining the distances required between elements for the realization of the interrelations among the elements.
Claim 18
Dependent Claim
29 words
A method according to claim 24 wherein said distances needed for realizing the interrelations among the elements are assumed to be located between consecutive sibling slices, in junction cells.
Claim 19
Dependent Claim
27 words
A method according to claim 17, wherein said determining of the distances needed for realizing the interrelations consists of assessing the latitudinal dimensions of the junction cells.
Claim 20
Dependent Claim
34 words
A method according to claim 18, wherein said assessing of the latitudinal dimensions of the junction cells is based on the assignment of nets to the junction cell segments between consecutive junction cell intersections.
Claim 21
Dependent Claim
44 words
A method according to claim 19, wherein said assignment of the nets to the junction cell segments between consecutive junction cell intersections is based on solving the Steiner problem on the junction cell intersection structure, using the slicing properties for reducing the computational complexity.
Claim 22
Dependent Claim
39 words
A method according to claim 1, wherein said shape constraints are convex piece-wise linear bounding functions, and said determining of dimensions, and position of said elements is performed using linear programming with a linear objective function of slice dimensions.
Claim 23
Dependent Claim
55 words
A method according to claim 1, wherein said shape constraints are monotonously non-increasing piece-wise linear bounding functions, and said calculation of dimensions, position, and orientation is performed by minimizing at least one of area, perimeter, and any other quasi-concave objective function of the dimensions of the enveloping rectangle, which is monotone in both its arguments.
Claim 24
Dependent Claim
15 words
A method according to claim 1, wherein said surface is a mask for circuit integration.
Claim 25
Dependent Claim
44 words
A method according to claim 1, comprising the further steps of: selecting a pin distribution over the sides of at least a portion of said elements; and determining said orientation of said elements using said pin distribution and said configuration of said element centers.
References Cited (Backward Citations)
US3490320A
Cited
US3490147A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1988-11-18 | 1989-05-20 | 1989-11-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1992-11-18 | 1993-05-20 | 1993-11-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1996-11-18 | 1997-05-20 | 1997-11-19 | $7700.00 | Window Closed / Lapsed |