Patent US5870313A successfully refreshed from Google Patents.
US5870313A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimization processing for integrated circuit physical design automation system using parallel moving windows
Assignee: LSI Corp
•
Filing: 1997-12-09
•
Granted: 1999-02-09
•
Expires: 2017-12-09
Abstract
Abstract One or more non-overlapping moving windows are positioned over a placement of cells for an integrated circuit chip to delineate respective subsets of cells. A fitness improvement operation such as simulated evolution is performed on the subsets simultaneously using parallel processors. The windows are either moved to specifically identified high interconnect congestion areas of the placement, or are moved across the placement in a raster type pattern such that each area of the placement is processed at least once. Exchange of misplaced cells between subsets can be accomplished by dimensioning the windows and designing the window movement pattern such that the subsets overlap. Alternatively, such exchange can be accomplished by using two sets of windows of different sizes. As yet another alternative, the improvement operation can allow misplaced cells to move to a border area outside a window. Each misplaced cell is placed on a list, and then moved to the centroid of a net of cells to which it is connected, which can be outside the subset that originally included the misplaced cell.
Inventors
- 👤 Douglas B. Boyle
- 👤 James S. Koford
- 👤 Ranko Scepanovic
- 👤 Edwin R. Jones
- 👤 Michael D. Rostoker
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:53
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 62
Claim 1
Independent Claim
70 words
A physical design automation system for improving a cell placement of a circuit layout design, comprising: a controller for defining a movable window that delineates subsets of cells of said circuit layout design; and a computer for performing a predetermined placement improvement operation on said subsets, wherein the controller moves said window to locations in said circuit layout design that are selected in accordance with a predetermined local fitness criterion.
Claim 2
Dependent Claim
70 words
A physical design automation system for improving a cell placement of a circuit layout design, comprising: a controller for defining a movable window that delineates subsets of cells of said circuit layout design; and a computer for performing a predetermined placement improvement operation on said subsets, wherein the controller moves said window to locations in said circuit layout design that are selected in accordance with a predetermined local fitness criterion.
Claim 3
Dependent Claim
20 words
A system as in claim 1, in which said local fitness criterion comprises cell interconnect congestion in said layout design.
Claim 4
Dependent Claim
38 words
A system as in claim 1, in which said local fitness criterion comprises identifying low fitness areas in said circuit layout design; and the controller selects said locations such that said window successively delineates said low fitness areas.
Claim 5
Dependent Claim
85 words
A physical design automation system for improving a cell placement of a circuit layout design, comprising: a controller for defining a movable window that delineates subsets of cells of said circuit layout design; and a computer for performing a predetermined placement improvement operation on said subset, wherein the controller successively moves said window to a plurality of predetermined locations in said circuit layout design, and wherein the computer successively applies said improvement operation to subsets that are delineated by said window in said locations respectively.
Claim 6
Dependent Claim
85 words
A physical design automation system for improving a cell placement of a circuit layout design, comprising: a controller for defining a movable window that delineates subsets of cells of said circuit layout design; and a computer for performing a predetermined placement improvement operation on said subset, wherein the controller successively moves said window to a plurality of predetermined locations in said circuit layout design, and wherein the computer successively applies said improvement operation to subsets that are delineated by said window in said locations respectively.
Claim 7
Dependent Claim
32 words
A system as in claim 4, in which said locations are selected such that each cell is delineated by said window and the computer performs said improvement operation thereon at least once.
Claim 8
Dependent Claim
23 words
A system as in claim 4, in which said window is dimensioned and said locations are selected such that adjacent subsets partially overlap.
Claim 9
Dependent Claim
58 words
A system as in claim 4, in which: the controller further successively moves a second window having a different size than said window to a plurality of predetermined second locations in said circuit layout design; the computer successively performs said improvement operation on said second subsets that are delineated by said second window in said second locations respectively.
Claim 10
Dependent Claim
25 words
A system as in claim 7, in which said locations and said second locations are selected such that said subsets partially overlap said second subsets.
Claim 11
Dependent Claim
42 words
A system as in claim 8, in which: said window is dimensioned and said locations are selected such that said subsets are contiguous; and said second window is dimensioned and said second locations are selected such that said second subsets are contiguous.
Claim 12
Dependent Claim
67 words
A system as in claim 4, in which: the controller further defines a second window that is integrally movable with and circumscribes said window such that a border area is defined between peripheries of said window and said second window; and the computer performs said improvement operation such that misplaced cells of said circuit layout design are allowed to move from said window into said border area.
Claim 13
Dependent Claim
18 words
A system as in claim 10, further comprising a memory for storing a list of said misplaced cells.
Claim 14
Dependent Claim
27 words
A system as in claim 10, in which the computer further computes and moves said misplaced cells to new locations respectively in accordance with a predetermined function.
Claim 15
Dependent Claim
32 words
A system as in claim 12, in which said predetermined function comprises computing each new location as a centroid of a net of cells to which a respective misplaced cell is connected.
Claim 16
Dependent Claim
36 words
A system as in claim 10, in which the computer further computes new locations for said misplaced cells in accordance with a predetermined function and attempts to move said misplaced cells to said new locations respectively.
Claim 17
Dependent Claim
32 words
A system as in claim 14, in which said predetermined function comprises computing each new location as a centroid of a net of cells to which a respective misplaced cell is connected.
Claim 18
Dependent Claim
34 words
A system as in claim 14, in which the computer further excludes a misplaced cell from a subsequent improvement operation if an attempt to move said misplaced cell to a new location is unsuccessful.
Claim 19
Dependent Claim
40 words
A system as in claim 16, in which the computer determines that an attempt to move a misplaced cell to a new location is unsuccessful if said new location is already occupied by another cell of said circuit layout design.
Claim 20
Dependent Claim
56 words
A system as in claim 16, in which: said predetermined function comprises computing a new location as a centroid of a net of cells to which a respective misplaced cell is connected; and the computer computes said centroid as comprising any of said misplaced cells that are included in said net in said new locations thereof.
Claim 21
Dependent Claim
95 words
A physical design automation system for improving a cell placement of a circuit layout design, comprising: a controller for defining a movable window that delineates subsets of cells of said circuit layout design; and a computer for performing a predetermined placement improvement operation on said subsets, wherein the controller further defines a movable second window that does not overlay said window and delineates second subsets of cells of said circuit layout design, and wherein the computer comprises first and second processors for simultaneously performing said improvement operation on said subsets and said second subsets respectively.
Claim 22
Dependent Claim
95 words
A physical design automation system for improving a cell placement of a circuit layout design, comprising: a controller for defining a movable window that delineates subsets of cells of said circuit layout design; and a computer for performing a predetermined placement improvement operation on said subsets, wherein the controller further defines a movable second window that does not overlay said window and delineates second subsets of cells of said circuit layout design, and wherein the computer comprises first and second processors for simultaneously performing said improvement operation on said subsets and said second subsets respectively.
Claim 23
Dependent Claim
18 words
A system as in claim 19, in which the controller moves said window and said second window integrally.
Claim 24
Independent Claim
99 words
A method of performing a predetermined operation on a permutation of a predetermined number of entities of a circuit layout design, comprising the steps of: (a) defining a window that variably delineates subsets of entities of said circuit layout design; and (b) performing said predetermined operation on said subsets, wherein said entities are arranged in said circuit layout design in a predetermined pattern, step (a) comprises moving said window to a plurality of predetermined locations in said pattern, and step (b) comprises successively performing said operation on said subsets that are delineated by said window in said locations respectively.
Claim 25
Independent Claim
99 words
A method of performing a predetermined operation on a permutation of a predetermined number of entities of a circuit layout design, comprising the steps of: (a) defining a window that variably delineates subsets of entities of said circuit layout design; and (b) performing said predetermined operation on said subsets, wherein said entities are arranged in said circuit layout design in a predetermined pattern, step (a) comprises moving said window to a plurality of predetermined locations in said pattern, and step (b) comprises successively performing said operation on said subsets that are delineated by said window in said locations respectively.
Claim 26
Dependent Claim
37 words
A method as in claim 21, in which step (a) comprises selecting said locations such that each entity of said circuit layout design is delineated by said window and said operation is performed thereon at least once.
Claim 27
Dependent Claim
24 words
A method as in claim 21, in which step (a) comprises dimensioning said window and selecting said locations such that adjacent subsets partially overlap.
Claim 28
Dependent Claim
56 words
A method as in claim 21, further comprising the steps of: (c) successively moving a second window having a different size than said window to a plurality of predetermined second locations in said pattern; and (d) successively performing said operation on said second subsets that are delineated by said second window in said second location respectively.
Claim 29
Dependent Claim
38 words
A method as in claim 24, in which: steps (a) and (c) comprise dimensioning said window and said second window and selecting said locations and said second locations such that said subsets and said second subsets partially overlay.
Claim 30
Dependent Claim
44 words
A method as in claim 25, in which: step (a) comprises dimensioning said window and selecting said locations such that said subsets are contiguous; and step (c) comprises dimensioning said second window and selecting said second locations such that said second subsets are contiguous.
Claim 31
Independent Claim
110 words
A method of performing a predetermined operation on a permutation of a predetermined number of entities of a circuit layout design, comprising the steps of: (a) defining a window that variably delineates subsets of entities of said circuit layout design; and (b) performing said predetermined operation on said subsets, wherein step (a) further comprises defining a second window that is integrally movable with and circumscribes said window such that a border area is defined between peripheries of said window and said second window, and step (b) comprises performing said operation such that misplaced entities of said circuit layout design are allowed to move from said window into said border area.
Claim 32
Independent Claim
110 words
A method of performing a predetermined operation on a permutation of a predetermined number of entities of a circuit layout design, comprising the steps of: (a) defining a window that variably delineates subsets of entities of said circuit layout design; and (b) performing said predetermined operation on said subsets, wherein step (a) further comprises defining a second window that is integrally movable with and circumscribes said window such that a border area is defined between peripheries of said window and said second window, and step (b) comprises performing said operation such that misplaced entities of said circuit layout design are allowed to move from said window into said border area.
Claim 33
Dependent Claim
87 words
A physical design automation method of improving a cell placement for an integrated circuit layout design, comprising the steps of: (a) defining a movable window that delineates subsets of cells of said circuit layout design; and (b) individually performing a predetermined placement improvement operation on said subsets, wherein step (a) comprises moving said window to a plurality of predetermined locations in said circuit layout design, and step (b) comprises successively performing said improvement operation on said subsets that are delineates by said window in said locations respectively.
Claim 34
Dependent Claim
87 words
A physical design automation method of improving a cell placement for an integrated circuit layout design, comprising the steps of: (a) defining a movable window that delineates subsets of cells of said circuit layout design; and (b) individually performing a predetermined placement improvement operation on said subsets, wherein step (a) comprises moving said window to a plurality of predetermined locations in said circuit layout design, and step (b) comprises successively performing said improvement operation on said subsets that are delineates by said window in said locations respectively.
Claim 35
Dependent Claim
33 words
A method as in claim 28, in which step (a) comprises selecting said locations such that each entity is delineated by said window and said improvement operation is performed thereon at least once.
Claim 36
Dependent Claim
24 words
A method as in claim 28, in which step (a) comprises dimensioning said window and selecting said locations such that adjacent subsets partially overlap.
Claim 37
Dependent Claim
58 words
A method as in claim 28, further comprising the steps of: (c) successively moving a second window having a different size than said window to a plurality of predetermined second locations in said circuit layout design; and (d) successively performing said improvement operation on second subsets that are delineated by said second window in said second locations respectively.
Claim 38
Dependent Claim
38 words
A method as in claim 31, in which: steps (a) and (c) comprise dimensioning said window and said second window and selecting said locations and said second locations such that said subsets and said second subsets partially overlap.
Claim 39
Dependent Claim
44 words
A method as in claim 32, in which: step (a) comprises dimensioning said window and selecting said locations such that said subsets are contiguous; and step (c) comprises dimensioning said second window and selecting said second locations such that said second subsets are contiguous.
Claim 40
Dependent Claim
69 words
A method as in claim 28, in which: step (a) further comprises defining a second window that is integrally movable with and circumscribes said window such that a border area is defined between peripheries of said window and said second window; and step (b) comprises performing said improvement operation such that misplaced cells of said circuit layout design are allowed to move from said window into said border area.
Claim 41
Dependent Claim
28 words
A method as in claim 34, further comprising the step of: (c) computing and moving said misplaced cells to new locations respectively in accordance with a predetermined function.
Claim 42
Dependent Claim
31 words
A method as in claim 35, in which step (c) comprises computing each new location as a centroid of a net of cells to which a respective misplaced cell is connected.
Claim 43
Dependent Claim
38 words
A method as in claim 34, further comprising the step of: (c) computing new locations for said misplaced cells in accordance with a predetermined function; and (d) attempting to move said misplaced cells to said new locations respectively.
Claim 44
Dependent Claim
31 words
A method as in claim 37, in which step (c) comprises computing each new location as a centroid of a net of cells to which a respective misplaced cell is connected.
Claim 45
Dependent Claim
39 words
A method as in claim 37, further comprising the step of: (e) controlling step (b) to exclude a misplaced cell from a subsequent improvement operation if an attempt to move said misplaced cell to a new location is unsuccessful.
Claim 46
Dependent Claim
41 words
A method as in claim 39, in which step (e) comprises determining that an attempt to move a misplaced cell to a new location is unsuccessful if said new location is already occupied by another cell of said circuit layout design.
Claim 47
Dependent Claim
48 words
A method as in claim 39, in which step (c) comprises computing a new location as a centroid of a net of cells to which a respective misplaced cell is connected, comprising any of said misplaced cells that are included in said net in said new locations thereof.
Claim 48
Dependent Claim
84 words
A physical design automation method of improving a cell placement for an integrated circuit layout design, comprising the steps of: (a) defining a movable window that delineates subsets of cells of said circuit layout design; (b) individually performing a predetermined placement improvement operation on said subsets; (c) movably defining a second window that does not overlap said window and delineates second subsets of cells of said circuit layout design; and (d) independently performing said improvement operation on said subsets and said second subsets respectively.
Claim 49
Dependent Claim
84 words
A physical design automation method of improving a cell placement for an integrated circuit layout design, comprising the steps of: (a) defining a movable window that delineates subsets of cells of said circuit layout design; (b) individually performing a predetermined placement improvement operation on said subsets; (c) movably defining a second window that does not overlap said window and delineates second subsets of cells of said circuit layout design; and (d) independently performing said improvement operation on said subsets and said second subsets respectively.
Claim 50
Dependent Claim
21 words
A method as in claim 42, in which steps (a) and (c) comprise moving said window and said second window integrally.
Claim 51
Dependent Claim
89 words
A physical design automation system for improving a cell placement of a circuit layout design, comprising: a controller for defining a boundary that limits a cell placement improvement operation to operating on cells within said boundary, and for moving said boundary in a rectilinear raster type scan pattern to a plurality of regions of said circuit layout design to delineate cells within each of said plurality of regions; and a computer for performing said placement improvement operation on delineated cells of each respective region of said plurality of regions.
Claim 52
Dependent Claim
89 words
A physical design automation system for improving a cell placement of a circuit layout design, comprising: a controller for defining a boundary that limits a cell placement improvement operation to operating on cells within said boundary, and for moving said boundary in a rectilinear raster type scan pattern to a plurality of regions of said circuit layout design to delineate cells within each of said plurality of regions; and a computer for performing said placement improvement operation on delineated cells of each respective region of said plurality of regions.
Claim 53
Dependent Claim
89 words
A physical design automation system for improving a cell placement of a circuit layout design, comprising: a controller for defining a boundary that limits a cell placement improvement operation to operating on cells within said boundary, and for moving said boundary to a plurality of partially overlapping predetermined regions of said circuit layout design to delineate cells within each of said plurality of partially overlapping predetermined regions; and a computer for performing said placement improvement operation on said delineated cells of each region of said partially overlapping predetermined regions.
Claim 54
Dependent Claim
89 words
A physical design automation system for improving a cell placement of a circuit layout design, comprising: a controller for defining a boundary that limits a cell placement improvement operation to operating on cells within said boundary, and for moving said boundary to a plurality of partially overlapping predetermined regions of said circuit layout design to delineate cells within each of said plurality of partially overlapping predetermined regions; and a computer for performing said placement improvement operation on said delineated cells of each region of said partially overlapping predetermined regions.
Claim 55
Dependent Claim
84 words
A physical design automation system for improving a cell placement of a circuit layout design, comprising: a controller for defining a boundary that limits a cell placement improvement operation to operating on cells within said boundary, and for moving said boundary to a plurality of cell congested regions of said circuit layout design to delineate cells within each of said plurality of cell congested regions; and a computer for performing a predetermined placement improvement operation on said delineated cells of respective cell congested regions.
Claim 56
Dependent Claim
84 words
A physical design automation system for improving a cell placement of a circuit layout design, comprising: a controller for defining a boundary that limits a cell placement improvement operation to operating on cells within said boundary, and for moving said boundary to a plurality of cell congested regions of said circuit layout design to delineate cells within each of said plurality of cell congested regions; and a computer for performing a predetermined placement improvement operation on said delineated cells of respective cell congested regions.
Claim 57
Independent Claim
90 words
A method of improving a cell placement of a circuit layout design, comprising the steps of: defining a boundary that limits a cell placement improvement operation to operating on cells of said circuit layout design that are situated within said boundary; moving said boundary in a rectilinear raster type scan pattern to a plurality of regions of said circuit layout design to delineate cells within each of said plurality of regions; and performing said placement improvement operation on said delineated cells of each respective region of said plurality of regions.
Claim 58
Independent Claim
90 words
A method of improving a cell placement of a circuit layout design, comprising the steps of: defining a boundary that limits a cell placement improvement operation to operating on cells of said circuit layout design that are situated within said boundary; moving said boundary in a rectilinear raster type scan pattern to a plurality of regions of said circuit layout design to delineate cells within each of said plurality of regions; and performing said placement improvement operation on said delineated cells of each respective region of said plurality of regions.
Claim 59
Independent Claim
88 words
A method of improving a cell placement of a circuit layout design, comprising the steps of: defining a boundary that limits a cell placement improvement operation to operating on cells of said circuit layout design that are situated within said boundary; moving said boundary to a plurality of partially overlapping predetermined regions of said circuit layout design to delineate cells within each of said plurality of partially overlapping predetermined regions; and performing said placement improvement operation on said delineated cells of each of said partially overlapping predetermined regions.
Claim 60
Independent Claim
88 words
A method of improving a cell placement of a circuit layout design, comprising the steps of: defining a boundary that limits a cell placement improvement operation to operating on cells of said circuit layout design that are situated within said boundary; moving said boundary to a plurality of partially overlapping predetermined regions of said circuit layout design to delineate cells within each of said plurality of partially overlapping predetermined regions; and performing said placement improvement operation on said delineated cells of each of said partially overlapping predetermined regions.
Claim 61
Independent Claim
86 words
A method of improving a cell placement of a circuit layout design, comprising the steps of: defining a boundary that limits a cell placement improvement operation to operating on cells of said circuit layout design that are situated within said boundary; moving said boundary to a plurality of cell congested regions of said circuit layout design to delineate cells within each of said plurality of cell congested regions; and performing said cell placement improvement operation on said delineated cells of each of said cell congested regions.
Claim 62
Independent Claim
86 words
A method of improving a cell placement of a circuit layout design, comprising the steps of: defining a boundary that limits a cell placement improvement operation to operating on cells of said circuit layout design that are situated within said boundary; moving said boundary to a plurality of cell congested regions of said circuit layout design to delineate cells within each of said plurality of cell congested regions; and performing said cell placement improvement operation on said delineated cells of each of said cell congested regions.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-08 | 2002-08-10 | 2003-02-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-08 | 2006-08-10 | 2007-02-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-08 | 2010-08-10 | 2011-02-09 | $7700.00 | Window Closed / Lapsed |