SSTA with non-gaussian variation to second order for multi-phase sequential circuit with interconnect effect

FIELD OF THE INVENTION

0001The present invention relates to integrated circuit design, and more particularly to a design timing verification tool that is capable of handling the non-Gaussian variation effects to the second order for both gate and interconnect on Statistical Static Timing Analysis (SSTA) for multi-phase sequential circuit.

BACKGROUND OF THE INVENTION

0002It has been quite well-known that due to the complexity of integrated circuits, it is not possible to apply a finite set of test vectors to verify the circuit delays for all the critical paths in the chip. Therefore, the vector-less approach or Static Timing Analysis (STA) is used widely to verify the timing of chip for each corner case with fixed gate delays. However, in today's nanometer process technology the manufacturing process variation plays a significant role in circuit delays, making SSTA increasingly important. Furthermore, interconnect part can be as dominant as the gate part in today's technology. Therefore, the issue of including process variation effect in the study of interconnect becomes extremely important.

0003SSTA is formalized in a way very similar to that of STA in terms of path tracing algorithm, but with quite a few differences. In STA, the gate delay is a fixed number, while in SSTA the delay is expressed as a random variable with some probability distribution function (PDF). In STA the critical paths are presented to the users based on slack which is the delay exceeding the timing limit. However, SSTA uses slack which means the probability of the occurrence of the critical path exceeding the use-specified threshold in terms of probability. In the presence of multi-phase sequential elements the timing constraints become complicated in the sense that the timing constraint is not uniform for all the paths, thus complicating the path tracing algorithms based on the breadth first search approach. Some specific algorithm in STA has been described in detail by Chang before. For example in STA the latest arrival time with respect to clock phases are stored at each node, while in SSTA the node stored accumulated probability. The path tracing procedure in terms of probability used in this invention is different from algorithm used by Visweswariah.

0004The process of calculating the aforementioned accumulated probability in SSTA at each node can be much more involved than that of storing the latest arrival time in STA. In SSTA, first we need to store the latest arrival time by using the max operation for all arrival times from each input of the gate with all the arrival times being expressed by random variables. Even we start with Gaussian distribution after max operation the result becomes non-Gaussian. Therefore, we need to handle max operation for Non-Gaussian distribution. If a random variable, is the linear combination of several Gaussian variables, then this random variable is Gaussian. To include non-Gaussian behavior, this random variable needs to be expressed as a sum of each Gaussian random variables to the second order. Zhan has proposed an algorithm to handle max operation with non-Gaussian distributions. The concept of edge probability can be understood as follows. For gate C with two inputs A and B, we use the notation that A is the random variable of the latest arrival time at the output of gate C for signal propagating from A to the output of gate C, and random variable B is defined similarly. For gate C with two inputs A and B the edge probability from A to output of C is Prob(A>B) meaning the probability of the latest signal at gate output coming from A by taking the integral of the PDF of Prob(A>B). Prob(B>A) then follows from 1-Prob(A>B). The accumulated probability at the given node then is evaluated by taking the largest of the products of edge probability for each gate along the path reaching this said node. We have adopted the algorithm of carrying out breadth first search to achieve these aforementioned accumulated probability for each node and then using depth first traversal to trace backward recursively to generate the critical paths with probability of occurrence greater than a specified probability threshold.

0005In SSTA with non-Gaussian delay distribution, the procedure of pre-characterizing the timing library to quadratic order of the Gaussian random variables is quite different from that of STA. The timing library in STA stores the gate delay as a function of gate input slope and gate output loading. In SSTA, this timing library stores the coefficients which are random variables in terms of sum of several Gaussian random variables up to quadratic order, while in STA the said coefficients are merely numbers. In evaluating the non-Gaussian delay distribution function use slope and output load as random variables up to quadratic order for the Gaussian random variables, and the coefficients from the equation also to the second order.

0006The process of calculating the aforementioned accumulated probability in SSTA at each node can be further complicated in the presence of interconnect. In STA the effective capacitance is already quite well-known. In this approach the gate driving the interconnect part is decomposed into two stages, the first stage is the driving gate with the effective capacitance and the output of the immediate output of the driving gate serves as the driving point of the second stage, namely the interconnect. Therefore, driving point admittance matrix and voltage transfer from the driving point to interconnect outputs are needed to calculate the delay from the input of the gate to both the immediate output of the gate and the interconnect outputs. A mathematical algorithm is presented to calculate admittance matrix and voltage transfer to the second order in powers of those Gaussian random variables due to manufacturing process variation. Subsequently, all the poles and residues for both admittance matrix and voltage transfer are also expressed to the second order in powers of Gaussian random variables. Thus, voltage wave function also expressed as random variable is obtained and delay distribution can be obtained.

0007In the case of cross-talk, effective capacitance approach by using the admittance matrix with poles and residues with variations up to the second order is also adopted. The effective capacitance of each gate by taking into account of the shift time of aggressor's input with respect to the victim's input are calculated and using admittance matrix with poles and residues with variations up to the second order. As to the victim delays from the immediate output of the input driver to the victim outputs, they are calculated by making use voltage transfer up to the 2^ndorder variation effect. Again, in SSTA, all of these delay quantities are treated as non-Gaussian random variables.

0008Finally, with all delay information in place, path search is continued until all critical paths in terms of probability are identified.

SUMMARY OF THE INVENTION

0009This invention provides a tool and a method for performing SSTA of a circuit with multi-phase sequential elements with interconnect, consisting of using path analysis including both forward bread first search and backward depth first traversal considering constraint with multi-phase sequential elements to generate critical paths in term of probability of path occurrence, considering gate and interconnect delays with non-Gaussian variation up to quadratic order in the path analysis, handling cross-talk issue with non-Gaussian variation up to quadratic order in the path analysis, and characterizing cells with non-Gaussian variation up to quadratic order.

0010According to another aspect, a SSTA tool according to the invention provides a method of forward breadth first search considering constraint with multi-phase sequential elements to first store clock phases of the driven gates to determine whether two signals coming from different phases of inputs of the gate should merge at the output node, and calculate the accumulated probability at each node as a vector with respect to clock phases, and edge probability matrix associated with each clock phase of input of the gate and the clock phase of output of the gate.

0011According to another aspect, a SSTA tool according to the invention provides a method of backward depth first traversal considering timing constraint with multi-phase sequential elements to search paths backward from the flip-flop data input with negative slack in terms of probability and make use of accumulated probabilities at node and input of the fanin gate of the said node and the edge probability from the said input to said output with certain clock phases to determine the probability of the path passing through the said input associated with clock phase and keep searching recursively.

0012According to another aspect, a SSTA tool according to the invention provides a method to pre-characterize the timing library of the gate delay and its output slope as random variables in terms of input slope and output loading also as random variables with the coefficients in terms of process variations to the 2^ndorder.

0013According to another aspect, a SSTA tool according to the invention provides a method of considering gate and interconnect delays with non-Gaussian variation up to quadratic orders by evaluating the input admittance matrix and voltage transfer from interconnect input to its out outputs all of which are random variables to the 2^ndorder of variation effects and computing gate effective capacitance and interconnect delay also in terms of 2^ndorder variation effect.

0014According to another aspect, a SSTA tool according to the invention provides a method of computing gate effective capacitance up to quadratic order of variation effect using the input admittance matrix of the interconnect driven by the gate up to quadratic order of variation effect by adopting iterative procedure including evaluating waveform parameters with 2^ndorder variation effect and re-evaluating capacitance utilizing driving input admittance in terms of poles and residues with 2^ndorder variation effects.

0015According to another aspect, a SSTA tool according to the invention further provides a method of evaluating the driving input admittance matrix of the interconnect by formulating these up to quadratic order of variation effect and using Arnoldi's method including variations to achieve orthonormal bases and fitting each matrix element to simple pole format with pole and residue being expressed in terms of variations up to the 2^ndorder.

0016According to another aspect, a SSTA tool according to the invention further provides a method of adopting iterative procedure in computing effective capacitance by approximating waveform with combination of linear and exponential waveforms and achieving admittance matrix and effective capacitance exactly.

0017According to another aspect, a SSTA tool according to the invention further provides a method of handling cross-talk issue with non-Gaussian variation up to quadratic order by iteratively calculating effective capacitance for each port and obtaining waveform at each port in terms of parameters up to 2^ndorder of variation.

0018According to another aspect, a SSTA tool according to the invention further provides a method of calculating voltage transfer using Arnoldi's method up to 2^ndorder of variation and fitting matrix element into simple pole format with pole and residue as random variables including up to 2^ndorder of variation.

0019According to another aspect, a SSTA tool according to the invention further provides a method of calculating voltage wave at interconnect outputs by approximating the waveform at interconnect inputs with combination of linear and exponential waveforms and achieving voltage transfer pole and residues to the 2^ndorder of variation.

0020According to another aspect, a SSTA tool according to the invention further provides a method of finding the time at which the waveform expressed as a random variable up to 2^ndorder of variation reaches certain value.

BRIEF DESCRIPTION OF THE DRAWINGS

0021These and other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures, wherein:

0022<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram illustrating path based SSTA with cross-talk analysis according to the present invention;

0023<figref idref="DRAWINGS">FIG. 2</figref> shows the flowchart of forward propagation based on breadth first traversal in SSTA according to the present invention;

0024<figref idref="DRAWINGS">FIG. 3</figref> is an example circuit for illustrating the concept of forward propagation based on breadth first traversal and backward search based on depth first traversal in SSTA;

0025<figref idref="DRAWINGS">FIG. 4</figref> illustrates an example timing diagram for several clock phases;

0026<figref idref="DRAWINGS">FIG. 5</figref> shows an example timing graph of forward propagation in the presence of uniform timing constraint;

0027<figref idref="DRAWINGS">FIG. 6</figref> is the flowchart for the algorithm of forward propagation with non-uniform timing constraint;

0028<figref idref="DRAWINGS">FIG. 7</figref> is the timing graph showing an example of criticality calculation results for the example circuit with non-uniform timing constraints;

0029<figref idref="DRAWINGS">FIG. 8</figref> is a flowchart illustrating a method for backward propagation to generate all critical paths;

0030<figref idref="DRAWINGS">FIG. 9</figref> is a flowchart for the algorithm of pre-characterizing cells up to the second order of variation effect;

0031<figref idref="DRAWINGS">FIG. 10</figref> is a flowchart for RLC solver of admittance matrix with variation effects to the second order;

0032<figref idref="DRAWINGS">FIG. 11</figref> is a flowchart calculating the effective capacitance in the presence of variation effect to the second order with one port in RLC;

0033<figref idref="DRAWINGS">FIG. 12</figref> shows an example circuit with the driver's immediate output waveform in terms of t_xand t_D;

0034<figref idref="DRAWINGS">FIG. 13</figref> is a flowchart calculating the effective capacitance in the presence of variation effect to the second order with cross-talk in RLC;

0035<figref idref="DRAWINGS">FIG. 14</figref> shows an example circuit illustrating the victim's and aggressor's immediate output waveforms in terms of t_xand T_d;

0036<figref idref="DRAWINGS">FIG. 15</figref> is a flowchart for RLC solver of voltage transfer with variation effects to the second order;

0037<figref idref="DRAWINGS">FIG. 16</figref> shows an example finding time t up to the second order of random parameter for waveform reaching certain value.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

0038The present invention will now be described in detail with reference to the drawings, which are provided as illustrative examples of the invention so as to enable those skilled in the art to practice the invention. Notably, the figures and examples below are not meant to limit the scope of the present invention to a single embodiment, but other embodiments are possible by way of interchange of some or all of the described or illustrated elements. Moreover, where certain elements of the present invention can be partially or fully implemented using known components, only those portions of such known components that are necessary for an understanding of the present invention will be described, and detailed descriptions of other portions of such known components will be omitted so as not to obscure the invention. In the present specification, an embodiment showing a singular component should not be considered limiting; rather, the invention is intended to encompass other embodiments including a plurality of the same component, and vice-versa, unless explicitly stated otherwise herein. Moreover, applicants do not intend for any term in the specification or claims to be ascribed an uncommon or special meaning unless explicitly set forth as such. Further, the present invention encompasses present and future known equivalents to the known components referred to herein by way of illustration.

0039As set forth above, the issue of SSTA incorporating the interconnect effect has been addressed before. However, to increase accuracy of path analysis results, the physical quantities such as delay and slope of waveform in SSTA must be expressed as non-Gaussian PDF. Furthermore, to handle gate and interconnect delays correctly, these two parts must be treated together by using the well-known effective capacitance approach. Therefore, the cells and interconnect must be pre-characterized to quadratic order of the process variation effects. Besides, this problem becomes even more complicated if the circuit has multi-phase sequential elements. It is necessary to have a timing analysis engine using forward signal propagation based on breadth first search followed by backward propagation using depth first traversal to generate critical paths in terms of probability. In stark contrast, as shown in <figref idref="DRAWINGS">FIG. 1</figref>, according to an aspect of the invention, a method implemented into SSAT tool to resolve these issues is discussed.

0040In <figref idref="DRAWINGS">FIG. 1</figref> a circuit description <b>101</b>, which can be complicated in the presence of multi-phase sequential elements, is accepted by the tool SSTA <b>102</b> handling non-uniform timing constraints since paths between source and destination flip-flops can have different timing constraints. The circuit description <b>101</b> can be at gate level, or combination of gate and transistor level, due to the fact the tool targets at hybrid design. Since the transistor level description can be partitioned into gates, the timing analysis will be handled similarly at gate level. Our discussion for SSTA is limited to gate level, and there is no need to specifically distinguish gate and transistor level.

0041As shown in <figref idref="DRAWINGS">FIG. 1</figref> the SSTA tool <b>102</b> is used to pre-characterize timing of the cells in terms of a second-order delay model instead of first-order approximation <b>103</b> and results go to a file <b>106</b> used for future runs. The tool <b>102</b> is also used <b>104</b> to interconnect solver generating information needed to gate level delay calculation also up to second order of process variation effect and store the results in a file <b>105</b>. SSTA <b>102</b> carries out timing check for all paths with non-uniform timing constraints in two steps, namely forward propagation based on BFS <b>107</b> and backward traversal using DFT <b>108</b>. However, the detailed algorithms are different from those published algorithms by Visweswariah. The final result reports the critical path in terms of the probability of the path <b>109</b>.

0042According to one aspect of the invention, new timing analysis algorithm <b>107</b><b>108</b> in this tool of SSTA with uniform or non-uniform timing constraint <b>102</b> is discussed here in detail. First, some basic notation is reviewed. In SSTA, the delay or slope at the node is not a number, but expressed as a random variable with certain PDF due to process variation. If the random variable A has Gaussian distribution, then <br /><i>A=a+bx </i><br /> in which x is a random variable with normalized Gaussian distribution N(0,1). The PDF f_xfor random variable x is <br /><i>f</i>_x(<i>x</i>)=1/√2πexp(−<i>x</i>²)

0043while the PDF f_A(x) for random variable A is <br /><i>f</i>_x(<i>x</i>)=1/√2πexp(−((<i>x−a</i>)/<i>b</i>)²)

0044with a and b being the nominal value and variance for A, respectively.

0000In reality any random variable representing physical quantities like delay, slope etc. cannot be approximated by Gaussian distribution exactly, and must be modeled by non-Gaussian distribution including the second-order effect such as <br /><i>A=a+bx+cx</i>²<br /> Note that x can be a vector with each component representing independent process parameter. For example, transistor width and length are two independent process parameters. <br /> In SSTA the operation MAX(X,Y) is used to store PDF of max of the two random variables X and Y. Suppose a gate has two inputs i1 and i2 and one gate output out with their latest arrival times at two inputs i1 and i2 stored as two random variables A and B, respectively. Two delays delay_i1→outout and delay_i2→outout are represented by C and D also as random variables. The latest arrival times in terms of random variables at out from the two inputs i1 and i2 are E and F, respectively. We have <br /><i>A=a</i>₀<i>+a</i>₁<i>×+a</i>₂<i>x</i>²<br /><i>B=b</i>₀<i>+b</i>₁<i>×+b</i>₂<i>x</i>²<br /><i>C=c</i>₀<i>+c</i>₁<i>x+c</i>₂<i>x</i>²<br /><i>D=d</i>₀<i>+d</i>₁<i>x+d</i>₂<i>x</i>²<br /><i>E</i>=(<i>a</i>₀<i>+c</i>₀)+(<i>a</i>₁<i>+c</i>₁)<i>x</i>+(<i>a</i>₂<i>+c</i>₂)<i>x</i>²<br /><i>F</i>=(<i>b</i>₀<i>+d</i>₀)+(<i>b</i>₁<i>+d</i>₁)<i>x</i>+(<i>b</i>₂<i>+d</i>₂)<i>x</i>²<br />MAX(<i>E,F</i>)=<i>e</i>₀<i>+e</i>₁<i>x+e</i>₂<i>x</i>²<br /> Then, MAX(E,F) is computed to get e₀, e₁and e₂and it is the latest arrival time in terms of a random variable stored at the output of the gate. The computation of e₀, e₁and e₂by Zhan et al. is already quite well-known, and there is no need to repeat them here. In SSTA the probability of the path is needed besides the latest arrival time which is random variable. Still using the above example of a gate with two inputs, we need to know the probability for each of the two paths, namely from i1 to out and i2 to out. This information is obtained from the calculation of MAX(E>F) and MAX(F>E) with MAX(E,F)=MAX(E>F)+MAX(F>E). The probability for E>F is obtained by integrating the PDF (Probability Density Function) of MAX(E>F) and same for F>E.

