Abstract:
A method estimates the signal delay in a VLSI circuit and accurately estimates the delay and conversion time of a transmission signal in the circuit in order to prevent a designer of the VLSI circuit from erroneously judging the logic made by the designed circuit.

Description:
BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   This invention relates to a method of estimating the signal delay in a VLSI circuit and particularly to a method of feasibly fast calculating the delay and conversion time of a transmission signal in the VLSI circuit in order to prevent the erroneous logic judgment of a circuit design. 
   2. Description of Related Art 
   In a conventional technology, a method estimates the signal delay in an interconnection circuit by fixing the structure, number of components, and capacitance function of an interconnection network, but the technology could not be widely used in structures of different interconnection networks. 
   In a conventional technology that broke through the limit to the structure of a fixed interconnection network, a method feasibly estimates the transmission signal delay caused by components in two circuits, but it could not be used for calculating the total signal delay from input to output in a VLSI circuit. 
   Consequently, because of the technical defects described above and through wholehearted experience and research, the present invention was developed to effectively improve the defects described above. 
   SUMMARY OF THE INVENTION 
   This invention relates to a method of estimating the signal delay in a VLSI circuit and accurately estimating the delay and conversion time of a transmission signal in the circuit in order to prevent a designer of the VLSI circuit from erroneously judging the logic made by the designed circuit. 
   In a process of the algorithm of the clock signal delay in this invention, at first, calculation of the parasitic parameters, signal conversion time, logic cell library, and circuit architecture in an inputted file-based interconnection circuit is made for the voltage moment at each node and the current moment in a branch line of the specified interconnection circuit. Then, what is obtained is applied to a reduced model for forming a die original circuit, in which the reduced model retains passivity and stability and in which the operation conditions of its input and output nodes are identical to those of the original system. Finally, a signal time domain is simulated, and, then, the equivalent capacitance is calculated so that drive logic gate delay time, interconnection circuit delay time, and output signal conversion time are analyzed. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a flow chart of this invention; 
       FIG. 2  is a flow chart of a technique of recursion moment operation of this invention; 
       FIG. 3  is a flow chart of a technique of model reduction; 
       FIG. 4  is a flow chart of time domain simulation; 
       FIG. 5  is a flow chart of calculation of equivalent capacitance; 
       FIG. 6   a  is a view of an original RC circuit; 
       FIG. 6   b  is a view of a structured equivalent model; 
       FIG. 6   c  is a view of an equivalent circuit; and 
       FIG. 7  is a view of the validity of an algorithm in this invention. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   Now, the present invention will be described more specifically with reference to the following embodiments. It is to be noted that the following descriptions of the preferred embodiments of this invention are presented herein for purpose of illustration and description only; it is not intended to be exhaustive or to be limited to the precise form disclosed. 
   A method of estimating the signal delay in a VLSI circuit is provided in this invention, as shown in  FIG. 1 , in which at the step of Start, a file interconnect circuit parasitic parameter, a signal conversion time, a logic cell library, and a circuit structure are inputted to a file data read system. 
   For each network interconnection system, the structure of a specific target interconnection circuit is analyzed, and the system moment of the specified system is calculated. The calculation of moment is made for the voltage moment of each node and for the current moment of a branch line, which may be applied to the calculation of equivalent capacitance and the construction of a projection matrix. In the recursion moment operation, the circuit moment of each node in the circuit may be obtained in linear time, and, thus, the projection matrix is further constructed. 
   In the process of construction of the reduced model, it is determined whether the amount of nodes in the specified system is higher than a default order. When the specified order exceeds the default order, the system is significantly complicated. Due to the special structure of a tree network, this invention may be applied to a sparse matrix to store the circuit parameter of the original system, which significantly reduces the resource of operation. Sparse matrix multiplication is applied to obtain a final reduced model for analysis of the signal time domain simulation. The reduced model stays passive and stable, and the operation condition of its input and output node is identical to that of the original system. 
   Contrarily, when the order of the target interconnect circuit is less than a default order, a Modified Nodal Analysis matrix system is constructed directly corresponding to a Modified Nodal Analysis matrix system that represents its current and voltage behavior pattern for analysis of the time domain simulation. 
   At the step of analysis of the time domain simulation, the equivalent capacitance loaded by a drive element is first calculated, and a table look-up is applied to get an output signal of an input interconnect circuit structure. 
   By analysis of the time domain simulation, the time domain simulation is made for the Modified Nodal Analysis matrix system and is then off analyzed for drive logic gate delay time, interconnection circuit delay time, and output signal conversion time. 
   Determination is made whether a network interconnection system has not yet been processed. If a system has not yet been processed, the step of determining the interconnect circuit structure returns for analysis of a next interconnect circuit signal. If all of the interconnect circuits has been off processed, an end of estimation of the system delay of this invention takes place. 
   The algorithm applied to this invention comprises the techniques of moment calculation, model reduction, recursion moment operation, time domain analysis, and equivalent capacitance operation, which will be described in detail. 
   Moment Calculation 
     FIG. 2  illustrates a flow of calculation of voltage moment of each node and current moment of each branch line. At the step of Start, calculation must be done for the voltage moment and the current moment. For a RC interconnect circuit, a tree connection structure may be formed, in which each branch is resistance and each node is ground capacitance, both of which are calculated for the (voltage and current) moment by the recursion algorithm. 
   In this invention, calculation is done from the default order for the voltage moment of each node and for O(kn), the complexity of operation, in which k is the order of the reduced system and n is the number of the node, making the moment calculation (flow) end. 
   Recursion Moment Operation 
   In the technique of model reduction, the Arnoldi iteration algorithm and PVL iteration algorithm are conventionally used to construct the projection matrix. Matrix multiplication is included in the iteration process, so the complexity of operation of a large system increases. In  FIG. 2  according to this invention, the recursion algorithm is applied for moment calculation in order to speed up the execution of a program. The formula of the current and voltage moment between the nodes that is given for moment by the recursion algorithm may be expressed as: 
   
     
       
         
           
             
               
                 
                   I 
                   
                     j 
                     , 
                     k 
                   
                 
                 = 
                 
                   
                     
                       I 
                       
                         C 
                         
                           j 
                           , 
                           k 
                         
                       
                     
                     - 
                     
                       
                         ∑ 
                         
                           
                             n 
                             x 
                             i 
                           
                           ∈ 
                           
                             S 
                             ⁡ 
                             
                               ( 
                               
                                 n 
                                 j 
                                 i 
                               
                               ) 
                             
                           
                         
                       
                       ⁢ 
                       
                         
                           I 
                           
                             x 
                             , 
                             k 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         and 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           V 
                           
                             j 
                             , 
                             k 
                           
                         
                       
                     
                   
                   = 
                   
                     
                       V 
                       
                         
                           F 
                           ⁡ 
                           
                             ( 
                             j 
                             ) 
                           
                         
                         , 
                         k 
                       
                     
                     - 
                     
                       
                         R 
                         j 
                       
                       ⁢ 
                       
                         I 
                         
                           j 
                           , 
                           k 
                         
                       
                     
                   
                 
               
             
             
               
                 ( 
                 1 
                 ) 
               
             
           
         
       
     
   
   where I j,k  indicates the moment of current j in order k, I C     j,k    is the capacitive current related to node j, 
             ∑       n   x   i     ∈     S   ⁡     (     n   j   i     )           ⁢     I     x   ,   k             
