Abstract:
A method to analyze and correct dynamic power grid variations in an IC includes performing a dynamic power grid analysis of the circuit, identifying an excessive dynamic power grid voltage fluctuation from the analysis, and modifying the circuit to reduce the excessive dynamic power grid fluctuation.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of U.S. Provisional Application No. 60/474,711, filed May 29, 2003, which is hereby incorporated by reference in its entirety. 
    
    
     FIELD OF THE INVENTION 
     The invention is related to the field of electronic circuit design. 
     BACKGROUND AND SUMMARY 
     Electronic design automation tools help a user to create and assess a design of an electronic system in terms of its functionality, performance, and cost. For example, a user can simulate an electronic circuit before it is built to determine if it will perform as intended. If it performs below its desired level, the user can modify the design to improve system performance. 
     One factor that can affect a circuit&#39;s performance is the circuit&#39;s power consumption characteristics. For example, due to the constant reduction in scaling of integrated circuit (IC) process technology, the size and power consumption of integrated circuits continues to increase significantly. The instantaneous power and current demands of modern integrated circuits can be so large that the on-chip power grid that distributes power to these circuits are taxed by excessive voltage and power losses. For example, the power drawn by a given node at a given instant may overwhelm the power supply. These instantaneous demands can adversely affect the performance of the IC to the point of failure. Conventional design tools fail to account for dynamic variations in the power grid of the IC. 
     A method to analyze and correct dynamic power grid variations in an IC includes performing a dynamic power grid analysis of the circuit, identifying an excessive dynamic power grid voltage fluctuation from the analysis, and modifying the circuit to reduce the excessive dynamic power grid fluctuation. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows an example of a method for analyzing and correcting dynamic power grid variations. 
         FIG. 2  shows an example of Boolean variables describing circuit states advancing from one clock cycle to next. 
         FIG. 3  shows an example of an active clock net that triggers the output of a latch to change state. 
         FIGS. 4(   a ) and  4 ( b ) show an example of tracing and simulating an active clock net using channel-connected components. 
         FIG. 5  shows an example of a power grid and ground grid network having resistors, capacitors, current and voltage sources. 
         FIG. 6  shows an example of a power grid network having resistive loss from its decoupling capacitors. 
         FIG. 7  shows an example of a method for adding decoupling capacitors to top contributors of a failed node. 
         FIG. 8  is a block diagram of a computer system  800  suitable for implementing an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     To remedy the problem of dynamic power grid variations in an integrated circuit (IC), decoupling capacitors are inserted between the on-chip power and ground grids of the IC. A decoupling capacitor acts as a local repository of charge that replenishes the charge drawn by a transistor or logic gate when it transitions from one logic state to another. To prevent large instantaneous currents from being drawn from the off-chip power supply and traversing the on-chip power grid, adequate amounts of decoupling capacitors are added throughout the power grid. One aim of adding decoupling capacitance is to minimize instantaneous voltage drop in the power grid to a small percentage (such as, for example, less than 10%) of the supply voltage rail. In order to reduce or minimize dynamic power grid variations, a dynamic power grid analysis is performed in the presence of decoupling capacitance to both determine an adequate amount of decoupling capacitance and to determine the locations to insert decoupling capacitors in order to reduce instantaneous power grid voltage fluctuation to a tolerable level. 
     Dynamic Power Grid Analysis and Correction Method 
       FIG. 1  shows an example of a method for analyzing and correcting dynamic power grid variations. An analysis device, such as a computer processing system for example, receives an extracted circuit having logic gate instances and the power grid network interconnecting these instances,  110 . The extracted circuit is traversed starting from the primary inputs, and the instances are simulated in topological order to determine the transient current drawn from the power supply by each instance,  120 . A satisfiable synchronous methodology, described below, is used to traverse the circuit and to setup the transient input stimuli for the simulation of each instance. Once the transient instance currents are determined, they are injected into the power grid network, and the resulting voltage response of the power grid network is calculated,  130 . The peak to peak power grid voltage at each node in the network is then examined,  140 , to determine if it exceeds a user-specified tolerance level,  150 . If the voltage variation at a node is excessive, an adjoint calculation technique, described below, is used to determine the contribution of each instance current to the voltage variation at that node,  160 . The top instance contributors for that node are determined and for each contributing instance, adequate decoupling capacitance is added between the corresponding power and ground rails,  170 . Once the excessive node voltage variations have been addressed and requisite decoupling capacitors added, a re-examination of the power grid,  140  and  150 , is performed to ensure that subsequent dynamic voltage variations are within the specified tolerance. If not, more decoupling capacitance is added and the analysis/correction loop  140 ,  150 ,  160 ,  170  continues until convergence with the tolerance is reached. After all grid nodes are examined,  180 , the process determines if all grid voltages are within the specified tolerance,  190 , and the decoupled circuit is output by the processing system,  195 . 
     Transient Instance Current Calculation 
     An aim of calculating the transient instance current,  120 , is to determine the maximum instantaneous current drawn systematically from the power supplies when the logic circuit instances switch state. In a synchronous (clocked) design, a sizeable current dissipation occurs in a clock cycle when the clock net(s) are activated and the latch outputs switch state. Therefore, the method determines the circuit conditions that will result in the maximum number of latch outputs switching when the clock is asserted between two adjacent clock periods. To determine these circuit conditions, the Boolean logic for the circuit, as well as an optimization criterion, are formulated. Assuming a circuit with N nets comprising many combinational logic gates, each with a fanin of F, the Boolean logic may be represented as follows:
 
 x   i   P =ƒ( x   i1   P   , . . . , x   iF   P )  (a)
 
 x   i   N =ƒ( x   i1   N   , . . . , x   iF   N )  (b)
 