0045According to one aspect of the invention, <figref idref="DRAWINGS">FIG. 2</figref> shows the flowchart of forward propagation based on BFS <b>107</b>. First start with signals coming from the outputs of the flip-flops. As standard in BFS, those signals are put into queue <b>201</b>, start processing the elements in queue <b>203</b> to see if the inputs of the fanouts gates have been visited. If so, MAX operation for these inputs is carried out <b>204</b>. In stark contrast to Viseweswariah, the accumulated probability (accum_prob) of the node, which is the most critical probability for all paths ending at the said node, is being found in the following way. Compute x and y for probabilities from inputs, say e and f, to output c for gate C, then accum_prob(c), max(accum_prob(e)*x, accum_prob(f)*y) <b>204</b>. In case the said output c of the said gate C is the input of edge_triggered flip-flop <b>205</b>, the probability of failure of the most critical path needs to be computed. That is obtained by integrating the PDF of the latest arrival time, say D, with respect to the whole parameter space with the constraint that D greater than the timing constraint <b>207</b>. No paths will be searched beyond the destination of edge-triggered flip-flop. As to level sensitive latch, timing constraint become complicated, but the main algorithm of SSTA will not be changed. Therefore, the discussion on level sensitive latch is omitted here. If the said node c is not input of flip-flop <b>206</b>, then put it to queue and keep repeating the steps as discussed above until the queue becomes empty <b>208</b>.

0046The engine of forward propagation using BFS <b>107</b> in the presence of uniform timing constraint is further illustrated by referring to <figref idref="DRAWINGS">FIG. 3</figref>, <figref idref="DRAWINGS">FIG. 4</figref> and the timing graph <figref idref="DRAWINGS">FIG. 5</figref>. A simple sequential circuit with 6 flip-flops is shown in <figref idref="DRAWINGS">FIG. 3</figref> and the clock phases P1 and P2 are shown in <figref idref="DRAWINGS">FIG. 4</figref>. In the case of uniform timing constraint it is assumed that L1-L6 are positive edge-triggered flip-flops, and all of them are controlled by the rising clock edge of clock phase P1. Initially the outputs of flip-flops 11, 13, and 15 as shown in <figref idref="DRAWINGS">FIG. 5</figref> are put into queue <b>201</b> and start processing queue elements if queue is not empty <b>202</b>. After processing 13 and 15, fanout gate D <b>203</b> is checked. D begin to be evaluated since two inputs have been visited <b>204</b>. MAX(13,15) is calculated and the latest arrival time at d in terms of a random variable is obtained <b>204</b>. Note that the node name and the random variable associated with the node are expressed by the same symbol for the sake of clarity. For example 13 refers to both node and its random variable. The probabilities from 13 to d and from 15 to d are calculated to be 0.3 and 0.7, respectively. The next step is to update accum_prob at d. Since the accum_prob is assigned 1 at the starting signals 11, 13 an 15, then accum_prob at d is max(1*0.3,1*0.7)=0.7 <b>204</b>. Since d is not input of flip-flop <b>205</b>, so it is put into queue <b>206</b>. At node a, b, and c, it is easy to see accm_prob is for 1, since they are the outputs of single input gates. Similarly, by evaluating gate E in <figref idref="DRAWINGS">FIG. 3</figref>, the probabilities 0.8 and 0.2 from a to e and d respectively are obtained and accum_prob at e is max(1*0.8,0.7*0.2)=0.8. Then, at nodes c, f, and g which are inputs to the flip-flops <b>205</b>, the accum_prob are 1, 0.8, and 0.8. The arrival times at c, f, and g have been computed. By knowing the timing constraint say from L3 to L4, and the arrival time at f, it is straightforward to calculate the probability P for the failure of the path from 13 to f <b>207</b>. For example, the quadratic function with Gaussian random variables for the latest arrival time at the said node f is D=a+bx+cx²and timing constraint is T, then the said probability is to integrate the normalized Gaussian function 1/√2πexp(−(y²)) with respect to the whole space of y <br /><i>P=</i><img file="US9898564B2_D0001.tif" />_D>T1/√2πexp(−(<i>y</i>²))<i>dy </i><br /> Here y can be a vector with several process parameters.

0047<figref idref="DRAWINGS">FIG. 6</figref> is the flowchart for the algorithm of <b>107</b> with non-uniform timing constraint. Still referring to <figref idref="DRAWINGS">FIG. 3</figref> for the sequential circuit and <figref idref="DRAWINGS">FIG. 4</figref> for the clock phases, here we assume that L1-L6 are positive edge-triggered flip-flops, L3 and L4 are controlled by the rising clock edge of clock phase P2, while the remaining flip-flops are controlled by the rising edge of P1. Referring to the flowchart in <figref idref="DRAWINGS">FIG. 6</figref> and the timing graph as shown in <figref idref="DRAWINGS">FIG. 7</figref>, signals start propagating from outputs of flip-flops 11, 13, and 15 similar to <figref idref="DRAWINGS">FIG. 2</figref><b>201</b><b>202</b> and process gate when all inputs are visited <b>203</b>. The difficulty for non-uniform case can be understood by the processing of gate D in <figref idref="DRAWINGS">FIG. 3</figref>. The inputs 13 and 15 store latest arrival times with respect to rising edge of clock phases P2 and P1 <b>601</b>, respectively. However, at node d driven clock phases are P1 and P2 <b>602</b>, instead of only one clock phase either P1 or P2. This means at node d we must store two latest arrival times with respect to both P1 and P2 <b>603</b>. To be more specific, choose any pair of clock phases from the two inputs, add input delays to the latest arrival times with the two clock phases, compare with all driven clock phases <b>602</b>. If the ordering of these two clock phases is not fixed, then latest arrival times for these two clock phases must be stored in the output d of the said gate D <b>603</b>. This part in fact is similar to that used in STA addressed in detail by Chang elsewhere. In SSTA, the nominal numbers in the random variable of the latest arrival time are used to determine the clock phases with respect to which the latest arrival times at node d in terms of random variable are stored. In SSTA, the accumulated path probability with respect to each clock phase stored at the said node d is needed. In the case of the said gate D with inputs 13 and 15, output d, the accum_prob at 13 with respect to clock phase p2 is 1, so is accum_prob at 15 with respect to clock phase P1. Since the latest arrival time at node d still contain two clock phases without merging them into a single phase, the probability for the signal from 13 with respect clock phase p2 propagating to node d still with respect to P2 expressed as edge_prob(13,d,P2,P2) is 1. That is why accum_prob at node d with respect to P2 denoted at accum_prob(d,P2) is accum_prob(13,P2)*edge_prob(13,d,P2,P2)=1 and the same applies to accum(d,P1)=1 <b>603</b>. Besides, the input to output probability must be retrieved when doing path tracing back. The aforementioned probability edge_prob(13,d,P2,P2) associated with each clock phase of the input and each clock phase at the output is stored into the clock phase of the input. The forward propagation process stops when all signals have reached inputs of destination flip-flops. The delay variables for these nodes have been obtained. Probability for failure at the said node can be computed from the delay variable and its timing constraint. If the probability is greater than the user specified threshold probability, the difference is slack in terms of probability, not in terms of time. For example, the quadratic function with Gaussian random variables for the latest arrival time at the said node is D=a+bx+cx²and timing constraint is T, then the said probability <b>207</b> is to integrate the normalized Gaussian function 1/√2πexp(−(y²)) with respect to the whole space of y <br /><i>P=</i><img file="US9898564B2_D0002.tif" />_D>T1/√2πexp(−(<i>y</i>²))<i>dy </i>

0048Continue referring to <figref idref="DRAWINGS">FIG. 3</figref> and now gate F with input e and output f is being processed. Node e stores the latest arrival times d1 and d2 separately with respect to both clock phases P1 and P2 by the same reason as processing gate D is discussed. However, there is only one driven clock phase of node f, namely clock phase P2. Therefore, by comparing P1 and P2 stored in node e against the driven clock phase P2 as far as timing constraint is concerned, these P1 and P2 in e have fixed ordering and MAX(d1,d2) is operated with the result d3 being stored into node f. Prob(d1>d2) and Prob(d2>d1) for the probabilities for d1>d2 and d2>d1 are also calculated. In fact based on the previous notation, we have <br />edge_prob(<i>e,f,P</i>1,<i>P</i>1)=Prob(<i>d</i>1><i>d</i>2)<br /> in which e and f refer to input and output node, and the 3rd argument is the clock phase the delay at input is associated with, and the 4th argument is the clock phase the delay at output is associated with. Then, edge_prob(e,f,P2,P1)=Prob(d2>d1) follows similarly. <br /> As accum_prob at node f, since d3 is measured from phase P1, and there are two paths from e to f with two different clock phases. The correct accum_prob <b>604</b> is obtained as follows, <br />accum_prob(<i>f,P</i>1)=max(accum_prob(<i>e,P</i>1)*Prob(<i>d</i>1><i>d</i>2), accum_prob(<i>e,P</i>2)*Prob(<i>d</i>2><i>d</i>1))<br /> Similar to the case of uniform timing constraint, the forward propagation of the signals stop when the signals have reached inputs of destination flip-flops and the probability for failure at the said nodes are calculated <b>207</b>.

0049<figref idref="DRAWINGS">FIG. 7</figref> is the timing graph showing an example of criticality calculation results for the circuit in <figref idref="DRAWINGS">FIG. 3</figref> with non-uniform timing constraints. First, in multi-phase circuit the accum_prob at each node is expressed as a vector for each phase. At 11, 13, and 15 the accum_prob are (1,0), (0,1) and (1,0), meaning at 11 the accum_prob is 1 with respect to P1, at 13 the accum_prob is 1 with respect to P2, and at 15 the accum_prob is 1 with respect to P1. At node d the latest arrival times are calculated from the latest arrival times at node 13 and 15 plus the delays from 13 to node d and 15 to d, respectively. These two the latest arrival times at node d from 13 and 15 with different phases are not merged, so the probability from input 13 or 15 to output d is 1 for each phase. As to the edge between 13 and d, a 2×2 matrix is given with the 1st row storing probability from 1st input, which is 13, with phase P1 to output phases P1 and P2, respectively, and 2nd row being for input 13's phase P2 to output phases P1 and P2 at node d, respectively. Nodes a and e store delay with respect to phase P1, they both go through MAX operation to achieve the longest delay also with respect to P1. The probability for the edge from a to e is 0.7 while the probability from d to e is 0.3 for P1. This is why the edge matrix probability from a to e is

0050<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mi>P</mi><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mn>0.7</mn><mo>,</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><mn>0</mn><mo>,</mo><mn>0</mn></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow></math></maths><img file="US9898564B2_D0003.tif" /><img file="US9898564B2_D0004.tif" /><img file="US9898564B2_D0005.tif" /><img file="US9898564B2_D0006.tif" /><img file="US9898564B2_D0007.tif" /><img file="US9898564B2_D0008.tif" /><img file="US9898564B2_D0009.tif" /><img file="US9898564B2_D0010.tif" /><img file="US9898564B2_D0011.tif" /><img file="US9898564B2_D0012.tif" /><img file="US9898564B2_D0013.tif" /><img file="US9898564B2_D0014.tif" /><img file="US9898564B2_D0015.tif" /><img file="US9898564B2_D0016.tif" /><img file="US9898564B2_D0017.tif" /><img file="US9898564B2_D0018.tif" /><img file="US9898564B2_D0019.tif" /><img file="US9898564B2_D0020.tif" /><img file="US9898564B2_D0021.tif" /><br /> Using the previous notation for edge_prob, we have P₁₁=edge_prob(1,e,P1,P1). <br /> Note that the 2nd row is (0,0) because input a does not have any delay associated with P2. Since node a does not store the longest delay with respect to P2, the longest delay with respect to P2 in node d does not merge with any delay from a, meaning the probability of the delay from d with respect to phase P2 goes to node e also with respect to P2 is 1. This explains the matrix edge probability P between d and e is

0051<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mrow><mi>P</mi><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mn>0.3</mn><mo>,</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><mn>0</mn><mo>,</mo><mn>1</mn></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow></math></maths><img file="US9898564B2_D0022.tif" /><img file="US9898564B2_D0023.tif" /><img file="US9898564B2_D0024.tif" /><img file="US9898564B2_D0025.tif" /><img file="US9898564B2_D0026.tif" /><img file="US9898564B2_D0027.tif" /><img file="US9898564B2_D0028.tif" /><img file="US9898564B2_D0029.tif" /><img file="US9898564B2_D0030.tif" /><img file="US9898564B2_D0031.tif" /><img file="US9898564B2_D0032.tif" /><img file="US9898564B2_D0033.tif" /><img file="US9898564B2_D0034.tif" /><img file="US9898564B2_D0035.tif" /><img file="US9898564B2_D0036.tif" /><img file="US9898564B2_D0037.tif" /><img file="US9898564B2_D0038.tif" /><img file="US9898564B2_D0039.tif" /><img file="US9898564B2_D0040.tif" /><br /> With the information of accum_prob at nodes a and d, and the edge matrix probabilities between edges a to e and d to e, the accum_prob at node e is obtained easily. <br />accum_prob(<i>e,P</i>1)=max(accum_prob(<i>a,P</i>1)*edge_prob(<i>a,e,P</i>1,<i>P</i>1),<br />accum_prob(<i>d,P</i>1)*edge_prob(<i>d,e,P</i>1,<i>P</i>1))=max(1*0.7,1*0.3)=0.7<br />accum_prob(<i>e,P</i>2)=1<br /> This is how we get 0.7,1 for node e in <figref idref="DRAWINGS">FIG. 7</figref>. As to node e, the longest delay times are stored with respect to clock phases P1 and P2. By adding the delay from node e to f, we get the longest delays d1 and d2 associated with P1 and P2. Due to the fact that there is only one driven clock phase P2 at node f, d3=MAX(d1,d2) is used and d3 is with respect to P1 only. Assuming we have Prob(d1>d2)=0.9, Prob(d2>d1)=0.1, giving rise to edge_prob(e,f,P1,P1)=0.9 <br /> and edge_prob(e,f,P2,P1)=0.1. In terms of edge matrix it is

0052<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mrow><mi>P</mi><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mn>0.9</mn><mo>,</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><mn>0.1</mn><mo>,</mo><mn>0</mn></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow></math></maths><img file="US9898564B2_D0041.tif" /><img file="US9898564B2_D0042.tif" /><img file="US9898564B2_D0043.tif" /><img file="US9898564B2_D0044.tif" /><img file="US9898564B2_D0045.tif" /><img file="US9898564B2_D0046.tif" /><img file="US9898564B2_D0047.tif" /><img file="US9898564B2_D0048.tif" /><img file="US9898564B2_D0049.tif" /><img file="US9898564B2_D0050.tif" /><img file="US9898564B2_D0051.tif" /><img file="US9898564B2_D0052.tif" /><img file="US9898564B2_D0053.tif" /><img file="US9898564B2_D0054.tif" /><img file="US9898564B2_D0055.tif" /><img file="US9898564B2_D0056.tif" /><img file="US9898564B2_D0057.tif" /><img file="US9898564B2_D0058.tif" /><img file="US9898564B2_D0059.tif" /><br />accum_prob(<i>f,P</i>1)=max(accum_prob(<i>e,P</i>1)*edge_prob(<i>e,f,P</i>1,<i>P</i>1),<br />accum_prob(<i>e,P</i>2)*edge_prob(<i>e,f,P</i>2,<i>P</i>1))=max(0.7*0.9,1*0.1)=0.63<br />accum_prob(<i>f,P</i>1)=0.63<br />accum_prob(<i>f,P</i>2)=0<br /> In <figref idref="DRAWINGS">FIG. 7</figref>, it is shown as f 0.63 0.

