US5963455A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Advanced modular cell placement system with functional sieve optimization technique
Assignee: Bell Semiconductor LLC
•
Filing: 1996-06-28
•
Granted: 1999-10-05
•
Expires: 2016-06-28
Abstract
Abstract A system for optimizing placement of a cell on a surface of a semiconductor chip is disclosed herein. The cells may belong to nets and may belong to neighborhoods. The system initially calculates affinities based on repositioning the cell. The system then combines affinities and repositions cells based on these combined affinities. The system then computes a cost function and repeats the combining, repositioning, and computing functions a predetermined number of times.
Inventors
- 👤 Ranko Scepanovic
- 👤 James S. Koford
- 👤 Alexander E. Andreev
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:48
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
127 words
A method for optimizing placement of elements on a surface, wherein said elements are associated in groups, comprising the steps of: (a) combining a plurality of affinities for relocating said elements to alternate locations on said surface; (b) repositioning elements based on the combined affinities; (c) computing a cost function; (d) repeating said combining, repositioning, and computing steps a predetermined number of times; (e) calculating an average cost function based upon all cost functions from said iterated computing steps; (f) subsequently repeating said combining, repositioning, computing, repeating, and calculating steps until two consecutive average cost functions satisfy a given accuracy, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement.
Claim 2
Independent Claim
127 words
A method for optimizing placement of elements on a surface, wherein said elements are associated in groups, comprising the steps of: (a) combining a plurality of affinities for relocating said elements to alternate locations on said surface; (b) repositioning elements based on the combined affinities; (c) computing a cost function; (d) repeating said combining, repositioning, and computing steps a predetermined number of times; (e) calculating an average cost function based upon all cost functions from said iterated computing steps; (f) subsequently repeating said combining, repositioning, computing, repeating, and calculating steps until two consecutive average cost functions satisfy a given accuracy, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement.
Claim 3
Dependent Claim
29 words
The method of claim 1, wherein said combining step combines affinities for elements clustered together, affinities based on region capacity, and affinities based on groups crossing divisions between regions.
Claim 4
Dependent Claim
37 words
The method of claim 1, wherein said combining step comprises computing a total affinity based on affinities for elements clustered together and region capacities, and calculating affinity based on groups crossing divisions between regions and region capacities.
Claim 5
Dependent Claim
53 words
The method of claim 2, wherein said combining step comprises computing a total affinity by first combining affinities for elements clustered together, affinities based on region capacity, and affinities based on groups crossing divisions between regions, and subsequently combining affinities based on region capacity and affinities based on groups crossing divisions between regions.
Claim 6
Dependent Claim
30 words
The method of claim 4, where in the first affinity combination comprises weighing the affinity for elements clustered together greater than the affinities based on groups crossing divisions between regions.
Claim 7
Dependent Claim
30 words
The method of claim 4, wherein the first affinity combination comprises weighing the affinity for elements clustered together approximately equal to the affinities based on groups crossing divisions between regions.
Claim 8
Dependent Claim
31 words
The method of claim 4, wherein the first affinity combination comprises weighing the affinity for elements clustered together with a relatively small value and said predetermined number of times equals one.
Claim 9
Independent Claim
96 words
A system for optimizing placement of cells on a surface of a semiconductor chip, wherein said cells are associated in nets and belong to neighborhoods, said system comprising: (a) calculating a plurality of affinities based on repositioning said cells; (b) combining said affinities; (c) repositioning cells based on combined affinities; (d) computing a cost function; and (e) repeating said combining, repositioning, and computing steps a predetermined number of times, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement.
Claim 10
Independent Claim
96 words
A system for optimizing placement of cells on a surface of a semiconductor chip, wherein said cells are associated in nets and belong to neighborhoods, said system comprising: (a) calculating a plurality of affinities based on repositioning said cells; (b) combining said affinities; (c) repositioning cells based on combined affinities; (d) computing a cost function; and (e) repeating said combining, repositioning, and computing steps a predetermined number of times, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement.
Claim 11
Dependent Claim
29 words
The system of claim 8, further comprising the step of calculating an average cost function based upon all cost functions from said iterated computing steps in (d) and (e).
Claim 12
Dependent Claim
30 words
The system of claim 9, further comprising the step of subsequently repeating said combining, repositioning, computing, repeating, and calculating steps until two consecutive average cost functions satisfy a given accuracy.
Claim 13
Dependent Claim
36 words
The system of claim 8, wherein said plurality of affinities comprises at least two of: (a) affinities for cell neighborhoods; (b) affinities based on region capacities; and (c) affinities based on nets crossing divisions between regions.
Claim 14
Dependent Claim
38 words
The system of claim 11, wherein said combining step comprises computing a first affinity based on affinities for cell neighborhoods and region capacities, and calculating a second affinity based on groups crossing divisions between regions and region capacities.
Claim 15
Dependent Claim
52 words
The system of claim 11, wherein said combining step comprises computing a total affinity by first combining affinities for cell neighborhoods, affinities based on region capacities, and affinities based on groups crossing divisions between regions, and subsequently combining affinities based on region capacity and affinities based on groups crossing divisions between regions.
Claim 16
Dependent Claim
28 words
The system of claim 13, wherein the first affinity combination comprises weighing the affinities for cell neighborhoods greater than the affinities based on groups crossing divisions between regions.
Claim 17
Dependent Claim
29 words
The method of claim 13, wherein the first affinity combination comprises weighing the affinities for cell neighborhoods approximately equal to the affinities based on groups crossing divisions between regions.
Claim 18
Dependent Claim
30 words
The method of claim 13, wherein the first affinity combination comprises weighing the affinities for cell neighborhoods with a relatively small value and said predetermined number of times equals one.
Claim 19
Independent Claim
84 words
A method for optimizing placement of elements on a surface, comprising the steps of: (a) calculating affinities for repositioning elements; (b) repositioning elements based on said affinities; (c) computing a cost associated with repositioning the elements; and (d) repeating said calculating, repositioning, and computing steps until the difference between costs for two subsequent iterations satisfies a predetermined accuracy, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost relates to quality of a placement.
Claim 20
Independent Claim
84 words
A method for optimizing placement of elements on a surface, comprising the steps of: (a) calculating affinities for repositioning elements; (b) repositioning elements based on said affinities; (c) computing a cost associated with repositioning the elements; and (d) repeating said calculating, repositioning, and computing steps until the difference between costs for two subsequent iterations satisfies a predetermined accuracy, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost relates to quality of a placement.
Claim 21
Independent Claim
96 words
A system for optimizing placement of an element on a surface, comprising: (a) computing an affinity associated with repositioning said element; (b) repositioning said element if said affinity satisfies a specified criterion; (c) repeating said computing and repositioning steps a predetermined number of times; (d) calculating a cost function; and (e) repeating steps (a), (b), (c) and (d) until cost functions satisfy a predetermined accuracy on two subsequent iterations, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement.
Claim 22
Independent Claim
96 words
A system for optimizing placement of an element on a surface, comprising: (a) computing an affinity associated with repositioning said element; (b) repositioning said element if said affinity satisfies a specified criterion; (c) repeating said computing and repositioning steps a predetermined number of times; (d) calculating a cost function; and (e) repeating steps (a), (b), (c) and (d) until cost functions satisfy a predetermined accuracy on two subsequent iterations, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement.
Claim 23
Dependent Claim
98 words
A computer storage device having stored thereon a computer program comprising the following steps: (a) computing an affinity associated with repositioning said element; (b) repositioning said element if said affinity satisfies a specified criterion; (c) repeating said computing and repositioning steps a predetermined number of times; (d) calculating a cost function; and (e) repeating steps (a), (b), (c) and (d) until cost functions satisfy a predetermined accuracy on two subsequent iterations, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement.
Claim 24
Dependent Claim
98 words
A computer storage device having stored thereon a computer program comprising the following steps: (a) computing an affinity associated with repositioning said element; (b) repositioning said element if said affinity satisfies a specified criterion; (c) repeating said computing and repositioning steps a predetermined number of times; (d) calculating a cost function; and (e) repeating steps (a), (b), (c) and (d) until cost functions satisfy a predetermined accuracy on two subsequent iterations, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement.
References Cited (Backward Citations)
US3617714A
Cited
US3603771A
Cited
US4306286A
Cited
US4342090A
Cited
US4484292A
Cited
US4495559A
Cited
US4656580A
Cited
US4612618A
Cited
US4621339A
Cited
US4554625A
Cited
US4593363A
Cited
US4577276A
Cited
US4630219A
Cited
US4615011A
Cited
US4686629A
Cited
US4697242A
Cited
US4688072A
Cited
US4675829A
Cited
US4850027A
Cited
US4754408A
Cited
US4763288A
Cited
US5157778A
Cited
US5222029A
Cited
US4829446A
Cited
US4910680A
Cited
US4965739A
Cited
US4908772A
Cited
US4918614A
Cited
US4815003A
Cited
US4872125A
Cited
US5119313A
Cited
US5051895A
Cited
US5255345A
Cited
US5062054A
Cited
US4961152A
Cited
US4831725A
Cited
US5239465A
Cited
US5159682A
Cited
US5267176A
Cited
US5140526A
Cited
US5404313A
Cited
US5224057A
Cited
US5144563A
Cited
US5140530A
Cited
US5404561A
Cited
US5200908A
Cited
US5251147A
Cited
US5191542A
Cited
US5051938A
Cited
US5309371A
Cited
US5231590A
Cited
US5187668A
Cited
US5140402A
Cited
US5249259A
Cited
US5222031A
Cited
US5124927A
Cited
US5136686A
Cited
US5267177A
Cited
US5218551A
Cited
US5303161A
Cited
US5208759A
Cited
US5202840A
Cited
US5245550A
Cited
US5225991A
Cited
US5341308A
Cited
US5349536A
Cited
US5224056A
Cited
US5392222A
Cited
US5398195A
Cited
US5363313A
Cited
US5521837A
Cited
US5465218A
Cited
US5568322A
Cited
US5491641A
Cited
US5615128A
Cited
US5495419A
Cited
US5742510A
Cited
US5557533A
Cited
US5636125A
Cited
US5682322A
Cited
US5745363A
Cited
US5587923A
Cited
US5638293A
Cited
US5568636A
Cited
US5578840A
Cited
US5661663A
Cited
US5659717A
Cited
US5699265A
Cited
US5712793A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-10-04 | 2003-04-05 | 2003-10-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-10-04 | 2007-04-05 | 2007-10-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-10-04 | 2011-04-05 | 2011-10-05 | $7700.00 | Window Closed / Lapsed |