is the total of the moment of current flowing out of node j, V j,k  is the moment at node j in order k, and V F(j),k  is the moment of voltage at a father node of node j.
 
Model Reduction
 
   The model order of the interconnect VLSI circuit is quite huge. In order to reduce the complexity of system operation, the technique of model reduction is applied for a next step of simulation and analysis, in which the flow of model reduction is shown in  FIG. 3 . 
   First, regarding the analysis of interconnect circuit, Kirchhoff&#39;s current law is applied to give the following equation; 
   
     
       
         
           
             
               
                 
                   
                     
                       ( 
                       
                         
                           s 
                           ⁢ 
                           
                             
                               
                                 [ 
                                 
                                   
                                     
                                       
                                         C 
                                         1 
                                       
                                     
                                     
                                       0 
                                     
                                   
                                   
                                     
                                       0 
                                     
                                     
                                       
                                         C 
                                         2 
                                       
                                     
                                   
                                 
                                 ] 
                               
                               ︸ 
                             
                             M 
                           
                         
                         + 
                         
                           
                             
                               [ 
                               
                                 
                                   
                                     
                                       G 
                                       1 
                                     
                                   
                                   
                                     
                                       - 
                                       
                                         G 
                                         1 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       - 
                                       
                                         G 
                                         2 
                                       
                                     
                                   
                                   
                                     
                                       G 
                                       2 
                                     
                                   
                                 
                               
                               ] 
                             
                             ︸ 
                           
                           N 
                         
                       
                       ) 
                     
                     ⁢ 
                     
                       
                         
                           [ 
                           
                             
                               
                                 
                                   
                                     V 
                                     1 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     s 
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   
                                     V 
                                     2 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     s 
                                     ) 
                                   
                                 
                               
                             
                           
                           ] 
                         
                         ︸ 
                       
                       
                         X 
                         ⁡ 
                         
                           ( 
                           s 
                           ) 
                         
                       
                     
                   
                   = 
                   
                     
                       bV 
                       s 
                     
                     ⁡ 
                     
                       ( 
                       s 
                       ) 
                     
                   
                 
                 , 
                 
                     
                 
                 ⁢ 
                 
                   
                     Y 
                     ⁡ 
                     
                       ( 
                       s 
                       ) 
                     
                   
                   = 
                   
                     
                       c 
                       T 
                     
                     ⁢ 
                     
                       X 
                       ⁡ 
                       
                         ( 
                         s 
                         ) 
                       
                     
                   
                 
               
             
             
               
                 ( 
                 2 
                 ) 
               
             
           
         
       
     
   
   where X(s)∈R n  is a state vector, V s (s)∈R m  is an input vector, Y(s)∈R p  is an output vector, and M,N∈R n×n , b∈R n×m , c∈R n×p  are so-called MNA matrices, in which M and N matrix comprises a capacitor C and a conductance G. It is a Positive Definite matrix, M is a symmetric matrix, and N is an asymmetric matrix. n is the entries of nodes in the interconnect circuit. When the order of interconnect circuit is higher, the size of a matrix increases, with a great deal of memory data being wasted. When the system reduction (flow) starts, in which the special structure of RC circuit is considered in this invention, the sparse matrix is used to form an original system. The technique of sparse matrix is applied to store the data regarding the capacitance and resistance, thereby the system resource is significantly reduced. In order to form an equivalent reduced system, the voltage moment that is used to establish the projection matrix (as shown in  FIG. 2  illustrating the recursion moment) is applied to form a low-order system:
 
