Parasitic effects analysis of circuit structures

The present invention relates generally to analyzing circuit structures for parasitic effects.

Performing electromagnetic effects analysis on circuit structures typically involves calculating field solutions to Maxwell's equations, which govern electromagnetic behavior. Currently, when different circuit structures are to be analyzed, each circuit structure is analyzed from scratch (e.g., full field solutions are calculated), even if one circuit structure is structurally similar to another circuit structure (e.g., the one circuit structure is a sub-structure the other circuit structure) that has already been analyzed. Thus, electromagnetic effects analysis becomes more inefficient, costly, time consuming, and so forth as the number of circuit structures to be analyzed increases.

Method, system, and computer program product for analyzing circuit structures for parasitic effects are provided. The method provides for receiving a first circuit structure for analysis of a parasitic effect, comparing the first circuit structure to a second circuit structure not identical to the first circuit structure to determine whether the second circuit structure is similar to the first circuit structure, and analyzing the first circuit structure for the parasitic effect using data from a previous analysis of the second circuit structure for the parasitic effect when the second circuit structure is similar to the first circuit structure.

FIG. 1 depicts a process for analyzing circuit structures for parasitic effects according to an implementation of the invention.

FIG. 2 illustrates a system for analyzing circuit structures for parasitic effects according to an implementation of the invention.

FIG. 3 shows an approach to calculating field solutions for circuit structures.

FIGS. 4-5 depict approaches to analyzing circuit structures according to implementations of the invention.

FIGS. 6A-6D illustrate sample geometric and topological transformations of a circuit structure.

FIG. 7 shows a table comparing overall costs of utilizing traditional GMRES, KR-GMRES, and MKR-GMRES.

FIG. 8 is a Venn diagram depicting relationships between subspaces.

FIGS. 9A-9B illustrates an example of block reuse according to an implementation of the invention.

FIG. 10 depicts a sample bus structure.

FIG. 11 shows a table showing statistics of repetitive patterns in the sample bus structure of FIG. 10 .

FIG. 12 illustrates an example of a hash key.

FIG. 13 is a block diagram of a data processing system with which implementations of the invention can be implemented.

The present invention generally relates to analyzing circuit structures for parasitic effects. The following description is presented to enable one of ordinary skill in the art to make and use the invention and is provided in the context of a patent application and its requirements. The present invention is not intended to be limited to the implementations shown, but is to be accorded the widest scope consistent with the principles and features described herein.

Analysis of electromagnetic effects (e.g., resistance, capacitance, inductance, and so forth) in circuit structures typically starts with calculating field solutions to Maxwell's equations or some approximation of Maxwell's equations for a circuit structure. Maxwell's equations are a set of equations that describe the interrelationships between, for instance, electric fields, magnetic fields, electric charge, electric current, and so forth.

Current electromagnetic effects analysis approaches focus on efficiently analyzing a single circuit structure with fixed topology (e.g., layout, pattern, placement, or the like) and geometry (spacing, sizing, or the like). However, there is often a desire to vary the topology and/or geometry of a circuit structure and analyze the variations to determine how electromagnetic effects change as topological and/or geometrical changes are made.

With current electromagnetic effects analysis approaches, each variation will usually be analyzed as a separate circuit structure from scratch (e.g., a full field solution will be calculated), even when data from the analysis of other similar variations is available. Hence, as the number of variations/circuit structures increases, electromagnetic effects analysis becomes more inefficient, costly, time consuming, and so forth.

The problems associated with electromagnetic effects analysis also apply to other types of analysis, such as stress analysis, thermal analysis, diffraction analysis, simulation analysis, or the like. As used herein, the term “parasitic effect” analysis will used to refer to any one of the different types of analysis listed above and any other type of analysis that involves solving system of equations.

Depicted in FIG. 1 is a process 100 for analyzing circuit structures for parasitic effects according to an implementation of the invention. At 102 , a first circuit structure is received for analysis of a parasitic effect. The first circuit structure may be at a lower circuit structure level (e.g., wiring level) or may be at a higher circuit structure level (e.g., package level). In one implementation, the parasitic effect for which the first circuit structure is being analyzed is one of stress, thermal, simulation, diffraction, and electromagnetic effect.

At 104 , the first circuit structure is compared to a second circuit structure that is not identical to the first circuit structure. The second circuit structure was previously analyzed for the parasitic effect. A determination is made at 106 as to whether the second circuit structure is similar to the first circuit structure based on the comparison of the two circuit structures. In one implementation, the second circuit structure is similar to the first circuit structure when one of the first circuit structure and the second circuit structure is a sub-structure of the other (e.g., the first circuit structure is a sub-structure of the second circuit structure or the second circuit structure is a sub-structure of the first circuit structure).

