# Patent

## Title
Transient response of a distributed RLC interconnect based on direct pole extraction

## Abstract

A computer system for simulating performance of transmission lines, such as on-chip interconnects. The simulation uses direct extraction of poles, in contrast to conventional methods using poles obtained by a truncated transfer function. Using the directly extracted poles, far end response characteristic(s) can be determined to thereby aid in design of circuits using transmission lines. The far end response characteristic(s) that may be determined based on the directly extracted poles include, but are not necessarily limited to, frequency dependent effects, step response, ramp response, delay, 50% delay, rise time, 10% to 90% rise time, overshoot and normalized overshoot. A CAE tool designer and/or CAE tool user may decide how many pole pairs to directly extract to achieve a desired balance between computation resources required and resulting precision in the determination of far end response characteristic(s).

## Background
RELATED APPLICATION
The present application claims priority to U.S. Provisional Application No. 60/845,250, filed on Sep. 18, 2006; all of the foregoing patent-related document(s) are hereby incorporated by reference herein in their respective entirety(ies).


FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
The U.S. Government may have certain rights in this invention pursuant to Grant No. C040130 awarded by NYSTAR and Grant No. CCF0541206 awarded by National Science Foundation.


BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer systems for simulating (see definitions sections) the performance of electronic circuits and more particularly to computer software for simulating on-chip interconnects and/or other conductors that behave as transmission lines.
2. Description of the Related Art
Certain electrical conductors behave as transmission lines. When conducting electrical signals, these conductors exhibit far end response characteristics (see Definitions section), such as frequency dependent effects, step response, ramp response, delay, 50% delay, rise time, 10% to 90% rise time, overshoot and normalized overshoot. Designers of systems using transmission lines often must take various far end response characteristics into account in the circuit design. For example, on-chip interconnects exhibit significant transmission line behavior, especially with the scaling of CMOS technology and its associated high performance integrated circuits (ICs), which use relatively high frequencies and relatively long wire lengths.
For CMOS IC on-chip interconnect design, on-chip interconnect design more generally, and even other types of transmission line design, the circuits are simulated on computer systems, as they are designed. The computer system (generally in its software component) allows the designer to simulate transmission lines and to determine or estimate the far end characteristics. In this way, the timing characteristics sent over the transmission lines can be determined, preferably with sufficient accuracy and precision so that the design (for example, CMOS IC chip design) will work for its intended purpose at its operating frequency(ies).
In order for the computer system to simulate the transmission line and determine or estimate the desired far end response characteristics, the line is mathematically modeled as an RC interconnect or, more commonly, as an RLC interconnect (see Definitions section). For example, many computer aided engineering (CAE) simulation tools conventionally include RLC interconnect simulation for use in simulating the performance of on-chip interconnects. Some conventional methods for determining (see Definitions section) far end response characteristics of RLC interconnects will now be described.
Krylov-subspace-based methods, such as Amoldi algorithm, are commonly used in simulations of interconnect structures with lumped RLC components. For a single wire structure (that is, point-to-point connection) a large number of RLC lumped components are required to simulate the distributed RLC performance of a distributed RLC interconnect. This is relatively inefficient.
Spectre simulations are used in RLC interconnect simulation and can provide accurate results. However, Spectre simulations consume much more simulation time and are inefficient.
Another conventional method is disclosed in the following articles: (i) T. Sakurai, “Approximation of Wiring Delay in MOSFET LSI,” IEEE Journal of Solid-State Circuits, Vol. 18, No. 4, pp. 418-426, August 1983; and (ii) T. Sakurai, “Closed-Form Expressions for Interconnection Delay, Coupling, and Crosstalk in VLSI's,” IEEE Transactions on Electron Devices, Vol. 40, No. 1, pp. 118-124, January 1993. (collectively “Sakurai”). In Sakurai, an accurate closed-form solution is disclosed for distributed RC interconnect based on a single pole approximation.
By truncating the transfer function, multi-pole models have been proposed in the last decade to capture the effect of inductance. One example of this method, using two poles is disclosed in A. B. Kahng and S. Muddu, “An Analytical Delay Model for RLC Interconnects,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 16, No. 12, pp. 1507-1514, December 1997 (“Kahng”). At page 1509, Kahng sets forth the exact transfer function for an RLC interconnect, but then truncates it by expanding the hyperbolic functions present in the transfer function as infinite series, and then collecting terms in this series up to the coefficient of s2. Use this truncated version of the transfer function means that the poles obtained by Kahng are approximate and not exact. Kahng goes on to derive a delay model from the two pole response for the real pole case, the complex pole case and the double pole case.
Another example of this method of truncating the transfer function, using four poles, is disclosed in K. Banerjee and A. Mehrotra, “Accurate Analysis of On-Chip Inductance Effects and Implications for Optimal Repeater Insertion and Technology Scaling,” Proceedings of the IEEE Symposium on VLSI Circuits, pp. 195-198, June 2001 (“Banerjee”). No closed-form solution, however, is provided for the four-pole method. Like Kahng, Banerjee also sets forth the exact transfer function for an RLC interconnect (see Banerjee at equation (1)), including the hyperbolic terms in the denominator. Banerjee then proceeds to truncate this equation by substituting a fourth-order Padé approximation of the transfer function. The fourth-order approximation has terms up to the order of s4, instead of merely up to the order of s2, as in Kahng. Still, the transfer function itself is truncated. Banerjee proceeds to use this truncated version of transfer function to calculate step-response for appropriate residues and approximate poles.
In J. A. Davis and J. D. Meindl, “Compact Distributed RLC Interconnect Models—Part I: Single Line Transient, Time Delay, and Overshoot Expressions,” IEEE Transactions on Electron Devices, Vol. 47, No. 11, pp. 2068-2077, November 2000 (“Davis”), the solution for an open-ended interconnect with a step input signal is rigorously developed. This solution however is highly complicated and not suitable for an exploratory design process.
In Y. Eo, J. Shim, and W. R. Eisenstadt, “A Traveling-Wave-Based Waveform Approximation Technique for the Timing Verification of Single Transmission Lines,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 21, No. 6, pp. 723-730, June 2002 (“Eo”), a traveling wave analysis (TWA) model has been presented, where the key points of the waveform are determined with a three-pole model and linear or RC approximations are used to connect those key points to construct the waveform. This method is improved in J. Chen and L. He, “Piecewise Linear Model for Transmission Line With Capacitive Loading and Ramp Input,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 24, No. 6, pp. 928-937, June 2005 (“J. Chen”). In J. Chen, the key points and slopes are more accurately determined with the model described in Davis, and straight lines are used to construct the signal waveforms in different time regions. In both Eo and J. Chen, the output response is divided into a number of time regions where the waveform expressions for each of the regions are different, making the models less compact. Furthermore, none of these aforementioned papers consider frequency dependent effects.
With higher on-chip frequencies, frequency dependent effects in wider interconnect can no longer be ignored. One article dealing with frequency dependent effect was written by the named inventors for this document: G. Chen and E. G. Friedman, “An RLC Interconnect Model Based on Fourier Analysis,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 24, No. 2, pp. 170-183, February 2005 (“G. Chen Article”). In the G. Chen Article, a Fourier analysis based interconnect model is proposed, where the far end response is approximated by the first several harmonics. Frequency dependent effects can be included in this model; however, the model of the G. Chen Article is only suitable for periodic signals.
Description Of the Related Art Section Disclaimer: To the extent that specific publications are discussed above in this Description of the Related Art Section, these discussions should not be taken as an admission that the discussed publications (for example, published patents) are prior art for patent law purposes. For example, some or all of the discussed publications may not be sufficiently early in time, may not reflect subject matter developed early enough in time and/or may not be sufficiently enabling so as to amount to prior art for patent law purposes. To the extent that specific publications are discussed above in this Description of the Related Art Section, they are all hereby incorporated by reference into this document in their respective entirety(ies).
BRIEF SUMMARY OF THE INVENTION
The present invention is directed to a computer system that mathematically models the performance of a transmission line based on direct pole extraction of an exact transmission line transfer function rather than obtaining the poles of a truncated transfer function as is conventional. Preferably, closed form expressions of the poles are developed for the zero driver resistance case. To utilize these expressions in the case of a transmission line with driver resistance, the interconnect transmission with driver resistance can be converted to a system without a driver resistance. Based on these directly extracted poles, one or more far end response characteristic(s) may additionally be determined. For example, closed form expressions for the step and ramp responses are preferably determined.
With two pairs of poles, some embodiments of the present invention may provide an accurate delay estimate, exhibiting an average error of 1% as compared to Spectre simulations. Higher accuracy can be obtained with additional poles. A trade-off between accuracy and efficiency is provided by the simulation of the computer systems according to the present invention. Specifically, the computational complexity of the model is proportional to the number of pole-pairs that are included in the simulation.
Various embodiments of the present invention may exhibit one or more of the following objects, features and/or advantages:
(1) more efficient than Krylov-subspace-based methods and/or Spectre simulations in simulations of single interconnects;
(2) flexibility in simulation by choice of number of pole pairs, depending on factors such as computational resources available and required accuracy and/or precision;
(3) useful in CAE tools;
(4) allows timing of transmission line signals to be determined and controlled with relative accuracy and precision;
(5) can account for effects of interconnect inductance;
(6) average error in delay, rise-time and/or over-shoots can be made relatively small compared to other non-Spectre simulation type methods;
(7) allows simulation of frequency dependent effects, and excellent match has observed between simulation according to the present invention and corresponding Spectre simulation;
(8) distributed characteristic of the RLC interconnect is considered implicitly;
(9) in some applications, dummy fillings are inserted on-chip to achieve a uniform pattern density, making a uniform impedance assumption, as used in the present invention, a more accurate simulation;
(10) can be used as the basis of an EDA software tool;
(11) good performance for on-chip interconnect simulation at relatively high on-chip signal frequencies; and
(12) useful for simulations in the context of CMOS technology.
One aspect of the present invention is directed to a computer system including a first computer portion and a second computer portion. The first computer portion is structured and/or programmed to receive input characteristics of a transmission line to be simulated as an RLC distributed interconnect, with the input characteristics being sufficient to define a transfer function for the simulated RLC interconnect. The second computer portion is structured and/or programmed to determine at least one pole of the transfer function such that the transfer function is not truncated in the determination of the at least one pole.
A further aspect of the present invention is directed to a computer system including a first computer portion, a second computer portion and a third computer portion. The first computer portion is structured and/or programmed to receive input characteristics of a transmission line to be simulated as an RLC distributed interconnect, with the input characteristics being sufficient to define a transfer function for the simulated RLC interconnect. The second computer portion structured and/or programmed to approximate at least one pole of the transfer function. The third computer portion structured and/or programmed to determine at least one exact pole of the transfer function by applying Newton-Raphson method to the at least one pole as determined by the second computer portion.
A further aspect of the present invention is directed to a computer system including a first computer portion and a second computer portion. The first computer portion is structured and/or programmed to receive input characteristics of a transmission line to be simulated as an RLC distributed interconnect, with the input characteristics being sufficient to define a transfer function for the simulated RLC interconnect. The second computer portion is structured and/or programmed to determine at least one pole of the transfer function by transforming the denominator of the transfer function into terms of a variable x, finding at least one value for x such that the transformed denominator is equal to zero and using the at least one value for x to determine the at least one pole of the transfer function.