0053This invention presents an algorithm <b>108</b> for backward propagation to generate all critical paths as shown in <figref idref="DRAWINGS">FIG. 8</figref>. First identify the data input of the flip-flops with negative slack, meaning the paths ending at the said node with path probability exceeding the specified threshold probability. It is noted that the accumulated probability at the said node times A in which A=user specified probability-slack is the probability of failure cur_prob for the most critical path ending at the said node <b>801</b>. Search paths backward recursively based on DFT from these said nodes with arguments for node f, its clock phase P, and to only generate failing paths with their probabilities greater than the user specified threshold <b>802</b>. The procedure of back trace DFT in the presence of multi-phase circuit goes as follows. Get the fanin gate of the said node and the input e of the said fanin gate F <b>803</b>. The purpose is to determine if there are paths coming from the said input e to the said node f exceeding the user specified threshold probability. The said nodes e and f store the nominal and variation terms of latest arrival times for various independent clock phases and we choose one clock phase of e, say Q <b>804</b>, for illustration purpose. We obtain the following quantities, <br /><i>x</i>=edge_prob(<i>e,f,Q,P</i>)<br /><i>y</i>=accum_prob(<i>e,Q</i>)<br /><i>z</i>=accum_prob(<i>f,P</i>)

0054Since the most critical paths passing through node f have the probability cur_prob, then the probability for the path passing through e with clock phase Q to node f with clock phase P is <b>805</b><br />new_prob=cur_prob*<i>y*x/z </i><br /> By comparing new_prob with user specified threshold probability, it can be determined whether the path search can go beyond this node e. If so, then the process is done recursively <b>807</b>. If not then the next clock phase Q of node e will be accessed and the same process continues <b>808</b>. Then, when the clock phases of node e are exhausted, the next input of gate F is accessed <b>809</b> and so on until all critical paths with probability greater than user specified threshold probability.

0055Referring back to <figref idref="DRAWINGS">FIG. 7</figref> an explicit example for back tracing with non-uniform timing constraints in SSTA is given. Here we discuss the DFT from output node f to inputs 11,13, 15. Similar discussions on the path tracing from outputs node c and g are omitted. Assume the probability of critical path failure at output node f is 0.8 and the user specified threshold probability is 0, then the slack in terms of probability at node f is −0.8 as shown in <figref idref="DRAWINGS">FIG. 7</figref>. If the user specified threshold probability is 0, then all paths with any probability are considered to be critical paths. As discussed in the previous context, this said critical path failure probability at node f is obtained by integrating the delay time in terms of random variable at node f with respect to the whole variation space by considering timing constraint. The purpose is to trace back from node f to find the three critical paths in <figref idref="DRAWINGS">FIG. 7</figref>, namely paths consisting of nodes 11→a→e→f, 13→d→e→f, and 15→d→e→f. The most critical path failure probability is 0.8*0.63=0.504. Tracing backward first to node e with phase P1 and knowing the edge_prob(e,f,P1,P1)=0.9, the new probability at node e with P1 becomes 0.7*0.9/0.63*0.504=0.504. Then search further from node e with P1 to node a with P1, the new probability at node a with P1 becomes 1.0*0.7/0.7*0.504=0.504 and then to 11 and conclude the path 11→a→e→f is the most critical path with probability 0.504. Based on DFT, the search then goes back to node e and then to node d. First with phase P1 in node d, by using accum_prob(d,P1)=1 and edge_prob(d,e,P1,P1)=0.1, the new_prob=1*0.3/0.7*0.504=0.216. Since in this example illustrated by <figref idref="DRAWINGS">FIG. 7</figref>, the specified probability threshold is chosen to be 0, the new_prob is greater than specified probability threshold, therefore the searching does go beyond node d. Then, the search goes to 15 with edge_prob(15,d,P1,P1)=1, the second path 15→d→e→f with probability 0.216 is found. Since edge_prob(13,d,P1,P1)=edge_prob(13,d,P2,P1)=edge_prob(d,e,P2,P1)=0, then go backward to node e with phase P2. With edge_prob(e,f,P2,P1)=0.1, accum_prob(e,P2)=1 and accum_prob(f,P1)=0.63, new_prob=1*0.1/0.63*0.504=0.08. Then it is simple to see that edge_prob(13,d,P2,P2)=edge_prob(d,e,P2,P2)=1 the path 13→d→e→f is found with probability 0.08. It is interesting to check that the sum of the probabilities for these three paths, namely 0.504, 0.216 and 0.08, is 0.8 exactly as expected.

0056Referring back to <figref idref="DRAWINGS">FIG. 1</figref><b>105</b> for another aspect of the invention, the algorithm of pre-characterizing cells up to the second order of variation effect is discussed in <figref idref="DRAWINGS">FIG. 9</figref>. Pre-characterizing cell generates the mathematical equations describing the cell delay and output slew as a function of cell input slew time and cell output loading, with loading and delays being treated as random variables <b>901</b>. These random variables have non-Gaussian PDF and they are expressed by the random variables with normalized Gaussian PDF due to the independent process parameters such as transistor width and transistor length etc. to the second order. We use a simple example to illustrate the concept of pre-characterizing cell with variations to the second order. The random variable of delay or slew time X is denoted by <br /><i>X=a+bx+cy+dx</i>²<i>+ey</i>^e<i>+fxy </i><br /> in which x and y refer to random variables for transistor width and transistor length, respectively assumed to have normalized Gaussian distribution N(0,1). If X is for cell output slew time, then the coefficients a, b, c etc. depend on the cell input slew time and output loading which are also random variables. With this understanding, the procedure of pre-characterizing cell in the presence of variation effect is described as follows. The purpose is to characterize, say output slew S as a function of input slew, output loading and transistor width, length into <br /><i>S</i>_out<i>=a</i>(<i>S</i>_in<i>,L</i>_out)+<i>b</i>(<i>S</i>_in<i>,L</i>_out)<i>W+c</i>(<i>S</i>_in<i>,L</i>_out)<i>W+d</i>(<i>S</i>_in<i>,L</i>_out)<i>W</i>²<i>+e</i>(<i>S</i>_in<i>,L</i>_out)<i>W</i>²<i>+f</i>(<i>S</i>_in<i>,L</i>_out)<i>WL </i><br /> The delay of the cell from cell input to cell output denoted by D_in→outis discussed similarly, and there is no need to repeat it here. Since we use N(1,0) for x any y representing random variables for width W and length L, in the modeling W in fact is (W−μ)/σ assuming N(μ,σ) is the Gaussian PDF for W, and L follows the same. In the sampling for S_inand L_out<b>902</b>, choosing one sample point and then do sampling for W and L <b>903</b>, to get coefficient a, b, c, d, e, f at one chosen point for S_inand L_out<b>904</b>. By doing this way, the data for all the sampling points for the coefficients a, b, c, d, e and f, we therefore can fit each of them into relation <b>905</b><br /><i>a</i>(<i>S</i>_in<i>,L</i>_out)=ƒ(<i>i</i>)<i>Y</i>(<i>i</i>)<br /><i>Y</i>(1)=<i>S</i>_in<i>Y</i>(2)=<i>L</i>_out<i>*S</i>_in<i>Y</i>(3)=(<i>L</i>_out)³<br /><i>Y</i>(4)=<i>L</i>_out<i>Y</i>(5)=1

0057All f g and h are empirical fitting coefficient.

0000The explicit formula is given as follows <br /><i>S</i>_out<i>=A+Bx+x</i>^t<i>Cx </i><br /> where x=(x₁,x₂, . . . x_n)^tis 1×n vector representing n independent process parameters with normalized Gaussian PDF N(1,0), B is 1×n vector, and C is a n×n symmetric matrix and A is a scalar, which is the constant term. We have <br /><i>A=Σ</i>_i=1⁵<i>a</i>(<i>i</i>)<i>Y</i>(<i>i</i>)<br /><i>B</i>_m=Σ_i=1⁵<i>b</i>(<i>m,i</i>)<i>Y</i>(<i>i</i>)<br /><i>C</i>_mn=Σ_i=1⁵<i>c</i>(<i>m,n,i</i>)<i>Y</i>(<i>i</i>)<br /> in which B_mis the mth component of vector B, while C_mnis element of matrix C at row m and column n.

0058The SSTA engine is further complicated by the variation effects due to the RLC interconnect by referring to <b>104</b> in <figref idref="DRAWINGS">FIG. 1</figref>. As in the case of STA in the presence of RLC interconnect, effective capacitance approach is used in the case of the gate driving the interconnect delay and the cross-talk problems using both the well-known admittance matrix and voltage transfer which are expressed in terms of pole and residue format as a function of variation parameters by referring to the file <b>105</b><figref idref="DRAWINGS">FIG. 1</figref>. This invention presents an algorithm of <b>104</b> for RLC solver as shown in <figref idref="DRAWINGS">FIG. 10</figref>. First, the algorithm checks whether the file containing admittance matrix and voltage transfer already exists <b>1001</b>. If so, then skip the procedures of re-computing admittance matrix and voltage transfer and directly read information from the said file. Otherwise, the well-known Arnoldi's method is adopted by including variation effects <b>1002</b>. First, we review the basic steps in formulating this problem. For RLC circuit using modified nodal analysis (MNA) in frequency domain without variations as follows, <br />(<i>G+sC</i>)<i>x=b </i><br /> In MNA there are two types of elements, type 1 elements are nodal voltages and type 2 elements are branch currents respectively. The matrix G consists of time independent elements, while matrix C handles time dependent elements such as capacitors. The vector b contains nonzero external current at the ports and zero for the remaining components. By separating the ports from the remaining nodes, the above equation is further partitioned into

0059<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mrow><mrow><mrow><mo>[</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>G</mi><mi>p</mi></msub></mtd><mtd><msubsup><mi>G</mi><mi>C</mi><mi>T</mi></msubsup></mtd></mtr><mtr><mtd><msub><mi>G</mi><mi>C</mi></msub></mtd><mtd><msub><mi>G</mi><mi>I</mi></msub></mtd></mtr></mtable><mo>]</mo></mrow><mo>+</mo><mrow><mi>s</mi><mo>⁡</mo><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>C</mi><mi>p</mi></msub></mtd><mtd><msubsup><mi>C</mi><mi>C</mi><mi>T</mi></msubsup></mtd></mtr><mtr><mtd><msub><mi>C</mi><mi>C</mi></msub></mtd><mtd><msub><mi>C</mi><mi>I</mi></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow></mrow><mo>]</mo></mrow><mo>⁡</mo><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>x</mi><mi>p</mi></msub></mtd></mtr><mtr><mtd><msub><mi>x</mi><mi>I</mi></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>b</mi><mi>p</mi></msub></mtd></mtr><mtr><mtd><mn>0</mn></mtd></mtr></mtable><mo>]</mo></mrow></mrow></math></maths><img file="US9898564B2_D0060.tif" /><img file="US9898564B2_D0061.tif" /><img file="US9898564B2_D0062.tif" /><img file="US9898564B2_D0063.tif" /><img file="US9898564B2_D0064.tif" /><img file="US9898564B2_D0065.tif" /><img file="US9898564B2_D0066.tif" /><img file="US9898564B2_D0067.tif" /><img file="US9898564B2_D0068.tif" /><img file="US9898564B2_D0069.tif" /><img file="US9898564B2_D0070.tif" /><img file="US9898564B2_D0071.tif" /><img file="US9898564B2_D0072.tif" /><img file="US9898564B2_D0073.tif" /><img file="US9898564B2_D0074.tif" /><img file="US9898564B2_D0075.tif" /><img file="US9898564B2_D0076.tif" /><img file="US9898564B2_D0077.tif" /><img file="US9898564B2_D0078.tif" /><br /> Assuming there are m ports and n internal nodes in RLC circuit, here x_pare the m port node voltages and x_iinclude n internal node voltages and l inductor currents. G_Pis m×m matrix for m ports, so is C_P. G_Iand C_Iare (l+n)×(l+n) matrices representing n internal nodes and l inductors. Both G_Cand C_Care (l+n)×m connection conductance and susceptance matrices, respectively. The right hand side is a (m+l+n)×m matrix with b_Pas being the external current at the m port nodes. The admittance Y(s) is defined as <br /><i>Y</i>(<i>s</i>)<i>x</i>_P(<i>s</i>)=<i>b</i>_P(<i>s</i>)<br /> Through some calculation by eliminating x_i, by following Kerns formulation without considering variations Y(s) is obtained as follows, <br /><i>Y</i>(<i>s</i>)=<i>G</i>_P<i>+sC</i>_P−(<i>G</i>_C<i>+sC</i>_C)^T(<i>G</i>_I<i>+sC</i>_I)⁻¹(<i>G</i>_C<i>+sC</i>_C)<br /> Kerns and Yang have pointed out that by using Cholesky factorization G_Ican be transformed into unit matrix. Since this part will not affect the later discussions, it is omitted for the sake of brevity.

0060Our purpose is to calculate Y(s) as a function of variation parameters to the second order and express each matrix component of Y(s) in terms of pole and its residue to the second order effect due to variations. The conductance and susceptibility matrices can be formulated in powers of variation parameters. For example, resistance being assumed as a Gaussian random variable expressed as <br /><i>R=R</i>₀<i>+R</i>₁<i>a </i><br /> Similarly capacitance C has Gaussian distribution like <br /><i>C=C</i>₀<i>+C</i>₁<i>b </i><br /> Here R₀and C₀are nominal values and a and b are two independent variation parameters for resistance and capacitance, respectively <b>1003</b>. By using these, it is straightforward to evaluate G and C matrices in powers of a and b. We have <br /><i>G</i>_I<i>=G</i>_I,0<i>+V </i><br /><i>V=Σ</i>_i=1^N<i>G</i>_Ii<i>V</i>_i<br /> Here V_istands for ith random variable up to the second order. For example if there are two random parameters a and b, then V_ican be one of random variables a, b, ab, a², and b²in which a and b are independent process parameter with normalized Gaussian distribution N(0,1). The nominal value of G_Iis G_I0and G_Iiis the coefficient matrix of random variable y_i. The matrices C_P, G_P, C_P, G_Cand C_Care all defined similarly. To simplify the calculation the congruence transform is carried out by using

0061<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mrow><mi>X</mi><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mi>I</mi></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mrow><mrow><mo>-</mo><msubsup><mi>C</mi><mi>i</mi><mrow><mo>-</mo><mn>1</mn></mrow></msubsup></mrow><mo>⁢</mo><msub><mi>C</mi><mi>C</mi></msub></mrow></mtd><mtd><mi>I</mi></mtd></mtr></mtable><mo>]</mo></mrow></mrow></math></maths><img file="US9898564B2_D0079.tif" /><img file="US9898564B2_D0080.tif" /><img file="US9898564B2_D0081.tif" /><img file="US9898564B2_D0082.tif" /><img file="US9898564B2_D0083.tif" /><img file="US9898564B2_D0084.tif" /><img file="US9898564B2_D0085.tif" /><img file="US9898564B2_D0086.tif" /><img file="US9898564B2_D0087.tif" /><img file="US9898564B2_D0088.tif" /><img file="US9898564B2_D0089.tif" /><img file="US9898564B2_D0090.tif" /><img file="US9898564B2_D0091.tif" /><img file="US9898564B2_D0092.tif" /><img file="US9898564B2_D0093.tif" /><img file="US9898564B2_D0094.tif" /><img file="US9898564B2_D0095.tif" /><img file="US9898564B2_D0096.tif" /><img file="US9898564B2_D0097.tif" /><br /> After the congruence transform X^TGX and X^TCX the connection susceptibility matrix C_Cbecomes zero and Y(s) still remains the same. It is noted that the above mentioned X has V dependency. In the calculation we need to preserve up to V²term since V contains 1st order of random variable and we need computation to the 2nd order. For example, <br /><i>G</i>_I⁻¹=(<i>G</i>_I,0<i>+V</i>)⁻¹=(<i>I+G</i>_I,0⁻¹<i>V</i>)⁻¹<i>G</i>_I,0⁻¹<i>=G</i>_I,0⁻¹<i>−G</i>_I,0⁻¹<i>VG</i>_I,0⁻¹<i>+G</i>_I,0⁻¹<i>VG</i>_I,0⁻¹<i>V G</i>_I0⁻¹<br /> Note that the square terms for the random variables in V doesn't contribute in V²since we only need up to the 2nd order term of random variable. Therefore, X can be calculated to be <br /><i>X=X</i>₀<i>+V </i><br /><i>V=Σ</i>_i=1^N<i>X</i>_i<i>v</i>_i<br /> Where X₀is the nominal part of X, V is the variation part consisting N variational terms up to the second order of each independent variation parameter and X_iis the coefficient of each variation term v_i. <br /> For the sake of brevity of notation we stick to the same formula for Y(s) after congruence transform by X with the understanding that Cc is zero and the remaining matrices still up to the 2nd order of random variables but with different matrix coefficients. The admittance matrix Y(s) can then be written as <br /><i>Y</i>(<i>s</i>)=<i>G</i>_P<i>+sC</i>_P−(<i>G</i>_C)^T(<i>I+sG</i>_I⁻¹<i>C</i>_I)⁻¹(<i>G</i>_I⁻¹<i>G</i>_C)<br /> The next step is to use Arnoldi's procedure in finding the orthonormal bases [W₀,W₁, . . . W_q−1] for the Krylov space Kr(G_I⁻¹C_I, G_I⁻¹G_C, q) for matching q moments of the multiport admittance. We start with W_I, which is G_I⁻¹G_Cand followed by QR decomposition if the circuit has more than one port. It is worth noting that in QR process, we need to get vector divided by its norm. Here we use a simple example to illustrate this concept. Assuming there is one random parameter x, a vector with two components up to the second order of x is something like

