Computing resistance sensitivities with respect to geometric parameters of conductors with arbitrary shapes

A computer system selects a shape included in an integrated circuit's layout file, and then selects a first contact and a second contact located on the shape. Next, the computer system computes a nominal resistance between the first contact and the second contact based upon a nominal boundary of the shape, and then computes an adjoint system vector based upon a perturbed boundary of the shape. Using the adjoint system vector, the computer system computes a resistance sensitivity between the first contact and the second contact. In turn, the computer system simulates the integrated circuit using the computed nominal resistance and the computed resistance sensitivity.

BACKGROUND

Manufacturing variability affects integrated circuit resistance values at various points on the integrated circuit. For example, lithography, etching, and chemical-mechanical polishing, whether systematic or random, may combine to impact the boundaries of “shapes” printed on a wafer, thus leading to variations in their electrical properties. These shapes may correspond to pads, a device (e.g., transistor), wires, and/or vias that connect conductors between two metal layers or between a device layer and a metal layer.

SUMMARY

A computer system selects a shape included in an integrated circuit's layout file, and then selects a first contact and a second contact located on the shape. Next, the computer system computes a nominal resistance between the first contact and the second contact based upon a nominal boundary of the shape, and then computes an adjoint system vector based upon a perturbed boundary of the shape. Using the adjoint system vector, the computer system computes a resistance sensitivity between the first contact and the second contact. In turn, the computer system simulates the integrated circuit using the computed nominal resistance and the computed resistance sensitivity.

DETAILED DESCRIPTION

Certain specific details are set forth in the following description and figures to provide a thorough understanding of various embodiments of the disclosure. Certain well-known details often associated with computing and software technology are not set forth in the following disclosure, however, to avoid unnecessarily obscuring the various embodiments of the disclosure. Further, those of ordinary skill in the relevant art will understand that they can practice other embodiments of the disclosure without one or more of the details described below. Finally, while various methods are described with reference to steps and sequences in the following disclosure, the description as such is for providing a clear implementation of embodiments of the disclosure, and the steps and sequences of steps should not be taken as required to practice this disclosure. Instead, the following is intended to provide a detailed description of an example of the disclosure and should not be taken to be limiting of the disclosure itself. Rather, any number of variations may fall within the scope of the disclosure, which is defined by the claims that follow the description.

The following detailed description will generally follow the summary of the disclosure, as set forth above, further explaining and expanding the definitions of the various aspects and embodiments of the disclosure as necessary.

FIG. 1is a diagram showing a shape's nominal boundary being distorted into a perturbed boundary due to manufacturing effects such as diffusion and polysilicon rounding. Shape100, in an ideal world, has nominal boundary110. Shape100may be, for example, a pad, part of a device (e.g., transistor), and includes contacts120-150and holes160-170. The disclosure described herein also pertains to perturbations in wires and vias, such as those connecting conductors between two metal layers or between a device layer and a metal layer (seeFIG. 7and corresponding text for further details). In one embodiment, nominal resistance and resistance sensitivities are computed for non-homogeneous conducting mediums, such as copper interconnected with high-resistively liners or multilayered vias that connect transistors to a first metal layer.

Manufacturing effects may cause nominal boundary110to “distort” during manufacturing. The example shown inFIG. 1shows that nominal boundary110distorted to perturbed boundary180. This distortion changes the resistance between contacts120-150, which may change the overall performance of an integrated circuit. For example, a signal may propagate through shape100and, if not simulated correctly, the signal may cause a race condition (critical path) in an actual device and introduce intermittent failures.

In order to effectively simulate an integrated circuit, this disclosure computes resistance variations of an integrated circuit's “shapes” caused by manufacturing effects. This disclosure computes resistance variations using resistance sensitivities with respect to shape perturbations due to manufacturing effects. In turn, the resistance sensitivities are utilized during simulation to effectively simulate the integrated circuit (seeFIGS. 3-4and corresponding text for further details).

