US5208759A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for placement of circuit components in an integrated circuit
Assignee: Philips Semiconductors Inc
•
Filing: 1990-12-13
•
Granted: 1993-05-04
•
Expires: 2010-12-13
Abstract
Abstract In a method for optimizing placement of circuit components on at least one integrated circuit, a list of circuit components is constructed. For each pairing of circuit components on the list, a total cost of the pairing is calculated. The total cost being calculated by first calculating the dead space resulting from the pairing, then estimating the total increase in routing area resulting from the pairing, and finally adding the dead space to the total increase in routing area to obtain the total cost. The estimation of the total increase in routing area resulting from the pairing is done by first estimating an increase in connectivity area resulting from the pairing. Then, a decrease in connectivity area resulting from the pairing is estimated. Finally, the decrease in connectivity area is subtracted from the increase in connectivity area to obtain the total increase in routing area.
Inventors
- 👤 Dale M. Wong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 09:02
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
183 words
A method for optimizing placement of circuit components on at least one integrated circuit, the method comprising the steps of: (a) constructing a list of circuit components; (b) while there is more than one circuit component on the list, determining an order for merging circuit components on the list, the determining including the following substeps: (b1) for each pairing of circuit components on the list, calculating a total cost of the pairing, the total cost being calculated by calculating the dead space resulting from the pairing, estimating the total increase in routing area resulting from the pairing, and adding the dead space to the total increase in routing area to obtain the total cost; (b2) for a first pairing with a lowest total cost as calculated in step (b1), merging first circuit components which form the first pairing into a new circuit component, removing the first circuit components from the list, and adding the new circuit component to the list; and, (c) based on the order for merging determined in step (b), placing the circuit components on the at least one integrated circuit.
Claim 2
Independent Claim
183 words
A method for optimizing placement of circuit components on at least one integrated circuit, the method comprising the steps of: (a) constructing a list of circuit components; (b) while there is more than one circuit component on the list, determining an order for merging circuit components on the list, the determining including the following substeps: (b1) for each pairing of circuit components on the list, calculating a total cost of the pairing, the total cost being calculated by calculating the dead space resulting from the pairing, estimating the total increase in routing area resulting from the pairing, and adding the dead space to the total increase in routing area to obtain the total cost; (b2) for a first pairing with a lowest total cost as calculated in step (b1), merging first circuit components which form the first pairing into a new circuit component, removing the first circuit components from the list, and adding the new circuit component to the list; and, (c) based on the order for merging determined in step (b), placing the circuit components on the at least one integrated circuit.
Claim 3
Dependent Claim
46 words
A method as in claim 1, wherein step (c) includes the following substeps: (c1) constructing a merge tree based on the order for merging determined in step (b); and (c2) traversing the merge tree to place the circuit components on the at least one integrated circuit.
Claim 4
Independent Claim
225 words
A method for optimizing placement of circuit components on at least one integrated circuit, the method comprising the steps of: (a) constructing a list of circuit components; (b) while there is more than one circuit component on the list, determining an order for merging circuit components on the list, the determining including the following substeps (b1) for each pairing of circuit components on the list, calculating a total cost of the pairing, the total cost being calculated by calculating the dead space resulting from the pairing, estimating the total increase in routing area resulting from the pairing, including estimating an increase in connectivity area resulting from the pairing, estimating a decrease in connectivity area resulting from the pairing, and subtracting the decrease in connectivity area from the increase in connectivity area to obtain the total increase in routing area, and adding the dead space to the total increase in routing area to obtain the total cost, (b2) for a first pairing with a lowest total cost as calculated in step (b1), merging first circuit components which form the first pairing into a new circuit component, removing the first circuit components from the list, and adding the new circuit component to the list; and, (c) based on the order for merging determined in step (b), placing the circuit components on the at least one integrated circuit.
Claim 5
Independent Claim
225 words
A method for optimizing placement of circuit components on at least one integrated circuit, the method comprising the steps of: (a) constructing a list of circuit components; (b) while there is more than one circuit component on the list, determining an order for merging circuit components on the list, the determining including the following substeps (b1) for each pairing of circuit components on the list, calculating a total cost of the pairing, the total cost being calculated by calculating the dead space resulting from the pairing, estimating the total increase in routing area resulting from the pairing, including estimating an increase in connectivity area resulting from the pairing, estimating a decrease in connectivity area resulting from the pairing, and subtracting the decrease in connectivity area from the increase in connectivity area to obtain the total increase in routing area, and adding the dead space to the total increase in routing area to obtain the total cost, (b2) for a first pairing with a lowest total cost as calculated in step (b1), merging first circuit components which form the first pairing into a new circuit component, removing the first circuit components from the list, and adding the new circuit component to the list; and, (c) based on the order for merging determined in step (b), placing the circuit components on the at least one integrated circuit.
Claim 6
Dependent Claim
80 words
A method as in claim 3 wherein estimating the total increase in routing area includes: estimating an average length of a connection line routed within the pairing; and, producing an estimate of the total increase in routing area by multiplying the estimated average length times a width of the connection line times a number of connection lines which are connected to a circuit component not within the pairing and are connected to only a single circuit component within the pairing.
Claim 7
Dependent Claim
39 words
A method as in claim 4 wherein the average length of a connection line routed within the pairing is estimated to be one quarter of a periphery of a bounded area formed by merging circuit components of the pairing.
Claim 8
Dependent Claim
37 words
A method as in claim 4 wherein the average length of a connection line routed within the pairing is estimated to be a square root of a bounding area formed by merging circuit components of the pairing.
Claim 9
Dependent Claim
84 words
A method as in claim 3 wherein estimating the total decrease in routing area includes: estimating an average length of a connection line routed within a first area which is equal to twice a bounded are formed by merging circuit components of the pairing; and, producing an estimate of the total decrease in routing area by multiplying the estimated average length times a width of the connection line times a number of connection lines which are connected to both circuit components within the pairing.
Claim 10
Dependent Claim
31 words
A method as in claim 7 wherein the average length of a connection line routed within the pairing is estimated to be one quarter of a periphery of the first area.
Claim 11
Dependent Claim
29 words
A method as in claim 7 wherein the average length of a connection line routed within the pairing is estimated to be a square root of the first area.
Claim 12
Independent Claim
79 words
A method comprising the steps of: determining total area cost of a pairing of two circuit components in a plurality of circuit components, including the substeps of (a) calculating the dead space resulting from the pairing, (b) estimating the total increase in routing area resulting from the pairing, and (c) adding the dead space to the total increase in routing area to obtain the total cost; and placing the plurality of circuit components on at least one integrated circuit.
Claim 13
Independent Claim
79 words
A method comprising the steps of: determining total area cost of a pairing of two circuit components in a plurality of circuit components, including the substeps of (a) calculating the dead space resulting from the pairing, (b) estimating the total increase in routing area resulting from the pairing, and (c) adding the dead space to the total increase in routing area to obtain the total cost; and placing the plurality of circuit components on at least one integrated circuit.
Claim 14
Independent Claim
127 words
A method comprising the steps of: determining total area cost of a pairing of two circuit components in a plurality of circuit components, including the substeps of (a) calculating the dead space resulting from the pairing, (b) estimating the total increase in routing area resulting from the pairing including the substeps of (b1) estimating an increase in connectivity area resulting from the pairing, (b2) estimating a decrease in connectivity area resulting from the pairing, and (b3) subtracting the decrease in connectivity area from the increase in connectivity area to obtain the total increase in routing area, and (c) adding the dead space to the total increase in routing area to obtain the total cost; and, placing the plurality of circuit components on at least one integrated circuit.
Claim 15
Independent Claim
127 words
A method comprising the steps of: determining total area cost of a pairing of two circuit components in a plurality of circuit components, including the substeps of (a) calculating the dead space resulting from the pairing, (b) estimating the total increase in routing area resulting from the pairing including the substeps of (b1) estimating an increase in connectivity area resulting from the pairing, (b2) estimating a decrease in connectivity area resulting from the pairing, and (b3) subtracting the decrease in connectivity area from the increase in connectivity area to obtain the total increase in routing area, and (c) adding the dead space to the total increase in routing area to obtain the total cost; and, placing the plurality of circuit components on at least one integrated circuit.
Claim 16
Dependent Claim
79 words
A method as in claim 11 wherein substep (b2) includes: estimating an average length of a connection line routed within a first area which is equal to twice a bounded area formed by merging circuit components of the pairing; and, producing an estimate of the total decrease in routing area by multiplying the estimated average length times a width of the connection line times a number of connection lines which are connected to both circuit components within the pairing.
Claim 17
Dependent Claim
31 words
A method as in claim 12 wherein the average length of a connection line routed within the pairing is estimated to be one quarter of a periphery of the first area.
Claim 18
Dependent Claim
29 words
A method as in claim 12 wherein the average length of a connection line routed within the pairing is estimated to be a square root of the first area.
Claim 19
Independent Claim
196 words
A method comprising the steps of: determining total area cost of a pairing of two circuit components in a plurality of circuit components, including the substeps of (a) calculating the dead space resulting from the pairing, (b) estimating the total increase in routing area resulting from the pairing including the substeps of (b1) estimating an increase in connectivity area resulting from the pairing including the substeps of estimating an average length of a connection line routed within the pairing, and producing an estimate of the total increase in routing area by multiplying the estimated average length times a width of the connection line times a number of connection lines which are connected to a circuit component not within the pairing and are connected to only a single circuit component within the pairing, (b2) estimating a decrease in connectivity area resulting from the pairing, and (b3) subtracting the decrease in connectivity area from the increase in connectivity area to obtain the total increase in routing area, and (c) adding the dead space to the total increase in routing area to obtain the total cost; and placing the plurality of circuit components on at least one integrated circuit.
Claim 20
Independent Claim
196 words
A method comprising the steps of: determining total area cost of a pairing of two circuit components in a plurality of circuit components, including the substeps of (a) calculating the dead space resulting from the pairing, (b) estimating the total increase in routing area resulting from the pairing including the substeps of (b1) estimating an increase in connectivity area resulting from the pairing including the substeps of estimating an average length of a connection line routed within the pairing, and producing an estimate of the total increase in routing area by multiplying the estimated average length times a width of the connection line times a number of connection lines which are connected to a circuit component not within the pairing and are connected to only a single circuit component within the pairing, (b2) estimating a decrease in connectivity area resulting from the pairing, and (b3) subtracting the decrease in connectivity area from the increase in connectivity area to obtain the total increase in routing area, and (c) adding the dead space to the total increase in routing area to obtain the total cost; and placing the plurality of circuit components on at least one integrated circuit.
Claim 21
Dependent Claim
39 words
A method as in claim 15 wherein the average length of a connection line routed within the pairing is estimated to be one quarter of a periphery of a bounded area formed by merging circuit components of the pairing.
Claim 22
Dependent Claim
37 words
A method as in claim 15 wherein the average length of a connection line routed within the pairing is estimated to be a square root of a bounding area formed by merging circuit components of the pairing.
References Cited (Backward Citations)
US4577276A
Cited
US4910680A
Cited
US4908772A
Cited
US4918614A
Cited
US4811237A
Cited
US4815003A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-05-03 | 1996-11-02 | 1997-05-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-05-03 | 2000-11-02 | 2001-05-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-05-03 | 2004-11-02 | 2005-05-04 | $7700.00 | Window Closed / Lapsed |