The second circuit structure may also be similar to the first circuit structure when, for instance, at least a portion of the first circuit structure and at least a portion of the second circuit structure are topologically the same (e.g., same layout and so forth), but geometrically different (e.g., different spacing, sizing, and so forth), the first circuit structure and the second circuit structure share a sub-structure (e.g., a sub-structure of the first circuit structure is identical to a sub-structure of the second circuit structure), or the like.

If it is determined that the second circuit structure is similar to the first circuit structure, the first circuit structure is analyzed for the parasitic effect using data from the previous analysis of the second circuit structure for the parasitic effect at 108 . For example, a vector (e.g., a Krylov vector, a solution vector, an Eigen vector, a principal component vector, or the like) generated, a matrix assembled, and/or a matrix vector product computed during the previous analysis of the second circuit structure for the parasitic effect may be used to analyze the first circuit structure for the parasitic effect. Hence, a full field solution may not have to be calculated in order to analyze the first circuit structure for the parasitic effect.

On the other hand, if it is determined that the second circuit structure is not similar to the first circuit structure, then analysis of the first circuit structure for the parasitic effect is performed at 110 without data from the previous analysis of the second circuit structure for the parasitic effect. Thus, a full field solution will need to be calculated in order to analyze the first circuit structure for the parasitic effect.

Although in the implementation of FIG. 1 , the second circuit structure was previously analyzed for the same parasitic effect that the first circuit structure is currently being analyzed for, it is not necessary that the parasitic effect previously analyzed be the same as the parasitic effect currently being analyzed in order for data to be reused. For example, the parasitic effect previously analyzed may be a thermal effect, while the parasitic effect currently being analyzed is a stress effect. To give another example, even if the parasitic effect previously analyzed and the parasitic effect currently being analyzed are both electromagnetic effects, one may involve capacitance, while the other may involve inductance.

As seen from above, analysis of a circuit structure for a parasitic effect can be expedited, overhead associated with the analysis can be reduced, and efficiency of the analysis can be improved by using data from previous parasitic effect analysis on one or more other circuit structures that are similar to the circuit structure currently being analyzed. Improvements in analysis may depend on the degree of similarity between the circuit structure currently being analyzed and the one or more other circuit structures previously analyzed. Accuracy of analysis, however, will not be affected by the degree of similarity between the circuit structures.

FIG. 2 illustrates a system 200 for analyzing circuit structures for parasitic effects according to an implementation of the invention. System 200 includes a storage device 202 (e.g., hard drive, memory, floppy disk, or the like) and a field solver 204 in communication with storage device 202 . Storage device 202 stores information (e.g., topology, geometry, or the like) relating to a plurality of circuit structures previously analyzed for at least one parasitic effect as well as data from the at least one parasitic effect analysis previously performed on each of the plurality of circuit structures.

Field solver 204 receives a circuit structure 206 for analysis of one or more parasitic effects. In the implementation of FIG. 2 , none of the plurality of circuit structures previously analyzed is identical to circuit structure 206 . Field solver 204 compares circuit structure 206 to each of the plurality of circuit structures previously analyzed based on the information stored in storage device 202 relating to the plurality of circuit structures to determine whether any of the plurality of previously analyzed circuit structures is similar to circuit structure 206 .

In one implementation, when circuit structure 206 is received for analysis by field solver 204 , field solver 204 receives information relating to circuit structure 206 , such as topology, geometry, or the like. As a result, comparison of circuit structure 206 to the plurality of previously analyzed circuit structures may include comparing the topology and geometry of circuit structure 206 to the topology and geometry of each of the plurality of previously analyzed circuit structures.

When one or more of the plurality of previously analyzed circuit structures are similar to circuit structure 206 , field solver 204 uses some or all of the analysis data stored in storage device 202 for at least one of the one or more previously analyzed circuit structures that is similar to circuit structure 206 to analyze circuit structure 206 for the one or more parasitic effects. Field solver 204 then outputs analysis data 208 for circuit structure 206 . In one implementation, analysis data 208 outputted by field solver 204 is stored in storage device 202 so that analysis data 208 can later be used to analyze other circuit structures.