0062<maths id="MATH-US-00006" num="00006"><math overflow="scroll"><mrow><mo> </mo><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mn>4</mn><mo>+</mo><mrow><mn>2</mn><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>x</mi></mrow><mo>+</mo><mrow><mn>3</mn><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msup><mi>x</mi><mn>2</mn></msup></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mn>3</mn><mo>+</mo><mi>x</mi><mo>+</mo><mrow><mn>2</mn><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msup><mi>x</mi><mn>2</mn></msup></mrow></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow></math></maths><img file="US9898564B2_D0098.tif" /><img file="US9898564B2_D0099.tif" /><img file="US9898564B2_D0100.tif" /><img file="US9898564B2_D0101.tif" /><img file="US9898564B2_D0102.tif" /><img file="US9898564B2_D0103.tif" /><img file="US9898564B2_D0104.tif" /><img file="US9898564B2_D0105.tif" /><img file="US9898564B2_D0106.tif" /><img file="US9898564B2_D0107.tif" /><img file="US9898564B2_D0108.tif" /><img file="US9898564B2_D0109.tif" /><img file="US9898564B2_D0110.tif" /><img file="US9898564B2_D0111.tif" /><img file="US9898564B2_D0112.tif" /><img file="US9898564B2_D0113.tif" /><img file="US9898564B2_D0114.tif" /><img file="US9898564B2_D0115.tif" /><img file="US9898564B2_D0116.tif" /><br /> The norm is obtained by first taking the square <br />(4+2<i>x+</i>3<i>x</i>²)²+(3+1<i>x+</i>2<i>x</i>²)²=(16+16<i>x+</i>28<i>x</i>²)+(9+6<i>x+</i>13<i>x</i>²)=25+22<i>x+</i>41<i>x</i>²<br /> Then square root is in the format of (a+bx+cx²), and we easily get 5+2.2x+7.232x². As to W₂, W₃etc. they are obtained through standard procedure of Gram-Schmidt orthogonalization. We end up with the Arnoldi vector Wi (i=0, 1 . . . q−1) with variation effect as follows <br /><i>W</i>_i<i>=W</i>_i0<i>+M </i><br /><i>M=Σ</i>_m=1^N<i>W</i>_i,m<i>v</i>_m

0063Here W_i0is the nominal part of ith vector W_i, and W_i,mis the coefficient of the mth random parameter v_mwhich may contain second order of independent random variable. Set W=[W₀W₁. . . W_q−1] which is an orthonormal matrix spanning the Krylov space Kr(G_I⁻¹C_I, G_I⁻¹G_C, q). To preserve passivity of the circuit, the congruence transform of G and C by W is <b>1004</b><br /><i>{tilde over (G)}</i>_I<i>=W</i>^T<i>G</i>_I<i>W </i><br /><i>{tilde over (C)}</i>_I<i>=W</i>^T<i>C</i>_I<i>W </i><br /><i>{tilde over (G)}</i>_C<i>=W</i>^T<i>G</i>_C<br /><i>Y</i>(<i>s</i>)=<i>G</i>_P<i>+sC</i>_P−(<i>{tilde over (G)}</i>_C)^T(<i>{tilde over (G)}</i>_I<i>+s{tilde over (C)}</i>_I)⁻¹(<i>{tilde over (G)}</i>_C)

0064Now we are in the position to calculate poles and residues with variation terms. Y(s) is rewritten as follows, <br /><i>Y</i>(<i>s</i>)=<i>G</i>_P<i>+sC</i>_P−(<i>{tilde over (G)}</i>_C)^T(<i>I+s{tilde over (G)}</i>_I⁻¹<i>{tilde over (C)}</i>_I)⁻¹(<i>{tilde over (G)}</i>_I⁻¹<i>{tilde over (G)}</i>_C)<br /><i>A={tilde over (G)}</i>_I⁻¹<i>{tilde over (C)}</i>_I<i>=A</i>₀<i>+V </i><br /><i>V=Σ</i>_i=1^N<i>V</i>_i<i>y</i>_i<br /><i>B={tilde over (G)}</i>_I⁻¹<i>{tilde over (G)}</i>_C<i>=B</i>₀<i>+Y </i><br /><i>Y=Σ</i>_i=1^N<i>Y</i>_i<i>y</i>_i<br /><i>C</i>=(<i>{tilde over (G)}</i>_C)^T<i>=C</i>₀<i>+Z </i><br /><i>Z=Σ</i>_i−1^N<i>Z</i>_i<i>y</i>_i<br /> Note that A is the reduced matrix by Arnoldi method by considering variation effects up to the 2nd order of random parameters. Here we have <b>1005</b>

