Method and apparatus for simulating a microelectric interconnect circuit

Claim 3

The method of claim 1 wherein said microelectronic circuit comprises a microelectronic interconnect circuit.

Claim 4

The method of claim 1 wherein said producing step is followed by the steps of: modifying said microelectronic circuit in response to the time domain simulation of the behavior of said microelectronic circuit; and manufacturing the modified microelectronic circuit.

Claim 5

The method of claim 1 wherein said traversing step comprises the steps of: traversing said spanning tree; storing a representation of the traversal of said spanning tree; and obtaining said moments of said microelectronic circuit from the stored representation of said traversal of said spanning tree.

Claim 6

The method of claim 4 wherein said traversing step comprises the step of traversing said spanning tree only once.

Claim 7

The method of claim 4 wherein said traversal representation storing step comprises the step of storing instructions for generating tree branch currents for each node of the spanning tree which is traversed.

Claim 8

The method of claim 6 wherein said traversal representation storing step further comprises the step of storing instructions for generating node voltages for each node of the spanning tree which is traversed.

Claim 9

The method of claim 4 wherein said traversing and traversal representation storing steps comprise the steps of: reverse traversing said spanning tree; storing a first representation of the reverse traversal; forward traversing said spanning tree; and storing a second representation of the forward traversal.

Claim 10

The method of claim 4 wherein said traversal representation storing step comprises the step of storing a virtual path trace of said spanning tree; and wherein said obtaining moments step comprises the step of obtaining said moments of said microelectronic circuit by traversing said virtual path trace of said spanning tree.

Claim 11

The method of claim 9 wherein said microelectronic circuit includes a resistor loop; and wherein said obtaining step is preceded by the steps of: traversing said spanning tree with said resistor loop removed; and determining the resistor loop current from the traversal of said spanning tree with said resistor loop removed.

Claim 12

The method of claim 1 wherein said traversing step comprises the steps of; traversing said spanning tree; obtaining a generation of moments from the traversal of said spanning tree; and repeatedly performing said traversing and obtaining steps to obtain multiple generations of moments.

Claim 13

The method of claim 11 wherein said repeatedly performing step comprises the step of obtaining each of said multiple generations of moments based upon previously obtained generations of moments.

Claim 14

The method of claim 1 wherein said traversing step is followed by the steps of: determining at least one pole of said microelectronic circuit from said unshifted moments of said microelectronic circuit; and determining whether the at least one pole is stable; and wherein said moment shifting step comprises the step of shifting said unshifted moments if said at least one pole is unstable; wherein said pole determining step comprises the step of determining at least one stable pole of said microelectronic circuit from said shifted moments; wherein said residue determining step comprises the step of determining residues from said unshifted moments and the at least one stable pole; and wherein said time domain simulation producing step comprises the step of producing a time domain simulation of the behavior of said microelectronic circuit from the at least one stable pole and the residues.

Claim 15

The method of claim 1 wherein said traversing step comprises the step of producing an unshifted plurality of generations of moments for said microelectronic circuit, ranging from a low order moment generation to a high order moment generation, and is followed by the steps of: determining at least one pole of said microelectronic circuit from said unshifted plurality of generations of moments of said microelectronic circuit; and determining whether the at least one pole is stable; and wherein said moment shifting step comprises the step of shifting said unshifted plurality of generations of moments to include at least one next higher moment generation and eliminate at least one low order moment generation if said at least one pole is unstable and thereby produce a shifted plurality of generations of moments; wherein said pole determining step comprises the step of determining at least one stable pole from said shifted plurality of generations of moments; wherein said residue determining step comprises the step of determining residues from said unshifted plurality of generations of moments and the at least one stable pole; and wherein said time domain simulation producing step comprises the step of producing a time domain simulation of the behavior of said microelectronic circuit from the at least one stable pole and the residues.

Claim 16

