Abstract:
A method and verification of estimating crosstalk noise in coupled RLC interconnects with distributed line in nanometer integrated circuits is provided. In this invention, nanometer VLSI interconnects are modeled as distributed RLC coupled trees. The efficiency and the accuracy of moment computation of distributed lines can be shown that outperform those of lumped ones. The inductive crosstalk noise waveform can be accurately estimated in an efficient manner using the linear time moment computation technique in conjunction with the projection-based order reduction method. Recursive formulas of moment computations for coupled RC trees are derived with considering both self inductances and mutual inductances. Also, analytical formulas of voltage moments at each node will be derived explicitly. These formulas can be efficiently implemented for crosstalk estimations.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The present invention relates to a method of estimating crosstalk noise in high-speed VLSI interconnects, and more particularly to a method of using moment computations of coupled RLC-tree models with uniform distributed lines and project-based model-order reduction techniques.  
         [0003]     2. Description of Related Art  
         [0004]     Modern technological trends have caused interconnect modeling to have attracted considerable attention in high-speed VLSI designs. Owing to these designs with performance considerations, increasing clock frequency, shorter rising times, higher density of wires, and using low-resistivity materials, on-chip inductance effects can no longer be ignored in interconnect models. Furthermore, the importance of coupling inductance effects has grown continuously since nanometer technology has emerged over the last few years. It has been observed that crosstalk noise estimations made by considering inductance effects may yield more pessimistic results than those made without considering coupling inductance effects, as discussed in C. K. Cheng, J. Lillis, S. Lin, and N. H. Chang, Interconnect Analysis and Synthesis, John Wiley and Sons Inc., 2000. Such estimation errors follow from two main reasons: (1) more and longer wires in parallel increase the capacitive coupling, leading to large current changes on the victim nets. (2) increasing self inductance worsens overshooting spikes on aggressor nets. It may then pull the victims with them. For the above practical considerations, interconnect models shall be extended to be coupled RLC trees while considering the inductance effects.  
         [0005]     A common means of estimating crosstalk noise is implemented by simulating circuit-level VLSI interconnects. Although the results are very accurate, the computational complexity is excessive, especially for large-scale interconnect simulations. An alternative approach, called model-order reduction methods, has recently emerged to solve the problem, as disclosed in L. T. Pillage and R. A. Rohrer, “Asymptotic waveform evaluation for timing analysis,” IEEE Trans. Computer-Aided Design, vol. 9, no. 4, pp. 352-366, 1990; P. Feldmann and R. W. Freund, “Efficient linear circuit analysis by Pade approximation via the Lanczos process,” IEEE Trans. Computer-Aided Design, vol. 14, no. 5, 1995, and A. Odabasioglu, M. Celik, and L. T. Pileggi, “PRIMA: passive reduced-order interconnect macromodeling algorithm,” IEEE Trans. Computer-Aided Design, vol. 17, no. 8, pp. 645-653, 1998. Then, rather than directly estimating the crosstalk waveform of the original interconnects, the crosstalk noise of the reduced-order system is estimated. However, the computational cost is still too high for a noise optimization problem even though model-order reduction methods have reduced the cost, as disclosed in A. Devgan, “Efficient coupled noise estimatin for on-chip interconnects,” in Porc. ICCAD, 1997, pp. 147-151; M. Kuhlmann and S. S. Sapatnekar, “Exact and efficient crosstalk estimation,” IEEE Trans. Computer-Aided Design, vol. 20, no. 7, pp. 858-866, 2001.  
         [0006]     A consensus has emerged that of many model-order reduction techniques, the moment matching approach seems to be the most viable for estimating interconnect crosstalk noise. For computational efficiency, traditional models for estimating noise in coupled RC trees have been developed, including the one-pole model (1P) (as disclosed in A. Vittal, L. H. Chen, M. Marek-Sadowska, K. P. Wang, and S. Yang, “Crosstalk in VLSI interconnects,” IEEE Trans. Computer-Aided Design, vol. 18, pp. 1817-1824, 1999; and A. Vittal and M. Marek-Sadowska, “Crosstalk reduction for VLSI,” IEEE Trans. Computer-Aided Design, vol. 16, pp. 290-298, 1997), the modified one-pole model (M1P) (as disclosed in Q. Yu and E. S. Kuh, “Moment computation of lumped and distributed coupled RC trees with application to delay and crosstalk estimation,” Proceedings of the IEEE, vol. 89, no. 5, pp. 772-788, 2001), the two-pole model (2P) (as discussed in M. Kuhlmann and S. S. Sapatnekar, “Exact and efficient crosstalk estimation,” IEEE Trans. Computer-Aided Design, vol. 20, no. 7, pp. 858-866, 2001.; and Q. Yu and E. S. Kuh, “Moment computation of lumped and distributed coupled RC trees with application to delay and crosstalk estimation,” Proceedings of the IEEE, vol. 89, no. 5, pp. 772-788, 2001), (as disclosed in E. Acar, A. Odabasioglu, M. Celik, and L. T. Pileggi, “S2P: A stable 2-pole RC delay and coupling noise metric,” in Proc. 9th Great Lakes Symp. VLSI, Mar. 1999, pp. 60-63), and the guaranteed stable three-pole model (S3P) (as discussed in Q. Yu and E. S. Kuh, “Moment computation of lumped and distributed coupled RC trees with application to delay and crosstalk estimation,” Proceedings of the IEEE, vol. 89, no. 5, pp. 772-788, 2001). Unlike the general model-order reduction methods, the techniques simply estimate the peak value of crosstalk noise and the time at which it peaks rather than evaluating the waveform of crosstalk noise. Also, other patents U.S. Pat. No. 5,481,695, U.S. Pat. No. 5,535,133, U.S. Pat. No. 5,555,506, U.S. Pat. No. 5,568,395, U.S. Pat. No. 5,596,506, U.S. Pat. No. 6,018,623, U.S. Pat. No. 6,029,117, and U.S. Pat. No. 6,405,348 have been disclosed the techniques about the crosstalk noise estimations. However, since the interconnect crosstalk noise may have a non-monotonic response waveform, these models seem to be unsuitable for capturing the essential nature of such crosstalk noise.  
         [0007]     Recently, the delay and noise formulae by considering self inductances and mutual inductances have been disclosed in Y Cao, X. Huang, D. Sylvester, N. Chang, and C. Hu, “A new analytical delay and noise model for on-chip RLC interconnect,” in Proc. IEDM 2000, 2000, pp. 823-826. However, their model is restricted to two parallel lines. The analytical delay and overshooting formulae for coupled RLC lines have been disclosed in M. H. Chowdhury, Y. I. Ismail, C. V. Kashyap, and B. L. Krauter, “Performance analysis of deep sub micron VLSI circuits in the presence of self and mutual inductance,” in Proc. ISCAS 2002, 2002, pp. 197-200. However, issues concerning inductive crosstalk noise analysis have still not yet been studied. Furthermore, by exploring the special nature of RLC-tree structures, recursive algorithms for computing system moments with linear order have been developed, for example, by C. L. Ratzlaff and L. T. Pillage, “RICE: rapid interconnect circuit evaluation using AWE,” IEEE Trans. Computer-Aided Design, vol. 13, no. 6, pp. 763-776, 1994 and Q. Yu and E. S. Kuh, “Exact moment matching model of transmission lines and application to interconnect delay estimation,” IEEE Trans. VLSI syst., vol. 3, no. 2, pp. 311-322, 1995, independently. Moment models of general transmission lines were presented in Q. Yu, E. S. Kuh, and T. Xue, “Moment models of general transmission lines with application to interconnect analysis and optimization,” IEEE Trans. VLSI syst., vol. 4, no. 4, pp. 477-494, 1996. However, these studies did not mention moment computations for coupled RLC trees.  
         [0008]     The technique, “Crosstalk estimated in high-speed VLSI interconnect using coupled RLC-tree models”, which is proposed in Proc. 2002 IEEE Asia Pacific Conference on Circuits and Systems, is our initial research. Although the moment computation formulae for coupled RLC trees have been developed, the technique about efficiently constructing the crosstalk estimation model was not provided. Also, the stability of the model was still not analyzed. In addition, the line model is represented as sections of lumped RLC circuits. In order to increase accuracy of the estimation results, the number of the sections must be increase. However, this will increase the memory space for storing data and simulation time.  
       SUMMARY OF THE INVENTION  
       [0009]     The present invention discloses a method for efficiently estimating crosstalk noise of high-speed VLSI interconnects. In the invention, high-speed VLSI interconnects are modeled as RLC coupled trees with uniform distributed lines. The inductive crosstalk noise waveform can be accurately estimated in an efficient manner using the linear time recursive moment computation technique in conjunction with the projection-based order reduction method. Every moment of a line is represented as a polynomial of the coordinate of the line. Although a distributed line is a infinite order system in nature, the order of each moment polynomial can be shown finite. Notably, all of the coefficients of the polynomials of moments can be calculated recursively. Recursive moment computation formulas and a moment model for distributed coupling RLC-tree models are also developed. The efficiency and the accuracy of moment computation of distributed lines can be shown that outperform those of lumped ones. Crosstalk-metric models for distributed coupled RLC trees are also established. A stable reduced-order model will be constructed implicitly using the recursive moment computation technique in conjunction with the projection-based model-order reduction method.  
         [0010]     Crosstalk noise estimations will be made by investigating the crosstalk noise of this reduced-order network.  
         [0011]     Further benefits and advantages of the present invention will become apparent after a careful reading of the detailed description with appropriate reference to the accompanying drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]      FIG. 1  represents a flow chart of the method of estimating crosstalk noise in RLC coupled interconnects in accordance with the present invention;  
         [0013]      FIG. 2  is an illustration of a typical section of tree T i  in coupled RLC trees;  
         [0014]      FIG. 3  represents the distributed line model in coupled RLC trees;  
         [0015]      FIG. 4  represents the moment model of couple RLC lines;  
         [0016]      FIG. 5  illustrates three types of coupled RLC trees: (a) two lines (b) tree  1  (c) tree  2 . The lengths of the coupling lines of net  1  belong to the set L1={1, 2, 3, 4, 5} (mm) and those of net  2  are also in the. set L2={1, 2, 3, 4, 5} (mm); the latter are never longer than the former; 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0017]      FIG. 1  shows the flow chart of the crosstalk estimation algorithm in the disclosed invention. Three input files should be included, which contain input signal  10 , circuit parameters of the lumped coupled RLC trees  12 , and the order q of the reduced-order model  14 . Initially, in step  16 , calculate q-order moments {X 1 ,X 2 , . . . X q }. Then, in step  18 , construct q-order reduced-order MNA matrices {circumflex over (M)} and {circumflex over (N)}. In step  20 , calculate the coefficients {b 1 ,b 2 , . . . ,b q } of the equation |{circumflex over (N)}+s{circumflex over (M)}=1+b 1 s+b 2 s 2 + . . . +b q s q . Step  22  updates the values of the moments according to the input signal. Step  24  calculates the coefficients {a 0 ,a 1 , . . . ,a q−2 } of the transfer function of the qth-order reduced-order model  
           V   ^     ⁡     (   s   )       =         a   0     +       a   1     ⁢   s     +   …   +       a     q   -   2       ⁢     s     q   -   1             1   +       b   1     ⁢   s     +   …   +       b     q   -   1       ⁢     s     q   -   1         +       b   q     ⁢     s   q                 
 by using the moments obtained in step  22 . Then {circumflex over (V)}(s) is reformulated by the pole-residue form  
           V   ^     ⁡     (   s   )       =         k   1       s   -     p   1         +       k   2       s   -     p   2         +   …   +       k   q       s   -     p   q                 
 and the resultant time-domain crosstalk noise will be {circumflex over (v)}(t)=k 1 e p     1     t +k 2 e p     2     t + . . . +k q e p     q     t  by applying the inverse Laplace transform in step  26 . Finally, step  28  estimates the peak value the crosstalk noise and the algorithm is terminated in step  30 . 
 
         [0018]     The dynamics of RLC coupled trees can also be represented by the following MNA formula:  
                 (       s   ⁢       [             M   ^     d         0       0           0       C       0           0       0       L         ]       ︸   M         +       [             N   ^     d           -     A   d           0             A   d   T         G         A   l             0         -     A   l   T           R         ]       ︸   N         )     ⁢       [               X   ^     d     ⁡     (   s   )                   V   n     ⁡     (   s   )                   I   L     ⁡     (   s   )             ]       ︸     X   ⁡     (   s   )             =         [         0             A   s             0         ]       ︸   b       ⁢       V   s     ⁡     (   s   )                 (   1   )             
 
 where (s{circumflex over (M)} d +{circumflex over (N)} d ){circumflex over (X)} d (s)=A d V n (s) are the state equations of the reduced-order model of distributed lines; V n (s) and I L (s) represent the node voltage vector and R-L branch current vector; the matrices R, L, G, and C include lumped resistors, inductors, conductors, and capacitors; and A d , A i , and A s  are incidence matrices. 
 
         [0019]     Let vector X k =[{circumflex over (X)} d,k  V n,k  I L,k ] T  be the kth-order moment of X(s) about s=0. If Q=└X 0  X 1  . . . X q−1 ┘ is used as the congruence transform matrix, then the MNA matrices of the reduced-order model are obtained: {circumflex over (M)}=Q T MQ and {circumflex over (N)}=Q T NQ. Thus, the kth-row and the lth-column entry of {circumflex over (N)} and {circumflex over (M)} become {circumflex over (n)} k,l =X k−1   T NX l−1  and {circumflex over (m)} k,l =X k−1   T MX l−1 , respectively. Since the recursive moment formula implies 
 
 NX   0   =B  
 
 NX   i+1   =−MX   i , for i=0, 1 , . . .    q  
 
         [0020]     {circumflex over (n)} k,l  will be  
                       n   ^       k   ,   l       =       ⁢       -     X     k   -   1     T       ⁢   M   ⁢           ⁢     X     l   -   2                     =       ⁢         -     (       ⁢       X   ^       d   ,     k   -   1       T     ⁢       M   ^     d     ⁢       X   ^       d   ,     l   -   2           +       V     n   ,     k   -   1       T     ⁢   C   ⁢           ⁢     V     n   ,     l   -   2           +       I     L   ,     k   -   1       T     ⁢   L   ⁢           ⁢     I     L   ,     l   -   2         ⁢     )                       (   2   )             
 
 where V n,k−1   T CV n,l−2  and I L,k−1   T LI L,l−2 , related to lumped circuits, can be calculated by the technique: “Crosstalk estimated in high-speed VLSI interconnect using coupled RLC-tree models”, which is proposed in  Proc.  2002  IEEE Asia Pacific Conference on Circuits and Systems  by H. J. Lee, C. C. Chu, and W. S. Feng. For {circumflex over (X)} d,k−1   T {circumflex over (M)} d {circumflex over (X)} d,l−2 , the details will be shown as follows. 
 
 Moment Computations for Coupled RLC-Tree Interconnect Models 
 
         [0021]     A set of coupled RLC trees contains several individual RLC trees with capacitive and inductive couplings to each other. Each RLC tree comprises floating resistors and self inductors from the ground and capacitors connecting between nodes on the tree and the ground. A tree with a voltage source connected to its root is called an aggressor tree; by contrast, trees whose roots are grounding are called victim trees. By ignoring self inductances and mutual inductances, the conventional coupled RC-tree models are obtained. In this invention, coupled interconnects are modeled as coupled RLC trees for analyzing the crosstalk noises.  
         [0022]     To clearly describe the complex coupled RLC-tree structures, the invention first introduces the notation. Consider a typical section of tree T i  in coupled RLC trees shown in  FIG. 2 , where n j   i  is the j th node in the tree T i  and F(n j   i ) is the corresponding father node of n j   i . Node n 0   i  is the root of T i  and F(n 0   i )=φ. N i  is the set of the non-root nodes in T i . S(n j   i ) denotes the set of the son nodes of n j   i . Each root node has only one son node. This study assumes that the conventional lumped model between node n j   i  and its father node F(n j   i ) on coupled RLC trees is replaced with a distributed line Line j   i , where n j   i  is the jth node in the tree T i . As a result, the network is mixed with lumped and distributed circuits. R j   i , L j   i , and C j   i  are the per-unit resistance, inductance, and capacitance of Line j   i . C j,j     1     i,j     1    and M j,j     1     i,i     1    are the total coupling capacitance and mutual inductance between Line j   i  and Line j     1     i     1   . CC j   i  and MM j   i  the set of total coupling capacitance and mutual inductance corresponding to Line j   i . In general, the coupling effect, especially with inductive couplings, is not restricted to arising between two closest neighbors. Therefore, the proposed method will address the comprehensive circumstances that each set CC j   i  and MM j   i  may include several coupling capacitances and mutual inductances. P jk   i  is defined as the common path of the path P j   i  from n j   i  to the root of T i  and of the path P k   i  from n k   i  to the root of T i . The set of ancestor nodes of n j   i , defined as A(n j   i ), covers the nodes on the path P F(j)   i  from F(n j   i ) to the root of T i . Let Â(n j   i )={{A(n j   i )−n 0   i }∪ j   i }. Conversely, D(n j   i )={n x   i |n j   i ∈A(n x   i )} denotes the set of descendant nodes of n j   i .We also define {circumflex over (D)}(n j   i )={n j   i ∪D(n j   i )}.  
         [0000]     Moment Model of coupled RLC Lines  
         [0023]     Let V j   i (x,s), I j   i (x,s), and I c     j     i (x,s) be the transfer functions of the voltage, current, and capacitive current at coordinate x on Line j   i , where x=0 and x=1 correspond to the near end and the far end of the line, as shown in  FIG. 3 . Applying the Laplace transformation, the Telegrapher&#39;s equations of Line j   i  can be rewritten as follows:  
                 ∂       V   j   i     ⁡     (     x   ,   s     )           ∂   x       =         -     (       R   j   i     +     s   ⁢           ⁢     L   j   i         )       ⁢       I   j   i     ⁡     (   s   )         -       ∑     M   ⁢           ⁢     M   j   i         ⁢       (     ⁢   s   ⁢           ⁢     M     j   ,     j   1         i   ,     i   1         ⁢       I     j   1       i   1       ⁡     (     x   ,   s     )       ⁢     )                   (   3   )                   ∂       I   j   i     ⁡     (     x   ,   s     )           ∂   x       =         -   s     ⁢           ⁢     C   jT   i     ⁢       V   j   i     ⁡     (     x   ,   s     )         -       ∑     CC   j   i       ⁢       (     ⁢   s   ⁢           ⁢     C     j   ,     j   1         i   ,     i   1         ⁢       V     j   1       i   1       ⁡     (     x   ,   s     )       ⁢     )                   (   4   )             
 
 where C jT   i =C j   i +Σ cc     j     i C j,j     1     i,i     1    is the sum of the grounding capacitance and the coupling ones on Line j   i . Expanding V j   i (x,s), I j   i (x,s), and I C     j     i  (x,s) in power series, we have the kth-order moments V j,k   i (x), I j,k   i (x), and I C     j,k     i (x), which are the coefficients of s k , respectively. If k=0, each capacitor behaves as an open circuit, the zeroth-order current moment I C     j,0     i (x)=I j,0   i (1)=0 and the zeroth-order voltage moment V j,0   i (x)=V j,0   i (0)=V s   i . For k&gt;0, the kth-order moments  
                 I     C     j   ,   k       i     ⁡     (   x   )       =         C   jT   i     ⁢       V     j   ,     k   -   1       i     ⁡     (   x   )         -       ∑       C     j   ,     j   1         i   ,     i   1         ∈     CC   j   i         ⁢       V       j   1     ,     k   -   1         i   1       ⁡     (   x   )                   (   5   )                   I     j   ,   k     i     ⁡     (   x   )       =         I     j   ,   k     i     ⁡     (   1   )       +       ∫   x   j     ⁢         I     C     j   ,   k       i     ⁡     (   z   )       ⁢     ⅆ   z                   (   6   )                   V     j   ,   k     i     ⁡     (   x   )       =         V     j   ,   k     i     ⁡     (   0   )       -     (         xR   j   i     ⁢       I     j   ,   k     i     ⁡     (   x   )         +       ∫   0   τ     ⁢       zR   j   i     ⁢       I     C     j   ,   k     i       ⁡     (   z   )       ⁢     ⅆ   z           )     -     (         xL   j   i     ⁢       I     j   ,     k   -   1       i     ⁡     (   x   )         +       ∫   0   τ     ⁢       zL   j   i     ⁢       I     C     j   ,     k   -   1         i     ⁡     (   z   )       ⁢     ⅆ   z           )     -       ∑       M     j   ,     j   1         i   ,     i   1         ∈     MM   j   i         ⁢     (         xM     j   ,     j   1         i   ,     i   1         ⁢       I       j   1     ,     k   -   1         i   1       ⁡     (   x   )         +       ∫   0   τ     ⁢       zM     j   ,     j   1         i   ,     i   1         ⁢       I       j   1     ,     k   -   1         i   1       ⁡     (   z   )       ⁢     ⅆ   z           )                 (   7   )             
 
 where Eqs. (5) and (6) are derived from Kirchhoff&#39;s current law and Eq. (7) is derived from Kirchhoff&#39;s voltage law. 
 
         [0024]     In this invention, I C     j,k     i (x) and V j,k   i (x) are represented as polynomials and the corresponding coefficients are calculated, that is,  
                   I     C     j   ,   k       i     ⁡     (   x   )       =       ∑     n   =   0     m     ⁢       α     j   ,   kn     i     ⁢     x   n           ⁢     
     ⁢         V               j   ,   k       i     ⁡     (   x   )       =       ∑     n   =   0     p     ⁢       β     j   ,   kn     i     ⁢     x   n                   (   8   )             
 
 If k=0 , zeroth-order polynomial I C     j,0     i (x)=0 and V j,0   i (x)=V s   i imply that α j,00   i =0 and β j,00   i =V s   i . For k&gt;0. substituting Eq. (8) into Eq. (5) gives  
               α     j   ,   kn     i     =         C   jT   i     ⁢     β     j   ,       (     k   -   1     )     ⁢   n       i       -       ∑       C     j   ,     j   1         i   ,     i   1         ∈     CC   j   i         ⁢       C     j   ,     j   1         i   ,     i   1         ⁢     β       j   1     ,       (     k   -   1     )     ⁢   n         i   1                     (   9   )             
 
 Integrating I C     j,k   (z)dz from z=x to z=1 and zI C     j,k   (z)dz from z=0 to z=x, we have  
           ∫   x   j     ⁢         I     C     j   ,   k         ⁡     (   z   )       ⁢     ⅆ   z         =       ∑     n   =   0     m     ⁢         α     j   ,   kn     i       n   +   1       ⁢     (     1   -     x     n   +   1         )             
           ∫   0   x     ⁢     z   ⁢           ⁢       I     C     j   ,   k         ⁡     (   z   )       ⁢     ⅆ   z         =       ∑     n   =   0     m     ⁢         α     j   ,   kn     i       n   +   2       ⁢     x     n   +   2               
 
 Substituting Eq. (10) into Eq. (7) concludes that  
                   β     j   ,     k   ⁢           ⁢   0       i     =       V     j   ,   k     i     ⁡     (   0   )         ⁢     
     ⁢       β     j   ,     k   ⁢           ⁢   1       i     =       -       R   j   i     ⁡     (         I     j   ,   k     i     ⁡     (   1   )       +       ∑     n   =   0     m     ⁢       α     j   ,   kn     i       n   +   1           )         -       L   j   i     ⁡     (         I     j   ,     k   -   1       i     ⁡     (   1   )       +       ∑     n   =   0     m     ⁢       α     j   ,       (     k   -   1     )     ⁢   n       i       n   +   1           )       -       ∑       M     j   ,     j   1         i   ,     i   1         ∈     MM   j   i         ⁢     (         I       j   1     ,     k   -   1         i   1       ⁡     (   1   )       +       ∑     n   =   0     m     ⁢       α     j   ,       (     k   -   1     )     ⁢   n       i       n   +   1           )           ⁢     
     ⁢         β     j   ,     k   ⁡     (     n   +   2     )         i     =       1       (     n   +   1     )     ⁢     (     n   +   2     )         ⁢     (         R   j   i     ⁢     α     j   ,   kn     i       +       L   j   i     ⁢     α     j   ,       (     k   -   1     )     ⁢   n       i       +       ∑       M     j   ,     j   1         i   ,     i   1         ∈     MM   j   i         ⁢       M     j   ,     j   1         i   ,     i   1         ⁢     α       j   1     ,       (     k   -   1     )     ⁢   n         i   1             )         ,     
     ⁢     n   ≥   0         ⁢                   (   11   )             
 
 The relations between the order of polynomials m and p and the order of moments k can be found from Eqs. (9) and (11). First, m=0 when k=1. Second, from the third part of Eq. (11), we have p=m+2. Finally, from Eq. (9), the order of polynomial I C     j,k+1     i (x) is equal to p(=m+2). As a result, by induction, m=2(k−1) and p=2k are derived for coupled RLC trees with distributed lines. Notably, all these coefficients can be generated recursively. 
 
         [0025]     After the coefficients αs and βs are computed, the moment model of coupled RLC lines can be established. From Eq. (6), setting x=0, we obtain 
 
 I   j,k   i (0)= I   j,k   i (1)+ J   j,k   i   (12) 
 
 where  
               J     j   ,   k     i     =         ∫   0   J     ⁢         I     C     j   ,   k         ⁡     (   z   )       ⁢     ⅆ   z         =       ∑     n   =   0       2   ⁢     (     k   -   1     )         ⁢       α     j   ,   kn     i       n   +   1                   (   13   )             
 
 representing the summation of the capacitive currents of Line j   i . Moreover, Eq. (7) can be rewritten  
                   V     j   ,   k     i     ⁡     (   1   )       =         V     j   ,   k     i     ⁡     (   0   )       -       R   j   i     ⁢       I     j   ,   k     i     ⁡     (   1   )         -     E     LM     j   ,   k       i     -     E     j   ,   k     i         ⁢     
     ⁢   where           (   14   )                   E     LM     j   ,   k       i     =         L   j   i     ⁢       I     j   ,     k   -   1         i   1       ⁡     (   1   )         +       ∑       M     j   ,     j   1         i   ,     i   1         ∈     MM   j   i         ⁢       M     j   ,     j   1         i   ,     i   1         ⁢       I       j   1     ,     k   -   1         i   1       ⁡     (   1   )               ⁢     
     ⁢   and           (   15   )                       E     j   ,   k     i     =       ⁢         R   j   i     ⁢       ∫   0   J     ⁢         zI     C     j   ,   k       i     ⁡     (   z   )       ⁢     ⅆ   z           +       L   j   i     ⁢       ∫   0   J     ⁢         zI     C     j   ,     k   -   1         i     ⁡     (   z   )       ⁢     ⅆ   z           +                     ⁢       ∑       M     j   ,     j   1         i   ,     i   1         ∈     MM   j   i         ⁢       M     j   ,     j   1         i   ,     i   1         ⁢       ∫   0   J     ⁢         zI     C     j   ,     k   -   1         i     ⁡     (   z   )       ⁢     ⅆ   z                         =       ⁢         R   j   i     ⁢       ∑     n   =   0       2   ⁢     (     k   -   1     )         ⁢       α     j   ,   kn     i       n   +   2           +       L   j   i     ⁢       ∑     n   =   0       2   ⁢     (     k   -   2     )         ⁢       α     j   ,       (     k   -   1     )     ⁢   n       i       n   +   2           +     ∑       M     j   ,     j   1         i   ,     i   1         ∈     MM   j   i                           ⁢       M     j   ,     j   1         i   ,     i   1         ⁢       ∑     n   =   0       2   ⁢     (     k   -   2     )         ⁢       α     j   ,       (     k   -   1     )     ⁢   n       i       n   +   2                         (   16   )             
 
 E j,k   i  and E LM     j,k     i  represent the voltage drops from voltage moment V j,k   i (0), resulted from the kth-order and the (k-1)st-order capacitive current moment flowing through resistance and inductance of Line j   i , respectively. For coupled RC lines, E LM     j,k     i =0. The moment model of coupled RLC lines is depicted in  FIG. 4 . 
 
 Inserting Coupled Lines into Coupled RLC Trees 
 
         [0026]     This invention-uses a function, Line(n j   i ), to indicate a line connected between nodes n j   i  and F(n j   i ), Line(n j   i )=1, or not, Line(n j   i )=0. Thus the kth-order current moment I j,k   i (1) at x=1 can be obtained as below:  
                 I     j   ,   k     i     ⁡     (   1   )       =       I     C     j   ,   k       i     +       ∑       n   x   i     ∈     D   ⁡     (     S   ⁡     (     n   j   i     )       )           ⁢       (     ⁢     I     C     x   ,   k     i           +         Line   ⁡     (     n   x   i     )       ·     J     x   ,   k     i       ⁢     )                 (   17   )             
 
 Next, the voltage moment V j,k   i  is also considered. First, the added current source induces further voltage drops through resistances and inductances at all nodes A(n j   i ), the set of ancestor nodes of n j   i . Second, the voltage source E j,k   i  cause voltage drops only between V j,k   i  and V F(j),k   i . Thus V j,k   i  can be obtained as follows:  
               V     j   ,   k     i     =     -       ∑       n   p   i     ∈     A   ⁡     (     n   j   i     )           ⁢     (         R   p   i     ⁢       I     p   ,   k     i     ⁡     (   1   )         +       L   p   i     ⁢       I     p   ,     k   -   1       i     ⁡     (   1   )         +       ∑       M     p   ,     p   1         i   ,     i   1         ∈     MM   p   i         ⁢       M     p   ,     p   1         i   ,     i   1         ⁢       I       p   1     ,     k   -   1         i   1       ⁡     (   1   )           +       Line   ⁡     (     n   p   i     )       ·     E     j   ,   k     i         )                 (   18   )             
 
         [0027]     Finally, the recursive moment computation formulae can be obtained by incorporating the moment model of coupled distributed lines. From Eq. (17), the recursive relationship of the kth-order current moments is given as  
                   I     j   ,   k     i     ⁡     (   1   )       =       I     C     j   ,   k       i     +       ∑       n   y   i     ∈     S   ⁡     (     n   j   i     )           ⁢       I     y   ,   k     i     ⁡     (   0   )             ⁢     
     ⁢   where           (   19   )                   I     y   ,   k     i     ⁡     (   0   )       =         I     y   ,   k     i     ⁡     (   1   )       +       Line   ⁡     (     n   y   i     )       ·     J     y   ,   k     i                 (   20   )             
 
 Each current moment can be calculated from the leaves to the root of tree T i . Considering the relationships between voltage moments V j,k   i  and V F(j),k   i,k  Eq. (18) can be rewritten  
               V     j   ,   k     i     =       V       F   ⁡     (   j   )       ,   k     i     -       R   j   i     ⁢       I     j   ,   k     i     ⁡     (   1   )         -       L   j   i     ⁢       I     j   ,   k     i     ⁡     (   1   )         -       ∑       M     j   ,     j   1         i   ,     i   1         ∈     MM   j   i         ⁢       M     j   ,     j   1         i   ,     i   1         ⁢       I         j   1     ⁢   k     -   1       i   1       ⁡     (   1   )           -       Line   ⁡     (     n   j   i     )       ·     E     j   ,   k     i                 (   21   )             
 
 The computational complexity of the proposed recursive formulas of distributed models is O(nk 2  ), where n is the number of nodes in the tree. On the other hand, that of lumped models equals O(mk), where m is the number of nodes in the tree. In general, $m$ must be larger than nk so that the lumped model can be enough accurate. 
 
 Using the Moment Information to Construct Crosstalk Noise Estimation Model 
 
         [0028]     For {circumflex over (X)} d,k−1   T {circumflex over (M)} d {circumflex over (X)} d,l−2  in Eq. (2), Proposition 1 shows the results.  
         [0029]     Proposition 1: The term {circumflex over (X)} d,k−1   T {circumflex over (M)} d {circumflex over (X)} d,l−2  can be calculated by evaluating the contribution of each distributed line. The contributions of a line Line j   i  are  
                   ∫   0   J     ⁢         V     j   ,     k   -   1       i     ⁡     (   z   )       ⁢       I     C     j   ,     l   -   1         i     ⁡     (   z   )       ⁢     ⅆ   z         =       ∑     n   =   0       2   ⁢     (     k   +   l   -   3     )         ⁢       α     j   ,   n     i       n   +   1           ⁢     
     ⁢       where   ⁢           ⁢     a     j   ,   n     i       =       ∑     p   =     max   ⁡     (     0   ,     n   -     2   ⁢     (     l   -   2     )           )           min   ⁡     (       2   ⁢     (     k   -   1     )       ,   n     )         ⁢       β     j   ,     k   -   1     ,   p     i     ⁢     α     j   ,     l   -   1     ,     n   -   p       i     ⁢           ⁢   and                 (   22   )                   ∫   0   J     ⁢         I     j   ,     k   -   1       i     ⁡     (   z   )       ⁢       E     LM     j   ,     l   -   2         i     ⁡     (   z   )       ⁢     ⅆ   z         =       ∑     n   =   0       2   ⁢     (     k   +   l   -   4     )         ⁢       β     j   ,   n     i       n   +   1                 (   23   )             
 
 where b j,n   i  is the coefficient of the term z n  in the polynomial I j,k−1   i (z)E LM     j,j−2   (z) which can be calculated by polynomial multiplication of  
           I     j   ,     k   -   1       i     ⁡     (   1   )       +       ∑     n   =   0       2   ⁢     (     k   -   2     )         ⁢       1     n   +   1       ⁢       α     j   ,     k   -   1     ,   n     i     ⁡     (     1   -     x     n   +   1         )       ⁢           ⁢   and           
           L   j   i     ⁡     [         I     j   ,     k   -   1       i     ⁡     (   1   )       +       ∑     n   =   0       2   ⁢     (     l   -   3     )         ⁢       1     n   +   1       ⁢       α     j   ,     k   -   1     ,   n     i     ⁡     (     1   -     x     n   +   1         )             ]       +       ∑       M     j   ,     j   i         i   ,     i   1         ∈     MM   j   i         ⁢       M     j   ,     j   1         i   ,     i   1         ⁡     [         I       j   1     ,     k   -   1         i   1       ⁡     (   1   )       +       ∑     n   =   0       2   ⁢     (     l   -   3     )         ⁢       α       j   1     ,     k   -   1     ,   n       i   1       ⁡     (     1   -     x     n   +   1         )           ]             
 
 Moreover, subtle relationships between entries of {circumflex over (M)} and {circumflex over (N)}, and simplification of {circumflex over (N)} are summarized in Proposition 2. 
 
         [0030]     Proposition 2: Let matrices {circumflex over (M)} and {circumflex over (N)} be the MNA matrices for the reduced-order model that are generated by the congruence transformation Q, where Q=└X 0  X 1  . . . X q−1 ┘. Thus entries of {circumflex over (M)} and {circumflex over (N)} have the following subtle relationships: 
    1.{circumflex over (m)} ij =−X i−1   T NX j =−{circumflex over (n)} i,j+1       2. m ij =X j−1   T MX i−1 =−X j−1   T NX i =−{circumflex over (n)} j,i+1  
 
 entries in the first column and the first row of matrices {circumflex over (N)} the relationships shown as below: 
    1. {circumflex over (n)} 11 =0;     2. {circumflex over (n)} i1 (i&gt;1), denoted as I 1,i−1   a is equal to the (i−1)st-order moment of the current entering node n 1   a  in the aggressor tree T a ;     3. {circumflex over (n)} 1i =−{circumflex over (n)} i1  
 
 Crosstalk Noise Estimation Model 
   
 
         [0036]     Let V(s) and {circumflex over (V)}(s)be the step responses of the original model and the desired reduced-order model, respectively. Technique disclosed in M. Kuhlmann and S. S. Sapatnekar, “Exact and efficient crosstalk estimation,”  IEEE Trans. Computer - Aided Design , vol. 20, no. 7, pp. 858-866, 2001, suggested an appropriate formula of the q -pole reduced-order model {circumflex over (V)}(s) as follows (as in step  24 ):  
                 V   ^     ⁡     (   s   )       =         a   0     +       a   1     ⁢   s     +   …   +       a     q   -   2       ⁢     s     q   -   1             1   +       b   1     ⁢   s     +   …   +       b     q   -   1       ⁢     s     q   -   1         +       b   q     ⁢     s   q                   (   24   )             
 
 which causes the approximate crosstalk voltage {circumflex over (v)}(t) to be zero for t converging to 0 and ∞. Conventional moment matching techniques are often used to solve the unknown coefficients a i (0≦i≦q−2) and b j (1≦j≦q) by using the front 2q−1 moments {V 1 V 2 , . . . V 2q−1 } of the original model: 
 
 V ( s )= V   1 +V 2 s+V 3 s 2 + . . . +V 2q−1 s 2q−2 + . . . 
 
         [0037]     In step  26 , Eq. (24) can also be rewritten as the pole-residue form  
                 V   ^     ⁡     (   s   )       =         k   1       s   -     p   1         +       k   2       s   -     p   2         +   …   +       k   q       s   -     p   q                   (   25   )             
 
 where p i  for i=1,2, . . . ,q are poles of {circumflex over (V)}(s) and each k i  is the residue corresponding to the pole p i . By applying the inverse Laplace transformation, we have 
 