0065<maths id="MATH-US-00007" num="00007"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>Y</mi><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><msub><mi>G</mi><mi>P</mi></msub><mo>+</mo><mrow><mi>s</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>C</mi><mi>P</mi></msub></mrow><mo>-</mo><mrow><mrow><mo>(</mo><mrow><msub><mi>C</mi><mn>0</mn></msub><mo>+</mo><mi>Z</mi></mrow><mo>)</mo></mrow><mo>⁢</mo><msup><mrow><mo>(</mo><mrow><mi>I</mi><mo>+</mo><mrow><mi>s</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msub><mi>A</mi><mn>0</mn></msub><mo>+</mo><mi>V</mi></mrow><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><mrow><mo>(</mo><mrow><msub><mi>B</mi><mn>0</mn></msub><mo>+</mo><mi>Y</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><msub><mi>G</mi><mi>P</mi></msub><mo>+</mo><mrow><mi>s</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>C</mi><mi>P</mi></msub></mrow><mo>-</mo><mrow><msup><mrow><msub><mi>C</mi><mn>0</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>I</mi><mo>+</mo><mrow><mi>s</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>A</mi><mn>0</mn></msub></mrow></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><msub><mi>B</mi><mn>0</mn></msub></mrow><mo>+</mo><mrow><msup><mrow><msub><mi>C</mi><mn>0</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>I</mi><mo>+</mo><mrow><mi>s</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>A</mi><mn>0</mn></msub></mrow></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><mi>Y</mi></mrow><mo>+</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi /><mo>⁢</mo><mrow><mrow><msup><mrow><mi>Z</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>I</mi><mo>+</mo><mrow><mi>s</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>A</mi><mn>0</mn></msub></mrow></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><mi>sV</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msup><mrow><mo>(</mo><mrow><mi>I</mi><mo>+</mo><msub><mi>sA</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><msub><mi>B</mi><mn>0</mn></msub></mrow><mo>+</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi /><mo>⁢</mo><mrow><mrow><msup><mrow><msub><mi>C</mi><mn>0</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>I</mi><mo>+</mo><mrow><mi>s</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>A</mi><mn>0</mn></msub></mrow></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><msup><mrow><mi>sV</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>I</mi><mo>+</mo><msub><mi>sA</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><mi>Y</mi></mrow><mo>+</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi /><mo>⁢</mo><mrow><mrow><msup><mrow><msub><mi>C</mi><mn>0</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>I</mi><mo>+</mo><msub><mi>sA</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><msup><mrow><mi>sV</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>I</mi><mo>+</mo><msub><mi>sA</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><msub><mi>B</mi><mn>0</mn></msub></mrow><mo>+</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi /><mo>⁢</mo><mrow><msup><mrow><msub><mi>C</mi><mn>0</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>I</mi><mo>+</mo><msub><mi>sA</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><msup><mrow><mi>sV</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>I</mi><mo>+</mo><msub><mi>sA</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><msup><mrow><mi>sV</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>I</mi><mo>+</mo><msub><mi>sA</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><msub><mi>B</mi><mn>0</mn></msub></mrow></mrow></mtd></mtr></mtable></math></maths><img file="US9898564B2_D0117.tif" /><img file="US9898564B2_D0118.tif" /><img file="US9898564B2_D0119.tif" /><img file="US9898564B2_D0120.tif" /><img file="US9898564B2_D0121.tif" /><img file="US9898564B2_D0122.tif" /><img file="US9898564B2_D0123.tif" /><img file="US9898564B2_D0124.tif" /><img file="US9898564B2_D0125.tif" /><img file="US9898564B2_D0126.tif" /><img file="US9898564B2_D0127.tif" /><img file="US9898564B2_D0128.tif" /><img file="US9898564B2_D0129.tif" /><img file="US9898564B2_D0130.tif" /><img file="US9898564B2_D0131.tif" /><img file="US9898564B2_D0132.tif" /><img file="US9898564B2_D0133.tif" /><img file="US9898564B2_D0134.tif" /><img file="US9898564B2_D0135.tif" /><br /> calculated to the 2nd order of random parameters. The variation parts V, Y, and Z contain second order terms, so the quadratic terms like sV sV only contain 2nd order terms. Since A₀is the reduced matrix without variation, this matrix can be diagonalized by using congruence transform U consisting of eigenvectors of A₀. For the sake of brevity of notation, A₀is diagonalized matrix containing the eigenvalues of the original A₀. The matrix V after the congruence transform U cannot be diagonalized. The right hand matrices B₀=U^TB₀, Y=U^TY and the left hand matrices C₀=UC₀, Z=UZ. By simple observation for each matrix element of Y(s) it can have the form of simple, double, and cubic pole etc. However, we need to express simple pole and residue with its variation terms. Here we adopt the method by expanding pole and residue form in powers of variation parameters and compare with the exact solution of Y(s) to obtain the coefficients of variation terms for pole and residue. The procedure can be illustrated by the following example. Assuming there is only one random parameter x with the pole and residue form can be shown as follows <b>1006</b>

0066<maths id="MATH-US-00008" num="00008"><math overflow="scroll"><mrow><mfrac><mrow><mi>β</mi><mo>+</mo><mi>xc</mi><mo>+</mo><mrow><msup><mi>x</mi><mn>2</mn></msup><mo>⁢</mo><mi>d</mi></mrow></mrow><mrow><mi>s</mi><mo>+</mo><mi>α</mi><mo>+</mo><mi>xa</mi><mo>+</mo><mrow><msup><mi>x</mi><mn>2</mn></msup><mo>⁢</mo><mi>b</mi></mrow></mrow></mfrac><mo>=</mo><mrow><mfrac><mi>β</mi><mrow><mi>s</mi><mo>+</mo><mi>α</mi></mrow></mfrac><mo>+</mo><mrow><mi>x</mi><mo>⁡</mo><mrow><mo>[</mo><mrow><mfrac><mrow><mrow><mo>-</mo><mi>a</mi></mrow><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>β</mi></mrow><msup><mrow><mo>(</mo><mrow><mi>s</mi><mo>+</mo><mi>α</mi></mrow><mo>)</mo></mrow><mn>2</mn></msup></mfrac><mo>+</mo><mfrac><mi>c</mi><mrow><mi>s</mi><mo>+</mo><mi>α</mi></mrow></mfrac></mrow><mo>]</mo></mrow></mrow><mo>+</mo><mrow><msup><mi>x</mi><mn>2</mn></msup><mo>⁡</mo><mrow><mo>[</mo><mrow><mfrac><mrow><mrow><mo>-</mo><mi>β</mi></mrow><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>b</mi></mrow><msup><mrow><mo>(</mo><mrow><mi>s</mi><mo>+</mo><mi>α</mi></mrow><mo>)</mo></mrow><mn>2</mn></msup></mfrac><mo>-</mo><mfrac><mi>ac</mi><msup><mrow><mo>(</mo><mrow><mi>s</mi><mo>+</mo><mi>α</mi></mrow><mo>)</mo></mrow><mn>2</mn></msup></mfrac><mo>+</mo><mfrac><mi>d</mi><mrow><mo>(</mo><mrow><mi>s</mi><mo>+</mo><mi>α</mi></mrow><mo>)</mo></mrow></mfrac><mo>+</mo><mfrac><mrow><msup><mi>a</mi><mn>2</mn></msup><mo>⁢</mo><mi>β</mi></mrow><msup><mrow><mo>(</mo><mrow><mi>s</mi><mo>+</mo><mi>α</mi></mrow><mo>)</mo></mrow><mn>3</mn></msup></mfrac></mrow><mo>]</mo></mrow></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0136.tif" /><img file="US9898564B2_D0137.tif" /><img file="US9898564B2_D0138.tif" /><img file="US9898564B2_D0139.tif" /><img file="US9898564B2_D0140.tif" /><img file="US9898564B2_D0141.tif" /><img file="US9898564B2_D0142.tif" /><img file="US9898564B2_D0143.tif" /><img file="US9898564B2_D0144.tif" /><img file="US9898564B2_D0145.tif" /><img file="US9898564B2_D0146.tif" /><img file="US9898564B2_D0147.tif" /><img file="US9898564B2_D0148.tif" /><img file="US9898564B2_D0149.tif" /><img file="US9898564B2_D0150.tif" /><img file="US9898564B2_D0151.tif" /><img file="US9898564B2_D0152.tif" /><img file="US9898564B2_D0153.tif" /><img file="US9898564B2_D0154.tif" /><br /> The purpose is to find coefficients for random parameter x for the pole −α and residue β. By comparing with the exact result from Y(s) in powers of x and 1/(s+α) we can obtain a and c from x term and b and d from x²term. Note that in this example 1/(s+α)³term for x²term in fact is not needed, since the unknown a in the coefficient a²β has already been obtained in the other terms.

0067Referring back to <figref idref="DRAWINGS">FIG. 1</figref><b>110</b> for another aspect of the invention, the method in calculating the effective capacitance in the presence of variation effect is further discussed in <figref idref="DRAWINGS">FIG. 11</figref> with one port <b>1101</b> after we have obtained the admittance matrix in terms of poles and residues expressed in powers of variation parameters read from file <b>105</b>. The well-known criterion is used in obtaining effective capacitance, namely requiring the charge injected into the driving node of RLC interconnect from the driving gate using effective capacitance to be the same as that as obtained by using voltage at the said driving node and the admittance matrix for the RLC. Here we illustrate this method by using an example for the voltage wave form at the driving node of RLC, although the method is readily apparent to those of ordinary skill in the art for different types of voltage waveform. Here we have

0068<maths id="MATH-US-00009" num="00009"><math overflow="scroll"><mrow><mrow><mi>V</mi><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><msub><mi>V</mi><mi>i</mi></msub><mo>-</mo><msup><mi>ct</mi><mn>2</mn></msup></mrow></mtd><mtd><mrow><mn>0</mn><mo>≤</mo><mi>t</mi><mo>≤</mo><msub><mi>t</mi><mi>x</mi></msub></mrow></mtd></mtr><mtr><mtd><mrow><mi>a</mi><mo>+</mo><mrow><mi>b</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mi>x</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mtd><mtd><mrow><msub><mi>t</mi><mi>x</mi></msub><mo>≤</mo><mi>t</mi><mo>≤</mo><msub><mi>t</mi><mi>D</mi></msub></mrow></mtd></mtr><mtr><mtd><mrow><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mrow><mi>f</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msup><mi>e</mi><mi>td</mi></msup></mrow><mo>+</mo><msub><mi>V</mi><mi>f</mi></msub></mrow></mrow></mtd><mtd><mrow><mi>t</mi><mo>≥</mo><msub><mi>t</mi><mi>D</mi></msub></mrow></mtd></mtr></mtable></mrow></mrow></math></maths><img file="US9898564B2_D0155.tif" /><img file="US9898564B2_D0156.tif" /><img file="US9898564B2_D0157.tif" /><img file="US9898564B2_D0158.tif" /><img file="US9898564B2_D0159.tif" /><img file="US9898564B2_D0160.tif" /><img file="US9898564B2_D0161.tif" /><img file="US9898564B2_D0162.tif" /><img file="US9898564B2_D0163.tif" /><img file="US9898564B2_D0164.tif" /><img file="US9898564B2_D0165.tif" /><img file="US9898564B2_D0166.tif" /><img file="US9898564B2_D0167.tif" /><img file="US9898564B2_D0168.tif" /><img file="US9898564B2_D0169.tif" /><img file="US9898564B2_D0170.tif" /><img file="US9898564B2_D0171.tif" /><img file="US9898564B2_D0172.tif" /><img file="US9898564B2_D0173.tif" /><br /> As shown in <figref idref="DRAWINGS">FIG. 12</figref>, the origin of time is chosen to be the point where the input of the driver starts making transition, V_iis the initial value Vdd (0) when V(t) is in fall(rise) transition, and V_fis the final node value Vdd (0) when V(t) is in rise(fall) transition. In the following discussion we assume t₀is 0. We define t_xto be the time when the voltage falls(rises) to 80%(20%) of Vdd. In <figref idref="DRAWINGS">FIG. 11</figref>, the admittance is written as follows assuming there is one port <b>1102</b>.

0069<maths id="MATH-US-00010" num="00010"><math overflow="scroll"><mrow><mrow><mi>i</mi><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mrow><mrow><mi>Y</mi><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><mi>V</mi><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow></mrow><mo>+</mo><msub><mi>I</mi><mi>init</mi></msub></mrow><mo>=</mo><mrow><mrow><mrow><mo>(</mo><mrow><mrow><mi>α</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>s</mi></mrow><mo>+</mo><mi>β</mi><mo>+</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mfrac><msub><mi>δ</mi><mi>k</mi></msub><mrow><mi>s</mi><mo>+</mo><msub><mi>γ</mi><mi>k</mi></msub></mrow></mfrac></mrow></mrow><mo>)</mo></mrow><mo>⁢</mo><mrow><mi>V</mi><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow></mrow><mo>-</mo><mrow><mi>α</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>V</mi><mi>i</mi></msub></mrow><mo>+</mo><mrow><msub><mi>V</mi><mi>i</mi></msub><mo>⁢</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mfrac><mrow><msub><mi>δ</mi><mi>k</mi></msub><mo>/</mo><msub><mi>γ</mi><mi>k</mi></msub></mrow><mrow><mi>s</mi><mo>+</mo><msub><mi>γ</mi><mi>k</mi></msub></mrow></mfrac></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0174.tif" /><img file="US9898564B2_D0175.tif" /><img file="US9898564B2_D0176.tif" /><img file="US9898564B2_D0177.tif" /><img file="US9898564B2_D0178.tif" /><img file="US9898564B2_D0179.tif" /><img file="US9898564B2_D0180.tif" /><img file="US9898564B2_D0181.tif" /><img file="US9898564B2_D0182.tif" /><img file="US9898564B2_D0183.tif" /><img file="US9898564B2_D0184.tif" /><img file="US9898564B2_D0185.tif" /><img file="US9898564B2_D0186.tif" /><img file="US9898564B2_D0187.tif" /><img file="US9898564B2_D0188.tif" /><img file="US9898564B2_D0189.tif" /><img file="US9898564B2_D0190.tif" /><img file="US9898564B2_D0191.tif" /><img file="US9898564B2_D0192.tif" /><br /> in which V_iis he initial node value of the interconnect, and i(s) is the Laplace transform of the current i(t) at the said driving node of RLC interconnect. We require that

0070<maths id="MATH-US-00011" num="00011"><math overflow="scroll"><mrow><mrow><mi>Q</mi><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><msub><mi>C</mi><mi>eff</mi></msub><mo>⁢</mo><mrow><msubsup><mo>∫</mo><mn>0</mn><msub><mi>t</mi><mi>D</mi></msub></msubsup><mo>⁢</mo><mrow><mfrac><mrow><mi>d</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mi>V</mi><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow><mrow><mi>d</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow></mfrac><mo>⁢</mo><mstyle><mspace width="0.2em" height="0.2ex" /></mstyle><mo>⁢</mo><mi>d</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow></mrow></mrow><mo>=</mo><mrow><mrow><mrow><msub><mi>C</mi><mi>eff</mi></msub><mo>⁢</mo><mrow><mi>V</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>D</mi></msub><mo>)</mo></mrow></mrow></mrow><mo>-</mo><msub><mi>V</mi><mi>i</mi></msub></mrow><mo>=</mo><mrow><mrow><msubsup><mo>∫</mo><mn>0</mn><msub><mi>t</mi><mi>D</mi></msub></msubsup><mo>⁢</mo><mrow><mrow><mi>i</mi><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.2em" height="0.2ex" /></mstyle><mo>⁢</mo><mi>d</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow></mrow><mo>=</mo><mrow><msubsup><mo>∫</mo><mn>0</mn><msub><mi>t</mi><mi>D</mi></msub></msubsup><mo>⁢</mo><mrow><mrow><msup><mi>ℒ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mrow><mi>Y</mi><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><mi>V</mi><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow></mrow><mo>+</mo><msub><mi>I</mi><mi>init</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.2em" height="0.2ex" /></mstyle><mo>⁢</mo><mi>d</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0193.tif" /><img file="US9898564B2_D0194.tif" /><img file="US9898564B2_D0195.tif" /><img file="US9898564B2_D0196.tif" /><img file="US9898564B2_D0197.tif" /><img file="US9898564B2_D0198.tif" /><img file="US9898564B2_D0199.tif" /><img file="US9898564B2_D0200.tif" /><img file="US9898564B2_D0201.tif" /><img file="US9898564B2_D0202.tif" /><img file="US9898564B2_D0203.tif" /><img file="US9898564B2_D0204.tif" /><img file="US9898564B2_D0205.tif" /><img file="US9898564B2_D0206.tif" /><img file="US9898564B2_D0207.tif" /><img file="US9898564B2_D0208.tif" /><img file="US9898564B2_D0209.tif" /><img file="US9898564B2_D0210.tif" /><img file="US9898564B2_D0211.tif" /><br /> Here <img file="US9898564B2_D0212.tif" />⁻¹is the inverse Laplace transform and V(s) is the Laplace transform of V(t) as already defined <b>1104</b>. The value of C_effis achieved by using the above formula iteratively. The initial choice of C_effcan be chosen to be the total routing capacitance <b>1103</b>. The above formula is evaluated as follows. To make notation simple, δ and γ are used in replacement of δ_kand γ_kwithout loss of generality. We have

0071<maths id="MATH-US-00012" num="00012"><math overflow="scroll"><mrow><mrow><msup><mi>ℒ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mo>(</mo><mfrac><mi>δ</mi><mrow><mi>s</mi><mo>+</mo><mi>γ</mi></mrow></mfrac><mo>)</mo></mrow><mo>⁢</mo><mrow><mi>V</mi><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mfrac><mi>δ</mi><mi>γ</mi></mfrac><mo>⁢</mo><mrow><mi>V</mi><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow><mo>-</mo><mrow><msub><mi>V</mi><mi>i</mi></msub><mo>⁢</mo><mfrac><mi>δ</mi><mi>γ</mi></mfrac><mo>⁢</mo><msup><mi>e</mi><mrow><mo>-</mo><msup><mi>γ</mi><mi>t</mi></msup></mrow></msup></mrow><mo>-</mo><mrow><mfrac><mi>δ</mi><mi>γ</mi></mfrac><mo>⁢</mo><msup><mi>e</mi><mrow><mo>-</mo><msup><mi>γ</mi><mi>t</mi></msup></mrow></msup><mo>⁢</mo><mrow><msubsup><mo>∫</mo><mn>0</mn><mi>t</mi></msubsup><mo>⁢</mo><mrow><msup><mi>e</mi><mrow><mi>γ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>x</mi></mrow></msup><mo>⁢</mo><mrow><msup><mi>V</mi><mi>′</mi></msup><mo>⁡</mo><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.2em" height="0.2ex" /></mstyle><mo>⁢</mo><mi>d</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>x</mi></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0213.tif" /><img file="US9898564B2_D0214.tif" /><img file="US9898564B2_D0215.tif" /><img file="US9898564B2_D0216.tif" /><img file="US9898564B2_D0217.tif" /><img file="US9898564B2_D0218.tif" /><img file="US9898564B2_D0219.tif" /><img file="US9898564B2_D0220.tif" /><img file="US9898564B2_D0221.tif" /><img file="US9898564B2_D0222.tif" /><img file="US9898564B2_D0223.tif" /><img file="US9898564B2_D0224.tif" /><img file="US9898564B2_D0225.tif" /><img file="US9898564B2_D0226.tif" /><img file="US9898564B2_D0227.tif" /><img file="US9898564B2_D0228.tif" /><img file="US9898564B2_D0229.tif" /><img file="US9898564B2_D0230.tif" /><img file="US9898564B2_D0231.tif" /><maths id="MATH-US-00012-2" num="00012.2"><math overflow="scroll"><mrow><mrow><msup><mi>ℒ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mo>(</mo><mfrac><mrow><mi>δ</mi><mo>/</mo><mi>γ</mi></mrow><mrow><mi>s</mi><mo>+</mo><mi>γ</mi></mrow></mfrac><mo>)</mo></mrow><mo>⁢</mo><msub><mi>V</mi><mi>i</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><msub><mi>V</mi><mi>i</mi></msub><mo>⁢</mo><mfrac><mi>δ</mi><mi>γ</mi></mfrac><mo>⁢</mo><msup><mi>e</mi><mrow><mo>-</mo><msup><mi>γ</mi><mi>t</mi></msup></mrow></msup></mrow></mrow></math></maths><img file="US9898564B2_D0232.tif" /><img file="US9898564B2_D0233.tif" /><img file="US9898564B2_D0234.tif" /><img file="US9898564B2_D0235.tif" /><img file="US9898564B2_D0236.tif" /><img file="US9898564B2_D0237.tif" /><img file="US9898564B2_D0238.tif" /><img file="US9898564B2_D0239.tif" /><img file="US9898564B2_D0240.tif" /><img file="US9898564B2_D0241.tif" /><img file="US9898564B2_D0242.tif" /><img file="US9898564B2_D0243.tif" /><img file="US9898564B2_D0244.tif" /><img file="US9898564B2_D0245.tif" /><img file="US9898564B2_D0246.tif" /><img file="US9898564B2_D0247.tif" /><img file="US9898564B2_D0248.tif" /><img file="US9898564B2_D0249.tif" /><img file="US9898564B2_D0250.tif" /><maths id="MATH-US-00012-3" num="00012.3"><math overflow="scroll"><mrow><mrow><msup><mi>ℒ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mi>α</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mi>sV</mi><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow></mrow><mo>-</mo><mrow><mi>α</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>V</mi><mi>i</mi></msub></mrow></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><msup><mrow><mi>α</mi><mo>⁢</mo><mi>V</mi></mrow><mi>′</mi></msup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0251.tif" /><img file="US9898564B2_D0252.tif" /><img file="US9898564B2_D0253.tif" /><img file="US9898564B2_D0254.tif" /><img file="US9898564B2_D0255.tif" /><img file="US9898564B2_D0256.tif" /><img file="US9898564B2_D0257.tif" /><img file="US9898564B2_D0258.tif" /><img file="US9898564B2_D0259.tif" /><img file="US9898564B2_D0260.tif" /><img file="US9898564B2_D0261.tif" /><img file="US9898564B2_D0262.tif" /><img file="US9898564B2_D0263.tif" /><img file="US9898564B2_D0264.tif" /><img file="US9898564B2_D0265.tif" /><img file="US9898564B2_D0266.tif" /><img file="US9898564B2_D0267.tif" /><img file="US9898564B2_D0268.tif" /><img file="US9898564B2_D0269.tif" /><maths id="MATH-US-00012-4" num="00012.4"><math overflow="scroll"><mrow><mrow><msup><mi>ℒ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>β</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mi>V</mi><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mi>β</mi><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0270.tif" /><img file="US9898564B2_D0271.tif" /><img file="US9898564B2_D0272.tif" /><img file="US9898564B2_D0273.tif" /><img file="US9898564B2_D0274.tif" /><img file="US9898564B2_D0275.tif" /><img file="US9898564B2_D0276.tif" /><img file="US9898564B2_D0277.tif" /><img file="US9898564B2_D0278.tif" /><img file="US9898564B2_D0279.tif" /><img file="US9898564B2_D0280.tif" /><img file="US9898564B2_D0281.tif" /><img file="US9898564B2_D0282.tif" /><img file="US9898564B2_D0283.tif" /><img file="US9898564B2_D0284.tif" /><img file="US9898564B2_D0285.tif" /><img file="US9898564B2_D0286.tif" /><img file="US9898564B2_D0287.tif" /><img file="US9898564B2_D0288.tif" /><br /> Making use of

0072<maths id="MATH-US-00013" num="00013"><math overflow="scroll"><mrow><mrow><mi>β</mi><mo>+</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mfrac><msub><mi>δ</mi><mi>k</mi></msub><msub><mi>γ</mi><mi>k</mi></msub></mfrac></mrow></mrow><mo>=</mo><mn>0</mn></mrow></math></maths><img file="US9898564B2_D0289.tif" /><img file="US9898564B2_D0290.tif" /><img file="US9898564B2_D0291.tif" /><img file="US9898564B2_D0292.tif" /><img file="US9898564B2_D0293.tif" /><img file="US9898564B2_D0294.tif" /><img file="US9898564B2_D0295.tif" /><img file="US9898564B2_D0296.tif" /><img file="US9898564B2_D0297.tif" /><img file="US9898564B2_D0298.tif" /><img file="US9898564B2_D0299.tif" /><img file="US9898564B2_D0300.tif" /><img file="US9898564B2_D0301.tif" /><img file="US9898564B2_D0302.tif" /><img file="US9898564B2_D0303.tif" /><img file="US9898564B2_D0304.tif" /><img file="US9898564B2_D0305.tif" /><img file="US9898564B2_D0306.tif" /><img file="US9898564B2_D0307.tif" /><br /> We obtain <b>1105</b>

0073<maths id="MATH-US-00014" num="00014"><math overflow="scroll"><mrow><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mrow><mrow><mi>i</mi><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><msup><mi>ℒ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mrow><mi>Y</mi><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><mi>V</mi><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow></mrow><mo>+</mo><msub><mi>I</mi><mi>init</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mrow><mo>-</mo><msup><mi>e</mi><mrow><mrow><mo>-</mo><mi>γ</mi></mrow><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow></msup></mrow><mo>⁢</mo><mfrac><mi>δ</mi><mi>γ</mi></mfrac><mo>⁢</mo><mrow><msubsup><mo>∫</mo><mn>0</mn><mi>t</mi></msubsup><mo>⁢</mo><mrow><msup><mi>e</mi><mrow><mi>γ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>x</mi></mrow></msup><mo>⁢</mo><mrow><msup><mi>V</mi><mi>′</mi></msup><mo>⁡</mo><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.2em" height="0.2ex" /></mstyle><mo>⁢</mo><mi>d</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>x</mi></mrow></mrow></mrow><mo>+</mo><mrow><mi>α</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><msup><mi>V</mi><mi>′</mi></msup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0308.tif" /><img file="US9898564B2_D0309.tif" /><img file="US9898564B2_D0310.tif" /><img file="US9898564B2_D0311.tif" /><img file="US9898564B2_D0312.tif" /><img file="US9898564B2_D0313.tif" /><img file="US9898564B2_D0314.tif" /><img file="US9898564B2_D0315.tif" /><img file="US9898564B2_D0316.tif" /><img file="US9898564B2_D0317.tif" /><img file="US9898564B2_D0318.tif" /><img file="US9898564B2_D0319.tif" /><img file="US9898564B2_D0320.tif" /><img file="US9898564B2_D0321.tif" /><img file="US9898564B2_D0322.tif" /><img file="US9898564B2_D0323.tif" /><img file="US9898564B2_D0324.tif" /><img file="US9898564B2_D0325.tif" /><img file="US9898564B2_D0326.tif" /><maths id="MATH-US-00014-2" num="00014.2"><math overflow="scroll"><mrow><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mrow><mrow><msubsup><mo>∫</mo><mn>0</mn><mi>t</mi></msubsup><mo>⁢</mo><mrow><mrow><mi>i</mi><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.2em" height="0.2ex" /></mstyle><mo>⁢</mo><mi>d</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow></mrow><mo>=</mo><mrow><mrow><mfrac><mrow><mn>2</mn><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>c</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>δ</mi></mrow><msup><mi>γ</mi><mn>4</mn></msup></mfrac><mo>-</mo><mfrac><mrow><mn>2</mn><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>c</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>δ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow><msup><mi>γ</mi><mn>3</mn></msup></mfrac><mo>-</mo><mrow><mfrac><mrow><mn>2</mn><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>c</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>δ</mi></mrow><msup><mi>γ</mi><mn>4</mn></msup></mfrac><mo>⁢</mo><msup><mi>e</mi><mrow><mrow><mo>-</mo><mi>γ</mi></mrow><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow></msup></mrow><mo>-</mo><mrow><mrow><msup><mi>ct</mi><mn>2</mn></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>α</mi><mo>-</mo><mfrac><mi>δ</mi><msup><mi>γ</mi><mn>2</mn></msup></mfrac></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><mi>t</mi></mrow></mrow><mo>≤</mo><msub><mi>t</mi><mi>x</mi></msub></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0327.tif" /><img file="US9898564B2_D0328.tif" /><img file="US9898564B2_D0329.tif" /><img file="US9898564B2_D0330.tif" /><img file="US9898564B2_D0331.tif" /><img file="US9898564B2_D0332.tif" /><img file="US9898564B2_D0333.tif" /><img file="US9898564B2_D0334.tif" /><img file="US9898564B2_D0335.tif" /><img file="US9898564B2_D0336.tif" /><img file="US9898564B2_D0337.tif" /><img file="US9898564B2_D0338.tif" /><img file="US9898564B2_D0339.tif" /><img file="US9898564B2_D0340.tif" /><img file="US9898564B2_D0341.tif" /><img file="US9898564B2_D0342.tif" /><img file="US9898564B2_D0343.tif" /><img file="US9898564B2_D0344.tif" /><img file="US9898564B2_D0345.tif" /><maths id="MATH-US-00014-3" num="00014.3"><math overflow="scroll"><mrow><mrow><msubsup><mo>∫</mo><mn>0</mn><mi>t</mi></msubsup><mo>⁢</mo><mrow><mrow><mi>i</mi><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.2em" height="0.2ex" /></mstyle><mo>⁢</mo><mi>d</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow></mrow><mo>=</mo><mrow><mrow><mrow><mfrac><mrow><mn>2</mn><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>c</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>δ</mi></mrow><msup><mi>γ</mi><mn>4</mn></msup></mfrac><mo>⁢</mo><mrow><mo>(</mo><mrow><msup><mi>e</mi><mrow><mo>-</mo><mrow><mi>γ</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mi>x</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></msup><mo>-</mo><msup><mi>e</mi><mrow><mrow><mo>-</mo><mi>γ</mi></mrow><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow></msup></mrow><mo>)</mo></mrow></mrow><mo>-</mo><mfrac><mrow><mn>2</mn><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>c</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>δ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>t</mi><mi>x</mi></msub></mrow><msup><mi>γ</mi><mn>3</mn></msup></mfrac><mo>+</mo><mrow><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><mfrac><msub><mi>t</mi><mi>x</mi></msub><mn>2</mn></mfrac></mrow><mo>)</mo></mrow><mo>⁢</mo><mrow><mi>b</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>α</mi><mo>-</mo><mfrac><mi>δ</mi><msup><mi>γ</mi><mn>2</mn></msup></mfrac></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><msub><mi>t</mi><mi>x</mi></msub></mrow></mrow><mo>≤</mo><mi>t</mi><mo>≤</mo><msub><mi>t</mi><mi>D</mi></msub></mrow></mrow></math></maths><img file="US9898564B2_D0346.tif" /><img file="US9898564B2_D0347.tif" /><img file="US9898564B2_D0348.tif" /><img file="US9898564B2_D0349.tif" /><img file="US9898564B2_D0350.tif" /><img file="US9898564B2_D0351.tif" /><img file="US9898564B2_D0352.tif" /><img file="US9898564B2_D0353.tif" /><img file="US9898564B2_D0354.tif" /><img file="US9898564B2_D0355.tif" /><img file="US9898564B2_D0356.tif" /><img file="US9898564B2_D0357.tif" /><img file="US9898564B2_D0358.tif" /><img file="US9898564B2_D0359.tif" /><img file="US9898564B2_D0360.tif" /><img file="US9898564B2_D0361.tif" /><img file="US9898564B2_D0362.tif" /><img file="US9898564B2_D0363.tif" /><img file="US9898564B2_D0364.tif" /><maths id="MATH-US-00014-4" num="00014.4"><math overflow="scroll"><mrow><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mrow><mrow><msubsup><mo>∫</mo><mn>0</mn><mi>t</mi></msubsup><mo>⁢</mo><mrow><mrow><mi>i</mi><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.2em" height="0.2ex" /></mstyle><mo>⁢</mo><mi>d</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow></mrow><mo>=</mo><mrow><mrow><mrow><mfrac><mi>δ</mi><msup><mi>γ</mi><mn>2</mn></msup></mfrac><mo>⁢</mo><mrow><msup><mi>e</mi><mrow><mrow><mo>-</mo><mi>γ</mi></mrow><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>A</mi><mo>+</mo><mi>B</mi><mo>+</mo><mi>C</mi></mrow><mo>)</mo></mrow></mrow></mrow><mo>+</mo><mrow><mrow><mo>(</mo><mrow><mi>α</mi><mo>-</mo><mfrac><mi>δ</mi><msup><mi>γ</mi><mn>2</mn></msup></mfrac></mrow><mo>)</mo></mrow><mo>⁢</mo><mrow><mo>(</mo><mrow><mrow><mi>f</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msup><mi>e</mi><mi>td</mi></msup></mrow><mo>+</mo><msub><mi>V</mi><mi>f</mi></msub><mo>-</mo><msub><mi>V</mi><mi>i</mi></msub></mrow><mo>)</mo></mrow><mo>⁢</mo><mi>t</mi></mrow></mrow><mo>≥</mo><msub><mi>t</mi><mi>D</mi></msub></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0365.tif" /><img file="US9898564B2_D0366.tif" /><img file="US9898564B2_D0367.tif" /><img file="US9898564B2_D0368.tif" /><img file="US9898564B2_D0369.tif" /><img file="US9898564B2_D0370.tif" /><img file="US9898564B2_D0371.tif" /><img file="US9898564B2_D0372.tif" /><img file="US9898564B2_D0373.tif" /><img file="US9898564B2_D0374.tif" /><img file="US9898564B2_D0375.tif" /><img file="US9898564B2_D0376.tif" /><img file="US9898564B2_D0377.tif" /><img file="US9898564B2_D0378.tif" /><img file="US9898564B2_D0379.tif" /><img file="US9898564B2_D0380.tif" /><img file="US9898564B2_D0381.tif" /><img file="US9898564B2_D0382.tif" /><img file="US9898564B2_D0383.tif" /><maths id="MATH-US-00014-5" num="00014.5"><math overflow="scroll"><mrow><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mi>where</mi></mrow></math></maths><img file="US9898564B2_D0384.tif" /><img file="US9898564B2_D0385.tif" /><img file="US9898564B2_D0386.tif" /><img file="US9898564B2_D0387.tif" /><img file="US9898564B2_D0388.tif" /><img file="US9898564B2_D0389.tif" /><img file="US9898564B2_D0390.tif" /><img file="US9898564B2_D0391.tif" /><img file="US9898564B2_D0392.tif" /><img file="US9898564B2_D0393.tif" /><img file="US9898564B2_D0394.tif" /><img file="US9898564B2_D0395.tif" /><img file="US9898564B2_D0396.tif" /><img file="US9898564B2_D0397.tif" /><img file="US9898564B2_D0398.tif" /><img file="US9898564B2_D0399.tif" /><img file="US9898564B2_D0400.tif" /><img file="US9898564B2_D0401.tif" /><img file="US9898564B2_D0402.tif" /><maths id="MATH-US-00014-6" num="00014.6"><math overflow="scroll"><mrow><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mrow><mi>A</mi><mo>=</mo><mrow><mrow><mo>(</mo><mrow><mrow><mo>-</mo><mn>2</mn></mrow><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>c</mi></mrow><mo>)</mo></mrow><mo>⁢</mo><mrow><mo>(</mo><mrow><mrow><mrow><mo>-</mo><mfrac><mn>1</mn><msup><mi>γ</mi><mn>2</mn></msup></mfrac></mrow><mo>⁢</mo><msup><mi>e</mi><mrow><mi>γ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>t</mi><mi>x</mi></msub></mrow></msup></mrow><mo>+</mo><mrow><mfrac><msub><mi>t</mi><mi>x</mi></msub><mi>γ</mi></mfrac><mo>⁢</mo><msup><mi>e</mi><mrow><mi>γ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>t</mi><mi>x</mi></msub></mrow></msup></mrow><mo>+</mo><mfrac><mn>1</mn><msup><mi>γ</mi><mn>2</mn></msup></mfrac></mrow><mo>)</mo></mrow></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0403.tif" /><img file="US9898564B2_D0404.tif" /><img file="US9898564B2_D0405.tif" /><img file="US9898564B2_D0406.tif" /><img file="US9898564B2_D0407.tif" /><img file="US9898564B2_D0408.tif" /><img file="US9898564B2_D0409.tif" /><img file="US9898564B2_D0410.tif" /><img file="US9898564B2_D0411.tif" /><img file="US9898564B2_D0412.tif" /><img file="US9898564B2_D0413.tif" /><img file="US9898564B2_D0414.tif" /><img file="US9898564B2_D0415.tif" /><img file="US9898564B2_D0416.tif" /><img file="US9898564B2_D0417.tif" /><img file="US9898564B2_D0418.tif" /><img file="US9898564B2_D0419.tif" /><img file="US9898564B2_D0420.tif" /><img file="US9898564B2_D0421.tif" /><maths id="MATH-US-00014-7" num="00014.7"><math overflow="scroll"><mrow><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mrow><mi>B</mi><mo>=</mo><mrow><mfrac><mi>b</mi><mi>γ</mi></mfrac><mo>⁢</mo><mrow><mo>(</mo><mrow><msup><mi>e</mi><mrow><mi>γ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>t</mi><mi>D</mi></msub></mrow></msup><mo>-</mo><msup><mi>e</mi><mrow><mi>γ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>t</mi><mi>x</mi></msub></mrow></msup></mrow><mo>)</mo></mrow></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0422.tif" /><img file="US9898564B2_D0423.tif" /><img file="US9898564B2_D0424.tif" /><img file="US9898564B2_D0425.tif" /><img file="US9898564B2_D0426.tif" /><img file="US9898564B2_D0427.tif" /><img file="US9898564B2_D0428.tif" /><img file="US9898564B2_D0429.tif" /><img file="US9898564B2_D0430.tif" /><img file="US9898564B2_D0431.tif" /><img file="US9898564B2_D0432.tif" /><img file="US9898564B2_D0433.tif" /><img file="US9898564B2_D0434.tif" /><img file="US9898564B2_D0435.tif" /><img file="US9898564B2_D0436.tif" /><img file="US9898564B2_D0437.tif" /><img file="US9898564B2_D0438.tif" /><img file="US9898564B2_D0439.tif" /><img file="US9898564B2_D0440.tif" /><maths id="MATH-US-00014-8" num="00014.8"><math overflow="scroll"><mrow><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mrow><mi>C</mi><mo>=</mo><mrow><mi>fd</mi><mo>⁢</mo><mfrac><mn>1</mn><mrow><mi>d</mi><mo>+</mo><mi>γ</mi></mrow></mfrac><mo>⁢</mo><mrow><mo>(</mo><mrow><msup><mi>e</mi><mrow><mi>t</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>d</mi><mo>+</mo><mi>γ</mi></mrow><mo>)</mo></mrow></mrow></msup><mo>-</mo><msup><mi>e</mi><mrow><msub><mi>t</mi><mi>D</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>d</mi><mo>+</mo><mi>γ</mi></mrow><mo>)</mo></mrow></mrow></msup></mrow><mo>)</mo></mrow></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0441.tif" /><img file="US9898564B2_D0442.tif" /><img file="US9898564B2_D0443.tif" /><img file="US9898564B2_D0444.tif" /><img file="US9898564B2_D0445.tif" /><img file="US9898564B2_D0446.tif" /><img file="US9898564B2_D0447.tif" /><img file="US9898564B2_D0448.tif" /><img file="US9898564B2_D0449.tif" /><img file="US9898564B2_D0450.tif" /><img file="US9898564B2_D0451.tif" /><img file="US9898564B2_D0452.tif" /><img file="US9898564B2_D0453.tif" /><img file="US9898564B2_D0454.tif" /><img file="US9898564B2_D0455.tif" /><img file="US9898564B2_D0456.tif" /><img file="US9898564B2_D0457.tif" /><img file="US9898564B2_D0458.tif" /><img file="US9898564B2_D0459.tif" /><br /> Note that in the above formulae, the pole γ and residue δ refer to one of the poles and residues, and the summation with respect to all poles and residues are implied. The constant α then is independent of the summation of each pair of pole and residue. All the constants have variation terms to the second order. The coefficients b and c, and delays t_Dand t_xare also random variables calculated by using pre-characterized timing library with variations from input slew time and output loading based on C_effduring the process of iteration until the final C_effis obtained. Therefore, with all of terms such as poles, residues, t_xand t_Dbeing calculated to the 2nd order of random parameters, the term Q(t) up to the 2nd order of random parameters can also be achieved. For example, in calculating Q(t=t_D), we have one term like e^{γ t}_Dwith γ=γ_nom+X and t_D=t_D,nom+Y in which X and Y include variation terms up to 2nd order. Then, e^γt(t=t_D)=e^γ_nomt_D,nom(1+Xt_D,nom+Yγ_nom+XY t_D,nomγ_nom+X²t_D,nom²+Y²γ_nom²+2 XYt_D,nomγ_nom). By combining the coefficients of the same random parameter with the same order, e^γt(t=t_D) becomes e^γ_nom^t_D,nomZ where Z contain variation terms up to 2nd order. The calculation is straightforward but very tedious, so the final formula up to the 2nd order is not given here. Eventually we obtain Q(t=t_D)=Q₀+W with W being the variation term up to 2nd order of variation effects. Using <b>1106</b>

0074<maths id="MATH-US-00015" num="00015"><math overflow="scroll"><mrow><mrow><mrow><msub><mi>C</mi><mi>eff</mi></msub><mo>⁢</mo><mrow><mi>V</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>D</mi></msub><mo>)</mo></mrow></mrow></mrow><mo>-</mo><msub><mi>V</mi><mi>i</mi></msub></mrow><mo>=</mo><mrow><mrow><mi>Q</mi><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><msub><mi>C</mi><mi>eff</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>a</mi><mo>+</mo><mrow><mi>b</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msub><mi>t</mi><mi>D</mi></msub><mo>-</mo><msub><mi>t</mi><mi>x</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>-</mo><msub><mi>V</mi><mi>i</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><msub><mi>C</mi><mi>eff</mi></msub><mo>⁢</mo><mrow><mi>b</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msub><mi>t</mi><mi>D</mi></msub><mo>-</mo><mfrac><msub><mi>t</mi><mi>x</mi></msub><mn>2</mn></mfrac></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0460.tif" /><img file="US9898564B2_D0461.tif" /><img file="US9898564B2_D0462.tif" /><img file="US9898564B2_D0463.tif" /><img file="US9898564B2_D0464.tif" /><img file="US9898564B2_D0465.tif" /><img file="US9898564B2_D0466.tif" /><img file="US9898564B2_D0467.tif" /><img file="US9898564B2_D0468.tif" /><img file="US9898564B2_D0469.tif" /><img file="US9898564B2_D0470.tif" /><img file="US9898564B2_D0471.tif" /><img file="US9898564B2_D0472.tif" /><img file="US9898564B2_D0473.tif" /><img file="US9898564B2_D0474.tif" /><img file="US9898564B2_D0475.tif" /><img file="US9898564B2_D0476.tif" /><img file="US9898564B2_D0477.tif" /><img file="US9898564B2_D0478.tif" /><br /> C_effis reevaluated <b>1107</b>, and using new C_eff, which is a random variable up to 2nd order of random parameter, to obtain new constants such as t_D, t_x, a, b, c and achieve new Q(t) accordingly. This process is iterated until convergence <b>1108</b>.