The method of claim 1 wherein said traversing step comprises the step of traversing said spanning tree of said directed graph to obtain an unshifted plurality of generations of moments for said microelectronic circuit, ranging from a low order moment generation to a high order moment generation, and is followed by the steps of: determining poles of said microelectronic circuit from said unshifted plurality of generations of moments; determining whether the poles are stable; and wherein said moment shifting step comprises the step of shifting the unshifted plurality of generations of moments to include at least one next higher moment generation and eliminate at least one low order moment generation if any of said poles are unstable and thereby produce a shifted plurality of generation of moments; wherein said pole determining step comprises the step of determining stable poles from said shifted plurality of generations of moments; wherein said residue determining step comprises the step of determining residues from said unshifted plurality of generations of moments and the stable poles; and wherein said time domain simulation producing step comprises the step of producing a time domain simulation of the behavior of said microelectronic circuit from the stable poles and the residues.

Claim 17

The method of claim 1 wherein said microelectronic circuit includes a driving point; wherein said traversing step comprises the step of traversing said spanning tree to obtain unshifted driving point moments corresponding to said driving point, and is followed by the steps of: determining first driving point poles based on the unshifted driving point moments; and determining the stability of the first driving point poles by: shifting said unshifted driving point moments to obtain first shifted driving point moments; determining second driving point poles based on said first shifted driving point moments; and determining convergence of the first driving point poles with the second driving point poles; and wherein said moment shifting step comprises the step of shifting said first shifted driving point moments to obtain second shifted driving point moments if the first driving point poles are unstable; wherein said pole determining step comprises the step of determining third driving point poles based on the second shifted driving point moments; wherein said residue determining step comprises the step of determining residues from said unshifted driving point moments and the second driving point poles; and wherein said producing step comprises the step of producing a time domain simulation of the behavior of said microelectronic circuit from the second driving point poles and the residues.

Claim 18

The method of claim 16 wherein said producing step is preceded by the step of determining residues of said microelectronic circuit from said unshifted driving point moments of said microelectronic circuit and the second driving point poles; and wherein said residue determining step is preceded by the step of determining the stability of the second driving point poles based on convergence with the third driving point poles.

Claim 19

The method of claim 1 wherein said traversing step comprises the following steps: traversing said spanning tree of said directed graph; vectorizing the traversal of said spanning tree so as to traverse said spanning tree only once; and obtaining said moments of said microelectronic circuit from the vectorized traversal of said spanning tree.

Claim 20

The method of claim 1 wherein said microelectronic circuit includes a resistor loop; and wherein said traversing step comprises the steps of: traversing said spanning tree with said resistor loop removed; determining the resistor loop current from the traversal of said spanning tree with said resistor loop removed; and traversing said spanning tree including said resistor loop current to obtain moments of said microelectronic circuit.

Claim 21

The method of claim 1 wherein said microelectronic circuit is of tree or near-tree topology; wherein said converting step comprises the step of converting said equivalent DC circuit into an ordered nodal analysis matrix; and wherein said traversing step comprises the step of factorizing the ordered nodal analysis matrix to obtain moments of said microelectronic circuit.

Claim 24

The method of claim 21 wherein said microelectronic circuit is of tree or near-tree topology; wherein said converting step comprises the step of converting said equivalent DC circuit into an ordered nodal analysis matrix; and wherein said traversing step comprises the step of factorizing the ordered nodal analysis matrix to obtain moments of said microelectronic circuit.

Claim 26

The method of claim 21 wherein said microelectronic circuit comprises a microelectronic interconnect circuit.

Claim 27

The method of claim 21 wherein said producing step is followed by the steps of: modifying said microelectronic circuit in response to the time domain simulation of the behavior of said microelectronic circuit; and manufacturing the modified microelectronic circuit.

Claim 28

The method of claim 21 wherein said traversing step comprises the steps of: traversing said spanning tree; storing a representation of the traversal of said spanning tree; and obtaining said moments of said microelectronic circuit from the stored representation of said traversal of said spanning tree.

Claim 29

The method of claim 26 wherein said traversing step comprises the step of traversing said spanning tree only once.

Claim 30

The method of claim 26 wherein said traversal representation storing step comprises the step of storing instructions for generating tree branch currents for each node of the spanning tree which is traversed.

Claim 31

The method of claim 28 wherein said traversal representation storing step further comprises the step of storing instructions for generating node voltages for each node of the spanning tree which is traversed.

Claim 32