where x i   P  and x i   N  refer to the Boolean variable of net i in the previous and next clock cycles respectively, i 1 , . . . , i F εN, and each variable is a logic function ƒ of its fanin. The sequential logic transition between the two clock cycles is represented as:
 
Q j   N =D j   P   (c)
 
where j=1, . . . , S and S is the total number of latches in the circuit, with D and Q being the input and output of the latch respectively, as illustrated in  FIG. 2 , where the curved arrows indicate a cycle advance from previous to next cycle.
 
     These three equations constrain the operation of the circuit in two adjacent clock cycles. In addition, an optimization criterion is specified that will result in the maximum number of simultaneously switching nets while satisfying the logic operation equations. The optimization criterion is written as: 
                       MAX   N       i   =   1       ⁢           [       c   i     *     (       x   i   P     ⁢           ⁢   XOR   ⁢           ⁢     x   i   N       )       ]           (   d   )               
where c i  represents the optimization cost. To ensure that the maximum number of latch outputs switch state, c i  is set to 1 for all latch output nets and 0 for all other nets. The XOR condition enforces switching of logic level from the previous cycle to the next cycle on net i. The hazards are ignored in the above optimization criterion, because when a circuit simulation is run based on the generated 2-cycle setup (as described below), any hazard in the circuit and the resulting current consumption will be captured implicitly.
 
     The above equations describe a weighted max-satisfiability problem. Recent algorithmic advances in Boolean satisfiability, as well as highly efficient solver implementations enable the application of max-satisfiability towards industrial sized circuits [1]. In terms of implementation, each logic equation for the entire circuit is translated into individual clauses, which are fed to a SAT solver, such as Chaff [2] for example, to check for satisfiability. The solved max-satisfiability problem ensures that for each latch that can switch simultaneously, its data input and its output state in the current cycle are of opposite logic states. For example, as shown in  FIG. 3 , when the clock net arrives at the latch, the latch output is forced to switch states. 
     Next, starting at the primary clock inputs, each active clock net is traced by first partitioning the clock net into channel-connected components (CCCs) and then sensitizing each CCC to propagate a switching input forward. The sensitization is performed using a binary decision diagram (BDD) to detect the possible paths from the power and ground rails of the CCC to its output. Solving the BDD sets the side inputs of the CCC to appropriate values to ensure propagation of the switching input to the CCC output. An example of sensitizing a CCC to propagate a switching input forward is illustrated in  FIG. 4   a , where a side input of the NAND gate is held to logic state “1” to allow the switching input to propagate forward. 
     Once the tracing is completed, a simulation is performed on the traced CCCs, one by one, to determine the instantaneous current drawn when the switching input is propagated through it. The switching output waveform at the output of one CCC is used as the input stimulus to a subsequent CCC in the trace. The waveforms at the input pins of the traced clock nets are assumed known (and provided by the user). Note that a simulation ordering is enforced to ensure that in the case of a CCC with multiple switching inputs (as in the case for parallel clock drivers), the switching inputs waveforms of a CCC are determined before simulation of that CCC is performed. An example of the simulation methodology is illustrated in  FIG. 4   b.    
     In addition to simulating the clock net, each switching latch is also simulated with the traced waveform applied to the clock pin, and a fixed state (as determined by the max satisfiability solution) is applied to the data input to ensure that the output changes state. The latch simulation can be performed in multiple ways. For example, if the total number of latches is small, each latch can be simulated as a collection of CCCs during the clock net simulation. Alternatively, to save computational time, simulation of each unique latch cell can be done in a pre-characterization step whereby the latch is simulated under varying switching input slew and output load conditions. The power supply current waveforms drawn by the latch are stored and reused during clock net tracing and simulation. 
     In simulating the clock net(s) distribution and the subsequently activated latches, the simulation time (interval of time over which simulation is performed) is relatively short, being roughly equal to the clock skew from the primary clock input to the furthest latch from it. Since the simulation stops after each latch changes state, the switching latch output does not propagate through the combinational circuitry connected to it. However, even if switching the combinational circuitry does not affect the peak instantaneous current dissipation, it may still be helpful to capture the power supply current characteristics over the entire clock cycle. This would use an extra simulation to be performed for each cone of combinational logic between latches. 
     Capturing these characteristics may be accomplished by partitioning each cone of combinational logic into CCCs, applying the latch output switching waveforms as input stimuli to them, and propagating these switching waveforms through the CCCs. To simulate the combinational logic circuitry, note that no extra sensitization is necessary since the max satisfiability solution would have performed this task. However, simulation ordering is once again applied to ensure that the inputs to a CCC are known prior to propagating a switching input through a CCC. 
     As a byproduct of calculating the instantaneous power currents as described above, a transistor-level netlist of the traced circuitry (clock net, latches and combinational circuitry) is written out in a suitable syntax for a circuit simulator (such as, for example, SPICE or Spectre). Also, voltage sources are written for the switching stimuli connected to the primary inputs of the clock net(s) and for the static logic values applied at all other primary inputs as dictated by results of the max satisifiability solution. Furthermore, initial states are applied to the latch outputs using appropriate initial condition statements for the circuit simulator. As a validation step, a user can simulate the generated transistor-level netlist with his/her circuit simulator of choice, and validate accuracy of the calculated instantaneous power supply currents as described above. 
     Power Grid Response Calculation 
     The transient instance currents are injected into the power grid network,  130 , comprising resistive and capacitive parasitics as shown in  FIG. 5 . The resistive parasitics arise from discretizing the metal power and ground interconnects into smaller segments whereas the capacitive parasitics arise from the overlap or fringe capacitance between these metal segments. Capacitance between power and ground segments due to non-switching gates, well junctions and explicit decoupling capacitors are also included in the power grid network. The power and ground networks are assumed to terminate with ideal voltage supplies. A technique to include parasitics associated with the off-chip interconnections and package is discussed below. 
     To solve the network of  FIG. 5 , Kirchhoff&#39;s Current Law (KCL) is applied to the nodes on the power grid and ground grid, resulting in the following equations: 
                         G   v     ⁢     v   v       +       E   v     ⁢       C   vg     ⁡     (         ⅆ     v   vc         ⅆ   t       -       ⅆ     v   gc         ⅆ   t         )           =     -     I   vg               (   1   )                     G   g     ⁢     v   g       +       E   g     ⁢       C   vg     ⁡     (         ⅆ     v   gc         ⅆ   t       -       ⅆ     v   vc         ⅆ   t         )           =     I   vg             (   2   )               