0075Referring back to <figref idref="DRAWINGS">FIG. 1</figref><b>110</b> for another aspect of the invention, the method in calculating the effective capacitance in the presence of variation effect is further discussed in <figref idref="DRAWINGS">FIG. 13</figref> with cross-talk <b>1301</b> after we have obtained the admittance matrix in terms of poles and residues expressed in powers of variation parameters read from file <b>105</b>. Without loss of generality, assuming there are two ports for one victim and one aggressor as shown in <figref idref="DRAWINGS">FIG. 14</figref>. We have <b>1302</b><br /><i>A</i>₁₁(<i>s</i>)<i>V</i>₁(<i>s</i>)+<i>A</i>₁₂(<i>s</i>)<i>V</i>₂(<i>s</i>)=<i>i</i>₁(<i>s</i>)<br /><i>A</i>₂₁(<i>s</i>)<i>V</i>₁(<i>s</i>)+<i>A</i>₂₂(<i>s</i>)<i>V</i>₂(<i>s</i>)=<i>i</i>₂(<i>s</i>)<br /> in which A₁₁is the matrix element of 2×2 admittance matrix, V₁(s)(i₁(s)) and V₂(s) (i₂(s)) are voltages(currents) in s domain at victim and aggressor node. The purpose is to iteratively <b>1303</b> find the effective capacitances C_eff,1and C_eff,2at victim and aggressor nodes 1 and 2, respectively. Initial values for C_eff,1and C_eff,2are given first. Then the waveforms in terms of t_x,iand t_D,iat node i (i=1 and 2) are evaluated with t_xand t_Dbeing defined similar to the those in the case of one port. Here all of the constants C_eff,i, t_x,i, t_D,i(i=0,1) obviously are random variables up to 2nd order of random parameters. We have <b>1304</b><br />∫₀^t^{<sub2>D1</sub2>}<i>i</i>₁(<i>t</i>)<i>dt=∫</i>₀^t^{<sub2>D1</sub2>}<img file="US9898564B2_D0479.tif" />⁻¹(<i>i</i>_i(<i>s</i>))<i>dt=Q</i>₁<br />=<i>Q</i>₁₁<i>+Q</i>₁₂=∫₀^t^{<sub2>D1</sub2>}<img file="US9898564B2_D0480.tif" />⁻¹(<i>A</i>₁₁(<i>s</i>)<i>V</i>₁(<i>s</i>))<i>dt+∫</i>₀^t^{<sub2>D1</sub2>}<img file="US9898564B2_D0481.tif" />⁻¹(<i>A</i>₁₂(<i>s</i>)<i>V</i>₂(<i>s</i>))<i>dt </i><br /> Note that waveforms V₁(t) and V₂(<i>t</i>) in time domain at nodes 1 and 2 have different starting points. The integration range from 0 to t_D1are with respect to the starting point of waveform at node 1. We therefore need to transform 0 and t_D1to the coordinate system used by V₂(t). For example the waveform V₁(t) starts from, say T₁, from origin, while waveform at node 2 starts from T₂as shown in <figref idref="DRAWINGS">FIG. 14</figref>. Therefore, in carrying out the integral involving V₂(t) 0 and t_D,1become T₁−T₂and t_D,1+T₁−T₂. As to integration, the same formula as being used in one port case <b>1305</b> is adopted. Then C_eff,1is obtained by Q₁<b>1306</b>