FIG. 2is a diagram showing a shape with an overlayed triangular mesh for finite element method (FEM) computations. Shape200includes nominal boundary210, which corresponds to nominal area220. Nominal area220yields a “nominal resistance” between two contacts. As discussed above, manufacturing effects cause a distorted boundary, such as perturbed boundary230, which corresponds to variation area240and yields a “resistance variation” (computed using resistance sensitivity). As can be seen, the triangular mesh's internal nodes are unaltered, while the triangular mesh's boundary nodes fluctuate with perturbed boundary230. As such, this disclosure computes the overall resistance of shape200by combining the nominal resistance with the resistance variation (positive or negative) (seeFIGS. 3-4and corresponding text for further details).

FIG. 3is a high-level flowchart showing steps taken in designing and simulating an integrated circuit. Processing commences at300, whereupon processing receives input from integrated circuit designer305for designing the integrated circuit at step310. At step320, processing generates a layout file (nominal layout file) based upon the integrated circuit's design and process parameters, and stores the nominal layout file in layout store325. Layout store325may be stored on a nonvolatile storage area, such as a computer hard drive.

Next, processing retrieves manufacturing process variations from process variations store335and generates a perturbed layout file based upon the nominal layout file and the process variations. For example, the nominal layout file may include straight lines and sharp angles, while the perturbed layout file may include arbitrary shapes (seeFIGS. 5A-7and corresponding text for further details). Process variations store335may be stored on a nonvolatile storage area, such as a computer hard drive.

Next, processing computes resistance sensitivities for the arbitrary shapes included in the perturbed layout file using a finite element method and an adjoint method (pre-defined process block340, seeFIG. 4and corresponding text for further details). Processing stores the resistance sensitivities in resistance store345. Resistance store345may be stored on a nonvolatile storage area, such as a computer hard drive. Processing then simulates the integrated circuit using the computed resistance sensitivities at step350, and processing ends at360.

FIG. 4is flowchart showing steps taken in computing resistance sensitivities for arbitrary shapes. Processing commences at400, whereupon processing analyzes shape and technology information from a perturbed layout file located in layout store125(step405). The perturbed layout file was generated inFIG. 3and is based upon particular manufacturing anomalies.

At step410, processing selects a shape and identifies contacts on the shape. Processing then assembles a system matrix (M) input vector (B), and output vector (CT) for finite element method (FEM) computations. As those skilled in the art can appreciate, the system matrix is a table with a matrix of coefficients for mijpoints where i and j are the global indices of the nodes of triangles (seeFIGS. 8A-Cand corresponding text for further details). At step415, processing computes a nominal resistance using Finite Element Method formulas:
Mv=B; (System Formula)  (1)
Iq=CTv; (Total Current through portq)  (2)
R=1/Iq(Resistance)  (3)

Since sensitivity is of interest, processing uses an explicit system formula of (1) above, resulting in
M(P)v(P)=B(P)  (4)
where “P” is a vector of geometrical parameters, such as the dimensions of a shape and the relative position of the contacts within the shape. As such, the impact of the variation of such parameters “P” on the computed resistances may be effectively evaluated. Using the explicit system formula (4) above, processing uses the assembled system matrix M and input vector B to compute v(P).

Processing then uses formula (2) above and computes Iqusing CTand the computed v. Finally, processing uses formula (3) above to compute the nominal resistance R based upon the computed Iq(refer to the Resistance Calculation section below,FIGS. 8A-C, and corresponding text for further details).

At step420, processing computes the derivative of the system matrix M relative to the vector P (system matrix derivative, refer to the Derivative Computation section below,FIGS. 8A-C, and corresponding text for further details). Processing selects a contact located on the selected shape at step425. For example, referring toFIG. 1, processing selects contact120as “p.” At step430, processing assigns a potential of “1” to the selected contact and a potential of “0” to the other contacts located on the selected shape. Referring back toFIG. 1, processing assigns a potential of “1” to contact120and a potential of “0” to contacts130-150.