Calculating a field solution (e.g., solutions to some form of Maxwell's equations) for a circuit structure typically involves solving a system of linear equations Ax=b, where A is an N×N matrix, x is a column vector with N entries, and b is a column vector with N entries. Shown in FIG. 3 is one approach 300 to calculating field solutions for a plurality of circuit structures 302 - 306 . With approach 300 , each of circuit structures 302 - 306 are analyzed separately from scratch even though circuit structures 302 - 306 are similar to one another. In particular, the left element of each circuit structure 302 - 306 is of the same shape and size. Additionally, circuit structures 302 and 304 only differ in terms of spacing between the left and right elements. Further, circuit structures 302 and 306 only differ in terms of sizing of the right element.

FIG. 4 depicts an approach 400 to analyzing circuit structures 302 - 306 in FIG. 3 according to an implementation of the invention. With procedure 400 , all of circuit structures 302 - 306 are analyzed together instead of one at a time. Outputs for circuit structures 302 - 306 are also generated concurrently rather than separately. Further, some or all of the matrices for circuit structures 302 - 306 are implicitly assembled (e.g., assembled based on a previously assembled matrix). In other words, one or more blocks in a matrix are assembled from one or more blocks in a matrix previously assembled.

As a result, the costs associated with analyzing all of circuit structures 302 - 306 through approach 400 in FIG. 4 will be closer to that of the costs associated with analyzing a single circuit structure through approach 300 . In addition, unlike sensitivity or perturbation analysis, approach 400 does not require small perturbation assumptions. Hence, the differences between circuit structures 302 - 306 can be larger. Further, results obtained through approach 400 are exact. There is no approximation error that has to be carefully examined as in sensitivity or perturbation analysis.

Illustrated in FIG. 5 is an approach 500 to analyzing circuit structures 302 - 304 and a new circuit structure 308 that is a composite of circuit structures 302 - 304 according to an implementation of the invention. With approach 500 , a matrix is explicitly assembled and a vector is iteratively solved to produce an output for each of circuit structures 302 - 304 . The matrices assembled for circuit structures 302 - 304 are then used to implicitly assemble a matrix for circuit structure 308 . This can significantly reduce processor time.

Additionally, information collected to solve vectors for circuit structures 302 - 304 can be used to accelerate solving a vector for circuit structure 308 to produce an output. Thus, even though circuit structures 302 - 304 and 308 are analyzed separately, the costs and time associated with analyzing all of circuit structures 302 - 304 and 308 should still be less than if approach 300 was applied to separately analyze circuit structures 302 - 304 and 308 . Further, sensitivity and perturbation analysis would not even be applicable in this situation because the change is way too large for sensitivity and perturbation analysis.

In the sections below, various examples and implementations for analyzing circuit structures for parasitic effects using data from previous parasitic effects analysis of other circuit structures are discussed.

Changing Circuit Structures

To help illustrate how a system of linear equations changes with changing circuit structures, suppose there are i circuit structures to be analyzed. Analysis of the i circuit structures can be characterized as calculating a solution to the following sequence of linear systems

A (i) x (i) =b (i)   (1)

In equation (1), the matrix A (i) ε N×N or the RHS (right-hand side) b (i) ε N may change from one circuit structure to another. For instance, the RHS b may be changed when solving different columns of a multi-conductor problem. Changes to matrix A may result from, for instance, topologic or geometric transformations of a circuit structure.

FIGS. 6A-6D show sample geometric and topologic transformations of a circuit structure 600 . Circuit structure 600 a in FIG. 6A represents circuit structure 600 in its original geometry and topology with four conductors 602 a - 602 d . FIGS. 6B-6D show different examples of geometric/topological transformations to circuit structure 600 . Assume for FIGS. 6A-6D that each conductor 602 corresponds to diagonal blocks of the matrix A in equation (1) and the interaction between conductors 602 corresponds to off-diagonal blocks of matrix A.

Geometric/topologic transformations may change matrix A in different ways. For example, moving a conductor (e.g., moving of conductor 602 b as shown in FIG. 6B ) causes updates to matrix blocks associated with the moved conductor, excluding the diagonal block denoting the interaction of the conductor with itself. Enlarging a conductor (e.g., enlargement of conductor 602 b as shown in FIG. 6C ) causes updates to the corresponding matrix blocks, including the diagonal block. Adding a conductor (e.g., addition of a conductor 602 e as shown in FIG. 6D ) introduces new matrix blocks.

Suppose the matrices of an original circuit structure and an updated circuit structure are A 0 ε N 0 ×N 0 and Aε N×N , respectively, where N 0 and N are not necessarily the same. Then, A can be written as

A=f ( A 0 )+Δ  (2)

In equation (2), Δ is the incremental update and f(A 0 ) denotes the possible expansion or deflation of the matrix due to adding or removing of conductors, which is a simple modification to A 0 . For example, when adding a new block to a system with an existing block, suppose A 22 denotes the interaction of the new block to itself, and A 12 and A 21 are the coupling between the new block and the existing block, then the matrix A can be written as

Thus, f(A 0 ) and Δ can be defined as

With the above definition of the incremental update Δ, problems with and without dimensional change can be treated similarly. Thus, for the sake of simplicity, it can be assumed that the size of A 0 is identical to the size of A. For problems without geometrical/topological change, f(A 0 ) is simply given by f(A 0 )=A 0 .

For problems with geometrical/topological change, assuming the matrix-vector product A 0 v has previously been computed, computing the matrix-vector product Ax by using the previously computed matrix-vector product A 0 v and updating the matrix A 0 with the incremental update Δ should be faster than a regular computation of the matrix-vector product Ax.

To give an example, suppose only a small portion of the matrix A 0 will need to be updated to assemble the matrix A. If the off-diagonal blocks of the matrix A 0 are replaced by low-rank approximations and the incremental update Δ only affects the off-diagonal blocks, then Δv can be calculated quickly. In this case, the size of the updated block is comparable to the unchanged blocks, thus it implies that it is not necessary to assume the update can only be a small portion of the whole matrix.

GMRES with Krylov Recycling

Generalized minimal residual method (often referred to as GMRES), which is a type of Krylov subspace method, is an iterative method that can be used to solve the system of linear equations Ax=b for x. To deal with the problems of incremental system updates resulting from topological/geometrical circuit structure variations, Krylov vector recycling can be used to reduce the number of GMRES iterations.

Assume that all matrices are already right-preconditioned, which means A=ÃM −1 , where à is the actual matrix and M is the pre-conditioner such that the actual solution for the problem would be {tilde over (x)}=M −1 x, where x is the solution for Ax=b.

To solve equation A 0 x=b using GMRES, the residual is first calculated as r 0 =b−Ax 0 with initial guess x 0 . In iteration q, GMRES solves the least squares problem

min zε q (A,r 0 ) ∥r 0 −A z ∥  (5)

by constructing an orthonormal basis in q (A 0 ,b)=span(b,A 0 b, . . . , A 0 q−1 b) using Arnoldi's method, which leads to the following relation

A 0 V q =V q+1 H q   (6)

where V q ε n×q and H q ε (q+1)×q .

For the updated Ax=b systems, in order to recycle the previous generated vectors V q and thus recycle the Krylov subspace, it is necessary to define a subspace projector AV , which project any vector into subspace

=range( P )  (7)

where

P=AV q   (8)

and then the null space projector (I− AV ) actually acts as the contrary role to remove the residual component out of the subspace , i.e., ∀x it satisfies P T AV x=0.

This is comparable to solving the following least squares problem

min∥r 0 −Py∥  (9)

and resulting in the residual for any input vector r 0 .

One way to generate the projector is to perform QR decomposition

AV q =QR  (10)

Equation (9) can then be casted into

min∥r 0 −QRy ∥=min∥ Q T r 0 −Ry∥   (11)

Thus, the solution is given by y=R −1 P T r 0 , and the resulting residual is

r=r 0 −QRy =( I−QQ T ) r 0   (12)

The projector can then be defined as AV =QQ T .

With the definition of the subspace projector, GMRES with Krylov recycling (KR-GMRES) can be described as follows:

1) Given an initial residual r 0 associated with a guess x 0 , first remove its components out of subspace by