The method of claim 26 wherein said traversing and traversal representation storing steps comprise the steps of: reverse traversing said spanning tree; storing a first representation of the reverse traversal; forward traversing said spanning tree; and storing a second representation of the forward traversal.

Claim 33

The method of claim 26 wherein said traversal representation storing step comprises the step of storing a virtual path trace of said spanning tree; and wherein said obtaining moments step comprises the step of obtaining said moments of said microelectronic circuit by traversing said virtual path trace of said spanning tree.

Claim 34

The method of claim 31 wherein said microelectronic circuit includes a resistor loop; and wherein said obtaining step is preceded by the steps of: traversing said spanning tree with said resistor loop removed; and determining the resistor loop current from the traversal of said spanning tree with said resistor loop removed.

Claim 35

The method of claim 21 wherein said traversing step comprises the steps of; traversing said spanning tree; obtaining a generation of moments from the traversal of said spanning tree; and repeatedly performing said traversing and obtaining steps to obtain multiple generations of moments.

Claim 36

The method of claim 33 wherein said repeatedly performing step comprises the step of obtaining each of said multiple generations of moments based upon previously obtained generations of moments.

Claim 37

The method of claim 21 wherein said microelectronic circuit includes a resistor loop; and wherein said traversing step comprises the steps of: traversing said spanning tree with said resistor loop removed; determining the resistor loop current from the traversal of said spanning tree with said resistor loop removed; and traversing said spanning tree including said resistor loop current to obtain moments of said microelectronic circuit.

Claim 38

The method of claim 21 wherein said traversing step comprises the following steps: traversing said spanning tree of said directed graph; vectorizing the traversal of said spanning tree so as to traverse said spanning tree only once; and obtaining said moments of said microelectronic circuit from the vectorized traversal of said spanning tree.

Claim 39

A computer apparatus for simulating behavior of a microelectronic circuit, comprising: means for storing a representation of said microelectronic circuit in a computer; means, responsive to said storing means, for transforming the stored representation of said microelectronic circuit into an equivalent DC circuit containing resistive and capacitive elements; means, responsive to said transforming means, for converting said equivalent DC circuit for said microelectronic circuit into a directed graph having a spanning tree; means, responsive to said converting means, for traversing said spanning tree of said directed graph to obtain unshifted moments of said microelectronic circuit including resistive and capacitive elements; means, responsive to said traversing means, for shifting said unshifted moments to obtain shifted moments; means, responsive to said shifting means, for determining poles of said microelectronic circuit from said shifted moments; means, responsive to said traversing means and said pole determining means, for determining residues from said unshifted moments and the poles; and means, responsive to said pole determining means and said residue determining means, for producing a time domain simulation of the behavior of said microelectronic circuit from the poles and residues.

Claim 40

A computer apparatus for simulating behavior of a microelectronic circuit, comprising: means for storing a representation of said microelectronic circuit in a computer; means, responsive to said storing means, for transforming the stored representation of said microelectronic circuit into an equivalent DC circuit containing resistive and capacitive elements; means, responsive to said transforming means, for converting said equivalent DC circuit for said microelectronic circuit into a directed graph having a spanning tree; means, responsive to said converting means, for traversing said spanning tree of said directed graph to obtain unshifted moments of said microelectronic circuit including resistive and capacitive elements; means, responsive to said traversing means, for shifting said unshifted moments to obtain shifted moments; means, responsive to said shifting means, for determining poles of said microelectronic circuit from said shifted moments; means, responsive to said traversing means and said pole determining means, for determining residues from said unshifted moments and the poles; and means, responsive to said pole determining means and said residue determining means, for producing a time domain simulation of the behavior of said microelectronic circuit from the poles and residues.

Claim 41

The computer apparatus of claim 37 wherein said microelectronic circuit is of tree or near-tree topology; wherein said converting means comprises means for converting said equivalent DC circuit into an ordered nodal analysis matrix; and wherein said traversing means comprises means for factorizing the ordered nodal analysis matrix to obtain moments of said microelectronic circuit.

Claim 42

The computer apparatus of claim 38 wherein said microelectronic circuit comprises a microelectronic interconnect circuit.

Claim 43

