US5349536A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for optimally placing components of a VLSI circuit
Assignee: Philips Semiconductors Inc
•
Filing: 1991-08-20
•
Granted: 1994-09-20
•
Expires: 2011-08-20
Abstract
Abstract In a method for placement of components for a VLSI circuit, an initial number of current placements are selected. A greedy optimization is partially performed on each of the current placements. Then, a subset of the current placements which have been partially optimized is selected to be the new current placements. This selection is based on a global cost metric for the current placements. The global cost metric is, for example, based on the total length of all connection line networks for the circuit. The partial optimization and selection are repeated until there is only one current placement. Then, an optimization is performed on the remaining placement to obtain an optimized placement. The optimization is, for example, a completion of the partially performed greedy optimization.
Inventors
- 👤 Sunil V. Ashtaputre
- 👤 Dale M. Wong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 19:26
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
172 words
A method comprising the steps of: (a) selecting an initial number of current placements of components for a VLSI circuit, including, for each of the initial current placements, selecting locations within the VLSI circuit for placement of each of the components; (b) for each of the current placements, changing locations of the components to improve the current placement so that the current placement is partially optimized in accordance with partial performance of a greedy optimization; (c) selecting a subset of the current placements partially optimized in step (b) to be new current placements, the selection being based on a global cost metric for the current placements; (d) when there are more than one new current placements, repeating steps (a) through (d) with the new current placements being the current placements; (e) when there is only one new current placement, performing an optimization on the new current placement to obtain an optimized placement; and, (f) manufacturing the VLSI circuit with the components of the VLSI circuit arranged in accordance with the optimized placement.
Claim 2
Independent Claim
172 words
A method comprising the steps of: (a) selecting an initial number of current placements of components for a VLSI circuit, including, for each of the initial current placements, selecting locations within the VLSI circuit for placement of each of the components; (b) for each of the current placements, changing locations of the components to improve the current placement so that the current placement is partially optimized in accordance with partial performance of a greedy optimization; (c) selecting a subset of the current placements partially optimized in step (b) to be new current placements, the selection being based on a global cost metric for the current placements; (d) when there are more than one new current placements, repeating steps (a) through (d) with the new current placements being the current placements; (e) when there is only one new current placement, performing an optimization on the new current placement to obtain an optimized placement; and, (f) manufacturing the VLSI circuit with the components of the VLSI circuit arranged in accordance with the optimized placement.
Claim 3
Dependent Claim
73 words
A method as in claim 1 wherein in step (b) the partial performance of the greedy optimization performed is a single pass through a greedy optimization algorithm in which for each pass, the following substeps are performed for each component: determining, based on a local cost metric, a best location for the component; and, moving the component to the best location when doing so improves a current value for the global cost metric.
Claim 4
Dependent Claim
42 words
A method as in claim 2 wherein in step (a) the initial number is approximately equal to a total number of components in the circuit and in step (c) approximately half the current placements are selected to be the new current placements.
Claim 5
Dependent Claim
53 words
A method as in claim 2 wherein in step (a) the initial number is significantly less than a total number of components in the circuit and in step (c) a percentage of the current placements are selected to be the new current placements, the percentage increasing when the number of current placements decreases.
Claim 6
Dependent Claim
24 words
A method as in claim 4 wherein in step (e) the optimization performed is a completion of the greedy optimization performed in step (b).
Claim 7
Dependent Claim
24 words
A method as in claim 2 wherein in step (e) the optimization performed is a completion of the greedy optimization performed in step (b).
Claim 8
Dependent Claim
23 words
A method as in claim 2 wherein the global cost metric is based on total length of all connection lines of the circuit.
Claim 9
Dependent Claim
24 words
A method as in claim 7 wherein the local cost metric is based on total length of all connection lines connected to the component.
Claim 10
Dependent Claim
42 words
A method as in claim 1 wherein in step (a) the initial number is approximately equal to a total number of components in the circuit and in step (c) approximately half the current placements are selected to be the new current placements.
Claim 11
Dependent Claim
53 words
A method as in claim 1 wherein in step (a) the initial number is significantly less than a total number of components in the circuit and in step (c) a percentage of the current placements are selected to be the new current placements, the percentage increasing when the number of current placements decreases.
Claim 12
Dependent Claim
24 words
A method as in claim 1 wherein in step (e) the optimization performed is a completion of the greedy optimization performed in step (b).
Claim 13
Dependent Claim
22 words
A method as in claim 1 wherein the global cost metric is based on total length of connection lines for the circuit.
Claim 14
Dependent Claim
163 words
A computer implemented method for placement of components for a VLSI circuit, the method comprising the steps, performed by a computer, of: (a) selecting an initial number of current placements, including for each of the initial current placements selecting locations within the VLSI circuit for placement of each of the components; (b) for each of the current placements, changing locations of the components to improve the current placement so that the current placement is partially optimized in accordance with partial performance of a greedy optimization; (c) selecting a subset of the current placements partially optimized in step (b) to be new current placements, the selection being based on a global cost metric for the current placements; (d) when there are more than one new current placements, repeating steps (a) through (d) with the new current placements being the current placements; and, (e) when there is only one new current placement, performing an optimization on the new current placement to obtain an optimized placement.
Claim 15
Dependent Claim
163 words
A computer implemented method for placement of components for a VLSI circuit, the method comprising the steps, performed by a computer, of: (a) selecting an initial number of current placements, including for each of the initial current placements selecting locations within the VLSI circuit for placement of each of the components; (b) for each of the current placements, changing locations of the components to improve the current placement so that the current placement is partially optimized in accordance with partial performance of a greedy optimization; (c) selecting a subset of the current placements partially optimized in step (b) to be new current placements, the selection being based on a global cost metric for the current placements; (d) when there are more than one new current placements, repeating steps (a) through (d) with the new current placements being the current placements; and, (e) when there is only one new current placement, performing an optimization on the new current placement to obtain an optimized placement.
Claim 16
Dependent Claim
75 words
A computer implemented method as in claim 13 wherein in step (b) the partial performance of the greedy optimization performed is a single pass through a greedy optimization algorithm in which for each pass, the following substeps are performed for each component; determining, based on a local cost metric, a best location for the component; and, moving the component to the best location when doing so improves a current value for the global cost metric.
Claim 17
Dependent Claim
44 words
A computer implemented method as in claim 14 wherein in step (a) the initial number is approximately equal to a total number of components in the circuit and in step (c) approximately half the current placements are selected to be the new current placements.
Claim 18
Dependent Claim
55 words
A computer implemented method as in claim 14 wherein in step (a) the initial number is significantly less than a total number of components in the circuit and in step (c) a percentage of the current placements are selected to be the new current placements, the percentage increasing when the number of current placements decreases.
Claim 19
Dependent Claim
26 words
A computer implemented method as in claim 14 wherein in step (e) the optimization performed is a completion of the greedy optimization performed in step (b).
Claim 20
Dependent Claim
26 words
A computer implemented method as in claim 14 wherein the local cost metric is based on total length of all connection lines connected to the component.
Claim 21
Dependent Claim
44 words
A computer implemented method as in claim 13 wherein in step (a) the initial number is approximately equal to a total number of components in the circuit and in step (c) approximately half the current placements are selected to be the new current placements.
Claim 22
Dependent Claim
55 words
A computer implemented method as in claim 12 wherein in step (a) the initial number is significantly less than a total number of components in the circuit and in step (c) a percentage of the current placements are selected to be the new current placements, the percentage increasing when the number of current placements decreases.
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) | 1997-09-19 | 1998-03-21 | 1998-09-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-09-19 | 2002-03-21 | 2002-09-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-09-19 | 2006-03-21 | 2006-09-20 | $7700.00 | Window Closed / Lapsed |