r 1 =( I− AV ) r 0   (13)

2) Then perform GMRES iteration to generate Krylov subspace = m [( I− AV ) A,r 1 ] using Arnoldi's process with r 1 /∥r 1 ∥ as the starting vector and (I− AV )A as the operator, and minimize the residual in union subspace

= ∪   (14)

The use of (I− AV )A as the operator assures that the new generated subspace is orthogonal against subspace .

To analyze the computational complexity, before doing the real iteration when solving the updated system, q matrix-vector products may be performed to obtain P=AV q . The multiplication can be performed in an incremental manner as AV q =(A 0 +Δ)V q , where AV q is already performed in the previous GMRES iteration in equation (6). The cost is determined by the number of recycled vectors times the number of non-zeros in Δ. Suppose the non-zeros in Δ is k′N, then the cost for ΔV q is (k′qN). The value of k′ depends on the problem, but typically k′<<k, where kN is the number of non-zeros in A.

Another overhead cost is that to solve the least squares problem in equation (9), or to calculate the orthogonal projector AV with QR decomposition, O(q 2 N) time is needed. This time can be regarded as trivial if A is a numerically dense matrix, since a matrix-vector product needs O(N 2 ) cost, and typically q 2 <<N. With certain field solvers, however, the complexity of matrix-vector product is O(kN), where k is usually in the hundreds. Hence, the recycling cost is equivalent to q 2 /k times of matrix-vector product. As q increases, the ratio of q 2 /k increases quadratically, which limits the number of recycled vectors.

GMRES with Modified Krylov Recycling

The quadratic increase of projection cost in GMRES with Krylov recycling is due to the QR decomposition, which is used to solve the least squares problem in equation (9). The drawback of using QR decomposition is that it cannot be performed incrementally. Hence, every time the matrix updates, a full QR decomposition should be done, even for a tiny modification. To overcome this, GMRES with modified Krylov recycling (MKR-GMRES) is used according an implementation of the invention. With MKR-GMRES, an incrementally updatable method is used to solve the least squares problem, which can be done using the pseudo inverse.

Pseudo Inverse

The pseudo inverse of a matrix P is defined as

P + =(P T P) −1 P T   (15)

and with the definition, the solution of the least squares problem in equation (9) can be simply written as

y=P + r 0   (16)

