US5495419A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Integrated circuit physical design automation system utilizing optimization process decomposition and parallel processing
Assignee: LSI Corp
•
Filing: 1994-04-19
•
Granted: 1996-02-27
•
Expires: 2014-04-19
Abstract
Abstract In a physical design automation system for producing an optimized cell placement for an integrated circuit chip, a placement optimization methodology is decomposed into a plurality of cell placement optimization processes that are performed simultaneously by parallel processors on input data representing the chip. The results of the optimization processes are recomposed to produce an optimized cell placement. The fitness of the optimized cell placement is analyzed, and the parallel processors are controlled to selectively repeat performing the optimization processes for further optimizing the optimized cell placement if the fitness does not satisfy a predetermined criterion. The system can be applied to initial placement, routing, placement improvement and other problems. The processors can perform the same optimization process on different placements, or on areas of a single placement. Alternatively, the processors can perform different optimization processes simultaneously on a single initial placement, with the resulting processed placement having the highest fitness being selected as the optimized placement. The processors can further selectively reprocess areas of a placement having high cell interconnect congestion or other low fitness parameters.
Inventors
- 👤 Michael D. Rostoker
- 👤 James S. Koford
- 👤 Edwin R. Jones
- 👤 Douglas B. Boyle
- 👤 Ranko Scepanovic
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 05:09
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
136 words
A physical design automation system for producing an optimized cell placement for an integrated circuit chip, comprising: a decomposer for decomposing a placement optimization methodology into a plurality of cell placement optimization processes; a plurality of parallel processors for performing said optimization processes simultaneously on input data representing said chip; a recomposer for recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto; and a controller for analyzing a fitness of said optimized cell placement and controlling the parallel processors to selectively repeat performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion; in which the controller identifies low fitness areas of said optimized placement and selectively assigns the processors to repeat performing said optimization processes on said low fitness areas respectively.
Claim 2
Dependent Claim
136 words
A physical design automation system for producing an optimized cell placement for an integrated circuit chip, comprising: a decomposer for decomposing a placement optimization methodology into a plurality of cell placement optimization processes; a plurality of parallel processors for performing said optimization processes simultaneously on input data representing said chip; a recomposer for recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto; and a controller for analyzing a fitness of said optimized cell placement and controlling the parallel processors to selectively repeat performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion; in which the controller identifies low fitness areas of said optimized placement and selectively assigns the processors to repeat performing said optimization processes on said low fitness areas respectively.
Claim 3
Dependent Claim
14 words
A system as in claim 1, in which the controller controls the processors individually.
Claim 4
Dependent Claim
14 words
A system as in claim 1, in which said optimization processes comprise genetic alteration.
Claim 5
Dependent Claim
14 words
A system as in claim 1, in which said optimization processes comprise simulated annealing.
Claim 6
Dependent Claim
45 words
A system as in claim 1, in which the controller defines a plurality of movable windows that delineate subsets of cells in said low fitness areas respectively, and assigns the processors to repeat performing said optimization processes on said subsets delineated by said windows respectively.
Claim 7
Dependent Claim
90 words
A system as in claim 1, in which: the controller identifies cells in said low fitness areas having high interconnect congestion and assigns said cells to the parallel processors respectively; and the parallel processors compute centroids as a first predetermined function of locations of cells to which said cells are connected; compute first distances from current locations of said cells to said centroids; compute second distances as second predetermined functions of said first distances; and move said cells from said current locations toward said centroids by said second distances respectively.
Claim 8
Dependent Claim
56 words
A system as in claim 1, in which: the process decomposer generates a plurality of initial placements; the parallel processors perform said cell optimization processes on said initial placements to produce a plurality of processed cell placements respectively; and the process recomposer designates a processed cell placement having a highest fitness as said optimized cell placement.
Claim 9
Dependent Claim
37 words
A system as in claim 1, in which the process decomposer generates an initial placement, divides said initial placement into a plurality of areas and assigns the processors to perform said optimization processes on said areas respectively.
Claim 10
Dependent Claim
38 words
A system as in claim 1, in which the process decomposer generates an initial placement, divides said initial placement into a plurality of contiguous areas and assigns the processors to perform said optimization processes on said areas respectively.
Claim 11
Dependent Claim
32 words
A system as in claim 1, in which the process decomposer generates a plurality of different initial placements and assigns the processors to perform said optimization processes on said initial placements respectively.
Claim 12
Dependent Claim
63 words
A system as in claim 1, in which the parallel processors comprise: a plurality of worker processors for independently performing said optimization processes and producing results; and a host processor for distributively assigning said optimization processes to the worker processors in response to work requests received therefrom; each worker processor sending a work request to the host processor after completing an optimization process.
Claim 13
Dependent Claim
167 words
A physical design automation system for producing an optimized cell placement for an integrated circuit chip, comprising: a decomposer for decomposing a placement optimization methodology into a plurality of cell placement optimization processes; a plurality of parallel processors for performing said optimization processes simultaneously on input data representing said chip; a recomposer for recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto; and a controller for analyzing a fitness of said optimized cell placement and controlling the parallel processors to selectively repeat performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion, in which: the process decomposer generates a plurality of initial placements; the parallel processors perform said cell optimization processes on said initial placements to produce a plurality of processed cell placements respectively; the process recomposer designates a processed cell placement having a highest fitness as said optimized cell placement; and said optimization processes comprise genetic crossover between said initial placements.
Claim 14
Dependent Claim
167 words
A physical design automation system for producing an optimized cell placement for an integrated circuit chip, comprising: a decomposer for decomposing a placement optimization methodology into a plurality of cell placement optimization processes; a plurality of parallel processors for performing said optimization processes simultaneously on input data representing said chip; a recomposer for recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto; and a controller for analyzing a fitness of said optimized cell placement and controlling the parallel processors to selectively repeat performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion, in which: the process decomposer generates a plurality of initial placements; the parallel processors perform said cell optimization processes on said initial placements to produce a plurality of processed cell placements respectively; the process recomposer designates a processed cell placement having a highest fitness as said optimized cell placement; and said optimization processes comprise genetic crossover between said initial placements.
Claim 15
Dependent Claim
160 words
A physical design automation system for producing an optimized cell placement for an integrated circuit chip, comprising: a decomposer for decomposing a placement optimization methodology into a plurality of cell placement optimization processes; a plurality of parallel processors for performing said optimization processes simultaneously on input data representing said chip; a recomposer for recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto; and a controller for analyzing a fitness of said optimized cell placement and controlling the parallel processors to selectively repeat performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion, in which: said optimization processes comprise different algorithms respectively; the processor generates an initial placement; the parallel processors perform said cell optimization processes on said initial placement to produce a plurality of processed cell placements respectively; and the process recomposer designates a processed cell placement having highest fitness as said optimized cell placement.
Claim 16
Dependent Claim
160 words
A physical design automation system for producing an optimized cell placement for an integrated circuit chip, comprising: a decomposer for decomposing a placement optimization methodology into a plurality of cell placement optimization processes; a plurality of parallel processors for performing said optimization processes simultaneously on input data representing said chip; a recomposer for recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto; and a controller for analyzing a fitness of said optimized cell placement and controlling the parallel processors to selectively repeat performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion, in which: said optimization processes comprise different algorithms respectively; the processor generates an initial placement; the parallel processors perform said cell optimization processes on said initial placement to produce a plurality of processed cell placements respectively; and the process recomposer designates a processed cell placement having highest fitness as said optimized cell placement.
Claim 17
Dependent Claim
143 words
A physical design automation system for producing an optimized cell placement for an integrated circuit chip, comprising: a decomposer for decomposing a placement optimization methodology into a plurality of cell placement optimization processes; a plurality of parallel processors for performing said optimization processes simultaneously on input data representing said chip; a recomposer for recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto; and a controller for analyzing a fitness of said optimized cell placement and controlling the parallel processors to selectively repeat performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion; in which the process decomposer generates an initial placement, divides cells of said initial placement into a plurality of nets of interconnected cells and assigns the processors to perform said optimization processes on said nets respectively.
Claim 18
Dependent Claim
143 words
A physical design automation system for producing an optimized cell placement for an integrated circuit chip, comprising: a decomposer for decomposing a placement optimization methodology into a plurality of cell placement optimization processes; a plurality of parallel processors for performing said optimization processes simultaneously on input data representing said chip; a recomposer for recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto; and a controller for analyzing a fitness of said optimized cell placement and controlling the parallel processors to selectively repeat performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion; in which the process decomposer generates an initial placement, divides cells of said initial placement into a plurality of nets of interconnected cells and assigns the processors to perform said optimization processes on said nets respectively.
Claim 19
Dependent Claim
15 words
A system as in claim 14, in which said optimization processes comprise cell interconnect routing.
Claim 20
Dependent Claim
149 words
A physical design automation system for producing an optimized cell placement for an integrated circuit chip, comprising: a decomposer for decomposing a placement optimization methodology into a plurality of cell placement optimization processes; a plurality of parallel processors for performing said optimization processes simultaneously on input data representing said chip; a recomposer for recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto; and a controller for analyzing a fitness of said optimized cell placement and controlling the parallel processors to selectively repeat performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion; in which the process decomposer generates an initial placement, divides cells of said initial placement into a plurality of groups of cells in accordance with a predetermined hierarchial organization and assigns the processors to perform said optimization processes on said groups respectively.
Claim 21
Dependent Claim
149 words
A physical design automation system for producing an optimized cell placement for an integrated circuit chip, comprising: a decomposer for decomposing a placement optimization methodology into a plurality of cell placement optimization processes; a plurality of parallel processors for performing said optimization processes simultaneously on input data representing said chip; a recomposer for recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto; and a controller for analyzing a fitness of said optimized cell placement and controlling the parallel processors to selectively repeat performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion; in which the process decomposer generates an initial placement, divides cells of said initial placement into a plurality of groups of cells in accordance with a predetermined hierarchial organization and assigns the processors to perform said optimization processes on said groups respectively.
Claim 22
Dependent Claim
15 words
A system as in claim 16, in which said optimization processes comprise cell interconnect routing.
References Cited (Backward Citations)
US4306286A
Cited
US4484292A
Cited
US4495559A
Cited
US4656580A
Cited
US4612618A
Cited
US4621339A
Cited
US4615011A
Cited
US4850027A
Cited
US5157778A
Cited
US5222029A
Cited
US4908772A
Cited
US4872125A
Cited
US5051895A
Cited
US5255345A
Cited
US5159682A
Cited
US5267176A
Cited
US5140526A
Cited
US5144563A
Cited
US5140530A
Cited
US5200908A
Cited
US5251147A
Cited
US5249259A
Cited
US5222031A
Cited
US5136686A
Cited
US5208759A
Cited
US5202840A
Cited
US5245550A
Cited
US5224056A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-02-26 | 1999-08-28 | 2000-02-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-02-26 | 2003-08-28 | 2004-02-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-02-26 | 2007-08-28 | 2008-02-27 | $7700.00 | Window Closed / Lapsed |