BRIEF DESCRIPTION OF THE DRAWINGS
The present invention will be more fully understood and appreciated by reading the following Detailed Description in conjunction with the accompanying drawings, in which:
FIG. 1 is a schematic of a first embodiment of a computer system according to the present invention;
FIG. 2 is a flowchart of a first embodiment of a method according to the present invention;
FIG. 3 is a schematic of a transmission line type conductor that has been simulated as an RLC interconnect;
FIG. 4 is a graph showing the roots of equation (4);
FIG. 5 is a graph showing the solution of equation (3);
FIG. 6 is a graph showing the roots of equation (15);
FIG. 7 is a graph comparing exact and analytic solutions of equation (14);
FIG. 8 is a schematic of a wire structure used in transmission line simulation according to the methods of the present invention;
FIGS. 9A and 9B are graphs comparing the results of equation (21) to exact solutions for the RC and RLC with zero driver resistance cases;
FIGS. 10A to 10D are graphs comparing the direct extracted pole solutions of the present invention to corresponding Spectre simulation based solutions;
FIGS. 11A and 11B are graphs comparing transient response as obtained using various solution methods;
FIG. 12 is a graph comparing the value(s) of analytically obtained poles to corresponding exact poles;
FIG. 13 is a graph comparing waveforms obtained using methods of the present invention to corresponding waveforms obtained by corresponding Spectre simulation;
FIGS. 14A and 14B are graphs comparing transient response as obtained using methods of the present invention to corresponding Spectre simulation;
FIGS. 15A and 15B are graphs comparing various far end characteristics obtained using methods of the present invention to corresponding Spectre simulation;
FIGS. 16A and 16B are graphs comparing various 50% delay and 10%-to-90% rise time obtained using methods of the present invention to corresponding Spectre simulation;
FIG. 17 is a schematic of two stage ladder structure of frequency independent elements;
FIGS. 18A and 18B are graphs showing frequency dependent impedance of an interconnect;
FIG. 19 is a graph comparing waveforms obtained with and without consideration of frequency dependent effects; and
FIG. 20 is a graph comparing transfer functions obtained with and without consideration of frequency dependent effects.



DETAILED DESCRIPTION OF THE INVENTION
FIG. 1 shows a computer system 100 according to the present invention including server computer 102; network 106 and client computers 108(1) to 108(N). Server computer 102 includes CAE software 104 according to the present invention where the CAE software operates according to the methods for determining poles and/or far end characteristics of a simulated transmission line, such as an on-chip interconnect. FIG. 2 is a flowchart, including steps S10, S12, S13, S14, S16 and S18, describing the operation of software 104 in general terms. Network 106 may be any type of computer network now known or to be developed in the future, including wired networks, wireless networks and networks including both wired and wireless portions. Preferably, access to software 104 is password protected so that “seats” may be sold and the costs of developing and maintaining the software may be recovered by the software provider(s).
Alternatively, the computer systems of the present invention may perform the inventive methods and/or algorithms of the present invention in whole, or in part, by firmware and/or hardware. Although FIG. 1 shows a standard networked arrangement for distribution of the software and associated computation, other arrangements could be used, such as a stand-alone mainframe computer, a stand-alone personal computer, a server computer with dummy terminals, or any other computer architecture now known or to be developed in the future.
The simulation model, to be used in conjunction with the system of FIG. 1 and the method of FIG. 2 is based on a direct pole extraction of the exact transfer function of a transmission line, rather than by approximating the poles by truncating the transfer function, or matching moments. Closed-form waveform expressions will be discussed, permitting flexible tradeoffs between accuracy and efficiency.
Now, the exact poles of two special case interconnect systems will be determined. Based on these exact poles, the corresponding step and ramp responses will be developed. For a distributed RLC interconnect driven by a voltage source with a driver resistance Rd and loaded with a lumped capacitance CL, as shown in FIG. 3 at simulation schematic 300, the transfer function is given by the following equation (1):




  
    
      H
      ⁡
      
        (
        s
        )
      
    
    =
    
      l
      
        
          
            (
            
              1
              +
              
                
                  R
                  d
                
                ⁢
                
                  C
                  L
                
                ⁢
                s
              
            
            )
          
          ⁢
          
            cosh
            ⁡
            
              (
              θ
              )
            
          
        
        +
        
          
            (
            
              
                
                  R
                  d
                
                /
                
                  Z
                  c
                
              
              +
              
                
                  Z
                  c
                
                ⁢
                
                  C
                  L
                
                ⁢
                s
              
            
            )
          
          ⁢
          
            sinh
            ⁡
            
              (
              θ
              )
            
          
        
      
    
  
  ,




