US6175947B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of extracting 3-D capacitance and inductance parasitics in sub-micron VLSI chip designs using pattern recognition and parameterization
Assignee: International Business Machines Corp
•
Filing: 1998-04-20
•
Granted: 2001-01-16
•
Expires: 2018-04-20
Abstract
Abstract A method for accurately extracting capacitance and inductance parasitics from an electrical network representing a three-dimensional wiring of an integrated circuit chip or module is described. The extraction process can be performed either prior to or after completing a detailed wiring of the chip. In the former case, the method utilizes congestion information and approximate wiring length data to estimate the probability of encountering a particular pattern and the most accurate estimated capacitance which can arrived at. In the latter case, the wiring is partitioned into three-dimensional recognizable patterns, and a database of precomputed parasitics for each pattern is queried in order to obtain highly accurate parasitics within a limited number of machine cycles. The number of patterns is assumed to be sufficiently small to be memory and time efficient and to be arrived at in real-time.
Inventors
- 👤 Saila Ponnapalli
- 👤 Timothy Lehner
- 👤 Sanjay Upreti
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 22:56
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/36; G06F30/367
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
96 words
A method of extracting in parasitics real-time from an electrical network representing a three-dimensional wiring of an integrated circuit chip after completing an initial pass of the wiring of said chip, the method comprising the steps of: a) partitioning said wiring into recognizable patterns; b) querying a database of precomputed values of said parasitics of said recognizable patterns; c) recomposing said electrical network from said initial wiring and said precomputed parasitics; and d) storing in said database coefficients of low-order polynomials, polynomials corresponding to recognizable patterns having a different wiring width or a different wiring spacing.
Claim 2
Independent Claim
96 words
A method of extracting in parasitics real-time from an electrical network representing a three-dimensional wiring of an integrated circuit chip after completing an initial pass of the wiring of said chip, the method comprising the steps of: a) partitioning said wiring into recognizable patterns; b) querying a database of precomputed values of said parasitics of said recognizable patterns; c) recomposing said electrical network from said initial wiring and said precomputed parasitics; and d) storing in said database coefficients of low-order polynomials, polynomials corresponding to recognizable patterns having a different wiring width or a different wiring spacing.
Claim 3
Dependent Claim
22 words
The method as recited in claim 1 , wherein said parasitics are selected from the group consisting of resistance, capacitance and inductance.
Claim 4
Dependent Claim
147 words
The method as recited in claim 1 , further comprising the steps of: creating within a predetermined error a set of strong and weak masks for determining which of said recognizable patterns yield the same ones of said parasitics, and for providing the sequencing of entries into said database; running for a manageable set of said recognizable patterns a field solver for generating selected ones of said parasitics; within a predetermined number of machine cycles, indexing each of said recognizable patterns using a referencetarget pair number associated with a unique set of said strong masks and said weak masks; storing in said database each of said selected parasitics corresponding to each of said recognizable patterns having appropriate ones of said indexes; and storing in said database coefficients of low-order polynomials, said polynomials corresponding to said recognizable patterns having a different wiring width or a different wiring spacing.
Claim 5
Dependent Claim
50 words
The method as recited in claim 3 , wherein said coefficients correspond to two types of said polynomials, a first type of said polynomials providing a correction to said wiring having an irregular spacing and a second type of said polynomials providing a correction to wiring having an irregular width.
Claim 6
Dependent Claim
47 words
The method as recited in claim 4 , wherein only selected ones of said coefficients corresponding to a bit which represent a wire in said strong mask are stored in said database, wherein said strong mask is associated with said reference-target pair number on a one-to-one basis.
Claim 7
Dependent Claim
15 words
The method as recited in claim 3 , wherein said predetermined error is approximately 5%.
Claim 8
Dependent Claim
18 words
The method as recited in claim 3 , wherein said predetermined number of machine cycles is approximately 50.
Claim 9
Dependent Claim
24 words
The method as recited in claim 3 , wherein said parasitics are computed with an accuracy comparable to that of a three-dimensional field solver.
Claim 10
Dependent Claim
20 words
The method as recited in claim 3 , wherein said three-dimensional environment includes at least three levels of said wiring.
Claim 11
Dependent Claim
26 words
The method as recited in claim 1 , wherein said step of recomposing said electrical network further comprises making approximations of wiring congestion and wiring length.
Claim 12
Dependent Claim
19 words
The method as recited in claim 1 , wherein said parasitics from said electrical network are extracted in real-time.
Claim 13
Dependent Claim
17 words
The method as recited in claim 1 , wherein said precomputed parasitics are stored in said database.
Claim 14
Dependent Claim
32 words
The method as recited in claim 12 , wherein the number of said parasitics stored in said database is reduced by taking into account strong and weak interactions between said three-dimensional wiring.
Claim 15
Dependent Claim
23 words
The method as recited in claim 1 , wherein said database includes precomputed parasitics of said wiring having varying separation and wiring width.
Claim 16
Independent Claim
152 words
A method for extracting parasitics in real-time from an electrical network representing a three-dimensional wiring of an integrated circuit chip, prior to completing an initial pass of the wiring of said chip, the method comprising the steps of: a) performing a physical design of said chip by executing a floorplanning and placement; b) selecting a routing for a first wire which connects two pins of said chip; c) computing a percentage of encounters between said first wire and groups of wires in close proximity to said first wire, said group of wires traversing said first wire; d) querying a database of precomputed values of said parasitics of each recognizable pattern and computing a probability of said encounters occurring; and e) determining an accurate estimated parasitic for each of said recognizable patterns by summing up the product of said precomputed parasitics of each of said recognizable patterns and said probability of said encounters.
Claim 17
Independent Claim
152 words
A method for extracting parasitics in real-time from an electrical network representing a three-dimensional wiring of an integrated circuit chip, prior to completing an initial pass of the wiring of said chip, the method comprising the steps of: a) performing a physical design of said chip by executing a floorplanning and placement; b) selecting a routing for a first wire which connects two pins of said chip; c) computing a percentage of encounters between said first wire and groups of wires in close proximity to said first wire, said group of wires traversing said first wire; d) querying a database of precomputed values of said parasitics of each recognizable pattern and computing a probability of said encounters occurring; and e) determining an accurate estimated parasitic for each of said recognizable patterns by summing up the product of said precomputed parasitics of each of said recognizable patterns and said probability of said encounters.
Claim 18
Dependent Claim
18 words
The method as recited in claim 15 , wherein the accuracy of said estimated parasitics is approximately 5%.
Claim 19
Dependent Claim
19 words
The method as recited in claim 15 , wherein said groups of wires include 1, 2 or 3 wires.
Claim 20
Dependent Claim
15 words
The method as recited in claim 15 , wherein said routing is a Stiner tree.
Claim 21
Dependent Claim
73 words
The method as recited in claim 15 , wherein parasitic capacitance is determined by statistically estimating the number of times each of said patterns is encountered for said first wire, in accordance with equation (1): C(wire)=C(pattern) * P(pattern), (1) wherein C(wire) is the capacitance of the wire per unit length, C(pattern) is the per unit length capacitance of said pattern and P(pattern) is the probability of encountering said pattern for said first wire.
Claim 22
Dependent Claim
23 words
The method as recited in claim 19 , wherein said parasitics and said connectivity information create a distributed RC or RLC extracted netlist.
Claim 23
Dependent Claim
18 words
The method as recited in claim 15 , wherein said parasitics are instrumental in reconstructing said electrical network.
Claim 24
Dependent Claim
42 words
The method as recited in claim 15 , wherein said database stores connectivity information, said connectivity information comprising which of said recognizable patterns are associated with which of said wires, and which of said wires belong to which of said electrical network.
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) | 2004-01-16 | 2004-07-17 | 2005-01-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-16 | 2008-07-17 | 2009-01-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-16 | 2012-07-17 | 2013-01-16 | $7700.00 | Window Closed / Lapsed |