Moment computation algorithms in VLSI system

• US 8,156,466 B2
• Filed: 12/19/2008
• Issued: 04/10/2012
• Est. Priority Date: 11/20/2002
• Status: Expired due to Fees

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Guo, Weiqing, Bhutani, Sandeep
• Primary Examiner(s): Siek, Vuthe
• Application Number:
  US12/340,234
• Publication Number:
  US 20090158228A1
• Time in Patent Office: 1,208 Days
• Field of Search: 716/106, 716/115, 716/132, 716/136
• US Class Current: 716/136
• CPC Class Codes: G06F 30/367 Design verification, e.g. using simulation, simulation program with integrated circuit emphasis [SPICE], direct methods or relaxation methods

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.

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.

2. The method of claim 1, wherein the creating step (a) further comprises:

(a1) setting, by the computer system, an initial voltage of each node in the at least one parasitic graph; and

(a2) computing, by the computer system, an outgoing current for each node in the at least one parasitic graph.

3. The method of claim 2, wherein the setting step (a1) comprises:

(a1i) setting, by the computer system, an aggressor node of the at least one parasitic graph to a first initial voltage, wherein the first initial voltage accounts for coupling capacitance at the aggressor node; and

(a1ii) setting, by the computer system, victim nodes of the at least one parasitic graph to a second initial voltage.

4. The method of claim 1, wherein the determining step (b) further comprises:

(b1) updating, by the computer system, a current for each node of the at least one parasitic graph if the at least one parasitic graph has been reduced.

5. The method of claim 1, wherein the reducing step (c3) comprises:

(c3i) determining, by the computer system, a matrix, wherein each entry of the matrix represents an edge of the at least one parasitic graph;

(c3ii) changing, by the computer system, the matrix such that a voltage at the node is no longer coupled to other nodes in the at least one parasitic graph; and

(c3iii) reducing, by the computer system, the at least one parasitic graph by eliminating the node, wherein the changed matrix represents edges of the reduced graph.

6. The method of claim 1, wherein the reducing step (c) comprises:

(c1i) performing, by the computer system, a first depth-first-search on the at least one parasitic graph;

(c2i) determining, by the computer system, the degree for the deepest node with the smallest degree, wherein the node have a degree of one or two;

(c3i) reducing, by the computer system, the at least one parasitic graph by eliminating the node; and

(c4i) recursively performing, by the computer system, the determining step (c2i) and the reducing step (c3i) until the first depth-first-search completes.

7. The method of claim 6, further comprising:

(c5) determining, by the computer system, if nodes with degrees of three or more remain in the reduced graph;

(c6) performing, by the computer system, a second depth-first-search on the reduced graph, if nodes with degrees of three or more remain in the reduced graph;

(c7) determining, by the computer system, a degree of another deepest node with a smallest degree, wherein the other node can have a degree of three or more;

(c8) further reducing, by the computer system, the reduced graph by eliminating the other node; and

(c9) recursively performing, by the computer system, the determining step (c7) and the further reducing step (c8) until the second depth-first-search completes.

8. The method of claim 1, wherein the reducing step (c) further comprises:

(c5) determining, by the computer system, if the reduced graph has any non-reduced nodes;

(c6) marking, by the computer system, the reduced graph as completely reduced if there are no non-reduced nodes; and

(c7) marking, by the computer system, the reduced graph as not completely reduced if there are non-reduced nodes.

9. The method of claim 8, wherein the degree of the node of the at least one parasitic graph is a number of edges coupled to the node.

10. The method of claim 1, wherein the computing step (d) comprises:

(d1) determining, by the computer system, if the reduced graph has been completely reduced;

(d2) computing, by the computer system, moments for non-reduced nodes in the reduced graph using a matrix, if the reduced graph has not been completely reduced, wherein each entry of the matrix represents an edge of the reduced graph; and

(d3) computing, by the computer system, moments for reduced nodes in the reduced graph.

11. The method of claim 1, further comprising:

(e) determining, by the computer system, if moments for another parasitic graph for the interconnect circuit model are to be computed; and

(f) repeating steps (b)-(d), by the computer system, for the other parasitic graph, if moments for another parasitic graph are to be computed.

12. The method of claim 11, further comprising:

(g) determining, by the computer system, if all order of moments for the interconnect circuit model has been computed;

(h) setting, by the computer system, an initial voltage of each node of the at least one parasitic graph to a computed moment of a previous moment order, if not all order of moments has been computed; and

(i) recursively repeating steps (b)-(f), by the computer system, until all order of moments for the interconnect circuit model has been computed.

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.