where G v  is a N×N conductance matrix of the power grid, G g  is a M×M conductance matrix of the ground grid, v v , v g  are the vectors of N power grid node voltages and M ground grid node voltages, v vc , v gc  are vectors of P power grid and ground grid node voltages that are coupled by capacitors and C vg  is a P×P diagonal matrix representing these capacitors. Matrices E v  and E g  are matrices of size N×P and M×P respectively in which each column has a unit entry in the row corresponding to a capacitor connection and zero elsewhere. The voltage sources are not explicitly part of equations (1) or (2) since their contribution to the power grid response can be added to the power grid voltages, v v  as a direct current (DC) term. At a time point of interest, t+Δt, the following equation is obtained from (1).
 
                         G   v     ⁢       v   v     ⁡     (     t   +     Δ   ⁢           ⁢   t       )         +       (       E   v     ⁢     C   vg     ⁢     E   v   T       )     ⁢       ⅆ     v   v         ⅆ   t       ⁢     (     t   +     Δ   ⁢           ⁢   t       )         =         -     G   v     -   1         ⁢       I   vg     ⁡     (     t   +     Δ   ⁢           ⁢   t       )         +       E   v     ⁢     C   vg     ⁢       ⅆ     v   gc         ⅆ   t       ⁢     (   t   )                 (   3   )               
Note that in (3), the solution for the power grid node voltages is obtained by using the ground grid node voltage derivatives from the previous time point. This is equivalent to delaying the effect of the ground grid voltage by one time point. Similarly, the following equation is obtained from (2).
 
                         G   g     ⁢       v   g     ⁡     (     t   +     Δ   ⁢           ⁢   t       )         +       (       E   g     ⁢     C   vg     ⁢     E   g   T       )     ⁢       ⅆ     v   g         ⅆ   t       ⁢     (     t   +     Δ   ⁢           ⁢   t       )         =         G   g     -   1       ⁢       I   vg     ⁡     (     t   +     Δ   ⁢           ⁢   t       )         +       E   g     ⁢     C   vg     ⁢       ⅆ     v   vc         ⅆ   t       ⁢     (   t   )                 (   4   )               