Next, at step435, processing computes a derivative of the input vector B (input vector derivative), which was assembled back in step410. Processing then computes a derivative of the output vector C (output vector derivative, step440), which was also assembled back in step410(refer to the Derivative Computation section below,FIGS. 8A-C, and corresponding text for further details).

At step445, processing uses the system matrix (M) and output vector (C) assembled above to solve for the adjoint system vector (A) using the adjoint system formula:
MΛ=C=>Λ=CM−1(5)

Using formula (2) above, the derivative of output current Iqwith respect to P (output current derivative) is:
dIq/dP=(dCT/dP)v+CT(dv/dP)  (6)

Using formula (9), processing computes the derivative of the output current dIq/dP at step450.

As discussed in step415, R=1/Iq. As such, the derivative of R=1/Iqwith respect to P yields:
dRpq/dP=−R2pq(dIq/dP)  (10)

Processing uses formula 10 at step455to compute the resistance sensitivity dRpq/dP and store the resistance sensitivity in resistance store145. A determination is made as to whether there are more contacts to select on the selected shape (decision460). For example, referring back toFIG. 1, processing may select contact130(which processing subsequently assigns a potential of “1” and a potential of “0” to the other contacts). If there are more contacts to select, decision460branches to “Yes” branch462, which loops back to select and process the next contact. This looping continues until there are no more contacts to select, at which point decision460branches to “No” branch468.

A determination is made as to whether there are more shapes to select in the layout (decision470). If there are more shapes to select, decision470branches to “Yes” branch472, which loops back to select and process the next shape. This looping continues until each shape is processed, at which point decision470branches to “No” branch478whereupon processing returns at480.

FIG. 5Ais a diagram showing a nominal shape with a nominal boundary. Nominal shape500is included in a nominal layout file, which includes nominal boundary510. When nominal shape500is manufactured, however, the edges and corners do not end up as shown inFIG. 5A. Rather, nominal shape500is distorted, such as that shown inFIG. 5B.

FIG. 5Bis a diagram showing a perturbed shape with a perturbed boundary. Perturbed shape520is included in a perturbed layout file, which includes perturbed boundary530. Perturbed shape520is representative of nominal shape500after manufacturing. As such, perturbed shape520, which includes perturbed boundary530, must be considered when computing resistance sensitivities for simulation purposes. The disclosure described herein may also be applied to three dimensional shapes (seeFIG. 6A-7and corresponding text for further details).

FIG. 6Ais a diagram showing a nominal shape with a nominal boundary. Nominal shape600is designed to reside in a vertical plane (Z) relative to substrate layer610's plane, and is included in a nominal layout file, which includes nominal boundary620. When nominal shape600is manufactured, however, the top, sides and corners do not end up as shown inFIG. 6A. Rather, nominal shape600is distorted, such as that shown inFIG. 6B.

FIG. 6Bis a diagram showing a perturbed shape with a perturbed boundary. Perturbed shape630is included in a perturbed layout file and includes perturbed boundary650. Perturbed shape630is representative of nominal shape600after manufacturing. As such, perturbed shape630, which includes perturbed boundary650, must be considered when computing resistance sensitivities for simulation purposes (seeFIG. 6A,7and corresponding text for further details).

FIG. 7is a diagram of a transistor and a perturbed via. Diagram700includes a transistor's source720, gate730, and drain740. Drain740couples to wire710through via750. In an ideal situation, via750's boundary edges would be perpendicular to wire710. However, due to manufacturing anomalies, via750has a perturbed boundary. The disclosure described herein provides the capability to compute via750's resistance sensitivity with its perturbed shape, and perform simulation using via750's computed resistance sensitivity.