{circumflex over (N)}=Q T NQ, {circumflex over (M)}=Q T MQ, {circumflex over (b)}=Q T b, and ĉ=Q T c  (3)
 
   where the projection matrix Q is given to form the voltage moment of order k in formula (1). After the projection, an output reduced system of the original system is obtained and may be made to stay passive and stable. Finally, the system reduction ends. 
   Time Domain Simulation 
     FIG. 4  illustrates a time domain simulation starting from time domain simulation  150  for an equivalent capacitance. The time domain simulation analyzes clocks in the circuit, in which the flow may be divided into two parts. 
   For the first part of the signal delay, calculation is done for the delay of input signal passing through a drive element. This program makes use of the table look-up of a logic cell library to obtain such information. The method of table look-up is applied for the information on input signal conversion time and output load, thereby the signal delay and the output signal conversion time is obtained. 
   For the second part of the interconnect circuit analysis on the delay and conversion time of output signal passing through the interconnect circuit, the operation condition after calculation of the signal passing though the interconnect circuit is applied for the reduced model given in the technique of model reduction. A moment equation is solved for an output result, in which an ordinary moment equation may be expressed as:
 
 M{dot over (x)}+Nx=bV   s   (4)
 
where the time domain simulation is made to end.
 
Equivalent Capacitance Calculation
 
   Regarding the manner of table look-up for the algorithm of time domain simulation, the pieces of input information are the input signal transition time and the output load. Because the load connected to the drive element is an RC interconnect circuit, in order to obtain an equivalent capacitive load, a technique of calculating the equivalent capacitance is used to obtain an accurate output signal. 
   As shown in  FIG. 5  illustrating a flow of equivalent capacitance calculation, calculation of the equivalent capacitance starts. At the time of equivalent capacitance calculation, for a large interconnect RC circuit, the interconnect circuit is used to calculate the moment of first 4 orders, a π (equivalent) model is formed, and the manner of iteration is used to calculate equivalent capacitance. Thereby, the equivalent capacitance is obtained, and the equivalent capacitance calculation is made to end. 
   The structure of equivalent model, as shown in  FIGS. 6   a  through  6   c , is an original RC circuit system  250 . In this invention, calculation is done for the former 2 orders of voltage moment and the former 3 orders of current moment that are at the Root of the RC interconnect circuit. A technique of moment matching is applied to obtain three parameters C 1 , C 1 , and C 1   252  of the π model, and in case of: 
                       i   root       v   root       =         a   0     +     sa   1     +       s   2     ⁢     a   2           1   +     sb   1           ⁢     
     ⁢         then   ⁢           ⁢     c   1       =       a   1       b   1         ,           ⁢       c   2     =       a   1     -       a   2       b   1           ,           ⁢       and   ⁢           ⁢     R   π       =         b   1   2           b   1     ⁢     a   1       -     a   2         .                 (   5   )               