To solve (3) and (4), a first order implicit integration algorithm is employed to yield the following equations:
 
     
       
         
           
             
               
                 
                   
                     
                       v 
                       v 
                     
                     ⁡ 
                     
                       ( 
                       
                         t 
                         + 
                         
                           Δ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           t 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ( 
                         
                           
                             G 
                             v 
                           
                           + 
                           
                             
                               
                                 E 
                                 v 
                               
                               ⁢ 
                               
                                 C 
                                 vg 
                               
                               ⁢ 
                               
                                 E 
                                 v 
                                 T 
                               
                             
                             
                               Δ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               t 
                             
                           
                         
                         ) 
                       
                       
                         - 
                         1 
                       
                     
                     [ 
                     
                         
                     
                     ⁢ 
                     
                       
                         
                           - 
                           
                             G 
                             v 
                             
                               - 
                               1 
                             
                           
                         
                         ⁢ 
                         
                           
                             I 
                             vg 
                           
                           ⁡ 
                           
                             ( 
                             
                               t 
                               + 
                               Δt 
                             
                             ) 
                           
                         
                       
                       + 
                       
                         
                           E 
                           v 
                         
                         ⁢ 
                         
                           C 
                           vg 
                         
                         ⁢ 
                         
                           
                             ⅆ 
                             
                               v 
                               gc 
                             
                           
                           
                             ⅆ 
                             t 
                           
                         
                         ⁢ 
                         
                           ( 
                           t 
                           ) 
                         
                       
                       + 
                       
                         
                           ( 
                           
                             
                               E 
                               v 
                             
                             ⁢ 
                             
                               C 
                               vg 
                             
                             ⁢ 
                             
                               E 
                               v 
                               T 
                             
                           
                           ) 
                         
                         ⁢ 
                         
                           
                             v 
                             v 
                           
                           ⁡ 
                           
                             ( 
                             t 
                             ) 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       v 
                       g 
                     
                     ⁡ 
                     
                       ( 
                       
                         t 
                         + 
                         
                           Δ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           t 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ( 
                         
                           
                             G 
                             g 
                           
                           + 
                           
                             
                               
                                 E 
                                 g 
                               
                               ⁢ 
                               
                                 C 
                                 vg 
                               
                               ⁢ 
                               
                                 E 
                                 g 
                                 T 
                               
                             
                             
                               Δ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               t 
                             
                           
                         
                         ) 
                       
                       
                         - 
                         1 
                       
                     
                     [ 
                     
                         
                     
                     ⁢ 
                     
                       
                         
                           - 
                           
                             G 
                             g 
                             
                               - 
                               1 
                             
                           
                         
                         ⁢ 
                         
                           
                             I 
                             vg 
                           
                           ⁡ 
                           
                             ( 
                             
                               t 
                               + 
                               Δt 
                             
                             ) 
                           
                         
                       
                       + 
                       
                         
                           E 
                           g 
                         
                         ⁢ 
                         
                           C 
                           vg 
                         
                         ⁢ 
                         
                           
                             ⅆ 
                             
                               v 
                               vc 
                             
                           
                           
                             ⅆ 
                             t 
                           
                         
                         ⁢ 
                         
                           ( 
                           t 
                           ) 
                         
                       
                       + 
                       
                         
                           ( 
                           
                             
                               E 
                               g 
                             
                             ⁢ 
                             
                               C 
                               vg 
                             
                             ⁢ 
                             
                               E 
                               g 
                               T 
                             
                           
                           ) 
                         
                         ⁢ 
                         
                           
                             v 
                             g 
                           
                           ⁡ 
                           
                             ( 
                             t 
                             ) 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     The solutions to (5) and (6) are computationally dominated by the calculation of four matrix inversions, G v   −1 , G g   −1 , (G v +E v C vg E v   T /Δt) −1  and (G g +E g C vg E g   T /Δt) −1 . Since the matrices, G v  and G g  are the same matrices used in the calculation of a static IR drop analysis, which may be run prior to a dynamic analysis, the inverse matrices G v   −1  and G g   −1  can be readily available to solve (5) and (6). Furthermore, for a given right hand side, b, it is possible to calculate the solutions (G v +E v C vg E v   T /Δt) −1 .b and (G g +E g C vg E g   T /Δt) −1 .b by applying P rank one updates to Gv −1 .b and Gg −1 .b respectively, since C vg  is a diagonal matrix of rank P, (P&lt;N; N=rank(G)). This is accomplished by repeated use of the Sherman Morrison formula on the matrix equation: 
                       (       G   v     +         E   v     ⁢     C   vg     ⁢     E   v   T         Δ   ⁢           ⁢   t         )     ⁢           ⁢   x     =         (       G   v     +       ∑     i   =   1     P     ⁢           ⁢         C   ii       Δ   ⁢           ⁢   t       ⁢     e   i     ⁢     e   i   T           )     ⁢           ⁢   x     =   b             (   7   )               
where e i  is a vector of size N with a unit entry at row i and zero everywhere else. The inverse of a rank one update of matrix, G v  defined as:
 ( G   v   +αe   i   e   i   T ) x=b   (8) 
which is solved by solving the two auxiliary problems
 G v y=b  (9) G v z=αe i   (10) 
for the vectors y and z. The solution is given in terms of these as:
 
                   x   =     y   -       [         e   i   T     ⁢   y       (     1   +       e   i   T     ⁢   z       )       ]     ·   z               (   11   )               
Note that the dot products e i   T y and e i   T z are equivalent to picking out the i th  entry of vectors y and z respectively and hence equation (11) uses N floating point multiplications and N floating point subtractions. For P updates of rank one as is used in the solution of equation (7), one would need to solve equation (10) P times and equation (11) (P 2 +P)/2 times. However, if the time step employed in the integration algorithm is fixed, the P solutions to (10) and (P 2 −P)/2 solutions to (11) can be done only one time a priori and stored as P vectors of size N. Then, at every time step, the solution to (7) can be computed using P solutions of (11) requiring a total of N*P floating point operations.
 
     Therefore, at every time step the solution to equation (5) can be obtained using two forward back substitutions using the matrix inverse, G v   −1  requiring at most (N*N+1)/2 floating point operations (which may be much less owing to sparsity) and P rank one updates requiring N*P floating point operations. The solution to equation (6) is obtained likewise. Once the power and ground grid voltages are determined, the currents that flow into the pads (voltage sources), i p , i p2 , i g , i g2  are determined by applying KCL at the corresponding pad nodes. This vector of short circuit currents, i pgeq  is used in constructing an admittance macromodel of the power and ground grid network as described below. 
     Incorporating Effects of Off-Chip Parasitics 
     On an integrated circuit, the power and ground grids are connected through package and other off-chip parasitics to ideal board-level power supplies. Therefore, to predict on-chip dynamic power grid variations, the power and ground grid equations coupled with the package network equations are solved. To facilitate this solution, the power and ground pad nodes (connected to voltage sources) are defined as ports, and a macromodel of the coupled power and ground grid about the ports is constructed as follows: 
                     (     E   ·     i   pg       )     =     Gv   +     C   ⁢       ⅆ   v       ⅆ   t         +     (     E   ·     i   pgeq       )               (   12   )                 v   pg     =       E   T     ⁢   v             (   13   )               
where i pg  and v pg  are the port current and voltage vectors of size p (p is the number of pads), and E is a n×p matrix (n=N+M) where each column has a unit entry in the row corresponding to a port and zero elsewhere. Furthermore the matrices G and C of size n×n are defined as follows:
 
                   G   =         [           G   v         0           0         G   g           ]     ⁢           ⁢   C     =     [             E   v     ⁢     C   vg     ⁢     E   v   T               -     E   v       ⁢     C   vg     ⁢     E   g   T                   -     E   g       ⁢     C   vg     ⁢     E   v   T               E   g     ⁢     C   vg     ⁢     E   g   T             ]               (   14   )               
where the node voltage vector v is arranged as:
 
                   v   =     [           v   v               v   g           ]             (   15   )               
and the matrix E v , E g  are the same matrices as defined in the previous section.
 
     The current vector, i pgeq  is the short circuit current flowing out of the pads as described in the previous section. In matrix form (12) and (13) are written as follows: 
                       [           G   +   sC           -   E               E   T         0         ]     ⁡     [         v             i   pg           ]       =     [             -   E     ·     i   pgeq                 v   pg           ]             (   16   )               
To create a reduced order macromodel of (16), an orthonormal projection matrix, V q  is determined using the block Arnoldi process [3]. The block Arnoldi process recursively produces an orthonormal basis for the Krylov subspace generated by the matrix G −1 C and a starting block of vectors given by G −1 E. After k iterations, the block Arnoldi process produces an n×q matrix where q=k×p (p is the number of ports) and q&lt;n:
 V q =[V 0 V 1  . . . V k−1 ]  (17) 
whose columns form bases for the Krylov subspace generated by G −1 C and G −1 E. i.e.,
 colsp( V   q )= Kr ( G   −1   C, G   −1   E, q )  (18) 
Furthermore, its columns can be shown to be orthonormal. i.e.,
 V q   T V q =I  (19) 
The computational complexity of the block Arnoldi process is dominated by k solutions of the equation:
   V   j   =−G   −1   CV   j−1   (20) 
where V j  is the jth column and V j−1  the previous column of the matrix in (17). To calculate (20) quickly we exploit the block diagonal structure of the G and C matrix as follows:
 
                     [           v     v   ,   j                 v     g   ,   j             ]     =     -         [           G   v     -   1           0           0         G   g     -   1             ]     ⁡     [             E   v     ⁢     C   vg     ⁢     E   v   T               -     E   v       ⁢     C   vg     ⁢     E   g   T                   -     E   g       ⁢     C   vg     ⁢     E   v   T               E   g     ⁢     C   vg     ⁢     E   g   T             ]       ⁡     [           V     v   ,     j   -   1                   V     g   ,     j   -   1               ]                 (   21   )               
which leads to:
 
                     [           v     v   ,   j                 v     g   ,   j             ]     =     [             G   v     -   1       ⁡     (         E   v     ⁢     C   vg     ⁢     E   g   T     ⁢     V     g   ,     j   -   1           -       E   v     ⁢     C   vg     ⁢     E   v   T     ⁢     V     v   ,     j   -   1             )                   G   g     -   1       ⁡     (         E   g     ⁢     C   vg     ⁢     E   v   T     ⁢     V     v   ,     j   -   1           -       E   g     ⁢     C   vg     ⁢     E   g   T     ⁢     V     g   ,     j   -   1             )             ]             (   22   )               
which in turn is calculated efficiently by exploiting the fact that inverse matrices G v   −1  and G g   −1  are readily available, C vg  is a diagonal matrix and that application of the matrices E v , E g , E v   T  and E g   T  amounts to selecting the appropriate rows or columns of the subsequent matrix.
 
     Once the projection matrix, V q  is determined, it is appended with an identity matrix of size p such that the resulting matrix of size (n+p)×(q+p) projects the n+p equations of (16) to a matrix of q+p equations. The projection matrix is applied to (16) as follows: 
                           [           V   q         0           0       I         ]     T     ⁡     [           G   +   sC           -   E               E   T         0         ]       ⁡     [         v             i   pg           ]       =         [           V   q         0           0       I         ]     T     ⁡     [             -   E     ·     i   pgeq                 v   pg           ]               (   23   )               
Next, defining,
 
                     [         v             i   pg           ]     =       [           V   q         0           0       I         ]     ⁡     [           v   ^               i   pg           ]               (   24   )               
provides a (q+p)×(q+p) matrix of equations as follows:
 
                       [               V   q   T     ⁡     (     G   +   sC     )       ⁢     V   q               -     V   q   T       ⁢   E                 E   T     ⁢     V   q           0         ]     ⁡     [           v   ^               i   pg           ]       =     [             -     V   q   T       ⁢     E   ·     i   pgeq                   v   pg           ]             (   25   )               
In the time domain, the corresponding equations are:
 
                       V   q   T     ⁢     E   ·     i   pg         =         G   ^     ⁢     v   ^       +       C   ^     ⁢     ⅆ     ⅆ   t       ⁢     v   ^       +     (       V   q   T     ⁢     E   ·     i   pgeq         )               (   26   )                 v   pg     =       E   T     ⁢       V   q     ·     v   ^                 (   27   )                 G   ^     =         V   q   T     ⁢     GV   q     ⁢           ⁢     C   ^       =       V   q   T     ⁢     CV   q                 (   28   )               
which is a order q reduced order model of (12) and (13). The q order approximation guarantees that the first k=q/p block moments of the reduced order model and the original circuit model are the same.
 
     At time t+Δt, applying a first order integration algorithm to (26), (27) results in the following equation describing the reduced order macromodel: 
     
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         
                           
                             
                               
                                 G 
                                 ^ 
                               
                               + 
                               
                                 
                                   C 
                                   ^ 
                                 
                                 
                                   Δ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   t 
                                 
                               
                             
                           
                           
                             
                               
                                 - 
                                 
                                   V 
                                   q 
                                   T 
                                 
                               
                               ⁢ 
                               E 
                             
                           
                         
                         
                           
                             
                               
                                 E 
                                 T 
                               
                               ⁢ 
                               
                                 V 
                                 q 
                               
                             
                           
                           
                             0 
                           
                         
                       
                       ] 
                     
                     ⁡ 
                     
                       [ 
                       
                         
                           
                             
                               
                                 v 
                                 ^ 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   t 
                                   + 
                                   
                                     Δ 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     t 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         
                           
                             
                               
                                 i 
                                 pg 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   t 
                                   + 
                                   Δt 
                                 
                                 ) 
                               
                             
                           
                         
                       
                       ] 
                     
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                             
                               
                                 - 
                                 
                                   V 
                                   q 
                                   T 
                                 
                               
                               ⁢ 
                               
                                 E 
                                 · 
                                 
                                   i 
                                   pgeq 
                                 
                               
                             
                             + 
                             
                               
                                 
                                   C 
                                   ^ 
                                 
                                 
                                   Δ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   t 
                                 
                               
                               ⁢ 
                               
                                 
                                   v 
                                   ^ 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   t 
                                   ) 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               v 
                               pg 
                             
                             ⁡ 
                             
                               ( 
                               
                                 t 
                                 + 
                                 
                                   Δ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   t 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   29 
                   ) 
                 
               
             
           
         
       
     
     For the off-chip parasitics, applying a time domain integration to the equations governing them results in:
 
−i pg ( t+Δt )= i   off ( t+Δt )+ Y   off   v   pg ( t+Δt )  (30)
 
where i off  is the off-chip short circuit current vector and Y off  the off-chip admittance matrix at the given time point. Solving (29) and (30) simultaneously results in the solution for v pg (t+Δt) and {circumflex over (v)}(t+Δt).
 
     The updates to power and ground grid voltages due to off-chip parasitics can then be calculated as:
 
 v ( t+Δt )= V   q   ·{circumflex over (v)} ( t+Δt )  (31)
 
By linear superposition, the final power and ground voltage response is obtained as the sum of the solutions of (5), (6) and (31).
 
Incorporating Effects of Lossy Capacitors
 
     Sometimes, a series resistance is added to a decoupling capacitor to better control the time constant with which it responds to switching current demand. Moreover, while modeling the decoupling effect of non-switching circuits, it is important to model the holding resistance of a non-switching circuit in series with the decoupling capacitor, as is illustrated in  FIG. 6  for example. 
     To solve the network of  FIG. 6 , one could simply include the loss from resistors in the power grid network by defining an extended matrix, G v ′ as follows: 
                     G     v   ′       =     [             G   v     +       E   v     ⁢     G   vg     ⁢     E   v   T                 -     E   v       ⁢     G   vg                   -     G   vg       ⁢     E   v   T             G   vg           ]             (   32   )               
where G vg  is a diagonal P×P matrix containing the loss resistors. For each matrix solution, (G v ′) −1 b, the corresponding matrix equation is defined as follows.
 
                       [             G   v     +       E   v     ⁢     G   vg     ⁢     E   v   T                 -     E   v       ⁢     G   vg                   -     G   vg       ⁢     E   v   T             G   vg           ]     ⁡     [           v   N               v   p           ]       =     [           b   N               b   p           ]             (   33   )               
Next, multiplying the second row of (32) by E v  and adding to the first row results in:
 
                       [           G   v         0               -     G   vg       ⁢     E   v   T             G   vg           ]     ⁡     [           v   N               v   p           ]       =     [             b   N     +       E   v     ⁢     b   p                   b   p           ]             (   34   )               
which is then solved as two equations.
   v   N   =G   v   −1 ( b   N   +E   v   b   p )  (35)   v   p   =G   vg   −1 ( b   p   +G   vg   E   v   T   v   N )  (36) 
Note that (35) reuses the factorization of the original power grid matrix (i.e., excluding the loss resistors) and (36) requires a factorization of the diagonal P×P matrix, G vg . Using (35) and (36), the effect of loss resistors can be included in the dynamic power grid analysis with minimal computational overhead.
 
Top Instance Contributor Calculation
 
     For each power/ground grid voltage node whose voltage response exceeds the preset tolerance level (“failed node”), it may be helpful to determine the top instance contributors to the failed node voltage response,  160 . To reduce or minimize the voltage drop at the failed node, decoupling capacitance is added to the top contributing instances in order to provide local repositories of charge precisely where they are beneficial,  170 . In order to compute the contributions,  160 , the following equation is formulated:
 
 z   i =( G+sC ) −1   e   i   (32)
 
where i is the row number corresponding to the failed node in the vector of power and ground grid nodes, and z i  represents the impedance from the failed node to all the power and ground grid nodes. By reciprocity,
 
 z   ij   =e   j   T ( G+sC ) −1   e   i   =e   i   T ( G+sC ) −1   e   j   =z   ji   (33)
 
where z ij  is the impedance from node i to node j.
 
     Next, defining node i as a port and employing k iterations of the block Arnoldi process recursively produces an orthonormal basis, V k  for the Krylov subspace generated by the matrix G −1 C and a starting vector G −1 e i . Note that the projection matrix V k  has k columns (k&lt;&lt;n) owing to the fact that only a single port is defined and it is determined efficiently by exploiting the block diagonal structure of the G and C matrices. Applying the projection matrix to (32) results in:
 
 z   i   =V   k ( Ĝ+sĈ ) −1 (V k   T   ·e   i )  (34)
 
Ĝ=v k   T GV k Ĉ=V k   T CV k   (35)
 
where Ĝ and Ĉ are k×k matrices. The contributions of all the instance currents on the voltage response at node i can be expressed as:
 
                     v   i     =         z   i   T     ⁢   i     =           z     i   ⁢           ⁢   1       ⁢     i   1       +       z     i   ⁢           ⁢   2       ⁢     i   2       +   …     =       ⅇ   i   T     ⁢         V   k     ⁡     (       G   ^     +     s   ⁢     C   ^         )         -   1       ⁢       V   K   T     ⁡     [           i   1               i   2             …         ]                     (   36   )               
In the time domain this is calculated as:
 
                       v   ^     ⁡     (     t   +     Δ   ⁢           ⁢   t       )       =         (       G   ^     +       C   ^       Δ   ⁢           ⁢   t         )       -   1       ⁢     (         V   k   T     ⁡     (       e   i     ·       i   j     ⁡     (   t   )         )       +         C   ^       Δ   ⁢           ⁢   t       ⁢       v   ^     ⁡     (   t   )           )               (   37   )                   v   ij     ⁡     (     t   +     Δ   ⁢           ⁢   t       )       =       ⅇ   i   T     ⁢       V   k     ·       v   ^     ⁡     (     t   +     Δ   ⁢           ⁢   t       )                   (   38   )               
where v ij =z ij i j  is the contribution of the j th  instance current i j  at node i.
 
     Note that it is possible to diagonalize matrices Ĝ and Ĉ by employing a second projection on these matrices using the eigenvectors of Ĝ −1 Ĉ as the projection matrix. Thus, at every time step, the solution to (37) and (38) requires just 4*k floating point operations. 
     Adding Decoupling Capacitors 
     Once the contribution waveform v ij  at node i from each instance j is computed, the contributors are sorted by the peak magnitude of their contribution. Starting from the biggest instance contributor, decoupling capacitors are added 170 between power and ground rails of each of the top instance contributors until the magnitude of the voltage response at the failed node is below the predefined tolerance. 
     For example,  FIG. 7  shows an embodiment of a method for adding decoupling capacitors to top contributors of a failed node. The failed node is identified,  710 . The waveforms of instances that contribute to the failed node are determined,  720 . These contributors are sorted based on their peak magnitudes,  730 . The sorted contributors are examined, beginning with the contributor having the highest peak magnitude,  740 . A decoupling capacitor is added to the circuit design to alleviate the effects of the examined contributor, and the contributor&#39;s voltage contribution is subtracted from the voltage level of the failed node,  750 . If the failed node&#39;s voltage still exceeds the tolerance amount,  760 , the method returns to  740  to examine the next contributor in the sorted list. Otherwise, the method is completed for the failed node,  770 . 
     The size of the decoupling capacitance for the j th  instance contributor added during 750 is determined as: 
                     C   d     =         1     V   dd       ·       ∫   0   T     ⁢         i   j     ⁡     (   t   )       ⁢           ⁢     ⅆ   t           =       Q   d       V   dd                 (   39   )               
where the charge, Q d  dissipated over one clock period, T as determined by integrating the instance current i j (t), is used to determine the size of capacitor required to provide it. Once the decoupling capacitors have been added for a failed node, and its response is deemed fixed, the newly added decoupling capacitors are included in the global capacitance matrix so that they are included in the analysis required to fix the next failed node.
 
       FIG. 8  is a block diagram of a computer system  800  suitable for implementing an embodiment of the present invention. Computer system  800  includes a bus  802  or other communication mechanism for communicating information, which interconnects subsystems and devices, such as processor  804 , system memory  806  (e.g., RAM), static storage device  808  (e.g., ROM), disk drive  810  (e.g., magnetic or optical), communication interface  812  (e.g., modem or Ethernet card), display  814  (e.g., CRT or LCD), input device  816  (e.g., keyboard), and cursor control  818  (e.g., mouse or trackball). 
     According to one embodiment of the invention, computer system  800  performs specific operations by processor  804  executing one or more sequences of one or more instructions contained in system memory  806 . Such instructions may be read into system memory  806  from another computer readable medium, such as static storage device  808  or disk drive  810 . In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. 
     The term “computer readable medium” as used herein refers to any medium that participates in providing instructions to processor  804  for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media includes, for example, optical or magnetic disks, such as disk drive  810 . Volatile media includes dynamic memory, such as system memory  806 . Transmission media includes coaxial cables, copper wire, and fiber optics, including wires that comprise bus  802 . Transmission media can also take the form of acoustic or light waves, such as those generated during radio wave and infrared data communications. 
     Common forms of computer readable media includes, for example, floppy disk, flexible disk, hard disk, magnetic tape, any other magnetic medium, CD-ROM, any other optical medium, punch cards, paper tape, any other physical medium with patterns of holes, RAM, PROM, EPROM, FLASH-EPROM, any other memory chip or cartridge, carrier wave, or any other medium from which a computer can read. 
     In an embodiment of the invention, execution of the sequences of instructions to practice the invention is performed by a single computer system  800 . According to other embodiments of the invention, two or more computer systems  800  coupled by communication link  820  (e.g., LAN, PTSN, or wireless network) may perform the sequence of instructions required to practice the invention in coordination with one another. 
     Computer system  800  may transmit and receive messages, data, and instructions, including program, i.e., application code, through communication link  820  and communication interface  812 . Received program code may be executed by processor  804  as it is received, and/or stored in disk drive  810 , or other non-volatile storage for later execution. 
     In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. For example, the above-described process flows are described with reference to a particular ordering of process actions. However, the ordering of at least some of the described process actions may be changed without affecting the scope or operation of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than restrictive sense.