US5535134A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Object placement aid
Assignee: International Business Machines Corp
•
Filing: 1994-06-03
•
Granted: 1996-07-09
•
Expires: 2014-06-03
Abstract
Abstract An existing layout is modified to ensure compliance with design rules and any user-defined rules by deriving a horizontal constraint model and a vertical constraint model. For each of the vertical and horizontal orientations in turn, violations of the rules are identified. For each orientation in turn, the violations are removed in such a way that objects in the layout are moved the least amount necessary. A given object may also be inserted into an existing layout in such a way that perturbation of objects in the existing layout is minimized by exploring solutions allowing for object merger and non-merger solutions and choosing the best one based on predetermined criteria. Given a group of objects, a layout may also be created in such a way that successive objects are placed to minimize movement of objects already placed. Placement of an object in an existing layout may also be improved by removing the object and inserting it as if it were a new object a number of times until no further improvement is noted in its placement.
Inventors
- 👤 John M. Cohn
- 👤 Fook-Luen Heng
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 23:43
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/34; G06F30/347; G06F30/10; G06F30/18; G06F30/39; G06F2111/00; G06F2111/04
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
179 words
A method for modifying a layout of a plurality of objects to be in compliance with a plurality of predetermined rules, said method comprising: identifying within said layout at least one violation of said plurality of predetermined rules, wherein each of said plurality of objects is bounded by a plurality of edges; identifying a first group of edges as all transitive edges beyond said at least one violation closest to a predetermined reference in a direction away from said predetermined reference; identifying a second group of edges as all transitive edges beyond said at least one violation furthest away from said predetermined reference in a direction toward said predetermined reference; and modifying said layout to remove said at least one violation such that perturbation, resulting from said modifying, of said plurality of objects is minimized, wherein said perturbation is a function of the sum of the distances of the edges in said first group of edges from the predetermined reference and the sum of the distances of the edges in said second group of edges from said predetermined reference.
Claim 2
Independent Claim
179 words
A method for modifying a layout of a plurality of objects to be in compliance with a plurality of predetermined rules, said method comprising: identifying within said layout at least one violation of said plurality of predetermined rules, wherein each of said plurality of objects is bounded by a plurality of edges; identifying a first group of edges as all transitive edges beyond said at least one violation closest to a predetermined reference in a direction away from said predetermined reference; identifying a second group of edges as all transitive edges beyond said at least one violation furthest away from said predetermined reference in a direction toward said predetermined reference; and modifying said layout to remove said at least one violation such that perturbation, resulting from said modifying, of said plurality of objects is minimized, wherein said perturbation is a function of the sum of the distances of the edges in said first group of edges from the predetermined reference and the sum of the distances of the edges in said second group of edges from said predetermined reference.
Claim 3
Dependent Claim
25 words
The method of claim 1 wherein said plurality of predetermined rules comprises a minimum spacing between at least two objects in said plurality of objects.
Claim 4
Dependent Claim
23 words
The method of claim 1 wherein said plurality of predetermined rules comprises criteria for merging at least two of said plurality of objects.
Claim 5
Dependent Claim
23 words
The method of claim 1 wherein said plurality of predetermined rules comprises criteria for overlapping at least two of said plurality of objects.
Claim 6
Dependent Claim
15 words
The method of claim 1 wherein said plurality of predetermined rules comprises an object size.
Claim 7
Dependent Claim
34 words
The method of claim 1 wherein said step of modifying is performed first from one of a horizontal orientation and vertical orientation and second from the other of said horizontal orientation and vertical orientation.
Claim 8
Dependent Claim
17 words
The method of claim 1 wherein said plurality of objects comprises a plurality of integrated circuit devices.
Claim 9
Dependent Claim
53 words
The method of claim 1 further comprising deriving a constraint model for said layout prior to said first step of identifying, wherein said first step of identifying comprises identifying within said constraint model said at least one violation and wherein said step of modifying comprises modifying said layout subject to said constraint model.
Claim 10
Dependent Claim
82 words
The method of claim 8, wherein each of said plurality of objects is bounded in a first orientation by a first edge and a second edge opposite said first edge and bounded in a second orientation perpendicular to said first orientation by a third edge and a fourth edge opposite said third edge and wherein said step of deriving comprises determining for each said orientation a position for each edge of each of said plurality of objects relative to a predetermined reference.
Claim 11
Dependent Claim
130 words
The method of claim 9, wherein said step of modifying for each said orientation comprises minimizing perturbation P in the following equation, subject to said plurality of predetermined rules and said constraint model: P=Σ x.sub.(i)new -Σ x.sub.(j)new, wherein Σ x.sub.(i)new ≧Σ x.sub.(i)old and Σ x.sub.(j)new <=Σ x.sub.(j)old, wherein x.sub.(i) comprises a position for a given edge in said first group of edges relative to said predetermined reference, wherein x.sub.(j) comprises a position for a given edge in said second group of edges relative to said predetermined reference, wherein "new" denotes a position for said given edge relative to said predetermined reference as a result of said step of minimizing and wherein "old" denotes a position for said given edge relative to said predetermined reference prior to said step of minimizing.
Claim 12
Independent Claim
190 words
A method for automatically modifying a layout of a plurality of objects to ensure compliance with a plurality of predetermined rules, said method comprising: modifying said layout without regard to said plurality of predetermined rules; automatically identifying within said layout any violations of said plurality of predetermined rules, wherein each of said plurality of objects is bounded by a plurality of edges; automatically identifying a first group of edges as all transitive edges beyond said at least one violation closest to a predetermined reference in a direction away from said predetermined reference; automatically identifying a second group of edges as all transitive edges beyond said at least one violation furthest away from said predetermined reference in a direction toward said predetermined reference; and automatically modifying said layout to remove said any violations such that perturbation, resulting from said modifying, of said plurality of objects is minimized, wherein said perturbation is a function of the sum of the distances of the edges in said first group of edges from the predetermined reference and the sum of the distances of the edges in said second group of edges from said predetermined reference.
Claim 13
Independent Claim
190 words
A method for automatically modifying a layout of a plurality of objects to ensure compliance with a plurality of predetermined rules, said method comprising: modifying said layout without regard to said plurality of predetermined rules; automatically identifying within said layout any violations of said plurality of predetermined rules, wherein each of said plurality of objects is bounded by a plurality of edges; automatically identifying a first group of edges as all transitive edges beyond said at least one violation closest to a predetermined reference in a direction away from said predetermined reference; automatically identifying a second group of edges as all transitive edges beyond said at least one violation furthest away from said predetermined reference in a direction toward said predetermined reference; and automatically modifying said layout to remove said any violations such that perturbation, resulting from said modifying, of said plurality of objects is minimized, wherein said perturbation is a function of the sum of the distances of the edges in said first group of edges from the predetermined reference and the sum of the distances of the edges in said second group of edges from said predetermined reference.
Claim 14
Dependent Claim
57 words
The method of claim 11 further comprising automatically deriving a constraint model for said layout prior to said first step of automatically identifying, wherein said first step of automatically identifying comprises automatically identifying within said constraint model said any violations and wherein said step of automatically modifying comprises automatically modifying said layout subject to said constraint model.
Claim 15
Independent Claim
187 words
A system for modifying a layout of a plurality of objects to be in compliance with a plurality of predetermined rules, said system comprising: means for identifying within said layout at least one violation of said plurality of predetermined rules, wherein each of said plurality of objects is bounded by a plurality of edges; means for identifying a first group of edges as all transitive edges beyond said at least one violation closest to a predetermined reference in a direction away from said predetermined reference; means for identifying a second group of edges as all transitive edges beyond said at least one violation furthest away from said predetermined reference in a direction toward said predetermined reference; and means for modifying said layout to remove said at least one violation such that perturbation, resulting from said modifying, of said plurality of objects is minimized, wherein said perturbation is a function of the sum of the distances of the edges in said first group of edges from the predetermined reference and the sum of the distances of the edges in said second group of edges from said predetermined reference.
Claim 16
Independent Claim
187 words
A system for modifying a layout of a plurality of objects to be in compliance with a plurality of predetermined rules, said system comprising: means for identifying within said layout at least one violation of said plurality of predetermined rules, wherein each of said plurality of objects is bounded by a plurality of edges; means for identifying a first group of edges as all transitive edges beyond said at least one violation closest to a predetermined reference in a direction away from said predetermined reference; means for identifying a second group of edges as all transitive edges beyond said at least one violation furthest away from said predetermined reference in a direction toward said predetermined reference; and means for modifying said layout to remove said at least one violation such that perturbation, resulting from said modifying, of said plurality of objects is minimized, wherein said perturbation is a function of the sum of the distances of the edges in said first group of edges from the predetermined reference and the sum of the distances of the edges in said second group of edges from said predetermined reference.
Claim 17
Dependent Claim
16 words
The system of claim 13 further comprising means for deriving a constraint model for said layout.
Claim 18
Dependent Claim
123 words
The system of claim 14, wherein said modifying means comprises means for minimizing perturbation P in the following equation, subject to said plurality of predetermined rules and said constraint model: P=Σ x.sub.(i)new -Σ x.sub.(j)new, wherein Σ x.sub.(i)new ≧Σ x.sub.(i)old and Σ x.sub.(j)new <=Σ x.sub.(j)old, wherein x.sub.(i) comprises a position for a given edge in said first group of edges relative to said predetermined reference, wherein x.sub.(j) comprises a position for a given edge in said second group of edges relative to said predetermined reference, wherein "new" denotes a position for said given edge relative to said predetermined reference as a result of said minimizing and wherein "old" denotes a position for said given edge relative to said predetermined reference prior to said minimizing.
Claim 19
Independent Claim
198 words
A system for automatically modifying a layout of a plurality of objects to ensure compliance with a plurality of predetermined rules, said system comprising: means for modifying said layout without regard to said plurality of predetermined rules, wherein each of said plurality of objects is bounded by a plurality of edges; means for automatically identifying within said layout any violations of said plurality of predetermined rules; means for identifying a first group of edges as all transitive edges beyond said at least one violation closest to a predetermined reference in a direction away from said predetermined reference; means for identifying a second group of edges as all transitive edges beyond said at least one violation furthest away from said predetermined reference in a direction toward said predetermined reference; and means for automatically modifying said layout to remove said any violations such that perturbation, resulting from said modifying, of said plurality of objects is minimized, wherein said perturbation is a function of the sum of the distances of the edges in said first group of edges from the predetermined reference and the sum of the distances of the edges in said second group of edges from said predetermined reference.
Claim 20
Independent Claim
198 words
A system for automatically modifying a layout of a plurality of objects to ensure compliance with a plurality of predetermined rules, said system comprising: means for modifying said layout without regard to said plurality of predetermined rules, wherein each of said plurality of objects is bounded by a plurality of edges; means for automatically identifying within said layout any violations of said plurality of predetermined rules; means for identifying a first group of edges as all transitive edges beyond said at least one violation closest to a predetermined reference in a direction away from said predetermined reference; means for identifying a second group of edges as all transitive edges beyond said at least one violation furthest away from said predetermined reference in a direction toward said predetermined reference; and means for automatically modifying said layout to remove said any violations such that perturbation, resulting from said modifying, of said plurality of objects is minimized, wherein said perturbation is a function of the sum of the distances of the edges in said first group of edges from the predetermined reference and the sum of the distances of the edges in said second group of edges from said predetermined reference.
References Cited (Backward Citations)
US3654615A
Cited
US3617714A
Cited
US4551810A
Cited
US4551810B1
Cited
US4639604A
Cited
US4554625A
Cited
US4577276A
Cited
US4630219A
Cited
US4686629A
Cited
US4805113A
Cited
US4754408A
Cited
US5175696A
Cited
US4908772A
Cited
US4812962A
Cited
US4918614A
Cited
US4815003A
Cited
US4922432A
Cited
US5267176A
Cited
US5164907A
Cited
US5144563A
Cited
US5200908A
Cited
US5191542A
Cited
US5231590A
Cited
US5140402A
Cited
US5222031A
Cited
US5218551A
Cited
US5420800A
Cited
US5303161A
Cited
US5430831A
Cited
US5225991A
Cited
US5359538A
Cited
US5475608A
Cited
US5224056A
Cited
US5363313A
Cited
US5311443A
Cited
US5281558A
Cited
US5308798A
Cited
US5416722A
Cited
US5465218A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-09 | 2000-01-08 | 2000-07-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-09 | 2004-01-08 | 2004-07-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-09 | 2008-01-08 | 2008-07-09 | $7700.00 | Window Closed / Lapsed |