Finally, it is reduced to equivalent capacitance  254 .
 
   Regarding the analysis on the operation complexity, for example of a huge interconnect RC circuit, there are two parts in this algorithm, namely model reduction and time domain analysis. This algorithm lets n be the entries of nodes of the original system and k be the reduced order. In the technique of model reduction, the skill of recursion moment is applied to obtain the projection matrix. The complexity is O(nk), and at the step of model reduction fulfilled by the skill of congruent projection, the original system MN may represent a type of sparse matrix, so the complexity is O(nk 2 ) and O(k 2 ) for the matrix operation of the educed system. Thus, by all accounts, the complexity of operation is O(nk+nk 2 +k 2 ), and k&lt;&lt;n. 
   SIMPLE EMBODIMENT 
   In order to prove the accuracy of the algorithm in this invention, as shown in  FIG. 7 , a circuit model (Case  1 ) with 10 nodes is provided and applied to analyze the performance of algorithm. However, the application of this application is not limited to the structure only. 
   (Case  1 ) consists of 10 resistors and 10 capacitors, of which the parameters are 100Ω and 0.01 pF, respectively. Standard error margin discussion is made through the waveform of the input signal from the original circuit of this testing circuit and through the calculation in the technique of model reduction and the analysis on the output result. The result obtained from the calculation by the Golden SPICE software, in which Golden is the standard that is used in the industry and SPICE is a kind of software on language and simulation that is used in circuit description and simulation to detect the connection of circuits and the integrity of functions and to predict the behavior of a circuit. It is mainly used for the simulation of a simulated circuit and a mixed signal circuit. The drive logic cell delay error is defined to: 
   
     
       
         
           
             
               
                 
                   ( 
                   
                     
                       
                         
                           
                             
                               cell 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               delay 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               of 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               the 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               SPICE 
                             
                             - 
                           
                         
                       
                       
                         
                           
                             cell 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             delay 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             of 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             the 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             invention 
                           
                         
                       
                     
                     
                       delay 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       of 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       the 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       SPICE 
                     
                   
                   ) 
                 
                 * 
                 100 
                 ⁢ 
                 % 
               
             
             
               
                 ( 
                 6 
                 ) 
               
             
           
         
       
     
   
   The output signal delay error of the interconnect wire is defined to: 
   
     
       
         
           
             
               
                 
                   ( 
                   
                     
                       
                         
                           
                             
                               wire 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               delay 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               of 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               the 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               SPICE 
                             
                             - 
                           
                         
                       
                       
                         
                           
                             wire 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             delay 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             of 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             the 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             invention 
                           
                         
                       
                     
                     
                       
                           
                       
                       ⁢ 
                       
                         delay 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         of 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         the 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         SPICE 
                       
                     
                   
                   ) 
                 
                 * 
                 100 
                 ⁢ 
                 % 
               
             
             
               
                 ( 
                 7 
                 ) 
               
             
           
         
       
     
   
   The output signal transition error of the interconnect wire is defined to: 
   
     
       
         
           
             
               
                 
                   ( 
                   
                     
                       
                         
                           
                             
                               wire 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               transition 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               of 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               the 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               SPICE 
                             
                             - 
                           
                         
                       
                       
                         
                           
                             wire 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             transition 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             of 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             the 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             invention 
                           
                         
                       
                     
                     
                       wire 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       transition 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       of 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       the 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       SPICE 
                     
                   
                   ) 
                 
                 * 
                 100 
                 ⁢ 
                 % 
               
             
             
               
                 ( 
                 8 
                 ) 
               
             
           
         
       
     
   
   Five columns in Table 1 give respectively: (1) comparison between the error of cell delay and that of golden SPICE, (2) comparison between the error of wire delay and that of golden SPICE, (3) comparison between the error of wire transition and that of golden SPICE, (4) time spent for calculation, and (5) memory occupied for execution. 
   
     
       
             
             
             
             
             
             
           
             
             
             
             
             
             
             
           
         
             
                 
             
             
                 
                 
                 
                 
                 
               Occupied 
             
             
                 
                 
                 
                 
               Time 
               memory 
             
             
                 
               cell 
                 
               wire 
               spent for 
               size during 
             
             
               Case 
               delay 
               wire delay 
               transition 
               calculation 
               execution 
             
             
                 
             
           
           
             
                 
             
           
        
         
             
               1 
               0.74% 
               0.98% 
               0.90% 
               Less than 1 s 
               254 
               KB 
             
             
               2 
               0.51% 
               0.82% 
               0.88% 
               0.04 s 
               2736 
               KB 
             
             
               3 
               0.89% 
               0.74% 
               0.83% 
               0.07 s 
               3176 
               KB 
             
             
               4 
               1.22% 
               1.18% 
               1.33% 
               4.66 s 
               8 
               MB 
             
             
               Average 
               0.84% 
               0.93% 
               0.98% 
               Less than 1 s 
               4 
               MB 
             
             
                 
             
           
        
       
     
   
   Through the calculation for a mean error given in Table 1 by the comparison between the result obtained in the technique proposed in the present invention and that obtained by the Golden SPICE software, the accuracy of this invention is apparent. The algorithm in this invention is achieved by Ansi C, compiled by gcc in a Uxix system, and executed on the platform of SUN Blade 2000 with a memory of 2 GB. 
   Case 2  consists of five interconnect systems, amounting to 5 resistors and 15 capacitors. 
   Case 3  consists of ten interconnect systems, amounting to 178 resistors and 170 capacitors. 
   Case 4  consists of six interconnect systems, amounting to 6000 resistors and 6000 capacitors. 
   Case 2 ˜Case 4  separately consists of a plurality of interconnect systems. The values of resistance and capacitance vary with the interconnect systems in each different Case for achievement of an analysis of extensive testing and real performance. 
   While the invention has been described in terms of what is presently considered to be the most practical and preferred embodiments, it is to be understood that the invention needs not be limited to the disclosed embodiments. On the contrary, it is intended to cover various modifications and similar arrangements included within the spirit and scope of the appended claims which are to be accorded with the broadest interpretation so as to encompass all such modifications and similar structures.