then the minimized residual is r 1 =(I−PP T )r 0 , which means the orthogonal projector can be defined as AV =PP + .

The pseudo inverse exists for any matrix P with full column rank. But it is not so commonly used as QR decomposition for solving the least squares problem since, for general cases, the matrix P T P is not provably stable, and thus the inverse of it may encounter numerical problems.

In this case, however, P=AV, where V is orthonormal. Thus, it is provable that the condition number of P T P is strictly bounded using the following theorem.

Theorem 4.1: If V q is orthonormal, then with P defined in Equation (8), cond(P T P)≦cond(A T A) Proof:

Theorem 4.1 indicates that matrix P T P is never worse than A T A in terms of condition number, provided that V q is orthonormal. In integral equation based parasitic parameter extraction, the matrix A is generally well conditioned, plus in practice, the use of pre-conditioner further improves the condition, thus, the numerical problem here will not be too bad.

Incremental Update of Pseudo Inverse

From definition (15), to perform the incremental update of pseudo inverse, the first step is to update P, which can be done using

P=A 0 V q +ΔV q   (20)

With this assumption, the projector can be written as

P T ⁢ P = ( A 0 ⁢ V q + Δ ⁢ ⁢ V q ) T ⁢ ( A 0 ⁢ V q + Δ ⁢ ⁢ V q ) = P 0 T ⁢ P 0 + P 0 T ⁢ Δ ⁢ ⁢ V q + V q T ⁢ Δ ⁢ ⁢ P 0 + V q T ⁢ Δ ⁢ ⁢ V q ( 21 )

where P 0 =A 0 V q . The first term in the equation (21) can be obtained using equation (6)

P 0 T P 0 = H q T H q   (22)

Other terms in equation (21) can be calculated by exploiting the property of Δ. Otherwise, if, for example, P 0 T (ΔV q ) is calculated directly, the cost is q 2 N since ΔV q is dense.

For different field solvers, Δ has different forms. In a hierarchical solver, the matrix A can be decomposed as

A=J T MJ  (23)

where Jε R×N and Mε R×R are both sparse matrix. J is a projection matrix with blocks being either 1 or 0. The update of system only occurs in interaction matrix M, thus Δ can be written as

Δ=J T Δ M J  (24)

where Δ M is a sparse matrix with non-zeros distributed in only some small number of columns and rows. Thus, the term P 0 T ΔV q can be calculated as

P 0 T ΔV q =( P 0 T J T )Δ M JV q   (25)

The term of P 0 T J T and Δ M JV q are calculated separately, where the cost O(k′qN) for Δ M JV q is not additional one, since it is already done when updating P.

Suppose Δ M has N pi (subscript ‘pi’ stands for ‘pseudo leaf’ to be discussed below) rows with non-zero blocks, the cost for (P 0 T J T )Δ M JV q is q 2 N pi . For incremental updating systems, N pi <<N. Thus, the cost is much less than q 2 N.

For the last term in equation (21), the calculation is similar, and the cost is provable to be 3/2q 2 N pi . The whole cost to update pseudo inverse P + includes the update of P, which is k′qN and the inverse of P T P, which can be done using Cholesky decomposition in O(q 3 ) time. In this context, q<<N, thus, the cost of inverse of P T P is omitted.

Krylov Recycling with Pseudo Inverse

Suppose V q is the Krylov vectors to be recycled, the first step to recycle the Krylov subspace is to minimize the residual in range (V q ), resulting in the following least squares problem

min xεrange(v q ) ∥r 0 −Ax∥=∥r 0 −Py∥   (26)

which can be done by y=P + r 0 , and thus the following residual and solution are obtained

r 1 =( I−PP + ) r 0   (27)

x 1 =x 0 +V q P + r 0   (28)

By right multiplying P T to both sides of equations (27) and (28), and using equation (15), it is verified that r 1 ⊥P.

In the second step, an Arnoldi's procedure with (I−PP + )A as the operator and v 1 =r 1 /∥r 1 ∥ as the starting vector is performed to generate new orthonormal vectors V m , which produces the following Arnoldi's relation

( I−PP + ) AV m =V m+1 H m   (29)

The null space projector (I−PP + ) ensures that V m+1 ™P. When AV q =P is placed on both sides of equation (29), the following equation results

A ⁢ [ V q V m ] = [ P V m + 1 ] [ I B 0 H _ m ] ( 30 )

where B=P + AV m . By defining

V = [ V q V m ] , W = [ P V m + 1 ] , G = [ I B 0 H _ m ] ,

equation (30) can be recast into

AV=WG  (31)

At the end of each iteration, the following least squares problem is solved

min xεrange(V) ∥r 0 −Az ∥=min∥ r 0 −WGy∥   (32)

which can be reduced to the (m+q+1)×(m+q) least squares problem

Gy ≈( W T W ) −1 W T r 1   (33)

