US5745363A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimization processing for integrated circuit physical design automation system using optimally switched cost function computations
Assignee: LSI Corp
•
Filing: 1996-02-13
•
Granted: 1998-04-28
•
Expires: 2016-02-13
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-30 10:34
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
107 words
A physical design automation system for producing a highest fitness cell placement for an integrated circuit chip, comprising: a fitness computer for computing a fitness value for a population of cell placements; a placement alterator for altering said cell placements using a predetermined fitness improvement algorithm in accordance with said fitness values respectively; and a controller for controlling the fitness computer to initially compute said fitness values using a predetermined second fitness function after reaching a computation optimization criterion which is predetermined to maximize convergence of said cell placements toward an optimal configuration and to reduce probability of convergence of said cell placements toward a local optima.
Claim 2
Dependent Claim
107 words
A physical design automation system for producing a highest fitness cell placement for an integrated circuit chip, comprising: a fitness computer for computing a fitness value for a population of cell placements; a placement alterator for altering said cell placements using a predetermined fitness improvement algorithm in accordance with said fitness values respectively; and a controller for controlling the fitness computer to initially compute said fitness values using a predetermined second fitness function after reaching a computation optimization criterion which is predetermined to maximize convergence of said cell placements toward an optimal configuration and to reduce probability of convergence of said cell placements toward a local optima.
Claim 3
Dependent Claim
28 words
A system as in claim 1, in which the fitness computer computes said first fitness function as a predetermined function of cell interconnect congestion in said cell placements.
Claim 4
Dependent Claim
28 words
A system as in claim 2, in which the fitness computer computes said second fitness function as a predetermined function of cell interconnect length in said cell placements.
Claim 5
Dependent Claim
70 words
A system as in claim 1, in which the fitness computer computes said first and second fitness functions F1 and F2 respectively as comprising: F1=A 1 f1(p)+B 1 f2(p) and F2=A 2 f1(p)+B 2 f2(p) where f1(p) is a first predetermined function of said placement, f2(p) is a second predetermined function of said placement and A 1 , A 2 , B 1 , and B 2 are predetermined constants.
Claim 6
Dependent Claim
21 words
A system as in claim 4, in which f1(p) is a predetermined function of cell interconnect congestion in said cell placement.
Claim 7
Dependent Claim
21 words
A system as in claim 4, in which f2(p) is a predetermined function of cell interconnect length in said cell placement.
Claim 8
Dependent Claim
37 words
A system as in claim 1, in which the controller controls the fitness computer and the placement alterator to repeatedly compute said fitness values and alter said cell placements respectively until a predetermined termination criterion is reached.
Claim 9
Dependent Claim
35 words
A system as in claim 7, in which the controller selects a cell placement from said population that has a highest fitness value as said highest fitness cell placement after said termination criterion is reached.
Claim 10
Dependent Claim
60 words
A system as in claim 7, in which the controller controls the fitness computer to initially compute said fitness values using said first fitness function, and to compute said fitness values using said second fitness function after the fitness computer and the placement alterator have computed said fitness values and altered said cell placements respectively a predetermined number of times.
Claim 11
Dependent Claim
52 words
A system as in claim 7, in which the controller controls the fitness computer to initially compute said fitness values using said first fitness function, and to compute said fitness values using said second fitness function after a fitness value of a placement having a highest fitness has reached a predetermined value.
Claim 12
Dependent Claim
76 words
A system as in claim 7, in which the controller controls the fitness computer to initially compute said fitness values using said first fitness function, and to compute said fitness values using said second fitness function after the fitness computer and the placement alterator have computed said fitness values and altered said cell placements respectively a predetermined number of times without producing a change in a fitness value of a placement having a highest fitness value.
Claim 13
Dependent Claim
75 words
A system as in claim 7, in which the controller controls the fitness computer to initially compute said fitness values using said first fitness function, and to compute said fitness values using said second fitness function after the fitness computer and the placement alterator have computed said fitness values and altered said cell placements respectively and a fitness value of a placement having a highest fitness value has changed by less than a predetermined value.
Claim 14
Independent Claim
91 words
A method of increasing a fitness of a cell placement for an integrated circuit chip, comprising the steps of: (a) computing a fitness value for said cell placement; (b) altering said cell placement using a predetermined fitness improvement algorithm in accordance with said fitness value; and (c) controlling step (a) such that said fitness value is computed based on a predetermined computation optimization criterion which reduces risk of convergence of said cell placement at a local optima and which uses a predetermined first fitness function or a predetermined second fitness function.
Claim 15
Independent Claim
91 words
A method of increasing a fitness of a cell placement for an integrated circuit chip, comprising the steps of: (a) computing a fitness value for said cell placement; (b) altering said cell placement using a predetermined fitness improvement algorithm in accordance with said fitness value; and (c) controlling step (a) such that said fitness value is computed based on a predetermined computation optimization criterion which reduces risk of convergence of said cell placement at a local optima and which uses a predetermined first fitness function or a predetermined second fitness function.
Claim 16
Dependent Claim
32 words
A method as in claim 13, in which step (c) comprises controlling step (a) such that said first fitness function is a predetermined function of cell interconnect congestion in said cell placement.
Claim 17
Dependent Claim
32 words
A method as in claim 14, in which step (c) comprises controlling step (a) such that said second fitness function is a predetermined function of cell interconnect length in said cell placement.
Claim 18
Dependent Claim
69 words
A method as in claim 13, in which said first and second fitness functions are designated as F1 and F2 respectively and comprise: F1=A 1 f1(p)+B f 2(p) and F2=A 2 f1(p)+B 2 f2(p) where f1(p) is a first predetermined function of said placement, f2(p) is a second predetermined function of said placement and A 1 , A 2 , B 1 , and B 2 are predetermined constants.
Claim 19
Dependent Claim
21 words
A method as in claim 16, in which f1(p) is a predetermined function of cell interconnect congestion in said cell placement.
Claim 20
Dependent Claim
21 words
A method as in claim 17, in which f2(p) is a predetermined function of cell interconnect length in said cell placement.
Claim 21
Dependent Claim
24 words
A method as in claim 13, further comprising the step of: (d) repeating steps (a) and (b) until a predetermined termination criterion is reached.
Claim 22
Dependent Claim
57 words
A method as in claim 19, in which said computation optimization criterion in step (c) comprises initially controlling step (a) to compute said fitness value using said first fitness function, and controlling step (a) to compute said fitness value using said second fitness function after steps (a) and (b) have been repeated a predetermined number of times.
Claim 23
Dependent Claim
52 words
A method as in claim 19, in which said computation optimization criterion in step (c) comprises initially controlling step (a) to compute said fitness value using said first fitness function, and controlling step (a) to compute said fitness value using said second fitness function after said fitness value reaches a predetermined value.
Claim 24
Dependent Claim
65 words
A method as in claim 19, in which said computation optimization criterion in step (c) comprises initially controlling step (a) to compute said fitness value using said first fitness function, and controlling step (a) to compute said fitness value using said second fitness function after steps (a) and (b) have been repeated a predetermined number of times without producing a change in said fitness value.
Claim 25
Dependent Claim
67 words
A method as in claim 19, in which said computation optimization criterion in step (c) comprises initially controlling step (a) to compute said fitness value using said first fitness function, and controlling step (a) to compute said fitness value using said second fitness function after a repetition of steps (a) and (b) has produced a change in said fitness value that is smaller than a predetermined value.
References Cited (Backward Citations)
US4484292A
Cited
US4580228A
Cited
US4688072A
Cited
US4754408A
Cited
US4918614A
Cited
US4815003A
Cited
US5187668A
Cited
US5225991A
Cited
US5506788A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-04-27 | 2001-10-27 | 2002-04-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-04-27 | 2005-10-27 | 2006-04-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-04-27 | 2009-10-27 | 2010-04-28 | $7700.00 | Window Closed / Lapsed |