Moment computation algorithms in VLSI system
First Claim
1. A method for calculating moments for an interconnect circuit model by performing program instructions on a computer system, comprising the steps of:
- (a) creating, by the computer system, at least one parasitic graph for the interconnect circuit model, wherein the at least one parasitic graph comprises a plurality of nodes;
(b) determining, by the computer system, if the at least one parasitic graph has been reduced;
(c) reducing, by the computer system, the at least one parasitic graph if the at least one parasitic graph has not been reduced, wherein the reducing comprises;
(c1) performing, by the computer system, a depth-first-search on the at least one parasitic graph,(c2) determining, by the computer system, a degree of a deepest node with a smallest degree, wherein the node can have a degree of more than one,(c3) reducing, by the computer system, the at least one parasitic graph by eliminating the node, and(c4) recursively, by the computer system, performing the determining step (c2) and the reducing step (c3) until the depth-first-search completes; and
(d) computing, by the computer system, moments using a standard asymptotic waveform evaluation technique for the interconnect circuit model utilizing the reduced graph in order to approximate a propagation delay for the interconnect circuit model.
7 Assignments
0 Petitions
Accused Products
Abstract
An improved method for interconnect delay analysis for VLSI circuits reduces a parasitic graph for moment computation by eliminating one or more nodes in the graph. the elimination process is performed based upon the degree of the nodes. By eliminating nodes in this fashion, the computation complexity is significantly reduced. With this elimination process, resistor loops and crossed loops can also be solved. The order in which the nodes are eliminated is optimized using the depth-first-search method on the parasitic graphs, further reducing the computation complexity. The method provides a consistent functional interface, applicable to different circuit model structures. In addition, the method accounts for coupling capacitance between interconnects.
-
Citations
13 Claims
-
1. A method for calculating moments for an interconnect circuit model by performing program instructions on a computer system, comprising the steps of:
-
(a) creating, by the computer system, at least one parasitic graph for the interconnect circuit model, wherein the at least one parasitic graph comprises a plurality of nodes; (b) determining, by the computer system, if the at least one parasitic graph has been reduced; (c) reducing, by the computer system, the at least one parasitic graph if the at least one parasitic graph has not been reduced, wherein the reducing comprises; (c1) performing, by the computer system, a depth-first-search on the at least one parasitic graph, (c2) determining, by the computer system, a degree of a deepest node with a smallest degree, wherein the node can have a degree of more than one, (c3) reducing, by the computer system, the at least one parasitic graph by eliminating the node, and (c4) recursively, by the computer system, performing the determining step (c2) and the reducing step (c3) until the depth-first-search completes; and (d) computing, by the computer system, moments using a standard asymptotic waveform evaluation technique for the interconnect circuit model utilizing the reduced graph in order to approximate a propagation delay for the interconnect circuit model. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A non-transitory computer readable medium with program instructions for calculating moments for an interconnect circuit model, comprising the instructions for:
-
(a) creating at least one parasitic graph for the interconnect circuit model, wherein the at least one parasitic graph comprises a plurality of nodes; (b) determining if the at least one parasitic graph has been reduced; (c) reducing the at least one parasitic graph if the at least one parasitic graph has not been reduced, wherein the reducing comprises; (c1) performing a depth-first-search on the at least one parasitic graph, (c2) determining a degree of a deepest node with a smallest degree, wherein the node can have a degree of more than one, (c3) reducing the at least one parasitic graph by eliminating the node, and (c4) recursively performing the determining step (c2) and the reducing step (c3) until the depth-first-search completes; and (d) computing moments using a standard asymptotic waveform evaluation technique for the interconnect circuit model utilizing the reduced graph in order to approximate a propagation delay for the interconnect circuit model.
-
Specification