US6480816B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Circuit simulation using dynamic partitioning and on-demand evaluation
Assignee: Mentor Graphics Corp
•
Filing: 1999-06-14
•
Granted: 2002-11-12
•
Expires: 2019-06-14
Abstract
Abstract An EDA tool is provided with a circuit simulator that simulates circuit operation using dynamic partitioning and on-demand evaluation. The circuit simulator includes a static partitioner, a dynamic partitioner and an evaluation scheduler. The static partitioner pre-forms a number of static partitions for the circuit. During simulation, the dynamic partitioner forms and re-forms a number of dynamic partitions referencing the static partitions. At each simulation time step, the evaluation scheduler determines which, if any, of the dynamic partitions have to be evaluated, and evaluating on-demand only those where evaluations are necessary. In one embodiment, when evaluations are performed, they are performed through matrix solution when accuracy is needed.
Inventors
- 👤 Sanjay Dhar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 02:55
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/33; G06F30/36; G06F30/367
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
78 words
A computer implemented method for simulating a circuit, the method comprising: preprocessing sets of nodes, each set comprising one of a plurality of static partitions of the circuit, to determine an order for the nodes in each set that is particularly suited for dynamic partitioning of a respective static partition; and forming a plurality of dynamic partitions of the circuit by traversing each of the sets of nodes in the respective order and gathering active sets of nodes.
Claim 2
Dependent Claim
78 words
A computer implemented method for simulating a circuit, the method comprising: preprocessing sets of nodes, each set comprising one of a plurality of static partitions of the circuit, to determine an order for the nodes in each set that is particularly suited for dynamic partitioning of a respective static partition; and forming a plurality of dynamic partitions of the circuit by traversing each of the sets of nodes in the respective order and gathering active sets of nodes.
Claim 3
Dependent Claim
15 words
The method of claim 1 , wherein the method further comprises pre-forming said static partitions.
Claim 4
Dependent Claim
28 words
The method of claim 2 , wherein pre-forming the static partitions comprises organizing devices of the circuit into connected sets, with each connected set forming a static partition.
Claim 5
Dependent Claim
21 words
The method of claim 1 , wherein preprocessing the sets of nodes is performed at least in accordance with signal flow.
Claim 6
Dependent Claim
25 words
The method of claim 1 , wherein preprocessing the sets of nodes is performed at least in accordance with where strongly connected components are located.
Claim 7
Dependent Claim
36 words
The method of claim 1 , wherein preprocessing the sets of nodes comprises: generating a graphic representation of each of the plurality of static partitions; and ordering nodes and edges in each of the graphic representations.
Claim 8
Dependent Claim
40 words
The method of claim 6 , wherein ordering the nodes and edges in each of the graphic representations comprises: identifying bi-connected components in each of the graphic representations; and ordering the nodes and edges based on the identified bi-connected components.
Claim 9
Dependent Claim
62 words
The method of claim 1 , wherein gathering the active sets of nodes comprises identifying devices that are ON in a given static partition, and identifying nodes in a graphical representation of the given static partition that are connected by the devices that are ON, with each interconnected collection of nodes that are ON forming one of the plurality of dynamic partitions.
Claim 10
Dependent Claim
22 words
The method of claim 1 , wherein forming the plurality of dynamic partitions further comprises merging and/or breaking previously formed dynamic partitions.
Claim 11
Dependent Claim
37 words
The article of manufacture comprising: a recordable medium having stored therein a plurality of programming instructions to be executed by a processor, wherein when executed, causes the method as set forth in claim 1 to be performed.
Claim 12
Dependent Claim
25 words
The article of claim 10 , wherein the programming instructions, when executed, further causes the additional operations set forth in claim 9 to be performed.
Claim 13
Dependent Claim
33 words
The method of claim 1 further comprising: at each simulation time step, determining which of the plurality of dynamic partitions has to be evaluated, and evaluating only the dynamic partitions that require evaluation.
Claim 14
Dependent Claim
30 words
The method of claim 12 , wherein determining which of the plurality of dynamic partitions has to be evaluated comprises determining whether a given dynamic partition is in steady state.
Claim 15
Dependent Claim
28 words
The method of claim 12 , wherein determining which of the plurality of dynamic partitions has to be evaluated comprises preventing a zero-delay trigger loop from being formed.
Claim 16
Dependent Claim
40 words
The method of claim 12 , wherein evaluating the dynamic partitions that require evaluation comprises traversing a graphical representation of a given dynamic partition in an bottom-up manner, and computing a matrix solution for each node of the graphical representation.
Claim 17
Dependent Claim
98 words
A computer implemented method for simulating a circuit, the method comprising: forming a plurality of dynamic partitions of the circuit, using a plurality of pre-formed static partitions of said circuit; at each simulation time step, determining whether the dynamic partitions have to be evaluated, and evaluating only the dynamic partitions that require evaluation, wherein said determination of whether a dynamic partition has to be evaluated comprises determining whether a dynamic partition is in steady state, and, wherein said determination of whether a dynamic partition has to be evaluated further comprises preventing a zero-delay trigger loop from being formed.
Claim 18
Dependent Claim
98 words
A computer implemented method for simulating a circuit, the method comprising: forming a plurality of dynamic partitions of the circuit, using a plurality of pre-formed static partitions of said circuit; at each simulation time step, determining whether the dynamic partitions have to be evaluated, and evaluating only the dynamic partitions that require evaluation, wherein said determination of whether a dynamic partition has to be evaluated comprises determining whether a dynamic partition is in steady state, and, wherein said determination of whether a dynamic partition has to be evaluated further comprises preventing a zero-delay trigger loop from being formed.
Claim 19
Dependent Claim
116 words
An article of manufacture comprising: a recordable medium having stored therein a plurality of programming instructions to be executed by a processor, wherein when executed, implement a method comprising: forming a plurality of dynamic partitions of the circuit, using a plurality of pre-formed static partitions of said circuit; at each simulation time step, determining whether the dynamic partitions have to be evaluated, and evaluating only the dynamic partitions that require evaluation, wherein said determination of whether a dynamic partition has to be evaluated comprises determining whether a dynamic partition is in steady state, and, wherein said determination of whether a dynamic partition has to be evaluated further comprises preventing a zero-delay trigger loop from being formed.
Claim 20
Dependent Claim
116 words
An article of manufacture comprising: a recordable medium having stored therein a plurality of programming instructions to be executed by a processor, wherein when executed, implement a method comprising: forming a plurality of dynamic partitions of the circuit, using a plurality of pre-formed static partitions of said circuit; at each simulation time step, determining whether the dynamic partitions have to be evaluated, and evaluating only the dynamic partitions that require evaluation, wherein said determination of whether a dynamic partition has to be evaluated comprises determining whether a dynamic partition is in steady state, and, wherein said determination of whether a dynamic partition has to be evaluated further comprises preventing a zero-delay trigger loop from being formed.
Claim 21
Dependent Claim
120 words
A computer system comprising: a storage medium having stored therein a plurality of programming instructions implementing a circuit simulator to simulate a circuit, the circuit simulator including a static partitioner to preprocess sets of nodes, each set comprising one of a plurality of static partitions of the circuit, to determine an order for the nodes in each set that is particularly suited for dynamic partitioning of a respective static partition; and a dynamic partitioner to form a plurality of dynamic partitions of the circuit by traversing each of the sets of nodes in the respective order and gathering active sets of nodes; and a processor coupled to the storage medium to execute the programming instructions to operate the circuit simulator.
Claim 22
Dependent Claim
120 words
A computer system comprising: a storage medium having stored therein a plurality of programming instructions implementing a circuit simulator to simulate a circuit, the circuit simulator including a static partitioner to preprocess sets of nodes, each set comprising one of a plurality of static partitions of the circuit, to determine an order for the nodes in each set that is particularly suited for dynamic partitioning of a respective static partition; and a dynamic partitioner to form a plurality of dynamic partitions of the circuit by traversing each of the sets of nodes in the respective order and gathering active sets of nodes; and a processor coupled to the storage medium to execute the programming instructions to operate the circuit simulator.
Claim 23
Dependent Claim
20 words
The computer system of claim 18 , wherein said static partitioner is further to pre-form said plurality of static partitions.
Claim 24
Dependent Claim
66 words
The computer system of claim 18 , wherein said dynamic partitioner gathers the active sets of nodes by identifying devices that are ON in a given static partition, and identifying nodes in a graphical representation of the given static partition that are connected by the devices that are ON, with each interconnected collection of nodes that are ON forming one of the plurality of dynamic partitions.
Claim 25
Dependent Claim
43 words
The computer system of claim 18 wherein the circuit simulator further comprises: an evaluation scheduler to determine, at each simulation time step, which of the plurality of dynamic partitions has to be evaluated, and to evaluate only the dynamic partitions that require evaluation.
Claim 26
Dependent Claim
50 words
The computer system of claim 21 wherein the circuit simulator further comprises: node and model evaluators to evaluate a given dynamic partition requiring evaluation by traversing a graphical representation of a given dynamic partition in an bottom-up manner, and computing a matrix solution for each node of the graphical representation.
Claim 27
Independent Claim
103 words
A method for evaluating a dynamic partition of a circuit to simulate the circuit, the method comprising: preprocessing sets of nodes, each set comprising one of a plurality of static partitions of the circuit, to determine an order for the nodes in each set that is particularly suited for dynamic partitioning of a respective static partition; during simulation, forming dynamic partitions by traversing each of the sets of nodes in the respective order and gathering active sets of nodes; and evaluating selected ones of the dynamic partitions formed, with each selected dynamic partition being evaluated in an ordered manner through a matrix solution.
Claim 28
Independent Claim
103 words
A method for evaluating a dynamic partition of a circuit to simulate the circuit, the method comprising: preprocessing sets of nodes, each set comprising one of a plurality of static partitions of the circuit, to determine an order for the nodes in each set that is particularly suited for dynamic partitioning of a respective static partition; during simulation, forming dynamic partitions by traversing each of the sets of nodes in the respective order and gathering active sets of nodes; and evaluating selected ones of the dynamic partitions formed, with each selected dynamic partition being evaluated in an ordered manner through a matrix solution.
Claim 29
Dependent Claim
22 words
The method of claim 23 , wherein evaluating each of the selected dynamic partitions is performed on-demand, on an as needed basis.
Claim 30
Dependent Claim
116 words
A computer system comprising: a storage medium having stored therein a plurality of programming instructions; and a processor coupled to the storage medium to execute the programming instructions to: preprocess sets of nodes, each set comprising one of a plurality of static partitions of a simulated circuit, to determine an order for the nodes in each set that is particularly suited for dynamic partitioning of a respective static partition, during simulation, form dynamic partitions by traversing each of the sets of nodes in the respective order and gather active sets of nodes, and evaluate selected ones of the dynamic partitions formed, with each selected dynamic partition being evaluated in an ordered manner through a matrix solution.
Claim 31
Dependent Claim
116 words
A computer system comprising: a storage medium having stored therein a plurality of programming instructions; and a processor coupled to the storage medium to execute the programming instructions to: preprocess sets of nodes, each set comprising one of a plurality of static partitions of a simulated circuit, to determine an order for the nodes in each set that is particularly suited for dynamic partitioning of a respective static partition, during simulation, form dynamic partitions by traversing each of the sets of nodes in the respective order and gather active sets of nodes, and evaluate selected ones of the dynamic partitions formed, with each selected dynamic partition being evaluated in an ordered manner through a matrix solution.
Claim 32
Dependent Claim
26 words
The computer system of claim 25 , wherein the processor further executes the programming instructions to evaluate the dynamic partitions on-demand, on an as needed basis.
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) | 2005-11-11 | 2006-05-13 | 2006-11-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-11-11 | 2010-05-13 | 2010-11-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-11-11 | 2014-05-13 | 2014-11-12 | $7700.00 | Window Closed / Lapsed |