0076<maths id="MATH-US-00016" num="00016"><math overflow="scroll"><mrow><msub><mi>C</mi><mrow><mi>eff</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>=</mo><mfrac><msub><mi>Q</mi><mn>1</mn></msub><mrow><msub><mi>b</mi><mn>1</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><msub><mi>t</mi><mrow><mi>D</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>-</mo><mrow><msub><mi>t</mi><mrow><mi>x</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow></mrow></mfrac></mrow></math></maths><img file="US9898564B2_D0482.tif" /><img file="US9898564B2_D0483.tif" /><img file="US9898564B2_D0484.tif" /><img file="US9898564B2_D0485.tif" /><img file="US9898564B2_D0486.tif" /><img file="US9898564B2_D0487.tif" /><img file="US9898564B2_D0488.tif" /><img file="US9898564B2_D0489.tif" /><img file="US9898564B2_D0490.tif" /><img file="US9898564B2_D0491.tif" /><img file="US9898564B2_D0492.tif" /><img file="US9898564B2_D0493.tif" /><img file="US9898564B2_D0494.tif" /><img file="US9898564B2_D0495.tif" /><img file="US9898564B2_D0496.tif" /><img file="US9898564B2_D0497.tif" /><img file="US9898564B2_D0498.tif" /><img file="US9898564B2_D0499.tif" /><img file="US9898564B2_D0500.tif" /><br /> C_eff,2is obtained similarly. Through tedious calculation all of the above constants are random variable with nominal part and variation part up to the 2nd order of random parameter, thus C_eff,1and C_eff,2are also calculated to the 2nd power in random parameters. The process is iterated until convergence <b>1307</b> is reached. In cases of more than one aggressors, we need to find the switching tomes for each aggressor with respect to the victim in order to obtain maximum delay from victim input to victim output. This procedure is similar to that in the case of STA and not repeated here. The discussion on victim glitch is exactly the same as that in the case of calculating maximum delay of the victim except setting voltage a constant at the input of the victim driver. Therefore, there is no further discussion on glitch in cross-talk.

0077Referring back to <figref idref="DRAWINGS">FIG. 1</figref><b>111</b> for another aspect of the invention, the method for calculating delay as a random variable is addressed assuming the switching times of the aggressors are given. As shown in <figref idref="DRAWINGS">FIG. 15</figref> we use voltage transfer from RLC inputs to outputs <b>1501</b> to get output waveform by utilizing the waveform at the inputs. In case there are n inputs and m outputs, we have <br /><i>V</i>_out(<i>s</i>)=<i>T</i>(<i>s</i>)<i>V</i>_in(<i>s</i>)<br /> in which Vout (s) is a m×1 matrix, T(s) is m×n matrix and Vin (s) is n×1 matrix with each matrix element being a random variable up to the 2^ndorder of variation effects. Both admittance matrix and voltage transfer are treated under the same formulation. By using the same Arnoldi's method <b>1502</b> in obtaining W=[W₀W₁. . . W_q−1] which is an orthonormal matrix spanning the Krylov space Kr(G_I⁻¹C_I, G_I⁻¹G_C, q) and making the congruence transform as in the case of calculating admittance matrix, we achieve <b>1503</b><br /><i>Ñ=W</i>^T<i>N </i><br /><i>T</i>(<i>s</i>)=−({tilde over (<i>N</i>)})^T(<i>I+s{tilde over (G)}</i>_I⁻¹<i>{tilde over (C)}</i>_I)⁻¹(<i>{tilde over (G)}</i>_I⁻¹<i>{tilde over (G)}</i>_C)<br /> here N being defined as n×m matrix if the circuit has n outputs and m internal nodes and N initially prior to congruence transform by W, assuming C_Cis zero without loss of generality, is <br /><i>N</i>_ij=1 if <i>i</i>^thinput=<i>j</i>^thinternal node<br /> By comparing T(s) with Y(s) <br /><i>Y</i>(<i>s</i>)=<i>G</i>_P<i>+sC</i>_P−(<i>{tilde over (G)}</i>_C)^T(<i>I+s{tilde over (G)}</i>_I⁻¹<i>{tilde over (C)}</i>_I)⁻¹(<i>{tilde over (G)}</i>_I⁻¹<i>{tilde over (G)}C</i>)<br /> as obtained before, we see that G_P+s C_Pis not contained in T(s) and {tilde over (G)}_Cin Y(s) is replaced by Ñ in T(s). Thus, the matrix element of T(s) does not include α+βs. Similar to the handling of admittance matrix the voltage transfer can be expanded to the 2^ndorder of variation terms, and then fitted into simple pole and residue including variation terms to obtain poles and residues to the second order of variations. Without loss of generality we assume V_out(s) is a 3×1 matrix, T(s) is 3×2 matrix and V_in(s) is 2×1 matrix, V_out,1(t) and V_out,2(t) refer to waveform at output nodes of victim and aggressor, respectively. For output 1, we have <br /><i>V</i>_out,1(<i>t</i>)=<img file="US9898564B2_D0501.tif" />⁻¹(<i>T</i>₁₁(<i>s</i>)<i>V</i>_in,1(<i>s</i>))+<img file="US9898564B2_D0502.tif" />⁻¹(<i>T</i>₁₂(<i>s</i>)<i>V</i>_in,2(<i>s</i>))<br /> V_in,1(t) and V_in,2(t) are defined similarly as in the discussion of effective capacitance for the case of one port with the combination of three regions including quadratic, linear and exponential forms. In the actual implementation the quadratic part can be neglected without suffering too much inaccuracy. In this approximation V_in,1(t) stays at initial constant value V_i, which is either Vdd or 0 depending on fall or rise transition at RLC input, for the period of time denoted by t₀before the waveform starts changing. V_in,1(t) and V_in,2(t) have their own t₀, meaning they have different switching times. Using the aforementioned formula as follows, <br /><i>V</i>_in,1(<i>t</i>)=<i>a+b</i>(<i>t−t</i>_x)<br /> The starting point t₀when V_in,1(t) changes from initial value V_iis

0078<maths id="MATH-US-00017" num="00017"><math overflow="scroll"><mrow><msub><mi>t</mi><mn>0</mn></msub><mo>=</mo><mfrac><mrow><mo>(</mo><mrow><msub><mi>V</mi><mi>i</mi></msub><mo>-</mo><mi>a</mi><mo>+</mo><mrow><mi>b</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>t</mi><mi>x</mi></msub></mrow></mrow><mo>)</mo></mrow><mi>b</mi></mfrac></mrow></math></maths><img file="US9898564B2_D0503.tif" /><img file="US9898564B2_D0504.tif" /><img file="US9898564B2_D0505.tif" /><img file="US9898564B2_D0506.tif" /><img file="US9898564B2_D0507.tif" /><img file="US9898564B2_D0508.tif" /><img file="US9898564B2_D0509.tif" /><img file="US9898564B2_D0510.tif" /><img file="US9898564B2_D0511.tif" /><img file="US9898564B2_D0512.tif" /><img file="US9898564B2_D0513.tif" /><img file="US9898564B2_D0514.tif" /><img file="US9898564B2_D0515.tif" /><img file="US9898564B2_D0516.tif" /><img file="US9898564B2_D0517.tif" /><img file="US9898564B2_D0518.tif" /><img file="US9898564B2_D0519.tif" /><img file="US9898564B2_D0520.tif" /><img file="US9898564B2_D0521.tif" /><br /> The waveform at the RLC input is as follows <b>1504</b>,

0079<maths id="MATH-US-00018" num="00018"><math overflow="scroll"><mrow><mrow><msub><mi>V</mi><mrow><mi>in</mi><mo>,</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mo>,</mo><mn>2</mn></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><msub><mi>V</mi><mi>i</mi></msub></mtd><mtd><mrow><mn>0</mn><mo>≤</mo><mi>t</mi><mo>≤</mo><msub><mi>t</mi><mn>0</mn></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>V</mi><mi>i</mi></msub><mo>+</mo><mrow><mi>b</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow></mrow></mtd><mtd><mrow><msub><mi>t</mi><mn>0</mn></msub><mo>≤</mo><mi>t</mi><mo>≤</mo><msub><mi>t</mi><mi>D</mi></msub></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mi>f</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msup><mi>e</mi><mrow><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow><mo>⁢</mo><mi>d</mi></mrow></msup></mrow><mo>+</mo><msub><mi>V</mi><mi>f</mi></msub></mrow></mtd><mtd><mrow><mi>t</mi><mo>≥</mo><msub><mi>t</mi><mi>D</mi></msub></mrow></mtd></mtr></mtable></mrow></mrow></math></maths><img file="US9898564B2_D0522.tif" /><img file="US9898564B2_D0523.tif" /><img file="US9898564B2_D0524.tif" /><img file="US9898564B2_D0525.tif" /><img file="US9898564B2_D0526.tif" /><img file="US9898564B2_D0527.tif" /><img file="US9898564B2_D0528.tif" /><img file="US9898564B2_D0529.tif" /><img file="US9898564B2_D0530.tif" /><img file="US9898564B2_D0531.tif" /><img file="US9898564B2_D0532.tif" /><img file="US9898564B2_D0533.tif" /><img file="US9898564B2_D0534.tif" /><img file="US9898564B2_D0535.tif" /><img file="US9898564B2_D0536.tif" /><img file="US9898564B2_D0537.tif" /><img file="US9898564B2_D0538.tif" /><img file="US9898564B2_D0539.tif" /><img file="US9898564B2_D0540.tif" /><br /> It is emphasized that all of t, t₀and t_Dare measured from the origin which is the starting point when the input of the driver starts changing. We have

0080<maths id="MATH-US-00019" num="00019"><math overflow="scroll"><mrow><mrow><msup><mi>ℒ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><msub><mi>T</mi><mn>11</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><msub><mi>V</mi><mrow><mi>in</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mrow><mo>-</mo><msup><mi>e</mi><mrow><mrow><mo>-</mo><mi>γ</mi></mrow><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>t</mi></mrow></msup></mrow><mo>⁢</mo><mfrac><mi>δ</mi><mi>γ</mi></mfrac><mo>⁢</mo><mrow><msubsup><mo>∫</mo><mn>0</mn><mi>t</mi></msubsup><mo>⁢</mo><mrow><msup><mi>e</mi><mrow><mi>γ</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>x</mi></mrow></msup><mo>⁢</mo><mrow><msubsup><mi>V</mi><mrow><mi>in</mi><mo>,</mo><mn>1</mn></mrow><mi>′</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.2em" height="0.2ex" /></mstyle><mo>⁢</mo><mi>d</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>x</mi></mrow></mrow></mrow><mo>+</mo><mrow><mfrac><mi>δ</mi><mi>γ</mi></mfrac><mo>⁢</mo><mrow><msub><mi>V</mi><mrow><mi>in</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0541.tif" /><img file="US9898564B2_D0542.tif" /><img file="US9898564B2_D0543.tif" /><img file="US9898564B2_D0544.tif" /><img file="US9898564B2_D0545.tif" /><img file="US9898564B2_D0546.tif" /><img file="US9898564B2_D0547.tif" /><img file="US9898564B2_D0548.tif" /><img file="US9898564B2_D0549.tif" /><img file="US9898564B2_D0550.tif" /><img file="US9898564B2_D0551.tif" /><img file="US9898564B2_D0552.tif" /><img file="US9898564B2_D0553.tif" /><img file="US9898564B2_D0554.tif" /><img file="US9898564B2_D0555.tif" /><img file="US9898564B2_D0556.tif" /><img file="US9898564B2_D0557.tif" /><img file="US9898564B2_D0558.tif" /><img file="US9898564B2_D0559.tif" /><br /> The notation for summing all pairs of residue and pole is omitted. In actual calculation it is neat to change t coordinate from to and t_Dbecomes t_D−t₀, and then replace t by t−t₀. We have <b>1505</b>

0081For t&lt;t_D

0082<maths id="MATH-US-00020" num="00020"><math overflow="scroll"><mrow><mrow><msup><mi>ℒ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><msub><mi>T</mi><mn>11</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><msub><mi>V</mi><mrow><mi>in</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mi>b</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><msub><mi>δ</mi><mi>k</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mo>-</mo><mfrac><mn>1</mn><msubsup><mi>γ</mi><mi>k</mi><mn>2</mn></msubsup></mfrac></mrow><mo>+</mo><mrow><mfrac><mn>1</mn><msubsup><mi>γ</mi><mi>k</mi><mn>2</mn></msubsup></mfrac><mo>⁢</mo><msup><mi>e</mi><mrow><mo>-</mo><mrow><msub><mi>γ</mi><mi>k</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow></mrow></msup></mrow><mo>+</mo><mfrac><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow><msub><mi>γ</mi><mi>k</mi></msub></mfrac></mrow><mo>)</mo></mrow></mrow></mrow></mrow><mo>+</mo><msub><mi>V</mi><mi>i</mi></msub></mrow></mrow></math></maths><img file="US9898564B2_D0560.tif" /><img file="US9898564B2_D0561.tif" /><img file="US9898564B2_D0562.tif" /><img file="US9898564B2_D0563.tif" /><img file="US9898564B2_D0564.tif" /><img file="US9898564B2_D0565.tif" /><img file="US9898564B2_D0566.tif" /><img file="US9898564B2_D0567.tif" /><img file="US9898564B2_D0568.tif" /><img file="US9898564B2_D0569.tif" /><img file="US9898564B2_D0570.tif" /><img file="US9898564B2_D0571.tif" /><img file="US9898564B2_D0572.tif" /><img file="US9898564B2_D0573.tif" /><img file="US9898564B2_D0574.tif" /><img file="US9898564B2_D0575.tif" /><img file="US9898564B2_D0576.tif" /><img file="US9898564B2_D0577.tif" /><img file="US9898564B2_D0578.tif" />

0083For t>t_D