The computer apparatus of claim 37 further comprising: means, responsive to said producing means, for modifying said microelectronic circuit in response to the time domain simulation of the behavior of said microelectronic circuit; and means, responsive to said modifying means, for manufacturing the modified microelectronic circuit.

Claim 44

The computer apparatus of claim 37 wherein said traversing means comprises: means for traversing said spanning tree; means, responsive to said traversing means, for storing a representation of the traversal of said spanning tree; and means, responsive to said representation storing means, for obtaining said moments of said microelectronic circuit from the stored representation of said traversal of said-spanning tree.

Claim 45

The computer apparatus of claim 41 wherein said traversing means comprises means for traversing said spanning tree only once.

Claim 46

The computer apparatus of claim 41 wherein said traversal representation storing means comprises the means for storing instructions for generating tree branch currents for each node of the spanning tree which is traversed.

Claim 47

The computer apparatus of claim 43 wherein said traversal representation storing means further comprises means for storing instructions for generating node voltages for each node of the spanning tree which is traversed.

Claim 48

The computer apparatus of claim 41 wherein said traversing means comprises: means for reverse traversing said spanning tree; and means for forward traversing said spanning tree.

Claim 49

The computer apparatus of claim 41 wherein said traversal representation storing means comprises means for storing a virtual path trace of said spanning tree; and wherein said obtaining moments means comprises means for obtaining said moments of said microelectronic circuit by traversing said virtual path trace of said spanning tree.

Claim 50

The computer apparatus of claim 46 wherein said microelectronic circuit includes a resistor loop; and wherein said obtaining means comprises: means for traversing said spanning tree with said resistor loop removed; and means, responsive to said traversing means, for determining the resistor loop current from the traversal of said spanning tree with said resistor loop removed.

Claim 51

The computer apparatus of claim 38 further comprising: first means, responsive to said traversing means, for determining at least one pole of said microelectronic circuit from said unshifted moments of said microelectronic circuit; second means, responsive to said first means, for determining whether said at least one pole is stable; and wherein said shifting means comprises means for shifting said unshifted moments if said at least one pole is unstable, thereby obtaining shifted moments.

Claim 52

The computer apparatus of claim 38 wherein said traversing means comprises means for obtaining an unshifted plurality of generations of moments for said microelectronic circuit, ranging from a low order moment generation to a high order moment generation, said apparatus further comprising: first means, responsive to said obtaining means, for determining at least one pole of said microelectronic circuit from said unshifted plurality of generations of moments of said microelectronic circuit; and second means, responsive to said first means, for determining whether said at least one pole is stable; and wherein said shifting means comprises means, responsive to said second means, for shifting said unshifted plurality of generations of moments to include at least one next higher moment generation and eliminate at least one low order moment generation if said at least one pole is unstable, thereby obtaining shifted moments.

Claim 53

The computer apparatus of claim 38 wherein said traversing means comprises means for traversing said spanning tree of said directed graph to obtain an unshifted plurality of generations of moments for said microelectronic circuit, ranging from a lowest order moment generation to a highest order moment generation, said apparatus further comprising: first means, responsive to said obtaining means, for determining at least one pole of said microelectronic circuit from said unshifted plurality of generations of moments of said microelectronic circuit; and second means, responsive to said first means, for determining whether said at least one pole is stable; and wherein said shifting means comprises means, responsive to said second means, for shifting said unshifted plurality of generations of moments to include at least one next higher moment generation and eliminate at least one low order moment generation if any of said poles are unstable, thereby obtaining shifted moments.

Claim 54

The computer apparatus of claim 38 wherein said microelectronic circuit includes a driving point; wherein said traversing means comprises means for traversing said spanning tree of said directed graph to obtain unshifted moments corresponding to the driving point; wherein said shifting means comprises means for shifting said unshifted driving point moments to obtain shifted driving point moments; wherein said pole determining means comprises means for determining driving point poles from said shifted driving point moments; wherein said residue determining means comprises means for determining residues from said unshifted driving point moments and the driving point poles; and wherein said producing means comprises means for producing a time domain simulation of the behavior of said microelectronic circuit from the driving point poles and the residues.