A further detail description is below regarding resistance calculations, finite element method computations, adjoint sensitivity analysis, output function definition, and computing derivatives with respect to the geometrical parameter vector P. Some symbols in the description below may not be the same as those used in the above description. For example, the description above uses the symbol “v” for potential and the description below uses the symbol “φ” for potential. Those skilled in the art can appreciate and correlate the symbols used in the description below with the symbols used in the description above.

In a variation-aware VLSI extraction flow, both the nominal resistance and the sensitivity of the resistance to the geometrical variations may be utilized to predict the resistance of a slightly perturbed shape. More precisely, one may approximate the resistance function using a multivariate, first-order Taylor expansion

R=R0+∑m⁢∂R∂pm⁢Δ⁢⁢pm(11)
where Δpmis the perturbation around a nominal value of a parameter “pm,” and δR/δpmis the sensitivity (expressed as a partial derivative) of the resistance with respect to such perturbation. An algorithm for computing such sensitivities for conductors of arbitrary shapes is presented in this disclosure. In particular, a FEM resistance calculation tool may be augmented with a sensitivity calculation capability using adjoint variational analysis.

In a VLSI layout extraction flow, FEM may be used in two different approaches. The first approach is to compute accurate look-up tables of specific wiring patterns for which the wire-like resistance formula will fail. Such computations are done off-line and do not impact the processing cost of the resistance extraction step. The second approach is on-line where FEM is applied very selectively. In the latter approach, caching and pattern recognition are extensively employed to reduce the number of times the FEM solver is actually called. Another important aspect is that in the full layout extraction flow, the overall performance is gated by the capacitance extraction phase rather than the resistance extraction phase. This disclosure discusses FEM-based resistance sensitivities within the overall VLSI layout extraction context.

Resistance Calculation

Resistance calculation is governed by the following partial differential equations:
∇·(σ(r)(−∇φ(r)))=0rεD
σ(r)(−∇φ(r))·{circumflex over (n)}=0rε∂Dnc
φ(r)=φ0rε∂Dc(12)