Since W=[P V m+1 ] and V m+1 ⊥P,

Thus, with the definition of P + , equation (33) can be cast into

G y ≈ [ P + V m + 1 T ] ⁢ r 1 =  r 1  ⁢ e q + 1 ( 35 )

where e q+1 is the q+1 column of a unit matrix. The last equal sign in equation (35) exploits the fact that r 1 ⊥P and thus P + r 1 =0.

Below is an algorithm of the modified Krylov recycling method according to an implementation of the invention.

MKR-GMRES(A k+1 , b, x, V q , P q )

Calculate P=A k+1 V q and P + incrementally x 1 =VP + b, r 1 =(I−PP + )b v 1 =(I−PP + )Av m , B j,m =P j T (Av m ) w=(I−PP + )Av m , B j,m =P j T (Av m ) while ∥r m ∥>tol do

Depicted in FIG. 7 is a table 700 comparing the overall costs for traditional GMRES, Krylov Recycling GMRES (KR-GMRES), and Modified Krylov Recycling GMRES (MKR-GMRES). For traditional GMRES, the cost is solely due to iteration, which includes the cost for matrix-vector product and vector orthogonalization. For KR-GMRES and MKR-GMRES, the cost includes the projection time and iteration time. KR-GMRES and MKR-GMRES have the same number of iterations since the same subspace is recycled. The cost for each iteration in KR-GMRES and MKR-GMRES is also the same. The difference between KR-GMRES and MKR-GMRES lies in the projection time.

Enriching Recycled Subspace

The sections above relating to Krylov recycling assumed that the recycled subspace was limited to the Krylov subspace from previous GMRES iterations because

1) the Krylov subspace is a good approximation of the full space, since it contains the ‘exact’ solution for the previous system, and 2) the matrix-vector product AV q can be done incrementally

It is possible to recycle some other subspaces that also satisfy the two criterions. One of the ways to do this is to deflate the given Krylov subspace to form a smaller subspace that captures the essence of the Krylov subspace. This can be done by choosing the harmonic Ritz vectors corresponding to the smallest harmonic Ritz values. The advantage of this is the reduction of the overhead cost. The number of iterations, however, will not be reduced since the deflated subspace is a subset of the Krylov subspace.

Partitioned-And-Shifted Krylov Recycling (PSKR)

Suppose a Krylov subspace is given as V, if all the unknowns can be clustered as groups, correspondingly, the vectors V can also be partitioned as

The partition can be done spatially. For example, it can be in terms of the number of conductors, i.e., vectors V i corresponds to all unknowns in the i-th conductor.

A block diagonal matrix can be given as follows by shifting the blocks in matrix (36)

It can be verified that range(V)⊂range(V′), and therefore, another candidate for subspace recycling could be span(V′). One advantage of recycling V′ is that there is no additional cost to calculate P=AV′ compared to calculating AV, while V′ spans a bigger subspace that covers the subspace spanned by V. Thus, with the same cost of matrix-vector product, a larger subspace is obtained.

One drawback of recycling V′ is that it increases the size of recycle subspace from q to nq, which increases projection cost. In addition, after each GMRES solution, the matrix P iT P is required to be calculated, which requires n 2 q(q−q 0 )N/2 time, where q 0 and q are the numbers of Krylov vectors before and after the latest GMRES solution.

Another problem is that V′ is no longer an orthonormal matrix, and it is not guaranteed to be linear independent. Consequently, the product matrix P′ may also be linear dependent. In this case, the MKR-GMRES will fail.

To resolve the problem, a QR decomposition of V′ can be performed using the Gram-Schmidt process, resulting in

Q′R′=V′  (38)

during which if there is a linear dependent vector, the corresponding diagonal blocks of R′ would be close to zero. Hence, linear dependent vectors can be found and removed. By doing this, the resulting V′ is guaranteed to be full rank, and so is the product P. This can be done in an block-wise manner with q(q−q 0 )N time.

The QR decomposition in equation (38) can be done incrementally, unlike the QR decomposition discussed earlier, since V′ is invariant with the update of A. Therefore, Gram-Schmidt only needs to be performed for newly added vectors.

To further improve the numerical stability, Q′ can be chosen to replace V′ as the recycled vectors. This requires the following calculation to be performed

P′=PR′ −1 =AQ′  (39)

which can be done incrementally in O[nq(q−q 0 )N] time, considering the block-wise structure of R′. In the cases that iteration cost dominates overall cost, it is still useful to recycle V′.

Partitioned-And-Shifted Solution Recycling (PSSR)

Another recycling option is to recycle solution vectors. Suppose that a certain number (q s ) of systems have previously been solved. Hence, there are q s solution vectors stored in matrix X. Similar to matrix (36), the solution can be partitioned in terms of clustered unknowns and shifted like matrix (37)

A subspace of nq s can then be obtained. Typically q s <<q. Since span(X)⊂span(V q ), span(X′)⊂span(V′) can be verified.