Claim 55

The computer apparatus of claim 51 further comprising: means for determining whether the driving point poles are stable; and wherein said residue determining means comprises means for determining residues of said microelectronic circuit from said unshifted driving point moments of said microelectronic circuit and the driving point poles.

Claim 56

The computer apparatus of claim 37 wherein said traversing means comprises: means for traversing-said spanning tree of said directed graph; means, responsive to said traversing means, for vectorizing the traversal of said spanning tree so as to traverse said spanning tree only once; and means, responsive to said vectorizing means, for obtaining said moments of said microelectronic circuit from the vectorized traversal of said spanning tree.

Claim 57

The computer apparatus of claim 37 wherein said microelectronic circuit includes a resistor loop; and wherein said traversing means comprises: means for traversing said spanning tree with said resistor loop removed; means, responsive to said traversing means, for determining the resistor loop current from the traversal of said spanning tree with said resistor loop removed; and means, responsive to said determining means, for traversing said spanning tree including said resistor loop current to obtain moments of said microelectronic circuit.

Claim 58

A computer apparatus simulating behavior of a microelectronic circuit, comprising: means for storing a representation of said microelectronic circuit in a computer; means, responsive to said storing means, for transforming the stored representation of said microelectronic circuit into an equivalent DC circuit containing resistive and capacitive elements; means, responsive to said transforming means, for converting said equivalent DC circuit for said microelectronic circuit into a directed graph having a spanning tree; means, responsive to said converting means, for traversing said spanning tree of said directed graph to obtain moments of said microelectronic circuit including resistive and capacitive elements; means, responsive to said traversing means, for mapping said moments of said microelectronic circuit into poles and residues for said microelectronic circuit; means, responsive to said mapping means, for simultaneously constraining said mapping to produce stable poles for said microelectronic circuit; and means, responsive to said mapping means and said constraining means, for producing a time domain simulation of the behavior of said microelectronic circuit from the stable poles and residues.

Claim 59

A computer apparatus simulating behavior of a microelectronic circuit, comprising: means for storing a representation of said microelectronic circuit in a computer; means, responsive to said storing means, for transforming the stored representation of said microelectronic circuit into an equivalent DC circuit containing resistive and capacitive elements; means, responsive to said transforming means, for converting said equivalent DC circuit for said microelectronic circuit into a directed graph having a spanning tree; means, responsive to said converting means, for traversing said spanning tree of said directed graph to obtain moments of said microelectronic circuit including resistive and capacitive elements; means, responsive to said traversing means, for mapping said moments of said microelectronic circuit into poles and residues for said microelectronic circuit; means, responsive to said mapping means, for simultaneously constraining said mapping to produce stable poles for said microelectronic circuit; and means, responsive to said mapping means and said constraining means, for producing a time domain simulation of the behavior of said microelectronic circuit from the stable poles and residues.

Claim 60

The computer apparatus of claim 55 wherein said microelectronic circuit includes a resistor loop; and wherein said traversing means comprises: means for traversing said spanning tree with said resistor loop removed; means, responsive to said traversing means, for determining the resistor loop current from the traversal of said spanning tree with said resistor loop removed; and means, responsive to said determining means, for traversing said spanning tree including said resistor loop current to obtain moments of said microelectronic circuit.

Claim 61

The computer apparatus of claim 55 wherein said microelectronic circuit is of tree or near-tree topology; wherein said converting means comprises means for converting said equivalent DC circuit into an ordered nodal analysis matrix; and wherein said traversing means comprises means for factorizing the ordered nodal analysis matrix to obtain moments of said microelectronic circuit.

Claim 62

The computer apparatus of claim 55 wherein said constraining means comprises means for simultaneously constraining said mapping using a transformation function to produce stable poles for said microelectronic circuit.

Claim 63

The computer apparatus of claim 55 wherein said microelectronic circuit comprises a microelectronic interconnect circuit.

Claim 64

The computer apparatus of claim 55 further comprising: means, responsive to said producing means, for modifying said microelectronic circuit in response to the time domain simulation of the behavior of said microelectronic circuit; and means, responsive to said modifying means, for manufacturing the modified microelectronic circuit.