where φ(r) is the electric potential, σ(r) is the electric conductivity of the material, D is the closed domain of the problem, δDncis the union of the boundary segments which are not assigned a particular potential (referred to as non-terminal), δDcis the union of the boundary segments which are assigned a specific potential (referred to as terminal), and {circumflex over (n)} is the normal to the boundary surface. The second equation is the Neumann boundary condition at the non-terminal boundary of the problem and indicates that the current does not flow outside of the metal (the perpendicular current component vanishes). The last equation is the Dirichlet boundary condition at the terminals with prescribed potential φ0. For a set of Nccontacts the resistance between contacts p and q is computed by assigning unit potential to contact p (e.g., φp=Vp(=1), and assigning zero potential to all other contacts. In turn, formula 12 above may be solved to find φ(r) everywhere in D and subsequently computes the total current entering contact q as

Iq=∫∂Dcq⁢σ⁡(r)⁢(-∇ϕ⁡(r))·n^⁢⁢ⅆS
where δDcqis the boundary of contact q. In turn, the required resistance is R(p,q)=Vp/Iq. As can be seen, one simulation is required to compute an entire row of the resistance matrix R(p,x): 1≦x≦Nc.
Finite Element Method (FEM)

For the sake of simplicity, FEM is discussed below in a two-dimensional (2D) aspect. As those skilled in the art can appreciate, FEM as discussed below may also be extended to a three-dimensional aspect. Since formula (12) above has mixed Dirichlet-Neumann boundary conditions, the continuous FEM formulation is derived from minimizing the following energy functional:
E(φ(x,y))=∫Dσ(x,y)∇φ(x,y)·∇φ(x,y)dxdy(13)

Referring to FIG.8A's diagram800, which includes contacts805and810, in order to solve for φ(r), the geometry is first subdivided into smaller elements. For 2D structures, the Delaunay triangulation is used for the discretization, since it tends to guarantee triangles of reasonable aspect ratios. The resulting elements are described by the coordinates of their nodes. Each node has a unique global index to identify it in the mesh as well as a local index within each triangle it belongs to. Clearly, a given node may have more than one local index, since it may belong to more than one triangle. The local nodes shown in triangle Tk815are labeled k1820, k2825, and k3830. The potential within each triangular element is then approximated using a basis of polynomial functions. For simplicity, this basis is taken to be that of first-order polynomials, so that
φ(x,y)=βxx+βyy+β0(14)

Consequently, the potential of every element Tk815is described by the three unknown potentials of its nodes φ(k1), φ(k2), and φ(k3) and three coefficients βx, βy, and β0of formula (14). The gradient of the potential in formula (14) may then be rewritten in terms of the nodal potential as

A⁡(i,j)=∑k:(i,j)∈Tk⁢σ⁡(k)αTk⁢A⁡(ki)·A⁡(kj)(16)
where i and j are the global indices of the nodes, k is the index of the triangle, (i,j)εTkmeans that i and j belong to a triangle Tk, and Σ(k) is the conductivity of the region bounded by triangle Tk. It is further assumed that the local indices of i and j in Tkare kiand kj, respectively. Formula (15) is then rewritten as

ϕnT⁡(A11A12A21A22)⁢ϕn=ϕ1T⁢A11⁢ϕ1+ϕ2T⁢A21⁢ϕ1+ϕ1T⁢A12⁢ϕ2+ϕ2T⁢A22⁢ϕ2(17)
where φ1is the vector of the unknown potential (potential of all N non-contact nodes), φ2is the vector of the known fixed potential (potential of Nfnodes on the contacts), A11represents the self interaction of the non-contact nodes, A12=AT21mutual interaction of contact and non-contact nodes, and A22self interactions of the contact nodes. Formula (17) is then minimized with respect to the unknown potential vector φ1to obtain
A11φ1=−A12φ2(18)

Formula (18) is cast in the standard compact form Mφ=b, where M=A11, φ=φ1and b=−A12φ2. This linear system is then solved for φ to obtain the potential everywhere inside the domain D. As discussed above, in order to obtain a sensitivity calculation, the dependence of M, φ, and b on the problem parameters is made explicit, so the above linear system is written as
M(P)φ(P)=b(P)  (19)
where P is a vector of geometrical parameters, such as the dimensions of the structure and the relative position of the contacts within it. The goal is to efficiently evaluate the impact of the variation of such parameters on the computed resistances.
Adjoint Sensitivity Analysis

The adjoint sensitivity computation is an efficient algorithm for finding the sensitivity of a given vector f(P, φ(P)) of length n0with respect to a parameter vector P of length nP. A simple derivation of the adjoint method is summarized below.

Taking the total derivative of f(P, φ(P)) with respect to P results in

ⅆf⁡(P,ϕ⁡(P))ⅆP,∂f⁡(P,ϕ⁡(P))∂P
are matrices of size no×np,

∂f⁡(P,ϕ⁡(P))∂ϕ⁡(P)
is a
matrix of size no×N and

ⅆϕ⁡(P)ⅆP
is a matrix of size N×np.

Direct sensitivity methods are based on computing

ⅆϕ⁡(P)ⅆP
using a finite difference (FD) perturbation for each component of P, which is computationally very expensive since it requires npindependent system solves. However, taking the derivative of linear system (19) with respect to P results in the formula

Solving for

ⅆϕ⁡(P)ⅆP
and substituting into (20) results in the formula

Defining now the adjoint vector Λ as the solution of the adjoint linear system

M⁡(P)T⁢Λ=(∂f⁡(P,ϕ⁡(P))∂ϕ⁡(P))T(23)
the following equation is derived for the adjoint sensitivity method

The main advantage of the adjoint method is that with only two system solves, one for the nominal system (19) and one for the adjoint system (23), the sensitivity of ƒ(P,φ(P)) with respect to an arbitrary number of parameters nPmay be computed. In other words, when compared with the standard direct sensitivity method, the time complexity of the adjoint method is independent of the number of parameters. Furthermore, its accuracy is independent of numerical differentiation.

Defining the Output Function

Recall that the resistance

Rpq=VpIq
is a function of the total current Iqat a particular contact q, which in turn is a linear function of the potential φ(r). The total derivative of the resistance with respect to the parameter vector P is given by the formula

Consequently, the quantity of interest to extract Rpqis the total current at contact q due to a unit potential Vp=1 excitation at contact p, (e.g., the q-th component of the output vector is given by f(P,φ(P))(q)=Iq). Referring toFIG. 8B, bounding surface δBq840is a hypothetical closed boundary surrounding contact q835. By current continuity, the net current flowing through contact q835is the same as the net current flowing through bounding surface δBq840. The latter is computed from the relation between the current density and the potential

Iq=-∫∂Bq⁢σ⁡(r)⁢∇ϕ⁡(r)·n^⁢⁢ⅆl
where bounding surface δBq840is constructed as the union of the sides of the triangles touching contact q835at a single point (marked with “X's”). Without loss of generality, the local numbering of these triangles is made such that the point touching the contact may be numbered I1, where I is the index of the triangle. Let the side of triangle Tibelonging to bounding surface δBq840be referred to as δBql840. Note that the local normal to the boundary is the unit vector in direction of A(l1), i.e., {circumflex over (n)}={circumflex over (n)}(l1)=Â(l1). The Iqintegral is discredited as

Note that due to the assumed local indexing of triangle Tl, node l1is on the boundary of the contact and φ(l1)=0. This leads to the formula

Iq=∑Tl⁢∑k=23⁢σ⁡(l)αTl⁢A⁡(lk)·A⁡(l1)⁢ϕ⁡(lk)
which is simply the addition of the contributions of all the points on boundary surface δBq840that are connected to points on the contact boundary. A careful investigation of this formula reveals that with the aid of formula (17), it can be cast in the following compact form
Iq=Sq(A21φ1=A22φ2)  (26)
where Sqis a row vector of zeros and ones and the rest of the notation is as in (17). Sqhas ones at columns corresponding to the global indices of the nodes representing contact q835. Formula (26) indicates that the total current depends linearly on the potential of any point connected to a boundary point through a common triangle. More importantly, formula (26) indicates that the entries of the output matrices SqA21and SqA22, along with those of both the system matrix M and the RHS vector b all share the same formulas, i.e., they all rely on elements of the form in formula (26). This is useful when derivatives of such elements with respect to geometrical variations are computed (discussed below). Finally, formula (26) may be cast in a more compact linear relation between the current and potential
I(φ(P),P)=C1T(P)φ(P)+C2T(P)φ2(27)
where φ(P) is the unknown potential of the non-contact nodes, and φ2is the vector of fixed potentials of the contact nodes and is of length Nf, while C1(P) and C2(P) are known parameter-dependent matrices of size N×n0and Nf×no, respectively. Note that the above derivation is valid only for contacts that are assigned zero potential, i.e., q≠p, where p is the index of the excited contact. However this is not a limitation since only one contact is assigned a nonzero potential and the self-resistance of such contact is given by the sum of all the mutual resistances of the contact

Finally, the derivatives of the current function required for the adjoint formulas (23) and (24) are given by

∂I⁡(ϕ⁡(P),P)∂pi=ⅆC1T⁡(P)ⅆpi⁢ϕ⁡(P)+ⅆC2T⁡(P)ⅆpi⁢ϕ2∂I⁡(ϕ⁡(P),P)∂ϕ=C1T⁡(P)
where pmis the m-th component of P.
Derivative Computations with Respect to Parameter Vector P

In this subsection, the derivatives of the different matrix and vector entries with respect to the parameter vector P are computed. First, the matrix elements of the system matrix M, the right hand side vector b and the output matrices C1and C2are all computed from formula (26) and therefore computing the derivative of formula (26) with respect to the geometrical parameters covers all the required derivatives. Second, since all the entries of the matrices and vectors depend solely on the coordinates of the nodes, all geometrical perturbations may be defined by their effect on such nodal coordinates. Using formula (26) the derivative of any matrix element with respect to the geometrical parameter pmis given by

ⅆA⁡(i,j)ⅆpm=∑k:(i,j)∈Tk⁢∑zl∈Tk⁢∂a⁡(ki,kj)∂zl⁢ⅆzlⅆpm⁢⁢a⁡(ki,kj)=σ⁡(k)αTk⁢A⁡(ki)·A⁡(kj)(28)
where zlis one of the six coordinates (x and y coordinates of the three nodes of the triangle) on which the term A(i,j) depends. The global indices of the nodes of triangle Tkare (i,j,l) and the corresponding local indices are (ki, kj, kl). The computation of

∂a⁡(ki,kj)∂zl
is illustrated by the following example. The goal is to compute

∂a⁡(ki,kj)∂zl
where zl=xl, the x coordinate of the l-th global node in triangle Tk. This is achieved through the following algebra steps

Next, the chain rule factor

ⅆzlⅆpm
in formula (18) may be computed using an instance of a generic perturbation that implements uniform shape changes such as expansion or shrinking, as shown inFIG. 8C.

Since this type of perturbations affects only the boundary of the structure, all the internal nodes will remain unchanged, i.e.,

ⅆzlⅆpm=0
for any zlcoordinate of an internal node. Only nodes defining the outer boundary will change. The direction of the boundary node perturbation is in the average direction of the normals to both boundary segments connected through the node. This is direction {circumflex over (n)} inFIG. 8C. As an example, the node direction {circumflex over (n)} can be computed in the direction of perturbation of (x2,y2)

n^=1n^1+n^2⁢(n^1+n^2)
where ∥v∥ is the length of vector v and

Consequently, the sensitivities of coordinates (x2,y2) to a small node perturbation pialong the normal {circumflex over (n)} are given by

As those skilled in the art can appreciate, the approach suggested above for defining a perturbation is in fact general and can be used to model any geometric perturbation of either the domain boundaries or the contact locations. All that is required is to determine the set of nodes defining the perturbation, determine the changes in the coordinates of these nodes in response to a unit variation, and finally determine the partial derivatives.

Complexity Analysis of Sensitivity Extraction

A FEM system matrix M is symmetric and very sparse. Moreover, by proper numbering of the nodes in the FEM mesh one can generate a banded system matrix M. The maximum bandwidth B of the matrix is the maximum difference between the global indices of any interacting non-contact nodes (e.g., nodes that share a common triangle). As discussed below, B is assumed a constant much smaller than N but in the order of both npand no. The most important observation is that the adjoint system matrix in formula (23) is the transpose of the matrix M. Because the matrix M is symmetric, both the linear system and the adjoint system have the same system matrix. Following all the previous observations the complete set of equations may be summarized as

The complexity of solving the first equation is that of solving the same nominal sparse linear system with multiple right hand sides. The number of right hand sides is equal to 1+n0. Therefore, the complexity of solving all systems concurrently using Gaussian elimination is O(B2N). In other words, the complexity of our method is independent of the number of outputs, and indeed, one of the main pitfalls of the adjoint sensitivity method is avoided. Namely, the linear growth of the complexity as a function of the number of outputs. The Gaussian elimination complexity is inherited from the solution of the nominal system and therefore the incremental complexity of solving both systems as compared to solving only the original system is insignificant. The added complexity of forming

ⅆC1,2⁡(P)T⁢ϕ⁡(P)ⅆP,
which is n0matrix-vector products, is O(nonp) due to the sparsity of matrices C1and C2. Finally, the complexity of forming the term

∂M⁡(P)⁢ϕ⁡(P)∂P,
which is npsparse matrix-vector products, is O(Nnp). The total complexity is O(B2N+nonp+Nnp), which is O(B2N), i.e., it is the exact same complexity as solving only the nominal system. The memory complexity may also be shown to be O(B2N), which is the same memory complexity as the one required to solve for nominal resistance alone.

FIG. 9illustrates information handling system900, which is a simplified example of a computer system capable of performing the computing operations described herein. Information handling system900includes one or more processors910coupled to processor interface bus912. Processor interface bus912connects processors910to Northbridge915, which is also known as the Memory Controller Hub (MCH). Northbridge915connects to system memory920and provides a means for processor(s)910to access the system memory. Graphics controller925also connects to Northbridge915. In one embodiment, PCI Express bus918connects Northbridge915to graphics controller925. Graphics controller925connects to display device930, such as a computer monitor.

Northbridge915and Southbridge935connect to each other using bus919. In one embodiment, the bus is a Direct Media Interface (DMI) bus that transfers data at high speeds in each direction between Northbridge915and Southbridge935. In another embodiment, a Peripheral Component Interconnect (PCI) bus connects the Northbridge and the Southbridge. Southbridge935, also known as the I/O Controller Hub (ICH) is a chip that generally implements capabilities that operate at slower speeds than the capabilities provided by the Northbridge. Southbridge935typically provides various busses used to connect various components. These busses include, for example, PCI and PCI Express busses, an ISA bus, a System Management Bus (SMBus or SMB), and/or a Low Pin Count (LPC) bus. The LPC bus often connects low-bandwidth devices, such as boot ROM996and “legacy” I/O devices (using a “super I/O” chip). The “legacy” I/O devices (998) can include, for example, serial and parallel ports, keyboard, mouse, and/or a floppy disk controller. The LPC bus also connects Southbridge935to Trusted Platform Module (TPM)995. Other components often included in Southbridge935include a Direct Memory Access (DMA) controller, a Programmable Interrupt Controller (PIC), and a storage device controller, which connects Southbridge935to nonvolatile storage device985, such as a hard disk drive, using bus984.

ExpressCard955is a slot that connects hot-pluggable devices to the information handling system. ExpressCard955supports both PCI Express and USB connectivity as it connects to Southbridge935using both the Universal Serial Bus (USB) the PCI Express bus. Southbridge935includes USB Controller940that provides USB connectivity to devices that connect to the USB. These devices include webcam (camera)950, infrared (IR) receiver948, keyboard and trackpad944, and Bluetooth device946, which provides for wireless personal area networks (PANs). USB Controller940also provides USB connectivity to other miscellaneous USB connected devices942, such as a mouse, removable nonvolatile storage device945, modems, network cards, ISDN connectors, fax, printers, USB hubs, and many other types of USB connected devices. While removable nonvolatile storage device945is shown as a USB-connected device, removable nonvolatile storage device945could be connected using a different interface, such as a Firewire interface, etcetera.

Wireless Local Area Network (LAN) device975connects to Southbridge935via the PCI or PCI Express bus972. LAN device975typically implements one of the IEEE 802.11 standards of over-the-air modulation techniques that all use the same protocol to wirelessly communicate between information handling system900and another computer system or device. Optical storage device990connects to Southbridge935using Serial ATA (SATA) bus988. Serial ATA adapters and devices communicate over a high-speed serial link. The Serial ATA bus also connects Southbridge935to other forms of storage devices, such as hard disk drives. Audio circuitry960, such as a sound card, connects to Southbridge935via bus958. Audio circuitry960also provides functionality such as audio line-in and optical digital audio in port962, optical digital output and headphone jack964, internal speakers966, and internal microphone968. Ethernet controller970connects to Southbridge935using a bus, such as the PCI or PCI Express bus. Ethernet controller970connects information handling system900to a computer network, such as a Local Area Network (LAN), the Internet, and other public and private computer networks.