The inclusion relations between subspaces spanned by V q , V′, X, and X′ is illustrated in FIG. 8 as a Venn diagram 800 . In Venn diagram 800 , span(V′) is the biggest subspace, V q and X′ are both subsets of V′, and the solution subspace is in the intersection of span(V q ) and span(X′). All four subspaces cover the solutions. Hence, for a small matrix update, all of the subspaces can lead to the final solution without performing iterations.

Accelerating the System Setup

Previous sections discussed approaches to reduce the cost for solving a series of incrementally changing systems. However, solving the system is only one part of the total computation. The other is setting up the matrix in the linear system. The matrix is sometimes obtained through expensive potential integral (e.g., from Galerkin or Collocation schemes). As a result, the setup time may dominate the overall cost.

Sometimes, the dense diagonal blocks of the matrix are only calculated for the first system analyzed and only low-rank off-diagonal blocks are calculated when system changes are made. Thus, the average system setup time in terms of all systems may be reduced.

However, because the application of Krylov recycling reduces the system solving cost, the system setup time will play a more important role. In addition, for other kinds of incremental problems, such as problems with new blocks being added in an update, full-rank and dense blocks will still need to be calculated. Therefore, reducing setup time will further reduce overall cost.

In typical circuit design, the problems are not arbitrarily structured. As a result, there are some common properties, which make it possible to reuse system setup

1) Most of interconnects are cubic and placed in Manhattan manner 2) Coordinates of the layout are subject to a minimum step size, which can be represented by an integer after being scaled 3) Interconnects in the same layer have the same thickness 4) Many interconnects have the same width and/or length

Block Matrix Reuse

Consider a structure 900 comprising two identical conductors 902 and 904 with a square cross section, as shown in FIGS. 9A-9B . Each face of conductors 902 - 904 is assigned a number as its label. After meshing, as shown in FIG. 9B , each pair of faces corresponds to a block matrix in the final linear system. For example, the pair (1,2) corresponds to matrix block A 12 , and (1,1) corresponds to diagonal matrix block A 11 , and so forth.

If the faces are meshed in the same way, and each meshed panel in these faces are labeled in the same order, then it is clear that A 11 =A 22 =A 33 =A 44 and A 12 =A 34 , since they are equivalent to the same ‘patterns’. Hence, the block matrix for each pattern needs to be calculated only once, and reused as many times as the number of duplication.

Below is an algorithm to determine whether a pair of root panels is equivalent to an existing pattern according to an implementation of the invention.

PatternMatch(Panel P src , Panel P eval )

1) Rotate and move P src to a standard position, where a standard position means

The center of the panel is on the origin The panel is in x-y plane, and all of the edges are alone x- or y-directions The first corner (defined in input) of the panel are in the 3 rd quadrant

2) Perform the same transformation to P eval . The position relations between the transformed P src and the transformed P eval is called a pattern. 3) Search in the pattern library, if there exists the identical pattern, return true. Patterns are identical if

The first corners of P src in both patterns are identical, and In both patterns, P eval are identical in shape, in the same position, or symmetrical in z-direction

4) If the pattern does not exist in the library, insert the pattern into library and return false

In the above algorithm, the first panel is transformed to a standard position through rotation and shift. The first panel is then compared to the position and orientation of the second panel. Since the order of panels may be critical, in one implementation, the corners of panels are labeled and when comparing, the panels should be matched corner by corner.

Based on the pattern matching algorithm above, set forth below is a block reuse algorithm according to an implementation of the invention.

SetupWithBlockReuse(PanelList panelList)

For each pair of root panels P i and P j in panelist, do the following

If PatternMatch(P i , P j )=false, calculate block matrix A ij Otherwise, link a pointer to the corresponding existing block matrix

FIG. 10 depicts a sample 10×10 bus structure 1000 . A table 1100 indicating statistics of repetitive patterns in bus structure 1000 is illustrated in FIG. 11 . The left column of table 1100 is the top 5 patterns with most non-zeros when using hierarchical meshing. The right column is the corresponding repetition times. Each repetitive pattern needs to be calculated only once, and thus considerable time can be saved.

Hash Table

The block reuse method tries to find the redundancy before meshing. Another way to reduce the setup time is to find and make use of the redundancy after meshing, which can be done using a hash table. Referring back to FIG. 9B , the shapes of many leaf (e.g., meshed) panels are identical and as such, the self-coefficients are identical and need to be calculated only once. This can be done by building a library. Given a pair of panels, a library of previously analyzed panels could be searched using pattern recognition. If the pattern exists in the library, then no potential integral is needed, otherwise the coefficient is calculated, and size and positional information, as well as the corresponding coefficient are added to the library.

A hash table can be used to implement the library, where key-value pairs can be inserted into the hash table and the table can be looked up quickly using a hash code. The hash code is an integer number that serves as a digital “fingerprint”. The design of hash code determines the efficiency of the table look-up.