where θ=√{square root over ((R+Ls)Cs)} and Zc=√{square root over ((R+Ls/Cs)}=θ/Cs. R, L and C are respectively the resistance, inductance and capacitance of the simulated interconnect. The poles of equation (1) are difficult to solve directly, except for two special cases: (i) an RC interconnect; and (ii) an RLC interconnect with a zero driver resistance. Below, the poles of an RC interconnect system will be solved. Following the RC interconnect solution, the poles of an RLC interconnect with a zero driver resistance will be solved. Following the RLC solution, step and ramp responses will be developed.

For the RC interconnect, L=0. The transfer function, given in equation (1), can be rewritten as the following equation (2):




  
    
      
        
          
            
              H
              ⁡
              
                (
                s
                )
              
            
            =
            
              1
              
                
                  
                    (
                    
                      1
                      +
                      
                        A
                        ⁢
                        
                          
                        
                        ⁢
                        
                          θ
                          2
                        
                      
                    
                    )
                  
                  ⁢
                  
                    cosh
                    ⁡
                    
                      (
                      θ
                      )
                    
                  
                
                +
                
                  B
                  ⁢
                  
                    
                  
                  ⁢
                  θ
                  ⁢
                  
                    
                  
                  ⁢
                  
                    sinh
                    ⁡
                    
                      (
                      θ
                      )
                    
                  
                
              
            
          
          ,
          
            

          
          ⁢
          where
        
        ⁢
        
          

        
        ⁢
        
          
            A
            =
            
              
                R
                T
              
              ⁢
              
                C
                T
              
            
          
          ,
          
            

          
          ⁢
          
            B
            =
            
              
                R
                T
              
              +
              
                C
                T
              
            
          
          ,
          
            

          
          ⁢
          
            
              R
              T
            
            =
            
              
                R
                d
              
              /
              R
            
          
          ,
          
            

          
          ⁢
          
            
              C
              T
            
            =
            
              
                C
                L
              
              /
              C
            
          
          ,
          and
        
        ⁢
        
          

        
        ⁢
        
          θ
          =
          
            
              RCs
            
            .
          
        
      
    
    
      
        (
        2
        )
      
    
  




Let F(s)=1/H(s). The poles of H(s) are zeros of F(s) and satisfy F(s)=0. Observe that θ needs to be an imaginary number to make F(s) zero. Assume θ=jx, where x is a real number. Expression F(s)=0 can be transformed to the following equations (3) or (4):




  
    
      
        
          
            
              
                (
                
                  1
                  -
                  
                    Ax
                    2
                  
                
                )
              
              ⁢
              cos
              ⁢
              
                
              
              ⁢
              x
            
            -
            
              Bx
              ⁢
              
                
              
              ⁢
              sin
              ⁢
              
                
              
              ⁢
              x
            
          
          =
          0
        
        ,
        
          

        
        ⁢
        or
      
    
    
      
        (
        3
        )
      
    
  
  
    
      
        
          tan
          ⁢
          
            
          
          ⁢
          x
        
        =
        
          
            
              1
              -
              
                Ax
                2
              
            
            Bx
          
          .
        
      
    
    
      
        (
        4
        )
      
    
  




The roots of equation (4) are the crossing points of the functions of y=tan x and y=(1−Ax2)/(Bx), as shown in the graph of FIG. 4. FIG. 4 is a graph of the roots of equation (4), where RT=CT=1.

Applying Taylor series expansions of cos x≈1−x2/2+x4/24 and sin x≈x−x3/6 to equation (3), and ignoring those terms with an order higher than x4 results in the following equation (5):




  
    
      
        
          
            
              (
              
                
                  
                    1
                    2
                  
                  ⁢
                  A
                
                +
                
                  
                    1
                    6
                  
                  ⁢
                  B
                
                +
                
                  1
                  24
                
              
              )
            
            ⁢
            
              x
              4
            
          
          -
          
            
              (
              
                
                  1
                  2
                
                +
                A
                +
                B
              
              )
            
            ⁢
            
              x
              2
            
          
          +
          1
        
        =
        0.
      
    
    
      
        (
        5
        )
      
    
  




Although equation (5) applies a Taylor series expansion where higher order terms are ignored, this is not considered to be a truncation or an approximation of the transfer function because equations (3) and (4) do not represent the transfer function or a portion thereof. Solving (5) for the smaller x2 yields the following equation (6):





  
    
      
        
          
            x
            0
            2
          
          =
          
            
              
                
                  
                    
                      1
                      2
                    
                    +
                    A
                    +
                    B
                    -
                    
                      
                        
                          
                            (
                            
                              A
                              +
                              B
                            
                            )
                          
                          2
                        
                        -
                        A
                        +
                        
                          
                            1
                            3
                          
                          ⁢
                          B
                        
                        +
                        
                          1
                          12
                        
                      
                    
                  
                  
                    A
                    +
                    
                      
                        1
                        3
                      
                      ⁢
                      B
                    
                    +
                    
                      1
                      12
                    
                  
                
                .
                
                  

                
                ⁢
                When
              
              ⁢
              
                
              
              ⁢
              
                R
                T
              
            
            =
            
              
                C
                T
              
              =
              0
            
          
        
        ,
        
          the
          ⁢
          
            
          
          ⁢
          exact
          ⁢
          
            
          
          ⁢
          value
          ⁢
          
            
          
          ⁢
          of
          ⁢
          
            
          
          ⁢
          
            x
            0
            2
          
          ⁢
          
            
          
          ⁢
          is
          ⁢
          
            
          
          ⁢
          
            
              π
              2
            
            /
            4.
          
        
      
    
    
      
        (
        6
        )
      
    
  




In order to capture this trend, equation (6) is revised to the following equation (7):





  
    
      
        
          x
          0
          2
        
        =
        
          
            
              
                1
                2
              
              +
              A
              +
              B
              -
              
                
                  
                    
                      (
                      
                        A
                        +
                        B
                      
                      )
                    
                    2
                  
                  -
                  A
                  +
                  
                    
                      1
                      3
                    
                    ⁢
                    B
                  
                  +
                  
                    1
                    11.54
                  
                
              
            
            
              A
              +
              
                
                  1
                  3
                
                ⁢
                B
              
              +
              
                1
                12
              
            
          
          .
        
      
    
    
      
        (
        7
        )
      
    
  




Note that if the term x4 in equation (5) is ignored, the solution simplifies the following equation (8):





  
    
      x
      0
      2
    
    =
    
      
        1
        
          0.5
          +
          A
          +
          B
        
      
      =
      
        1
        
          0.5
          +
          
            R
            T
          
          +
          
            C
            T
          
          +
          
            
              R
              T
            
            ⁢
            
              C
              T
            
          
        
      
    
  
  ,




which is similar to the solution provided in Sakurai. Since the Taylor series approximations used in equation (5) are expanded around zero, the solution shown in equation (7) corresponds to the root x0 which is closest root to zero, as show in FIG. 4. In order to obtain other high order solutions, Taylor series approximations expanded at nπ(n=1, 2, . . . ) are used. Since the negative roots of equation (3) have the same absolute value as the positive roots, only positive roots are considered in this analysis. Let Δx=x−nπ, cos x≈(−1)n[1−(Δx)2/2], and sin x≈(−1)nΔx. Substituting these Taylor series approximations into equation (3) and ignoring those terms with an order higher than (Δx)2 results in the following equation 9:





  
    
      
        
          (
          
            A
            +
            B
            -
            
              
                1
                2
              
              ⁢
              E
            
          
          )
        
        ⁢
        
          
            (
            
              Δ
              ⁢
              
                
              
              ⁢
              x
            
            )
          
          2
        
      
      +
      
        
          (
          
            
              2
              ⁢
              A
            
            +
            B
          
          )
        
        ⁢
        n
        ⁢
        
          
        
        ⁢
        π
        ⁢
        
          
        
        ⁢
        Δ
        ⁢
        
          
        
        ⁢
        x
      
      +
      E
    
    =
    0
  
  ,
  
    

  
  ⁢
  
    
      where
      ⁢
      
        
      
      ⁢
      E
    
    =
    
      
        
          An
          2
        
        ⁢
        
          π
          2
        
      
      -
      1.
    
  




Although equation (9) applies a Taylor series expansion where higher order terms are ignored, this is not considered to be a truncation or an approximation of the transfer function because equation (3) does not represent the transfer function or a portion thereof. Solving equation (9) for xn results in the following equation (10):





  
    π
    n
  
  =
  
    
      
        
          -
          
            (
            
              
                2
                ⁢
                A
              
              +
              B
            
            )
          
        
        ⁢
        n
        ⁢
        
          
        
        ⁢
        π
      
      +
      
        
          
            
              (
              
                n
                ⁢
                
                  
                
                ⁢
                π
                ⁢
                
                  
                
                ⁢
                B
              
              )
            
            2
          
          +
          
            4
            ⁢
            
              (
              
                A
                +
                B
              
              )
            
          
          +
          
            2
            ⁢
            
              E
              2
            
          
        
      
    
    
      
        2
        ⁢
        
          (
          
            A
            +
            B
          
          )
        
      
      -
      E
    
  




FIG. 5 shows the analytic solution of equation (3) as compared with the exact solution for different values of RT and CT. The accuracy of equation (7) and equation (10) is illustrated in FIG. 5 for different values of RT and CT. As shown in FIG. 5, the error of the higher order solutions is larger for greater values of RT and CT. In these cases, the effect of the higher order solutions, however, is negligible.

After solving xn, the poles of an RC interconnect system can be obtained using the following equation (11):




  
    
      p
      n
    
    =
    
      
        
          θ
          2
        
        RC
      
      =
      
        
          -
          
            x
            n
            2
          
        
        RC
      
    
  
  ,
  
    n
    =
    0
  
  ,
  1
  ,
  2
  ,
  
    ...
    ⁢
    
      
    
    .
  




Although the solutions used for xn do not correspond to the exact solutions for xn (see FIG. 5), the determination of the poles pn are still considered to be based on an untruncated version of the transfer function because no truncation or approximation of the transfer function itself was used in obtaining these pn values. Also, the pn values can be refined using methods such as Newton Raphson, as explained below to obtain exact poles. The residue of the corresponding poles is given by the following equation (12):





  
    
      
        
          k
          n
        
        =
        
          
            lim
            
              s
              →
              
                p
                n
              
            
          
          ⁢
          
            
              s
              -
              
                p
                n
              
            
            
              F
              ⁡
              
                (
                s
                )
              
            
          
        
      
    
  
  
    
      
        =
        
          1
          
            
              F
              ′
            
            ⁡
            
              (
              
                p
                n
              
              )
            
          
        
      
    
  
  
    
      
        
          =
          
            
              2
              ⁢
              
                
                  x
                  n
                
                /
                
                  (
                  RC
                  )
                
              
            
            
              
                
                  (
                  
                    1
                    +
                    B
                    -
                    
                      Ax
                      n
                      2
                    
                  
                  )
                
                ⁢
                sin
                ⁢
                
                  
                
                ⁢
                
                  x
                  n
                
              
              +
              
                
                  (
                  
                    
                      2
                      ⁢
                      A
                    
                    +
                    B
                  
                  )
                
                ⁢
                
                  x
                  n
                
                ⁢
                cos
                ⁢
                
                  
                
                ⁢
                
                  x
                  n
                
              
            
          
        
        ,
      
    
  




where F′(pn) is the derivative of F(s) at pn.

Now an RLC interconnect with a zero driver resistance (Rd) will be considered. If Rd is zero, then equation (1) simplifies to the following equation (13):




  
    H
    ⁡
    
      (
      s
      )
    
  
  =
  
    
      1
      
        
          cosh
          ⁡
          
            (
            θ
            )
          
        
        +
        
          
            C
            T
          
          ⁢
          θ
          ⁢
          
            
          
          ⁢
          
            sinh
            ⁡
            
              (
              θ
              )
            
          
        
      
    
    .
  




Note that θ also needs to be an imaginary number to make F(s) zero. Similar to the approach for the RC case, assume θ=jx, where x is a real number. The poles of the transfer function should satisfy the following equations (14) and (15):





  
    
      
        
          
            
              cos
              ⁢
              
                
              
              ⁢
              x
            
            -
            
              
                C
                T
              
              ⁢
              x
              ⁢
              
                
              
              ⁢
              sin
              ⁢
              
                
              
              ⁢
              x
            
          
          =
          0
        
        ,
        
          

        
        ⁢
        or
      
    
    
      
        (
        14
        )
      
    
  
  
    
      
        x
        =
        
          
            
              cot
              ⁢
              
                
              
              ⁢
              x
            
            
              C
              T
            
          
          .
        
      
    
    
      
        (
        15
        )
      
    
  




FIG. 6 is a graph of the roots of equation (15) when CT=1. The roots of equation (15) are the crossing point of the curves of functions y=x and y=cot x/CT, as shown in FIG. 6.
By applying Taylor series approximations, x can be solved using the following equation (16):




  
    x
    n
  
  =
  
    {
    
      
        
          
            
              
                
                  
                    1
                    2
                  
                  +
                  
                    C
                    T
                  
                  -
                  
                    
                      
                        C
                        T
                        2
                      
                      +
                      
                        
                          1
                          3
                        
                        ⁢
                        
                          C
                          T
                        
                      
                      +
                      
                        1
                        12
                      
                    
                  
                
                
                  
                    
                      1
                      3
                    
                    ⁢
                    
                      C
                      T
                    
                  
                  +
                  
                    1
                    12
                  
                
              
            
            ,
          
        
        
          
            n
            =
            0
          
        
      
      
        
          
            
              
                
                  
                    (
                    
                      1
                      +
                      
                        C
                        T
                      
                    
                    )
                  
                  ⁢
                  n
                  ⁢
                  
                    
                  
                  ⁢
                  π
                
                +
                
                  
                    
                      
                        (
                        
                          
                            C
                            T
                          
                          ⁢
                          n
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        )
                      
                      2
                    
                    +
                    2
                    +
                    
                      4
                      ⁢
                      
                        C
                        T
                      
                    
                  
                
              
              
                1
                +
                
                  2
                  ⁢
                  
                    C
                    T
                  
                
              
            
            ,
          
        
        
          
            n
            ≥
            1.
          
        
      
    
  




Although equation (16) applies a Taylor series approximation, this is not considered to be a truncation or an approximation of the transfer function itself because equations (14) and (15) do not represent the transfer function or a portion thereof. Note that when CT approaches zero, equation (14) becomes cos x=0, and the solution xn approaches (n+1⁄2)π, where n=0, 1, 2, . . . . In order to capture this trend, equation (16) is revised as the following equation (17):





  
    x
    n
  
  =
  
    {
    
      
        
          
            
              
                
                  
                    1
                    2
                  
                  +
                  
                    C
                    T
                  
                  -
                  
                    
                      
                        C
                        T
                        2
                      
                      +
                      
                        
                          1
                          3
                        
                        ⁢
                        
                          C
                          T
                        
                      
                      +
                      
                        1
                        11.54
                      
                    
                  
                
                
                  
                    
                      1
                      3
                    
                    ⁢
                    
                      C
                      T
                    
                  
                  +
                  
                    1
                    12
                  
                
              
            
            ,
          
        
        
          
            n
            =
            0
          
        
      
      
        
          
            
              
                
                  
                    (
                    
                      1
                      +
                      
                        C
                        T
                      
                    
                    )
                  
                  ⁢
                  n
                  ⁢
                  
                    
                  
                  ⁢
                  π
                
                +
                
                  
                    
                      
                        (
                        
                          
                            C
                            T
                          
                          ⁢
                          n
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        )
                      
                      2
                    
                    +
                    
                      
                        π
                        2
                      
                      4
                    
                    +
                    
                      4
                      ⁢
                      
                        C
                        T
                      
                    
                  
                
              
              
                1
                +
                
                  2
                  ⁢
                  
                    C
                    T
                  
                
              
            
            ,
          
        
        
          
            n
            ≥
            1.
          
        
      
    
  




In FIG. 5, the analytic solution of equation (14) is compared with the exact solution for different values of CT. The accuracy of equation (17) is illustrated in FIG. 7 for different values of CT. As shown in FIG. 7, when CT increases from zero to infinity, xn decreases from (n+1⁄2)π to nπ.

The poles of the transfer function can be obtained from the following equation (18):

LCs2+RCs=θ2=−xn2, n=0, 1, 2, . . . .

Each xn corresponds to a pair of poles, given by the following equation (19):





  
    p
    
      n
      ,
      ±
    
  
  =
  
    
      
        
          -
          RC
        
        ±
        
          
            
              
                R
                2
              
              ⁢
              
                C
                2
              
            
            -
            
              4
              ⁢
              LC
              ⁢
              
                
              
              ⁢
              
                x
                n
                2
              
            
          
        
      
      
        2
        ⁢
        LC
      
    
    .
  




Although the solutions used for xn do not exactly correspond to the exact solutions for xn (see FIG. 7), the poles pn are still considered to be based on an untruncated version of the transfer function because no truncation or approximation of the transfer function itself was used in obtaining these pn values. Also, the pn values can be refined using methods such as Newton Raphson, as explained below to obtain exact poles. The residue of the corresponding poles kn,± can be solved as the following equation (20):




  
    
      
        
          
            k
            
              n
              ,
              ±
            
          
          =
          
            
              lim
              
                
                  s
                  →
                  
                    p
                    n
                  
                
                ,
                ±
              
            
            ⁢
            
              
                s
                -
                
                  p
                  
                    n
                    ,
                    ±
                  
                
              
              
                F
                ⁡
                
                  (
                  s
                  )
                
              
            
          
        
      
    
    
      
        
          =
          
            1
            
              
                F
                ′
              
              ⁡
              
                (
                
                  p
                  
                    n
                    ,
                    ±
                  
                
                )
              
            
          
        
      
    
    
      
        
          
            =
            
              
                
                  ±
                  2
                
                ⁢
                
                  x
                  n
                
              
              
                D
                ⁡
                
                  [
                  
                    
                      
                        (
                        
                          1
                          +
                          
                            C
                            T
                          
                        
                        )
                      
                      ⁢
                      sin
                      ⁢
                      
                        
                      
                      ⁢
                      
                        x
                        n
                      
                    
                    +
                    
                      
                        C
                        T
                      
                      ⁢
                      
                        x
                        n
                      
                      ⁢
                      cos
                      ⁢
                      
                        
                      
                      ⁢
                      
                        x
                        n
                      
                    
                  
                  ]
                
              
            
          
          ,
        
      
    
  




  
    where
    ⁢
    
      :
    
  




  
    D
    =
    
      
        
          
            
              R
              2
            
            ⁢
            
              C
              2
            
          
          -
          
            4
            ⁢
            LC
            ⁢
            
              
            
            ⁢
            
              x
              n
              2
            
          
        
      
      .
    
  



Step and ramp responses will now be developed. From the poles and corresponding residues, the transfer function can be represented as the following equation (21):




  
    
      H
      ⁡
      
        (
        s
        )
      
    
    =
    
      
        ∑
        i
      
      ⁢
      
        
          k
          i
        
        
          s
          -
          
            p
            i
          
        
      
    
  
  ,




where i is the index covering all of the poles. Consider a wire structure example as shown in FIG. 8. Wire structure 800 includes: orthogonal layers 802, 804; Ground 806; and signal line 808. The interconnect parameters per unit length are Rint=12.24 mΩ/μm, Lint=0.74 pH/μm, and Cint=0.266 fF/μm. These values can be extracted from FastHenry and FastCap with a signal frequency of 2 GHz. The amplitude of the transfer function obtained from equation (21) is compared with the exact transfer function for the RC case in FIG. 9A and RLC case with a zero Rd in FIG. 9B, respectively.

For the graphs of FIGS. 9A and 9B, the wire length is 5 mm and the load capacitance is CL=50 fF. In the graph of FIG. 9A, Rd=30Ω. In FIG. 9A, m is the number of poles considered in the model. In FIG. 9B, m is the number of pole pairs, since the poles in this case are in pairs. As shown in the FIGS. 9A and 9B, the analytic transfer function converges to the exact transfer function with increasing m. As compared with the RC case, more poles are required for the RLC case to obtain an accurate result.
From equation (21): (i) the normalized step response Vs(t)/Vdd is given by the following equation (22); (ii) ramp response Vr(t)/Vdd is given by equation (23); (iii) the V1 term used in these equations is given by equation (24):




  
    
      
        
          
            
              
                V
                s
              
              ⁡
              
                (
                t
                )
              
            
            
              V
              dd
            
          
          =
          
            
              u
              ⁡
              
                (
                t
                )
              
            
            ⁡
            
              [
              
                1
                +
                
                  
                    ∑
                    i
                  
                  ⁢
                  
                    (
                    
                      
                        
                          k
                          i
                        
                        
                          p
                          i
                        
                      
                      ⁢
                      
                        e
                        
                          
                            p
                            i
                          
                          ⁢
                          t
                        
                      
                    
                    )
                  
                
              
              ]
            
          
        
        ,
      
    
    
      
        (
        22
        )
      
    
  
  
    
      
        
          
            
              
                V
                r
              
              ⁡
              
                (
                t
                )
              
            
            
              V
              dd
            
          
          =
          
            
              
                V
                1
              
              ⁡
              
                (
                t
                )
              
            
            -
            
              
                V
                1
              
              ⁡
              
                (
                
                  t
                  -
                  
                    t
                    r
                  
                
                )
              
            
          
        
        ,
      
    
    
      
        (
        23
        )
      
    
  
  
    
      
        
          
            
              V
              1
            
            ⁡
            
              (
              t
              )
            
          
          =
          
            
              
                u
                ⁡
                
                  (
                  t
                  )
                
              
              
                t
                r
              
            
            ⁡
            
              [
              
                t
                +
                
                  m
                  1
                
                +
                
                  
                    ∑
                    i
                  
                  ⁢
                  
                    (
                    
                      
                        
                          k
                          i
                        
                        
                          p
                          i
                          2
                        
                      
                      ⁢
                      
                        e
                        
                          
                            p
                            i
                          
                          ⁢
                          t
                        
                      
                    
                    )
                  
                
              
              ]
            
          
        
        ,
      
    
    
      
        (
        24
        )
      
    
  




In equations (22) and (24), u(t) is the step function. In these equations, the moment information used is given by the following equations (25) and (26):




  
    
      
        
          
            -
            
              
                ∑
                i
              
              ⁢
              
                
                  k
                  i
                
                
                  p
                  i
                
              
            
          
          =
          
            
              m
              0
            
            =
            1
          
        
        ,
      
    
    
      
        (
        25
        )
      
    
  
  
    
      
        
          -
          
            
              ∑
              i
            
            ⁢
            
              
                k
                i
              
              
                p
                i
                2
              
            
          
        
        =
        
          
            m
            1
          
          .
        
      
    
    
      
        (
        26
        )
      
    
  




For an RC interconnect, the following equation (27) applies:

m1=−Rd(C+CL)−R(0.5C+CL),

and for an RLC interconnect with a zero driver resistance, the following equation (28) applies:

m1=−R(0.5C+CL).

The step and ramp responses obtained from equation (22) and equation (23) are compared with Spectre simulations in FIGS. 10A, 10B, 10C and 10D. In the Spectre simulation, the transmission line is modeled as a series of π-shaped RC or RLC segments. Each segment is 10 μm long. Good agreement between the analytic solution and Spectre simulations is observed. The accuracy of the ramp response is much higher than that of the step response since a ramp signal consists of fewer high frequency components. In FIGS. 10A to 10D, step and ramp response obtained analytically are compared with Spectre simulations as follows: (i) FIG. 10A shows step response, RC case; (ii) FIG. 10B shows ramp response, RC case; (iii) FIG. 10C shows step response, RLC case; and (iii) FIG. 10D shows ramp response, RLC case.
Now, a distributed RLC interconnect with non-zero driver resistance will be considered, and an interconnect simulation with general circuit parameters will be solved. The Newton-Raphson method will be used to determine the exact poles of this simulation. For an interconnect driven by a gate, there are primarily two kinds of approaches for timing analysis.
In the first approach, the driver and the interconnect are separated. The voltage waveform at the gate output is obtained through precharacterized delay and transition time information characterizing the gate. This waveform is applied at the input of the interconnect to obtain the far end response. With increasing inductive effects, more complicated driver output models are required to characterize the reflection behavior of the propagating signals, such as the two-ramp model described in K. Agarwal, D. Sylvester, and D. Blaauw, “An Effective Capacitance Based Driver Output Model for On-Chip RLC Interconnects,” Proceedings of the IEEE/ACM Design Automation Conference, pp. 376-381, June 2003 and the three-piece model in L. K. Vakati and J. Wang, “A New Multi-Ramp Driver Model with RLC Interconnect Load,” Proceedings of the IEEE International Symposium of Circuits and Systems, pp. V269-V271, May 2004. Recently, several current source models (CSM) have been developed where the nonlinear behavior of the gate is characterized, making the driver output response more accurate. For the first approach, the analytic solution proposed in connections with equations (13) to (20) can be applied directly by representing the driver output voltage response as a piecewise-linear waveform. As mentioned above, it should be kept in mind that these equations (13) to (20) do not truncate or approximate the transfer function itself, which means that this first approach method of determining the poles of an RLC interconnect with driver resistance does not truncate the transfer function and thereby improves accuracy.
In the second approach, the driver and interconnect are analyzed as a single system, where the Thevenin model is generally used, as shown in FIG. 3. In this approach, the interaction between the driver and the interconnect is modeled as a single system. For the second voltage-approach, the method proposed in connection with equations (13) to (20) needs to be improved to include the effect of the driver resistance.
With a system transform, the poles of a general RLC interconnect system will now be solved. In J. Chen, the circuit model as shown in FIG. 3 is mapped into an open-ended interconnect system by matching the moments. Similarly, the interconnect system with a driver resistance can also be mapped into a system without a driver resistance. This mapping may be considered as an approximation of the transfer function for the system, but it is not a truncation of the transfer function for the system. Consider a step signal at the input of the circuit shown in FIG. 3. The height of the initial step at the driver output is VddZ0/(Rd+Z0), where Z0=√{square root over (L/C)} is the characteristic impedance of a lossless line. As described in Y. I. Ismail, E. G. Friedman, and J. L. Neves, “Figures of Merit to Characterize the Importance of On-Chip Inductance,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 7, No. 4, pp. 442-449, December 1999, the attenuation coefficient of a transmission line saturates with increasing frequency to the asymptotic value R/(2Z0). Assume the total interconnect resistance of the new system (without a driver resistance) is R′ and the load capacitance is C′L. The amplitude of the initial propagating wave can be matched by the following equation (29):




  
    
      
        V
        dd
      
      ⁢
      
        
          Z
          0
        
        
          
            R
            d
          
          +
          
            Z
            0
          
        
      
      ⁢
      
        e
        
          -
          
            R
            
              2
              ⁢
              
                Z
                0
              
            
          
        
      
    
    =
    
      
        V
        dd
      
      ⁢
      
        e
        
          -
          
            
              R
              ′
            
            
              2
              ⁢
              
                Z
                0
              
            
          
        
      
    
  
  ,




R′ can be obtained using the following equation (30):





  
    R
    ′
  
  =
  
    R
    +
    
      2
      ⁢
      
        Z
        0
      
      ⁢
      
        
          log
          ⁡
          
            (
            
              1
              +
              
                
                  R
                  d
                
                
                  Z
                  0
                
              
            
            )
          
        
        .
      
    
  




The first moments of the two systems can be matched using the following equation (31):

−m1=Rd(CL+C)+R(0.5C+CL)=R′(0.5C+C′L)

C′L can be obtained using the following equation (32):





  
    C
    L
    ′
  
  =
  
    
      
        -
        
          m
          1
        
      
      
        R
        ′
      
    
    -
    
      0.5
      ⁢
      
        
      
      ⁢
      
        C
        .
      
    
  




After this conversion, the method proposed above in connection with equations (13) to (20) can be applied. As mentioned above, it should be kept in mind that these equations (13) to (20) do not truncate or approximate the transfer function itself. Although equations (13) to (20) are applied to an approximated system transfer function in this second approach method, as explained above, a truncated transfer function is never resorted to even in this second approach method. This means that this second approach method of determining the poles of an RLC interconnect with driver resistance does not truncate the transfer function and thereby improves accuracy.
To explain the second approach method in other words, an original system with driver resistance undergoes a system transform to yield a roughly equivalent approximated system having no driver resistance. The poles of this approximated system are then solved with equations (13) to (20). These poles, as determined by equations (13) to (20) will only be approximate poles for the original system with driver resistance, but the Newton Raphson method can be applied, if needed or desired, to refine these approximate poles into exact poles.
In FIGS. 11A and 11B, the waveform obtained from the proposed model is compared with Spectre simulations and the four-pole model described in Banerjee. FIGS. 11A and 11B compare transient response of a transmission line as obtained with: (i) the model described herein; (ii) four-pole model; and (iii) Spectre simulations. For purposes of this comparison tr=50 ps; CL=50 fF; Rd=20Ω (FIG. 11A); and Rd=300Ω (FIG. 11B). As mentioned above, this four-pole model of Banerjee is obtained by truncating the denominator of the transfer function to the fourth order; however, no closed-form solution is available for solving the four poles. Note that although both the model described herein and the four-pole model are based on an approximation of the four poles of the system, the model described herein is much more accurate than the four-pole model when inductive effects are important (a system with a small driver resistance), as shown in FIG. 11A. When the system is dominated by the driver resistance, the model described herein is less accurate, particularly at the beginning period of the waveform, as shown in FIG. 11B.
The accuracy of the poles are further improved with the Newton-Raphson method as will now be described. The location of the low order poles obtained analytically is compared with the location of the exact poles in FIG. 12. The graph of FIG. 12 shows mapping between the approximated poles and the exact poles, where Rd=100Ω. From FIG. 12, note that there is a one-to-one mapping between the approximated poles and the exact poles. The real pole without an arrow in FIG. 12 should be mapped to a real pole which is out of the range of the graph of FIG. 12. From these approximated poles, the exact poles can be obtained through the Newton-Raphson method, permitting the accuracy of the model to be significantly improved. In general, the number of iterations required for convergence is less than five.
Special attention needs to be paid to those real poles when applying the Newton-Raphson method. For example, the Newton-Raphson process starting from the approximated pole −3.892×1010 (the left real pole as shown in FIG. 12) incorrectly converges to the exact pole −6.396×109 rather than converges to the exact pole outside the range of the figure.
In order to distinguish this case from the double real pole case, the following condition needs to be evaluated. If p is a double real pole of the system, p satisfies the following equation (33):




  
    
      lim
      
        s
        →
        p
      
    
    ⁢
    
      
        
          F
          ⁡
          
            (
            s
            )
          
        
        
          s
          -
          p
        
      
      ⁢
      
        
          F
          ′
        
        ⁡
        
          (
          p
          )
        
      
    
  
  =
  0.




For systems with multiple real poles, the system is dominated by the real pole with the smallest magnitude and the effect of the other real poles can be ignored, unless these poles are close to the dominant pole. The distance between the other real poles and the dominant real pole is related to the value of F′(pd), where pd is the dominant pole. If there is another pole px which is close to pd, F′(pd) should be small. When px approaches pd, the value of F′(pd) approaches zero. In the limit, px=pd, pd is a double pole, and F′(pd)=0, as expressed in equation (33).

Pseudo-code for generating the exact poles of a single interconnect system is shown in FIG. 13. In FIG. 13, the function Newton_Raphson( ) is the Newton-Raphson converging process starting with the input argument. In FIG. 13, the variable over_damped is used to indicate whether the system is overdamped or not. For overdamped systems, the higher order real poles (with n>0) are ignored. A threshold value Fth is set for F′(p), which is used to indicate the distance between other high order real poles and the dominant real pole.
After the dominant real pole (if the system has real poles, the dominant real pole is always p0,+) is determined, F′(p0,+) is evaluated. F(s) can be represented by the poles as set forth in the following equation (34):




  
    F
    ⁡
    
      (
      s
      )
    
  
  =
  
    
      ∏
      
        n
        =
        0
      
      ∞
    
    ⁢
    
      
        (
        
          1
          -
          
            s
            
              p
              
                n
                ,
                +
              
            
          
        
        )
      
      ⁢
      
        
          (
          
            1
            -
            
              s
              
                p
                
                  n
                  ,
                  -
                
              
            
          
          )
        
        .
      
    
  




From equation (34), equation (35) is obtained as follows:





  
    
      F
      ′
    
    ⁡
    
      (
      
        p
        
          0
          ,
          +
        
      
      )
    
  
  =
  
    
      
        
          -
          1
        
        
          p
          
            0
            ,
            +
          
        
      
      ⁢
      
        (
        
          1
          -
          
            
              p
              
                0
                ,
                +
              
            
            
              p
              
                0
                ,
                -
              
            
          
        
        )
      
      ⁢
      
        
          ∏
          
            n
            =
            1
          
          ∞
        
        ⁢
        
          
            (
            
              1
              -
              
                
                  p
                  
                    0
                    ,
                    +
                  
                
                
                  p
                  
                    n
                    ,
                    +
                  
                
              
            
            )
          
          ⁢
          
            (
            
              1
              -
              
                
                  p
                  
                    0
                    ,
                    +
                  
                
                
                  p
                  
                    n
                    ,
                    -
                  
                
              
            
            )
          
        
      
    
    <
    
      
        
          -
          1
        
        
          p
          
            0
            ,
            +
          
        
      
      ⁢
      
        
          (
          
            1
            -
            
              
                p
                
                  0
                  ,
                  +
                
              
              
                p
                
                  0
                  ,
                  -
                
              
            
          
          )
        
        .
      
    
  




If |p0,−|>2|p0,+|, F′(p0,+)<−0.5/p0,+. With some overhead, Fth is determined as −0.3/p0,+. If F′(p0,+)<Fth, which means pole p0,− is close to p0,+, a Newton_Raphson process is launched from point 2p0,+ to determine p0,−. Otherwise, the Newton_Raphson process is launched from point 5p0,+ to determine p0,−. If the process does not converge or incorrectly converges to p0,+, which means the true value of |p0,−| is greater than 5|p0,+|, the effect of p0,− can be ignored. For the double pole case, the process of solving the residue requires the second order derivative of F(s), which is complicated. The code produces an output message if a double pole occurs. In this case, a small change in the circuit parameters can avoid a double pole, while the effect on the output signal waveform caused by this parameter change cannot be distinguished. After the exact poles are extracted, a step or ramp response is constructed from equation (22) or equation (23). In order to eliminate the artificial discontinuity of the waveform at the end of the input rising edge, the first moment m1 in equation (24) is calculated from the truncated summation, as shown in the left side of equation (26), rather than the exact value of 0.5R′C+R′C′L.

For the same circuit examples used in FIGS. 11A and 11B, the waveform obtained from the improved method is re-plotted in FIGS. 14A and 14B. In FIGS. 14A and 14B, transient response of transmission line obtained with the improved analytic method as compared with Spectre simulations, where m=2; Rd=20Ω (FIG. 14A); and Rd=300Ω (FIG. 14B). From FIGS. 14A and 14B, the difference between the analytic waveforms and Spectre simulations is difficult to distinguish except for the period of the initial time-of-flight.
The accuracy and efficiency of the simulation methods of the present invention will now be discussed. The 50% delay, 10%-to-90% rise time, and the normalized overshoot obtained from the proposed model are compared in FIGS. 15A and 15B with Spectre simulations for different input rise times (the input rise time is determined from 0 to Vdd). FIGS. 15A and 15B compare the 50% delay, 10%-to-90% output rise time, and the normalized overshoot obtained from the methods of the present invention and corresponding Spectre simulations, where Rd=20Ω, CL=50 fF, and 1=5 mm. FIG. 15A shows delay and rise time. FIG. 15B shows overshoot.
Since the signal delay is generally determined by the low frequency components, two pairs of poles provide a sufficiently accurate delay estimation. The average error is 1% for different input rise times. For the output rise time and overshoot, the error is larger for smaller input rise times. The error decreases with increasing input rise time, since the output rise time and overshoot are closely related to the high frequency components (a signal with a shorter rise time consists of additional high frequency components). The average error with two pairs of poles is 9.5% for the output rise time and 5.5% for the overshoot. When the number of pole pairs increases to ten, these two average errors decrease to 2.0% and 1.9%, respectively.
The computational complexity of the proposed method is approximately proportional to the number of pole pairs. These experiments have been performed on a SunBlade1500 workstation. The time required for Spectre to perform a 700 ps transient simulation (250 time steps) is 1.8 seconds. The simulation according to the present invention was implemented with Matlab. The comparable run time is 3.1 ms for m=2 and 10.9 ms for m=10, thereby demonstrating the computational efficiency of the present invention. To achieve an accuracy similar to the proposed model (m=2), more than 12 poles are required in the traditional moment matching method. Since there are no closed-form solutions for solving the poles from the moments, the computational complexity of the moment matching method is higher as compared with the proposed method. Specifically, the run time for the moment matching method with 12 poles is 13.5 ms as compared to 3.1 ms for the method methods of the present invention where m=2. Furthermore, the moment matching method suffers numerical stability problems with high order approximations.
The accuracy of the methods of the present invention are also verified for different interconnect lengths and illustrated in FIGS. 16A and 16B. FIGS. 16A and 16B compare the 50% delay and 10%-to-90% output rise time obtained from the methods of the present invention to corresponding Spectre simulations, where tr=50 ps. FIG. 16A shows 50% delay. FIG. 16B shows 10%-to-90% output rise time.
Frequency dependent effects will now be discussed. Both interconnect inductance and resistance are a function of frequency. This frequency dependent interconnect impedance affects the signal waveform, particularly for those signals containing a greater number of high frequency components. From equation (30), the contribution of the driver resistance to the effective interconnect resistance is Rd eff=2Z0 log(1+Rd/Z0), which is frequency independent (the frequency dependence due to Z0 is ignored, and the Z0 used here is determined at DC). The effective load capacitance is also determined at DC, as shown in equation (32). Considering the effect of the driver resistance and the frequency dependence of R and L of the interconnect, the effective propagation coefficient θ is given by equation (36):




  
    
      
        θ
        =
        
          
            
              
                [
                
                  
                    R
                    d_eff
                  
                  +
                  
                    R
                    ⁡
                    
                      (
                      s
                      )
                    
                  
                  +
                  
                    
                      L
                      ⁡
                      
                        (
                        s
                        )
                      
                    
                    ⁢
                    s
                  
                
                ]
              
              ⁢
              C
              ⁢
              
                
              
              ⁢
              s
            
          
          .
        
      
    
    
      
        (
        36
        )
      
    
  




For different functional forms of R(s) and L(s), the poles of the transfer function of an interconnect can be obtained by solving equation (36). Closed-form solutions may also be available depending upon the expressions of R(s) and L(s).

The frequency dependent impedance can be modeled by ladder structures of frequency-independent elements. These ladder structures are particularly suitable to capture skin effects. A two stage ladder structure is adopted for simplicity, in the exemplary embodiment of shown in FIG. 17 which shows a segment of interconnect with length Δl. Since the frequency dependent effect is naturally more significant at high frequencies, a wider interconnect is adopted here as an example so that additional high frequency components can propagate across the interconnect, distinguishing the frequency dependent effects. The signal wire width is 10 μm, the space between the signal line and ground is 5 μm, and the remaining geometric parameters are the same as depicted in FIG. 8. The parameters in the ladder structure are calculated by matching the DC and high frequency resistance and inductance of the ladder structure with the extracted values. Since the resistance of the interconnect does not saturate at high frequencies, a value of 40 is assumed as the high frequency resistance in this example, resulting in the following parameters: R0=40Ω, R1=28.1Ω, L0=1.9 nH, and L1=1.12 nH. The DC impedance is Rdc=16.5, Ldc=2.287 nH, and C=4.18 pF.
The resistance and inductance of the ladder approximation are compared with the extracted values in FIGS. 18A and 18B. FIGS. 18A and B show frequency dependent impedance of an interconnect with a length of 5 mm. FIG. 18A shows resistance, and FIG. 18B shows inductance. With this ladder approximation, the expression used to solve the poles of the system are given by the following equation (37):




  
    
      
        
          
            [
            
              
                R
                d_eff
              
              +
              
                
                  L
                  0
                
                ⁢
                s
              
              +
              
                
                  
                    R
                    0
                  
                  ⁡
                  
                    (
                    
                      
                        R
                        1
                      
                      +
                      
                        
                          L
                          1
                        
                        ⁢
                        s
                      
                    
                    )
                  
                
                
                  
                    R
                    0
                  
                  +
                  
                    R
                    1
                  
                  +
                  
                    
                      L
                      1
                    
                    ⁢
                    s
                  
                
              
            
            ]
          
          ⁢
          C
          ⁢
          
            
          
          ⁢
          s
        
        =
        
          
            θ
            2
          
          =
          
            -
            
              
                x
                n
                2
              
              .
            
          
        
      
    
    
      
        (
        37
        )
      
    
  




The poles can be analytically solved by the following equations (38) to (44):





  
    
      p
      
        n
        ,
        ±
      
    
    =
    
      
        -
        
          
            a
            2
          
          3
        
      
      -
      
        
          X
          2
        
        ±
        
          
            
              3
            
            2
          
          ⁢
          i
          ⁢
          
            
              
                X
                2
              
              +
              
                4
                ⁢
                Q
              
            
          
        
      
    
  
  ,
  
    

  
  ⁢
  
    Q
    =
    
      
        
          3
          ⁢
          
            a
            1
          
        
        -
        
          a
          2
          2
        
      
      9
    
  
  ,
  
    

  
  ⁢
  
    P
    =
    
      
        
          9
          ⁢
          
            a
            1
          
          ⁢
          
            a
            2
          
        
        -
        
          27
          ⁢
          
            a
            0
          
        
        -
        
          2
          ⁢
          
            a
            2
            3
          
        
      
      54
    
  
  ,
  
    

  
  ⁢
  
    X
    =
    
      
        
          P
          +
          
            
              
                Q
                3
              
              +
              
                P
                2
              
            
          
        
        3
      
      +
      
        
          P
          -
          
            
              
                Q
                3
              
              +
              
                P
                2
              
            
          
        
        3
      
    
  
  ,
  
    

  
  ⁢
  
    
      a
      2
    
    =
    
      
        
          
            L
            0
          
          ⁢
          
            R
            0
          
        
        +
        
          
            L
            0
          
          ⁢
          
            R
            1
          
        
        +
        
          
            R
            0
          
          ⁢
          
            L
            1
          
        
        +
        
          
            L
            1
          
          ⁢
          
            R
            d_eff
          
        
      
      
        
          L
          0
        
        ⁢
        
          L
          1
        
      
    
  
  ,
  
    

  
  ⁢
  
    
      a
      1
    
    =
    
      
        
          
            R
            0
          
          ⁢
          
            R
            1
          
          ⁢
          C
        
        +
        
          
            (
            
              
                R
                0
              
              +
              
                R
                1
              
            
            )
          
          ⁢
          
            R
            d_eff
          
          ⁢
          C
        
        +
        
          
            x
            n
            2
          
          ⁢
          
            L
            1
          
        
      
      
        
          L
          0
        
        ⁢
        
          L
          1
        
        ⁢
        C
      
    
  
  ,
  
    

  
  ⁢
  
    
      a
      0
    
    =
    
      
        
          
            (
            
              
                R
                0
              
              +
              
                R
                1
              
            
            )
          
          ⁢
          
            x
            n
            2
          
        
        
          
            L
            0
          
          ⁢
          
            L
            1
          
          ⁢
          C
        
      
      .
    
  




From equation (38), the Newton-Raphson method can be applied to solve the exact poles as discussed above in connection with FIG. 13. In FIG. 19, the output signal waveforms are compared for the DC impedance case and the frequency dependent (FD) impedance case. FIG. 19 compares the output signal waveforms with and without the frequency dependent effect, where Rd=10Ω, CL=50 pF, and tr=50 ps. As shown in FIG. 19, by considering the FD effect, additional high frequency components are suppressed, making the waveform smoother since the high frequency components experience much greater attenuation due to the increasing interconnect resistance, as shown in FIG. 20. FIG. 20 compares transfer functions with and without the frequency dependent effect, where Rd=10Ω and CL=50 pF. For the high frequency related waveform properties, such as the rise time and overshoot, the FD effect should be considered. For low frequency related waveform properties, such as delay, the FD effect can be neglected. The run time of the Spectre simulation (700 ps, 225 time steps) is 2.45 s and the run time for the corresponding analytic method according to the present invention (with m=2) is 3.8 ms. This represents three orders of magnitude improvement in computational time.
By extracting the exact poles, an efficient method for determining the transient output response of a distributed RLC interconnect can be achieved according to the present invention. Also, far end response characteristics can be more accurately and/or precisely determined by using the exact poles. Two pairs of poles can provide an accurate delay estimate exhibiting an average error of 1% as compared with Spectre simulations. For high frequency related waveform properties, such as the rise time and overshoot, an average error of less than 2% can be obtained with ten pairs of poles. The computational complexity of the proposed method is proportional to the number of pole pairs. By using a ladder structure, frequency dependent effects can also be included in the methods of the present invention. Excellent agreement is observed between the proposed model and Spectre simulations.
Definitions
The following definitions are provided to facilitate claim interpretation and claim construction:
Present invention: means at least some embodiments of the present invention; references to various feature(s) of the “present invention” throughout this document do not mean that all claimed embodiments or methods include the referenced feature(s).
First, second, third, etc. (“ordinals”): Unless otherwise noted, ordinals only serve to distinguish or identify (e.g., various members of a group); the mere use of ordinals implies neither a consecutive numerical limit nor a serial limitation.
Far End Response Characteristic(s): far end response characteristic(s) include, but are not necessarily limited to, frequency dependent effects, step response, ramp response, delay, 50% delay, rise time, 10% to 90% rise time, overshoot and normalized overshoot.
RLC Interconnect: an RLC interconnect or an RC interconnect.
Determine/Determining: determining precisely and/or estimating.
Simulating/simulation: this refers to mathematical modeling of a conductor, regardless of whether the simulation involves breaking the conductor into segments (for example, Spectre simulation) or whether the simulation analytically treats the entire conductor, or interconnect, as a whole.
To the extent that the definitions provided above are consistent with ordinary, plain, and accustomed meanings (as generally shown by documents such as dictionaries and/or technical lexicons), the above definitions shall be considered controlling and supplemental in nature. To the extent that the definitions provided above are inconsistent with ordinary, plain, and accustomed meanings (as generally shown by documents such as dictionaries and/or technical lexicons), the above definitions shall control. If the definitions provided above are broader than the ordinary, plain, and accustomed meanings in some aspect, then the above definitions shall be considered to broaden the claim accordingly.
To the extent that a patentee may act as its own lexicographer under applicable law, it is hereby further directed that all words appearing in the claims section, except for the above-defined words, shall take on their ordinary, plain, and accustomed meanings (as generally shown by documents such as dictionaries and/or technical lexicons), and shall not be considered to be specially defined in this specification. Notwithstanding this limitation on the inference of “special definitions,” the specification may be used to evidence the appropriate ordinary, plain and accustomed meanings (as generally shown by dictionaries and/or technical lexicons), in the situation where a word or term used in the claims has more than one alternative ordinary, plain and accustomed meaning and the specification is actually helpful in choosing between the alternatives.
Unless otherwise explicitly provided in the claim language, steps in method steps or process claims need only be performed in the same time order as the order the steps are recited in the claim only to the extent that impossibility or extreme feasibility problems dictate that the recited step order (or portion of the recited step order) be used. This broad interpretation with respect to step order is to be used regardless of whether the alternative time ordering(s) of the claimed steps is particularly mentioned or discussed in this document.

## Claims

1. A computer system comprising:
a first computer portion structured and/or programmed to receive input characteristics of a transmission line to be simulated as a distributed resistance-capacitance (RC) interconnect, with the input characteristics being sufficient to define a transfer function for the simulated RC interconnect; and
a second computer portion structured and/or programmed to determine at least one pole of the transfer function such that the transfer function is not truncated in the determination of the at least one pole;
wherein:
the transmission line has negligible inductance and is simulated as an RC interconnect;
the input characteristics comprise interconnect resistance (R), interconnect capacitance (C), driver resistance (Rd), load capacitance (CL) and input signal waveform;
the transfer function is given by the following equation:
H(s)=1/(1+Aθ2)cos h(θ)+Bθ sin h(θ) where A=RTCT, B=RT+CT, RT=Rd/R, CT=CL/C, θ=√{square root over (RCs)}=jxn where j is the imaginary unit and xn is the coefficient of the imaginary number jxn corresponding to the nth pole in the series of poles n=0,1,2, . . . , s=frequency variable of the transfer function, and pn=the nth pole in the series of poles n=0,1,2, . . . ;
the second computer portion determines the at least one pole by transforming the denominator of the transfer function into terms of a variable x, finding at least one value for x such that the transformed denominator is equal to zero and using the at least one value for x to determine the at least one pole of the transfer function; and
the at least one pole of the transfer function is solved in terms of variable x as:





  
    
      p
      n
    
    =
    
      
        -
        
          x
          n
          2
        
      
      
        R
        ⁢
        
          
        
        ⁢
        C
      
    
  
  ,
  
    n
    =
    0
  
  ,
  1
  ,
  2
  ,
  
    ...
    ⁢
    
      
    
    .

2. A computer system comprising:
a first computer portion structured and/or programmed to receive input characteristics of a transmission line to be simulated as a distributed resistance-capacitance-inductance (RLC) interconnect, with the input characteristics being sufficient to define a transfer function for the simulated RLC interconnect; and
a second computer portion structured and/or programmed to determine at least one pole of the transfer function such that the transfer function is not truncated in the determination of the at least one pole;
wherein:
the input characteristics comprise interconnect inductance (L), interconnect resistance (R), interconnect capacitance (C), driver resistance (Rd), load capacitance (CL) and input signal waveform;
the second computer portion simulates the RLC interconnect by separating the driver and the interconnect and by representing the input signal waveform as a piecewise-linear waveform;
the transfer function of the separated interconnect is given by the following equation:
H(s)=1/cos h(θ)+CTθ sin h(θ) where CT=CL/C, θ=√{square root over (RCs)}=jxn where j is the imaginary unit and xn is the coefficient of the imaginary number jxn corresponding to the nth pole in the series of poles n=0,1,2, . . . , s=frequency variable of the transfer function, and pn=the nth pole in the series of poles n=0,1,2, . . . ; and
the second computer portion determines the at least one pole by transforming the denominator of the transfer function into terms of a variable x, finding at least one value for x such that the transformed denominator is equal to zero and using the at least one value for x to determine the at least one pole of the transfer function.

3. The computer system of claim 2 wherein the second computer portion applies at least a portion of a Taylor series expansion to at least one trigonometric function in the transformed denominator in order to solve for the at least one value of x.

4. The computer system of claim 2 wherein the at least one pair of poles of the transfer function is solved in terms of variable x as:




  
    
      p
      
        n
        ,
        ±
      
    
    =
    
      
        
          -
          RC
        
        ±
        
          
            
              
                R
                2
              
              ⁢
              
                C
                2
              
            
            -
            
              4
              ⁢
              LC
              ⁢
              
                
              
              ⁢
              
                x
                n
                2
              
            
          
        
      
      
        2
        ⁢
        LC
      
    
  
  ,
  
    n
    =
    0
  
  ,
  1
  ,
  2
  ,
  
    ...
    ⁢
    
      
    
    .

5. A computer system comprising:
a first computer portion structured and/or programmed to receive input characteristics of a transmission line to be simulated as a distributed resistance-inductance-capacitance (RLC) distributed interconnect, with the input characteristics being sufficient to define a transfer function for the simulated RLC interconnect; and
a second computer portion structured and/or programmed to determine at least one pole of the transfer function such that the transfer function is not truncated in the determination of the at least one pole;
wherein:
the input characteristics comprise interconnect inductance (L), interconnect resistance (R), interconnect capacitance (C), driver resistance (Rd), load capacitance (CL) and input signal waveform;
the second computer portion simulates the RLC interconnect by mapping the RLC interconnect with driver resistance into a system without driver resistance and determines corresponding values for interconnect resistance (R′) and load capacitance (CL');
the transfer function of the mapped interconnect is given by the following equation:
H(s)=1/cos h(θ)+CTθ sin h(θ) where CT=CL′/C, θ=√{square root over (R′Cs)}=jxn where j is the imaginary unit and xn is the coefficient of the imaginary number jxn corresponding to the nth pole in the series of poles n=0,1,2, . . . , s=frequency variable of the transfer function, and pn=the nth pole in the series of poles n=0,1,2, . . . ; and
the second computer portion determines the at least one pole by transforming the denominator of the transfer function into terms of a variable x, finding at least one value for x such that the transformed denominator is equal to zero and using the at least one value for x to determine the at least one pole of the transfer function.

6. The computer system of claim 5 wherein the second computer portion applies at least a portion of a Taylor series expansion to at least one trigonometric function in the transformed denominator in order to solve for the at least one value of x.

7. The computer system of claim 5 wherein the at least one pair of poles of the transfer function is solved in terms of variable x as:




  
    
      p
      
        n
        ,
        ±
      
    
    =
    
      
        
          -
          RC
        
        ±
        
          
            
              
                R
                2
              
              ⁢
              
                C
                2
              
            
            -
            
              4
              ⁢
              LC
              ⁢
              
                
              
              ⁢
              
                x
                n
                2
              
            
          
        
      
      
        2
        ⁢
        LC
      
    
  
  ,
  
    n
    =
    0
  
  ,
  1
  ,
  2
  ,
  
    ...
    ⁢
    
      
    
    .

8. A computer system comprising:
a first computer portion structured and/or programmed to receive input characteristics of a transmission line to be simulated as a distributed resistance-inductance-capacitance (RLC) interconnect, with the input characteristics being sufficient to define a transfer function for the simulated RLC interconnect; and
a second computer portion structured and/or programmed to determine at least one pole of the transfer function by transforming the denominator of the transfer function into terms of a variable x, finding at least one value for x such that the transformed denominator is equal to zero and using the at least one value for x to determine the at least one pole of the transfer function;
wherein:
the input characteristics comprise interconnect inductance (L), interconnect resistance (R), interconnect capacitance (C), driver resistance (Rd), load capacitance (CL) and input signal waveform;
the second computer portion simulates the RLC interconnect by mapping the RLC interconnect with driver resistance into a system without driver resistance and determines corresponding values for interconnect resistance (R′) and load capacitance (CL′); and
the transfer function of the mapped interconnect is given by the following equation:
H(s)=1/cos h(θ)+CTθ sin h(θ) where CT=CL′/C, θ=√{square root over (R′Cs)}=jxn where j is the imaginary unit and xn is the coefficient of the imaginary number jxn corresponding to the nth pole in the series of poles n=0,1,2, . . . , s=frequency variable of the transfer function, and pn=the nth pole in the series of poles n=0,1,2, . . . .