{circumflex over ( v )}( t )= k   1   e   p     1     t   +k   2   e   p     2     t   + . . . +k   q   e   p     q     t  
 
         [0038]     In step  28 , the peak value of the crosstalk waveform will occur at time t=t m  where {circumflex over (v)}′(t m )=0 and {circumflex over (v)}″(t m )&lt;0.  
         [0039]     In the previous moment computations, the input waveform is assumed to be a step function. However, the input signal in step  10  may be with an arbitrary waveform. Let the updated v(s) be 
 
 V ( s )= m   1   ′s+m   2   ′s   2   +m   3   ′s   3   +m   4   ′s   4   +m   5   ′s   5   (26) 
 
         [0040]     For example, suppose that the input signal is a ramp function as follows:  
         v   ⁢           ⁢     (   t   )       =         t   τ     ⁢   u   ⁢           ⁢     (   t   )       -       t   τ     ⁢   u   ⁢           ⁢     (     t   -   τ     )       +     u   ⁢           ⁢     (     t   -   τ     )             
 
 where u(t) is a step function and 1/τ is the slope of the ramp function. Applying the Laplace transform, we have  
               V   ⁢           ⁢     (   s   )       =       1   s     ⁢     (     1   -       τ   2     ⁢   s     +         τ   2     6     ⁢     s   2       -         τ   3     24     ⁢     s   3       +         τ   4     120     ⁢     s   4       +   …     ⁢           )               (   27   )             
 
         [0041]     Comparing the coefficients of Eqs. (26) and (27) concludes  
               m   1   ′     =     m   1                   m   2   ′     =       m   2     -       τ   2     ⁢     m   1                       m   3   ′     =       m   3     -       τ   2     ⁢     m   2       +         τ   2     6     ⁢     m   1                       m   4   ′     =       m   4     -       τ   2     ⁢     m   3       +         τ   2     6     ⁢     m   2       -         τ   3     24     ⁢     m   1                         m   5   ′     =       m   5     -       τ   2     ⁢     m   4       +         τ   2     6     ⁢     m   3       -         τ   3     24     ⁢     m   2       +         τ   4     120     ⁢     m   1           ⁢     
     ⁢           ⁢   ⋮             
 
       ILLUSTRATIVE EXAMPLES  
       [0042]     To verify the accuracy of the proposed method, a coupling circuit but not limiting examples shown in  FIG. 5  are studied for crosstalk estimations. The squares represent the roots of the trees and and the circles stand for the leaves of the trees for crosstalk estimations. Among all circuits, the line parameters are resistance: 35 Ω/cm, grounding capacitance: 5.16 pF/cm, self inductance: 3.47 nH/cm, coupling capacitance: 6 pF/cm, and mutual inductance: 1 nH/cm. The wire resistance, capacitance and inductance are distributed per 100 μm. The loading of each line is 50 fF. We examine peak values of noises and peak noise occurring time for the cases with different circuit topologies, line lengths, coupling locations, effective driver impedances, and rising times. For the circuits in  FIG. 5 , the lengths of the coupling line of net  1  belong to the set L1={1, 2, 3, 4, 5}(mm) and those of net  2  are also in the set L2={1, 2, 3, 4, 5}(mm) that are never longer than the lengths of net  1 . Each net  2  changes the coupling locations and shifts 1 mm each time from alignment at the near end of net  1  to that at the far end of net  1 . In each case, net  1  and net  2  are excited independently. In addition, four effective driver impedance pairs: 3Ω-3Ω, 3Ω-30Ω, 30Ω-3Ω and 30Ω-30Ω, which are connected to the near ends of the two nets, are examined. The voltage source connected to the aggressor net is a ramp function with two rising time 0.02 ns and 0.2 ns and with a normalized unit magnitude. Thus, we have total 560 cases to examine accuracy of the proposed method.  
         [0043]     The conventional one-pole model (1P) and two-pole model (2P) and our new method with three-pole model (S3P), . . . , six-pole model (S6P) are investigated for comparison studies. Absolute and relative errors of crosstalk peak values in comparison with HSPICE simulation results are summarized in Tables 1 Among the 560 cases, model 1P has unstable poles in 48 cases and model 2P is unstable in 98 cases. Table 2 summarizes the computational times of moments and the relative errors of model S6P generated by lumped couple RLC-tree models with different number of sections per 1 mm long, to compare the efficiency and the accuracy between distributed lines and lumped ones.  
         [0000]     From simulation results, we have the following observations:  
         [0044]     1. The models generated by the proposed method outperform the conventional 1P and 2P models. Thus these conventional models are no longer appropriate for coupled RLC trees. Increasing the order of the reduced-order models allows the proposed models perform more accurately.  
         [0045]     2. From the viewpoints of the absolute errors in Table1, model S3P, whose average. errors are smaller than 10%, seems acceptable for estimating crosstalk noise. However, the relative errors imply that model S3P seems not accurate as expected. Model S6P is recommended to balance computational efficiency and estimation performance.  
         [0046]     3. The computational time of moments and the relative errors of Model S6P yielded by the proposed method are 8.27 seconds and 5.15%, respectively. Table 2 displays that it must cost more than 271.96 seconds to obtain the same relative error by using lumped coupled RLC lines. Obviously, the efficiency and the accuracy of distributed models outperform those of lumped models.  
                                                                                                                             TABLE 1                           Comparisons of the absolute and relative       errors of the crosstalk peak values                1P   2P   S3P   S4P   S5P   S6P                            Absolute Error (%)            Maximum   18425   41671   20.16   23.95   19.97   10.62       Average   106.57   227.56   4.45   3.61   2.06   1.08       Minimum   0.01   0.28   0.02   0   0   0                Relative Error (%)            Maximum   47140   192110   64.28   75.99   64.44   53.9       Average   347.25   1043.8   22.67   16.18   10.56   5.15       Minimum   0.08   1.58   0.05   0.05   0   0                  
 
         [0047]    
       
         
               
             
               
               
             
               
               
               
               
               
               
             
               
               
             
               
               
               
               
               
               
             
           
               
                 TABLE 2 
               
               
                   
               
               
                   
               
               
                 Computational times of moments and relative errors 
               
               
                 of model S6P generated by lumped couple RLC-tree 
               
               
                 models with different number of sections per 1 mm 
               
               
                 long (Intel P4 2.66 GHz CPU and 1 GB RAM) 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 No. of Sections 
               
             
          
           
               
                   
                 2 
                 3 
                 4 
                 5 
                 6 
               
               
                   
               
               
                 Time (sec.) 
                 9.58 
                 14.68 
                 19.25 
                 24.28 
                 29.48 
               
               
                 Relative Error (%) 
                 7.63 
                 6.56 
                 6.06 
                 5.81 
                 5.66 
               
               
                   
               
             
          
           
               
                   
                 No. of Sections 
               
             
          
           
               
                   
                 10 
                 20 
                 30 
                 40 
                 50 
               
               
                   
               
               
                 Time (sec.) 
                 49.96 
                 103.12 
                 157.21 
                 213.77 
                 271.96 
               
               
                 Relative Error (%) 
                 5.40 
                 5.23 
                 5.19 
                 5.17 
                 5.16