Method for reducing a parasitic graph in moment computation in VLSI systems

• US 7,082,583 B2
• Filed: 11/20/2002
• Issued: 07/25/2006
• 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 Logic Corporation (Broadcom, Inc.)
• Inventors: Bhutani, Sandeep, Guo, Weiqing
• Primary Examiner(s): THOMPSON, ANNETTE M
• Application Number:
  US10/301,069
• Publication Number:
  US 20040098677A1
• Time in Patent Office: 1,343 Days
• Field of Search: 716/4, 703/13, 703/14, 403/14
• US Class Current: 716/115
• 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 reducing a parasitic graph for an interconnect model circuit, the parasitic graph comprising a plurality of nodes, comprising the steps of:

(a) performing a depth-first-search on the graph;

(b) determining a degree of a deepest node with a smallest degree, wherein the node can have a degree of more than one;

(c) reducing the graph by eliminating the node, wherein the node is a member of a resistor loop, wherein the reducing comprises;

(c1) determining a matrix, wherein each entry of the matrix represents an edge of the graph,

(c2) changing the matrix such that a voltage at the node is no longer coupled to other nodes in the graph, and

(c3) reducing the graph by eliminating the node, wherein the changed matrix represents edges of the reduced graph; and

(d) recursively performing the determining step (b) and the reducing step (c) until the depth-first-search completes.

2. The method of claim 1, comprising:

(a1) performing a first depth-first-search on the graph;

(b1) determining the degree of the deepest node with the smallest degree, wherein the node has a degree of one or two;

(c1) reducing the graph by eliminating the node; and

(d1) recursively performing the determining step (b1) and the reducing step (c1) until the first depth-first-search completes.

3. The method of claim 2, further comprising:

(e) determining if nodes with degrees of three or more remain in the reduced graph;

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

(g) determining a degree for another deepest node with a smallest degree, wherein the other node has a degree of three or more;

(h) further reducing the reduced graph by eliminating the other node, wherein the other node is a member of another resistor loop; and

(i) recursively performing the determining step (f) and the further reducing step (g) until the second depth-first-search completes.

4. The method of claim 1, further comprising:

(e) determining if the reduced graph has any non-reduced nodes;

(f) marking the reduced graph as completely reduced if there are no non-reduced nodes; and

(g) marking the reduced graph as not completely reduced if there are non-reduced nodes.

5. The method of claim 1, wherein the degree of the node of the graph is a number of edges coupled to the node.

6. A method for reducing a parasitic graph for a interconnect model circuit, he parasitic graph comprising a plurality of nodes, comprising the steps of:

(a) performing a first depth-first-search on the graph;

(b) determining a degree of a deepest node with the smallest degree, wherein the node has a degree of one or two;

(c) reducing the graph by eliminating the node, wherein the node is a member of a resistor loop, wherein the reducing comprises;

(c1) determining a matrix, wherein each entry of the matrix represents an edge of the graph,

(c2) changing the matrix such that a voltage at the node is no longer coupled to other nodes in the graph, and

(c3) reducing the graph by eliminating the node, wherein the changed matrix represents edges of the reduced graph;

(d) recursively performing the determining step (b) and the reducing step (c) until the first depth-first-search completes;

(e) determining if nodes of degrees of three or more remain in the reduced graph;

(f) performing a second depth-first-search on the reduced graph, if nodes of degrees of three of more remain in the reduced graph;

(g) determining a degree for another deepest node with a smallest degree, wherein the other node has a degree of three or more;

(h) further reducing the reduced graph by eliminating the other node, wherein the other node is a member of another resistor loop; and

(i) recursively performing the determining step (g) and the further reducing step (h) until the second depth-first-search completes.

7. A computer readable medium with program instructions for reducing a parasitic graph for an interconnect model circuit, the parasitic graph comprising a plurality of nodes, comprising the instructions for:

(a) performing a depth-first-search on the graph;

(b) determining a degree of a deepest node with a smallest degree, wherein the node has a degree of more than one;

(c) reducing the graph by eliminating the node, wherein the node is a member of a resistor loop, wherein the reducing comprises;

(c1) determining a matrix, wherein each entry of the matrix represents an edge of the graph,

(c2) changing the matrix such that a voltage at the node is no longer coupled to other nodes in the graph, and

(c3) reducing the graph by eliminating the node, wherein the changed matrix represents edges of the reduced graph; and

(d) recursively performing the determining instruction (b) and the reducing instruction (c) until the depth-first-search completes.