In the hash table, the hash key is unique and the hash code can be shared by different hash keys. When multiple hash keys share a hash code, the situation is referred to as a conflict. If a conflict occurs, then additional comparison will need to be done to pick the desired panel. Thus, a conflict is supposed to be avoided. However, to a design a never-conflict hash code generally requires large amount of computation. Thus, the principal in designing a hash code is to have balance between the computational complexity of the key and the probability of conflict.

FIG. 12 shows an example of a hash key 1200 comprising three 3-D vectors, which used to uniquely describe a panel pair. In FIG. 12 , it is supposed that one of the panels (panel # 1 ) is already located in standard position. The first vector v 1 denotes the size (in x- and y-direction) of panel # 1 . The second vector v 2 denotes the relative coordinate of the centroid of panel # 2 . The third vector v 3 denotes the size and orientation of panel # 2 .

Due to symmetrical invariant of coefficient of potential, two patterns can be regarded as identical if the corresponding vectors v 1 , v 2 , and v 3 are identical in terms of their absolute value. The rotation of the first panel in order to transform it to standard position may have already been done in, for example, the block reuse stage. Hence, there is no additional cost, except for moving the panel to the origin. Since the pattern can be uniquely described by vectors v 1 , v 2 , and v 3 , the 3-D vector can be encoded into an integer using any prime-number based methods.

In one implementation, a two-level hash table is used. The first level hash table uses v 1 as the key and hash(v 1 ) as the hash code. The second level hash table uses v 2 and v 3 as the hash key, but only hash(v 2 ) as the hash code.

For a certain panel pair, by looking up the first level hash table, panel # 1 is matched, and a pointer of a second level hash table associated with given v 1 is found. The look-up of the first level hash table can be reused by appropriately arranging the order of potential coefficient calculation.

In the second level hash table, since only v 2 is used to generate the hash code, conflict will occur if different patterns have the same v 2 , but different v 3 . This is acceptable because the comparison cost is relatively small, and the probability for this kind of conflict is also small for realistic cases.

As seen in the discussions above, many types of data generated during parasitic effects analysis of circuit structures can be recycled and/or reused to improve the efficiency, cost, timing, and so forth associated with parasitic effects analysis of additional circuit structures. Specifically, recycling various types of vectors, reusing matrices, and hierarchically applying the recycling and/or reuse of data assist in reducing costs, increasing efficiency, expediting analysis, and so forth. In addition, the ideas herein may be applicable to other engineering problems involving linear partial differential equations, such as structural analysis, aerodynamic analysis, or the like.

The invention can take the form of an entirely hardware implementation, an entirely software implementation, or an implementation containing both hardware and software elements. In one aspect, the invention is implemented in software, which includes, but is not limited to, application software, firmware, resident software, microcode, etc.

Furthermore, the invention can take the form of a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer or any instruction execution system. For the purposes of this description, a computer-usable or computer-readable medium can be any apparatus that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.

The medium can be an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system (or apparatus or device) or a propagation medium. Examples of a computer-readable medium include a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk, and an optical disk. Current examples of optical disks include DVD, compact disk-read-only memory (CD-ROM), and compact disk-read/write (CD-R/W).

FIG. 13 depicts a data processing system 1300 suitable for storing and/or executing program code. Data processing system 1300 includes a processor 1302 coupled to memory elements 1304 a - b through a system bus 1306 . In other implementations, data processing system 1300 may include more than one processor and each processor may be coupled directly or indirectly to one or more memory elements through a system bus.

Memory elements 1304 a - b can include local memory employed during actual execution of the program code, bulk storage, and cache memories that provide temporary storage of at least some program code in order to reduce the number of times the code must be retrieved from bulk storage during execution. As shown, input/output or I/O devices 1308 a - b (including, but not limited to, keyboards, displays, pointing devices, etc.) are coupled to data processing system 1300 . I/O devices 1308 a - b may be coupled to data processing system 1300 directly or indirectly through intervening I/O controllers (not shown).

In the implementation, a network adapter 1310 is coupled to data processing system 1300 to enable data processing system 1300 to become coupled to other data processing systems or remote printers or storage devices through communication link 1312 . Communication link 1312 can be a private or public network. Modems, cable modems, and Ethernet cards are just a few of the currently available types of network adapters.

While various implementations for analyzing circuit structures for parasitic effects have been described, the technical scope of the present invention is not limited thereto. For example, the present invention is described in terms of particular systems having certain components and particular methods having certain steps in a certain order. One of ordinary skill in the art, however, will readily recognize that the methods described herein can, for instance, include additional steps and/or be in a different order, and that the systems described herein can, for instance, include additional or substitute components. Hence, various modifications or improvements can be added to the above implementations and those modifications or improvements fall within the technical scope of the present invention.