0084<maths id="MATH-US-00021" num="00021"><math overflow="scroll"><mrow><mrow><msup><mi>ℒ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><msub><mi>T</mi><mn>11</mn></msub><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><msub><mi>V</mi><mrow><mi>in</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><mrow><msub><mi>A</mi><mi>k</mi></msub><mo>⁢</mo><msup><mi>e</mi><mrow><mo>-</mo><mrow><msub><mi>γ</mi><mi>k</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mi>D</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></msup></mrow><mo>+</mo><mrow><msub><mi>B</mi><mi>k</mi></msub><mo>⁢</mo><msup><mi>e</mi><mrow><mi>d</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow></msup></mrow><mo>+</mo><mrow><msub><mi>C</mi><mi>k</mi></msub><mo>⁢</mo><msup><mi>e</mi><mrow><mo>-</mo><mrow><msub><mi>γ</mi><mi>k</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow></mrow></msup></mrow></mrow><mo>)</mo></mrow></mrow><mo>+</mo><msub><mi>V</mi><mi>f</mi></msub></mrow></mrow></math></maths><img file="US9898564B2_D0579.tif" /><img file="US9898564B2_D0580.tif" /><img file="US9898564B2_D0581.tif" /><img file="US9898564B2_D0582.tif" /><img file="US9898564B2_D0583.tif" /><img file="US9898564B2_D0584.tif" /><img file="US9898564B2_D0585.tif" /><img file="US9898564B2_D0586.tif" /><img file="US9898564B2_D0587.tif" /><img file="US9898564B2_D0588.tif" /><img file="US9898564B2_D0589.tif" /><img file="US9898564B2_D0590.tif" /><img file="US9898564B2_D0591.tif" /><img file="US9898564B2_D0592.tif" /><img file="US9898564B2_D0593.tif" /><img file="US9898564B2_D0594.tif" /><img file="US9898564B2_D0595.tif" /><img file="US9898564B2_D0596.tif" /><img file="US9898564B2_D0597.tif" /><maths id="MATH-US-00021-2" num="00021.2"><math overflow="scroll"><mrow><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mrow><msub><mi>A</mi><mi>k</mi></msub><mo>=</mo><mrow><mrow><mo>-</mo><mi>b</mi></mrow><mo>⁢</mo><mfrac><msub><mi>δ</mi><mi>k</mi></msub><msub><mi>γ</mi><mi>k</mi></msub></mfrac><mo>⁢</mo><mfrac><mi>d</mi><mrow><msub><mi>γ</mi><mi>k</mi></msub><mo>+</mo><mi>d</mi></mrow></mfrac></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0598.tif" /><img file="US9898564B2_D0599.tif" /><img file="US9898564B2_D0600.tif" /><img file="US9898564B2_D0601.tif" /><img file="US9898564B2_D0602.tif" /><img file="US9898564B2_D0603.tif" /><img file="US9898564B2_D0604.tif" /><img file="US9898564B2_D0605.tif" /><img file="US9898564B2_D0606.tif" /><img file="US9898564B2_D0607.tif" /><img file="US9898564B2_D0608.tif" /><img file="US9898564B2_D0609.tif" /><img file="US9898564B2_D0610.tif" /><img file="US9898564B2_D0611.tif" /><img file="US9898564B2_D0612.tif" /><img file="US9898564B2_D0613.tif" /><img file="US9898564B2_D0614.tif" /><img file="US9898564B2_D0615.tif" /><img file="US9898564B2_D0616.tif" /><maths id="MATH-US-00021-3" num="00021.3"><math overflow="scroll"><mrow><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mrow><msub><mi>B</mi><mi>k</mi></msub><mo>=</mo><mrow><mfrac><msub><mi>δ</mi><mi>k</mi></msub><msub><mi>γ</mi><mi>k</mi></msub></mfrac><mo>⁢</mo><mfrac><mi>f</mi><mrow><msub><mi>γ</mi><mi>k</mi></msub><mo>+</mo><mi>d</mi></mrow></mfrac></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0617.tif" /><img file="US9898564B2_D0618.tif" /><img file="US9898564B2_D0619.tif" /><img file="US9898564B2_D0620.tif" /><img file="US9898564B2_D0621.tif" /><img file="US9898564B2_D0622.tif" /><img file="US9898564B2_D0623.tif" /><img file="US9898564B2_D0624.tif" /><img file="US9898564B2_D0625.tif" /><img file="US9898564B2_D0626.tif" /><img file="US9898564B2_D0627.tif" /><img file="US9898564B2_D0628.tif" /><img file="US9898564B2_D0629.tif" /><img file="US9898564B2_D0630.tif" /><img file="US9898564B2_D0631.tif" /><img file="US9898564B2_D0632.tif" /><img file="US9898564B2_D0633.tif" /><img file="US9898564B2_D0634.tif" /><img file="US9898564B2_D0635.tif" /><maths id="MATH-US-00021-4" num="00021.4"><math overflow="scroll"><mrow><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mrow><msub><mi>C</mi><mi>k</mi></msub><mo>=</mo><mfrac><mrow><msub><mi>δ</mi><mi>k</mi></msub><mo>⁢</mo><mi>b</mi></mrow><msubsup><mi>γ</mi><mi>k</mi><mn>2</mn></msubsup></mfrac></mrow></mrow></math></maths><img file="US9898564B2_D0636.tif" /><img file="US9898564B2_D0637.tif" /><img file="US9898564B2_D0638.tif" /><img file="US9898564B2_D0639.tif" /><img file="US9898564B2_D0640.tif" /><img file="US9898564B2_D0641.tif" /><img file="US9898564B2_D0642.tif" /><img file="US9898564B2_D0643.tif" /><img file="US9898564B2_D0644.tif" /><img file="US9898564B2_D0645.tif" /><img file="US9898564B2_D0646.tif" /><img file="US9898564B2_D0647.tif" /><img file="US9898564B2_D0648.tif" /><img file="US9898564B2_D0649.tif" /><img file="US9898564B2_D0650.tif" /><img file="US9898564B2_D0651.tif" /><img file="US9898564B2_D0652.tif" /><img file="US9898564B2_D0653.tif" /><img file="US9898564B2_D0654.tif" /><br /> After the waveform at the output node of the victim is obtained, the next step is to find the time t_out,1at which the waveform of the victim V_out,1(t) is at 50% of Vdd, then the delay from the input of RLC input, say node 1 which is the input of the victim, to the output node can be obtained as <b>1506</b>, <br />Delay=<i>t</i>_out,1<i>−t</i>_D,1<br /> Note that Delay is a random variable up to the 2^ndorder variation effect. Knowing that all the constants such as t₀, t_D, f, d, b in fact are random variables expressed by random parameters up to the second order, the waveform at output node is also a random variable up to the 2nd order effect. We use an example as shown in <figref idref="DRAWINGS">FIG. 16</figref> with only one random parameter a to explain this method, and the generalization to more than one random parameters is straightforward. The output waveform, say f(t,α), can be expanded in powers of α as follows <b>1601</b>, <br /><i>f</i>(<i>t</i>,α)=<i>f</i>₀(<i>t</i>)+<i>f</i>₁(<i>t</i>)α+<i>f</i>₂(<i>t</i>)α²<br /> The purpose is to find the random variable t being expressed as <b>1602</b><br /><i>t=t</i>_n<i>+Δt=t</i>_n<i>+xα+yα</i>²<br /><i>f</i>(<i>t</i>,α)=0.5 Vdd<br /> The function f(t,α) is further expanded in power of Δt <b>1603</b>

0085<maths id="MATH-US-00022" num="00022"><math overflow="scroll"><mrow><mrow><mi>f</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>,</mo><mi>α</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><msub><mi>f</mi><mn>0</mn></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mrow><msubsup><mi>f</mi><mn>0</mn><mi>′</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><mo>(</mo><mrow><mrow><mi>x</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>α</mi></mrow><mo>+</mo><mrow><mi>y</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msup><mi>α</mi><mn>2</mn></msup></mrow></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><msubsup><mi>f</mi><mn>0</mn><mi>″</mi></msubsup><mo>(</mo><mrow><mrow><mrow><msub><mi>t</mi><mrow><mi>n</mi><mo>)</mo></mrow></msub><mo>⁢</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><mo>⁢</mo><msup><mi>x</mi><mn>2</mn></msup><mo>⁢</mo><msup><mi>α</mi><mn>2</mn></msup></mrow><mo>+</mo><mrow><mrow><msub><mi>f</mi><mn>1</mn></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>⁢</mo><mi>α</mi></mrow><mo>+</mo><mrow><mrow><msubsup><mi>f</mi><mn>1</mn><mi>′</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><mo>(</mo><mrow><mi>x</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msup><mi>α</mi><mn>2</mn></msup></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mrow><msub><mi>f</mi><mn>2</mn></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>⁢</mo><msup><mi>α</mi><mn>2</mn></msup></mrow></mrow><mo>=</mo><mrow><mrow><msub><mi>f</mi><mn>0</mn></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>α</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mrow><msubsup><mi>f</mi><mn>0</mn><mi>′</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>⁢</mo><mi>x</mi></mrow><mo>+</mo><mrow><msub><mi>f</mi><mn>1</mn></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><msup><mi>α</mi><mn>2</mn></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><msub><mi>f</mi><mn>2</mn></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mrow><msubsup><mi>f</mi><mn>0</mn><mi>′</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>⁢</mo><mi>y</mi></mrow><mo>+</mo><mrow><mrow><msubsup><mi>f</mi><mn>0</mn><mi>″</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>⁢</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><mo>⁢</mo><msup><mi>x</mi><mn>2</mn></msup></mrow><mo>+</mo><mrow><mrow><msubsup><mi>f</mi><mn>1</mn><mi>′</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>⁢</mo><mi>x</mi></mrow><mo>+</mo><mrow><msub><mi>f</mi><mn>2</mn></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US9898564B2_D0655.tif" /><img file="US9898564B2_D0656.tif" /><img file="US9898564B2_D0657.tif" /><img file="US9898564B2_D0658.tif" /><img file="US9898564B2_D0659.tif" /><img file="US9898564B2_D0660.tif" /><img file="US9898564B2_D0661.tif" /><img file="US9898564B2_D0662.tif" /><img file="US9898564B2_D0663.tif" /><img file="US9898564B2_D0664.tif" /><img file="US9898564B2_D0665.tif" /><img file="US9898564B2_D0666.tif" /><img file="US9898564B2_D0667.tif" /><img file="US9898564B2_D0668.tif" /><img file="US9898564B2_D0669.tif" /><img file="US9898564B2_D0670.tif" /><img file="US9898564B2_D0671.tif" /><img file="US9898564B2_D0672.tif" /><img file="US9898564B2_D0673.tif" /><br /> We therefore obtain t_n, x and y as by solving the following equations sequentially <b>1604</b>

0086<maths id="MATH-US-00023" num="00023"><math overflow="scroll"><mrow><mrow><msub><mi>f</mi><mn>0</mn></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mn>0.5</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Vdd</mi></mrow></mrow></math></maths><img file="US9898564B2_D0674.tif" /><img file="US9898564B2_D0675.tif" /><img file="US9898564B2_D0676.tif" /><img file="US9898564B2_D0677.tif" /><img file="US9898564B2_D0678.tif" /><img file="US9898564B2_D0679.tif" /><img file="US9898564B2_D0680.tif" /><img file="US9898564B2_D0681.tif" /><img file="US9898564B2_D0682.tif" /><img file="US9898564B2_D0683.tif" /><img file="US9898564B2_D0684.tif" /><img file="US9898564B2_D0685.tif" /><img file="US9898564B2_D0686.tif" /><img file="US9898564B2_D0687.tif" /><img file="US9898564B2_D0688.tif" /><img file="US9898564B2_D0689.tif" /><img file="US9898564B2_D0690.tif" /><img file="US9898564B2_D0691.tif" /><img file="US9898564B2_D0692.tif" /><maths id="MATH-US-00023-2" num="00023.2"><math overflow="scroll"><mrow><mi>x</mi><mo>=</mo><mrow><mo>-</mo><mfrac><mrow><msub><mi>f</mi><mn>1</mn></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mrow><msubsup><mi>f</mi><mn>0</mn><mi>′</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow></mfrac></mrow></mrow></math></maths><img file="US9898564B2_D0693.tif" /><img file="US9898564B2_D0694.tif" /><img file="US9898564B2_D0695.tif" /><img file="US9898564B2_D0696.tif" /><img file="US9898564B2_D0697.tif" /><img file="US9898564B2_D0698.tif" /><img file="US9898564B2_D0699.tif" /><img file="US9898564B2_D0700.tif" /><img file="US9898564B2_D0701.tif" /><img file="US9898564B2_D0702.tif" /><img file="US9898564B2_D0703.tif" /><img file="US9898564B2_D0704.tif" /><img file="US9898564B2_D0705.tif" /><img file="US9898564B2_D0706.tif" /><img file="US9898564B2_D0707.tif" /><img file="US9898564B2_D0708.tif" /><img file="US9898564B2_D0709.tif" /><img file="US9898564B2_D0710.tif" /><img file="US9898564B2_D0711.tif" /><maths id="MATH-US-00023-3" num="00023.3"><math overflow="scroll"><mrow><mi>y</mi><mo>=</mo><mrow><mo>-</mo><mfrac><mrow><mrow><msub><mi>f</mi><mn>2</mn></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mrow><msubsup><mi>f</mi><mn>0</mn><mi>″</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>⁢</mo><mfrac><msup><mi>x</mi><mn>2</mn></msup><mn>2</mn></mfrac></mrow><mo>+</mo><mrow><mrow><msubsup><mi>f</mi><mn>1</mn><mi>′</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow><mo>⁢</mo><mi>x</mi></mrow><mo>+</mo><mrow><msub><mi>f</mi><mn>2</mn></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow></mrow><mrow><msubsup><mi>f</mi><mn>0</mn><mi>′</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>t</mi><mi>n</mi></msub><mo>)</mo></mrow></mrow></mfrac></mrow></mrow></math></maths><img file="US9898564B2_D0712.tif" /><img file="US9898564B2_D0713.tif" /><img file="US9898564B2_D0714.tif" /><img file="US9898564B2_D0715.tif" /><img file="US9898564B2_D0716.tif" /><img file="US9898564B2_D0717.tif" /><img file="US9898564B2_D0718.tif" /><img file="US9898564B2_D0719.tif" /><img file="US9898564B2_D0720.tif" /><img file="US9898564B2_D0721.tif" /><img file="US9898564B2_D0722.tif" /><img file="US9898564B2_D0723.tif" /><img file="US9898564B2_D0724.tif" /><img file="US9898564B2_D0725.tif" /><img file="US9898564B2_D0726.tif" /><img file="US9898564B2_D0727.tif" /><img file="US9898564B2_D0728.tif" /><img file="US9898564B2_D0729.tif" /><img file="US9898564B2_D0730.tif" />

0087In conclusion, the issue of SSTA in multi-phase sequential circuit with cross-talk in consideration of process variations up to the 2^ndorder is not addressed well. There are several difficulties. First, in multi-phase sequential circuit timing constraint can be non-uniform and complex. This invention provides a novel method to utilize breadth first traversal and special algorithm to store longest arrival time as random variable and accumulated probability at each node with respect to clock phases and generates edge probability matrix from input to output of the gate associated with stored input and output clock phases, then followed by backward search to get critical paths in terms of probability. Secondly, the accuracy of delay based on Gaussian distribution is questionable. This invention solves the problem by adopting Non-Gaussian behavior and provides a method to pre-characterize the timing library for the gate output delay and slope as random variables as a function input slope and output loading up to the 2^ndorder of variation. Thirdly, the issue of interconnect including cross-talk needs to be handled by considering non-Gaussian behavior. This invention provides a novel way to calculate admittance matrix and voltage transfer up to 2^ndorder of process variation and fitted the results into simple pole format to obtain poles and residues for each matrix element up to 2^ndorder of variation. Effective capacitance and interconnect delay can be calculated up to 2^ndorder of variation by using poles and residues including up to second order variation effects of both admittance matrix and voltage transfer, accordingly. The invention further provides a method for cross-talk with multiple ports to evaluate effective capacitances at the ports individually and waveforms at the ports are then used to calculate delay expressed as random variable containing 2^ndorder variation terms at victim outputs. With all of these in place, SSTA is used to identify critical paths in terms of probability in an accurate manner.

0088It should be noted that a timing verification tool according to the invention may have one or more of the above-described capabilities in any combination, and any of these novel capabilities can be combined with conventional or other novel timing verification tools.

0089Accordingly, although the present invention has been particularly described with reference to the preferred embodiments thereof, it should be readily apparent to those of ordinary skill in the art that changes and modifications in the form and details may be made without departing from the spirit and scope of the invention. It is intended that the appended claims encompass such changes and modifications.