⬇ Download Markdown  ·  ⬇ Download LaTeX  ·  ⬇ original  ·  view original  ·  CSV: table 1, table 2

IEEE TRANSACTIONS ON COMPONENTS, PACKAGING AND MANUFACTURING TECHNOLOGY, VOL. 1, NO. 9, SEPTEMBER 2011 1447

Partitioned Latency Insertion Method with a Generalized Stability Criteria

Patrick Goh, José E. Schutt-Ainé, Fellow, IEEE, Dmitri Klokotov, Jilin Tan, Senior Member, IEEE,

Ping Liu, Wenliang Dai, and Feras Al-Hawari Abstract— This paper presents a modular approach to the high-frequency simulation of large networks. By utilizing the latency insertion method (LIM) and by studying the stability criteria of partitions of different latencies in the circuit, a robust method is formulated that is able to perform transient simulations significantly faster than the conventional LIM method. The LIM method is also extended to handle dependent sources, and a general stability criterion for selecting the time step, independent of the topology of the circuit, is proposed. The new method is verified with existing commercial tools for circuit simulations, and the improvement in run time is also depicted.

Index Terms— Circuit simulation, dependent sources, latency insertion method, partitioned latency insertion method, stability.

I. I NTRODUCTION

W ITH the increase in the density of interconnects and the complexity of high-speed packages, signal integrity becomes an important aspect in the design of modern devices. Circuit designers are constantly in need of newer and better methods that are able to capture the complicated electromagnetic behaviors of complex circuits. In this aspect, the ability to accurately simulate large circuits in a reasonable amount of time is invaluable in the design of any circuit. As a result, there is a constant need and push toward faster circuit simulation methods that are able to handle large circuits in a fraction of the time taken by conventional circuit simulators.

The latency insertion method (LIM) [1] has recently emerged as an efficient approach for performing fast simulations of very large circuits. By exploiting latencies in the circuit, LIM is able to solve the voltages and the currents in the circuit explicitly at each time step. This results in a computationally efficient algorithm that is able to simulate large circuits significantly faster than conventional matrix inversion–based methods such as SPICE [2].

The two main advantages of LIM over SPICE-like simulators for transient simulations are its linear numerical complex-

Manuscript received January 8, 2011; revised March 27, 2011; accepted April 29, 2011. Date of publication July 14, 2011; date of current version September 21, 2011. Recommended for publication by Associate Editor M. Cases upon evaluation of reviewers’ comments.

P. Goh, J. E. Schutt-Ainé, and D. Klokotov are with the Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (e-mail: [email protected]; [email protected]; [email protected]).

J. Tan, P. Liu, W. Dai, and F. Al-Hawari are with Cadence Design Systems, Inc., Chelmsford, MA 01824 USA (e-mail: [email protected]; [email protected]; [email protected]; [email protected]).

Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org.

Digital Object Identifier 10.1109/TCPMT.2011.2158540 ity and its linear memory requirement [3]. For this reason, LIM is most efficiently used for solving large circuits where the number of elements is in the order of millions. For example, in [4]–[8], LIM has been used in both the transient and steadystate analysis of power distribution networks, where the usage of conventional simulators is prohibited by the large circuit size. In addition, LIM is also well suited to handle simulations of high-frequency circuits such as the tightly coupled transmission lines [9], [10] and circuits with frequency-dependent effects [11]–[13]. On the other hand, one of the disadvantages of LIM is its reliance on latency elements in the circuit in order to perform its time-stepping algorithm. The LIM algorithm is only conditionally stable, with an upper bound on the maximum time step which depends mainly on the smallest inductance and capacitance in the circuit. When the circuit contains very small latency elements, the time step required for a stable simulation could be equally small, which would result in a large number of time steps in a transient simulation. In order to alleviate this problem, a block-processing technique has been proposed [14]–[16], which utilizes different time steps for different parts of the circuit. However, selecting the maximum time step for each part of the circuit is still a challenging task, and the basic method used in [14]–[16] to select the time step can only be applied under very restrictive assumptions [17]. Specifically, each node in the circuit has to be connected to only two branches, and the values of the circuit elements have to be the same everywhere in each subcircuit. In this paper, we propose a more robust method to select the maximum time step of the LIM simulation, which is independent of the circuit topology. We then apply the method, along with the block-processing technique, to the simulation of circuits with partitions of different latencies, and demonstrate the accuracy and speed improvements of the proposed method over the basic LIM. In addition, we will also extend the basic LIM to handle dependent sources.

The remainder of this paper is organized as follows. Section II reviews the basic LIM formulation. Section III presents the matrix version of the semi-implicit LIM formulation, along with the usage of the amplification matrix to predict the stability of a time step. Section IV details the modification to the circuit parameter matrices to include dependent sources, and the resulting modifications to the amplification matrix. Section V will present the usage of multiple time steps to simulate circuits with partitions of different latencies, by applying the amplification matrix to select the time steps for each partition, and the speed improvement over the regular LIM.

2156–3950/$26.00 © 2011 IEEE 1448 IEEE TRANSACTIONS ON COMPONENTS, PACKAGING AND MANUFACTURING TECHNOLOGY, VOL. 1, NO. 9, SEPTEMBER 2011

I i3 I i2 I ik H i G i C i I i1 V i . 1. Node topology. merical results are shown in Section VI, and a conclusion iven in Section VII. II. BA SIC LIM FO RMULATION n this section, the formulation of the basic LIM will be iewed. LIM can be applied to any arbitrary network, where s assumed that through the use of Thévenin and Norton nsformations, the branches and nodes of the circuit can be cribed by a general topology. Each node is represented by arallel combination of a current source, a conductance, a capacitor to ground. The connection between two ferent nodes forms a branch and it is represented by a series bination of a voltage source, a resistor, and an inductor. . 1 shows a node i with k branches connected to it, while . 2 shows a branch connecting nodes i and j . The voltage ode i is defined as Vi while the current flowing from node o j is defined as Ii j . In order to solve for the voltages currents in the circuit, LIM discretizes the time variable ereby the voltages and currents are collated in half time ps. Specifically, the voltages are solved at half time steps ile the currents are solved at full time steps. From Fig. 1, iting K irchhoff’s current law (KCL) at node i yields Ci ⎛ ⎝ V n+1 2 i − V n−1 2 i t ⎞ ⎠ + G i V n+1 2 i − H n i = − Mi k=1 I n i k (1) V i L ij R ij l ij E ij V j −+ Fig. 2. Branch topology. Solving for the unknown current yields I n+1 i j = I n i j + t L ij V n+1 2 i − V n+1 2 j − Ri j I n i j + E n+1 2 i j . (4) The computation of the node voltages and the branch currents are alternated as time progresses in a leapfrog manner. In this aspect, LIM is similar to Yee’s algorithm for the solution of Maxwell’s equations in the finite difference time domain (FDTD) method [18]. It is clear that the LIM algorithm relies on the latencies in the network to perform the leapfrog time- stepping formulation. Thus, at every node, a capacitor to ground has to be present. If it is not, a small fictitious capacitor is inserted. Similarly, small fictitious inductors are inserted into branches without latencies. The effects of these fictitious elements on the accuracy of the general LIM has been studied in [3]. In Section V, we will examine the effects of these elements on the speed of the LIM and propose a generalized solution to improve the speed of the simulations of circuits with partitions of different latencies. As with the traditional FDTD method [18], LIM is only conditionally stable. In other words, there is an upper bound on the time step that will result in a numerically stable solution to (2) and (4). Previous work on the subject has resulted in an analytical stability condition on the time step for stable simulations in the case of resistance-inductance-capacitance (RLC) and gate-level characterization (GLC) circuits [3], [19]. However, there has not been any analytical method to predict the stability of a time step for a general RLGC circuit. In Section III, we will show a numerical method to predict the stability of a time step for any general circuit topology. Since this method does not impose any requirement on the circuit topology, it can also be used to predict the stability of a time step in the presence of dependent sources as will be shown in Section IV. III. VE CTOR- MA TRIX SE MI- IM PLICIT LIM FO RMULATION

n+1 2 = Ci V n−1 2 i t + H n i − Mi k=1 I n ik Ci + G

anch ij yields V n+1 2 i − V n+1 2 j = L ij I n+1 i j − I n i j t + Ri j I n i j − E n+1 2 i j . (3)

In this section, the formulation of the vector-matrix version of the semi-implicit LIM [20] will be reviewed. From (1), we

write the semi-implicit formulation as Ci ⎛ ⎝ V n+1 2 i − V n−1 2 i t ⎞ ⎠ + G i ⎛ ⎝ V n+1 2 i + V n−1 2 i 2 ⎞ ⎠ − H n i

=− M i 

I ik n . (5) k=1 Equation (5) can then be written in a vector-matrix formulation as 

C v n+1 2 −v n−1 2 t + 1 2 G v n+1 2 + v n−1 2 − hn = −Min (6)

GOH et al.: PARTITIONED LATENCY INSERTION METHOD 1449

where v is the node voltage vector of dimension Nn , i is the branch current vector of dimension Nb , C and G are diagonal matrices, respectively, of dimensions Nn × Nn ,with the values of the capacitors and conductances at each node on the main diagonal, h is a vector of dimension Nn containing all the current sources at the nodes, and M is the Nn × Nb incidence matrix defined as follows: Mq p = 1 i f br anch p i s i nci dent at node q and the curr ent f lows away f r om node q. Mq p = −1 i f br anch p i s i nci dent at node q and the curr ent f lows i nto node q. Mq p = 0 i f br anch p i s not i nci dent at node q. Solving (6) for vn +1/2 yields v n+1 2 = C t + G 2 −1 C t − G 2 v n−1 2 + hn − Min . (7) Similarly, we may write the semi-implicit formulation of (3) in vector-matrix form as MT v n+1 2 = L t in +1 −in + R 2 in +1 + in − e n+1 2 (8) where L and R are diagonal matrices, of dimensions Nb × Nb , with the values of the inductances and resistances at each branch on the main diagonal, and e is a vector of dimension Nb containing all the voltage sources at the branches. Solving (8) for in +1 yields in +1 = L t + R 2 −1 L t − R 2 in + e n+1 2 + MT v n+1 2 . (9) Equations (7) and (9) can then be used in place of (2) and (4) as the update equations to calculate the voltage and currents at each time step. The advantage of the vector-matrix formulation lies in its ability to accurately predict if a time step will be stable. To see this, we return to (7) and (9) and expand them to get v n+1 2 = P+ P − v n−1 2 − P+ M in + P+ h n (10) in +1 = Q+ Q − i n +Q+ M T v n+1 2 + Q+ e n+1 2 (11) where we have made the definitions P+ = C t + G 2 −1 P− = C t − G 2 (12) Q+ = L t + R 2 −1 Q− = L t − R 2 . (13) Substituting (10) into (11) and rearranging the terms, we obtain in +1 = Q+ M T P+ P − v n−1 2 + Q+ Q − − Q+ M T P+ M in +Q+ e n+1 2 + Q+ M T P+ h n . (14) l i3 l i2 l ik l i1 H i G i C i B ikV k S ipl p V i Fig. 3. Node topology with dependent sources. Equation (15) defines a discrete linear time invariant (DLTI) system in the form of x(t + 1) = Ax(t) + Bu(t). (16) Theorem 1: The DLTI given in (16) is asymptotically stable if and only if all the eigenvalues of A have magnitude strictly smaller than 1. The reader is referred to [21] for a proof of this theorem. Comparing (1 5) and (16), we define matrix A as A = P+ P − −P+ M Q+ M T P+ P − Q+ Q − − Q+ M T P+ M (17) and call it the amplification matrix since in the absence of input, the voltages and the currents in the circuit will be amplified by matrix A at each time step. From Theorem 1, we see that all the eigenvalues of the amplification matrix defined in (17) must have magnitude strictly smaller than 1 for the simulation to be stable. Thus, we can use the amplification matrix to predict the stability of a time step t. IV. DE PENDENT SO URCES In this section, we develop the voltage and current update equations in the presence of dependent sources, and the resulting modification to the amplification matrix. Fig. 3 shows the node topology with a voltage-controlled current source (VCCS) and a current-controlled current source (CCCS) connected to it. Writing the KCL at the node, in semi- implicit form, gives Ci ⎛ ⎝ V n+1 2 i − V n−1 2 i t ⎞ ⎠ + G i ⎛ ⎝ V n+1 2 i + V n−1 2 i 2 ⎞ ⎠ − H n i −Bi k ⎛ ⎝ V n+1 2 k + V n−1 2 k 2 ⎞ ⎠ − Si p I n p = − Mi k=1 I n i k (18) where Bi k is the coefficient of the VCCS at node i due to node k and Si p is the coefficient of the CCCS at node i due to

uations (1 0) and (14) can then be grouped together to o v n+1 2 in +1 = P+ P − −P+ M Q+ M T P+ P − Q+ Q − − Q+ M T P+ M × v n−1 2 + 0 P+ e n+1 2 .

× v n−1 2 in + 0 P+ Q+ Q+ M T P+ e n+1 2 hn . (15)

form as 

C v n+1 2 −v n−1 2 t + 1 2 G v n+1 2 + v n−1 2 − hn

− 1 2 B v n+1 2 + v n−1 2 − Sin = −Min . (19)

1450 IEEE TRANSACTIONS ON COMPONENTS, PACKAGING AND MANUFACTURING TECHNOLOGY, VOL. 1, NO. 9, SEPTEMBER 2011

V i V j l ij L ij R ij E ij T ijkT k Z ijpql pq + − + − + − Branch topology with dependent sources. can be rearranged to read Length 10 cm TLINE 1 50 50 50 External network L 1 250 nH/m C 1 100 nH/m R 1 1 /m

hich can be rearranged to read C v n+1 2 −v n−1 2 t + 1 2 G′ v n+1 2 + v n−1 2 − hn = −M′ in (20)

Fig. 5. Transmission line connected to an external network.

t 2 where G′ = G − B and M′ = M − S. (21) Solving (20) for vn +1/2 yields v n+1 2 = C t + G′ 2 −1 C t − G′ 2 v n−1 2 + hn − M′ in (22) which is the voltage update equation in the presence of dependent sources. Fig. 4 shows the branch topology with a voltage-controlled voltage source (VCVS) and a current-controlled voltage source (CCVS) connected to it. KVL at the branch, in semi-implicit form, gives V n+1 2 i − V n+1 2 j = L ij I n+1 i j − I n i j t + Ri j I n+1 i j + I n i j 2 −E n+1 2 i j − Ti j k V n+1 2 k − Z i j pq I n+1 pq + I n pq 2 (23) where Ti j k is the coefficient of the VCVS at branch ij due to node k, and Z i j pq is the coefficient of the CCVS at branch ij due to branch pq. Writing (23) in vector-matrix form and rearranging the terms, we obtain MT ′ v n+1 2 = L t in +1 −in + R′ 2 in +1 + in − e n+1 2 (24) where MT ′ = MT + T and R′ = R − Z. (25) Solving (24) for in +1 yields in +1 = L t + R′ 2 −1 L t − R′ 2 in + e n+1 2 + MT ′ v n+1 2 . (26) Equations (22) and (26) then give the new update equations for circuits with dependent sources. Note that in the absence of dependent sources, all the G’, M’, MT ’, and R’ will converge to G, M, MT ,and R, and (22) and (26) will converge to (7) and (9) as expected. In order to analyze the stability of a time step in the presence of dependent sources, we proceed as in Section III, to obtain the new amplification matrix A′, where we now have A′ = P′+ P ′− −P′+ M ′ Q′+ M T ′ P′+ P ′− Q′+ Q ′− − Q′+ M T ′ P′+ M ′ (27) 0.01 0.01 50 50 50 1 pF 1 pF 1 cm 2.5 nH 2.5 nH 0.025 nH TLINE 1 0.025 nH External network 0.025 nH 0.01 pF 0.01 pF 0.01 pF Fig. 6. LIM enabled circuit. where P′+ = C t + G′ 2 −1 P′− = C t − G′ 2 (28) Q′+ = L t + R′ 2 −1 Q′− = L t − R′ 2 . (29) From Theorem 1, we see that all the eigenvalues of the amplification matrix A’, defined in (27), must have magnitude strictly smaller than 1 for the simulation with dependent sources to be stable. This is written compactly as follows: λ i A′ (t) < 1 i = 1, 2, . . . , Nn + Nb . (30) Thus, we can use the new amplification matrix A’, to predict the stability of a time step t in the presence of dependent sources. V. SI MULATING CI RCUITS WITH PA RTITIONS OF DI FFERENT LA TENCIES In this section, we present a robust method to simulate circuits with partitions of different latencies. We first illustrate the motivation of the method via an example. Consider a case where LIM is used to simulate a circuit consisting of a transmission line TLINE 1 connected to a purely resistive external network as shown in Fig. 5. The transmission line has RLCG values shown in Fig. 5 where for simplicity we have assumed that G = 0 such that the method presented in [3] for selecting the time step for an RLC circuit can be applied. In order to simulate this circuit in LIM, we model the transmission line with 10 segments of RLC lumped elements, and insert fictitious latency elements into the external network

GOH et al.: PARTITIONED LATENCY INSERTION METHOD 1451

Start For partitions 1, 2, ..., N part, determine maximum time step, t1 , t2 , ..., tN part . Select smallest time step as the main simulation time step, t. Start transient simulation, t 0. Update all particions in first run. For n 1,2, ..., N part: if (t/△t mod △tn / △t0), update partition n.* t t + △t t ≥ t stop Yes End transient simulation. End No 50 14.53 10 M 2.3 50 47.3 43.2 nH 10 M 4.53 21.2 5.3 10 pF 5 pF 2 10 pF 5 pF 0.02 V2 1.8 l1 –3 1 3 4 22 nH 21.2 nH 32.2 nH 32.4 nH 1.2 nH + − +− Fig. 8. Circuit in example A. This suggests that the section with higher latency can be simulated with a larger time step without violating the stability criteria. Consider then the following method for simulating circuits with partitions of different latencies. First, a stable time step is determined for each partition. In the case of an RLC or a GLC circuit, the method in [3] and [19] is employed as shown in (31). However, for a general circuit (or in the presence of dependent sources), (31) cannot be applied and the more general numerical method presented in Theorem 1

Fig. 7. Simulation algorithm for partitioned LIM.

as shown in Fig. 6, where the fictitious elements have been made small so as not to affect the accuracy of the solution.

The time step required for a stable simulation of this RLC circuit can then be shown to be [3]

t < √ 2 N nmin i=1 ⎛ ⎝ Ci Mi M imin p=1 L i, p ⎞ ⎠

< √ 2 N nmin i=1 ⎝ Ci Mi M imin p=1 L i, p ⎠ < √ 2 0.01 p 3 0.025n = 4.08 × 10− 13 s

< √ 2 0.01 p 3 0.025n = 4.08 × 10− 13 s (31)

where L i, p denotes the value of the pth inductor connected to node i . Notice that in this case, the L and C of the external network completely determine the maximum time step. In other words, the maximum time step to ensure stability is dictated by the section with the smallest latency. However, note that if we had considered a circuit with only the transmission line TLINE 1, the maximum time step would have been

, the maximum time step would have been t < 2.5n · 1 p = 5 × 10− 11 s. (32)

must be used. Once all the time steps have been determined, the smallest time step is used in LIM to simulate the circuit, but each partition is updated only as needed, depending on its maximum stable time step. This results in a computationally efficient algorithm, with large speed-ups in the simulation time, especially when the partition with the smallest latency is small compared to the rest of the circuit. The method is summarized in Fig. 7.

VI. N UMERICAL R ESULTS

In this section, the methods presented in Section IV and V are applied to perform simulations of circuits using LIM in the presence of dependent sources and with partitions of different latencies. First, the formulation in Section IV is used to simulate a circuit with four dependent sources (VCCS, CCCS, VCVS, and CCVS). In order to validate the method, the same circuit is simulated in SPECTRE [22], a commercial circuit solver from Cadence Design Systems utilizing the modified nodal analysis (CS-MNA) method, and the results are compared. Next, the usage of multiple time steps is depicted with an example circuit with partitions of different latencies. Speed improvements over the conventional LIM will be illustrated.

A. Dependent Sources

In this example, the circuit shown in Fig. 8 is simulated in the LIM environment. It is assumed that all the branches and IEEE TRANSACTIONS ON COMPONENTS, PACKAGING AND MANUFACTURING TECHNOLOGY, VOL. 1, NO. 9, SEPTEMBER 2011 (a)

6 5 4 3 2 1 0 0 0.2 0.4 Time step (s) 0.6 0.8 1 X: 6.8643-011 Y: 1 V 1 ( V o l t s ) 0.5 0.4 0.3 0.2 0.1 0 −0.1 −0.2 0 5 10 15 20 25 30 35 40 LIM CS-MNA

1.005 × 10 −10

Time (ns)

(a)

max (eig(A))

max (eig(A))

1452 1 0.995 0.99 (b)

0 0.2 0.4 Time step (s) − 10 0.6 0.8 1 X: 6.8643-011 Y: 1 V 4 ( V o l t s ) 0.5 0.4 0.3 0.2 0.1 0 −0.1 −0.2 0 5 10 15 20 25 30 35 40 LIM CS-MNA

× 10 −10 Fig. 9. Sweep of eigenvalues of the amplification matrix, A. (a) Broad view. (b) Expanded view.

the nodes in the circuit have inherent latencies as shown in the figure such that no fictitious elements have to be inserted. The input is a current source with a single trapezoidal pulse of rise and fall times equal to 1 ns and a pulse width of 4 ns. The maximum amplitude is 0.02 A. In order to validate Theorem 1 and the subsequent result in (30), a sweep of the eigenvalues of the amplification matrix A is performed and the maximum time step for stability is determined from where the magnitude of the maximum eigenvalue equals 1. This is shown in Fig. 9. Note that in practice, this process can be time consuming, especially when the circuit under consideration is large. In that case, the circuit can be partitioned into multiple segments, and the method presented in Section V can be used to simulate the different partitions with different time steps. Also, a more effective search algorithm can be employed to determine the maximum time step.

From Fig. 9, the maximum time step is determined to be t max < 6.864 × 10 −11 s. We then perform two transient simulations, first using a time step slightly smaller than the maximum time step, and then using a time step slightly larger Time (ns)

(b) Fig. 10. Simulation of circuit in Fig. 8 with  t = 6.8×10 −11 s. (a) Voltage at node 1. (b) Voltage at node 4.

V o l t a g e ( V ) 1.5 1 0.5 0 0.5 1 −1.5 0 5 10 15 Time (ns) 20 V4 V1 × 109 g. 11. Simulation of circuit in Fig. 8 with △ t = 6.9 × 10− 11 s.

than the maximum time step. Plots of the resulting waveforms at the input (node 1) and output (node 4) are shown in Fig. 10. We see that the simulation using the properly chosen time step GOH et al.: PARTITIONED LATENCY INSERTION METHOD

1453

32.2 nH 1a 50 14.53 14.53 10 M 10 M 10 M 0.514 b−3c 0.02 1.8 3V2 c V2 c I4 b−3c 10 pF 4a 4b 4c 5 pF 0.05 pF 5 pF 10 M 5 pF 10 M 0.05 pF 1 0 M 5 pF 50 Partition 1 Partition 2 Partition 3 10 pF 50 0.1 pF 50 10 3a 2a 2b 2c 3b 3c 5.3 22 nH 1.2 nH 0.012 nH 1.2 nH 32.4 nH 0.324 nH 32.4 nH 45.3 2.3 2.3 2.3 21.2 nH 21.2 43.2 nH 47.3 43.2 nH 47.3 43.2 nH 47.3 0.22 nH 4.53 0.212 nH 21.2 22 nH 4.53 21.2 nH 21.2 32.2 nH 5.3 0.322 nH 5.3 − − + +

10 pF Circuit in example B.

results in a stable and accurate solution, which can be seen from the comparison with the CS-MNA shown in Fig. 10. On the other hand, the simulation using the time step slightly larger than t max results in an unstable simulation as can be seen in Fig. 11. Note that selecting a time step to ensure stability does not necessarily ensure accuracy. In general, the time step must also be small enough for sufficient accuracy. However, typically for an LIM simulation, the time step to ensure stability is small enough such that the accuracy is also preserved.

V(Volts)

Fig. 12.

In this example, the circuit in Fig. 12 is simulated in the LIM environment. The circuit consists of three partitions detailed as follows.

  1. Partition 1: High-latency partition. 2) Partition 2: Low-latency partition. (In practice, this could

be a partition with no latency, whereby small fictitious elements have been inserted to enable LIM.) 3) Partition 3: Dependent sources. Using the method in Sections III and IV, the maximum time

step of each partition is determined to be t1 = 1.0486 × 10− 10 s, t2 = 1.07 × 10− 12 s, and t3 = 6.741 × 10− 11 s,

corresponding to partitions 1, 2, and 3, respectively. Note that we have chosen the time steps to be the integer multiples of the smallest time step (in this case t 2 ) as mentioned in Section V.

The circuit is then simulated using the algorithm in Fig. 7 for performing LIM with partitions of different latencies, that is, partitioned latency insertion method (PLIM), and the results at the input (node 1a) and output (node 4c) are shown in Fig. 13. Next, the same circuit is simulated using the traditional LIM with time step t = t 2 = 1.07 × 10 −12 s and the results are also plotted in Fig. 13. No loss in accuracy is observed when using PLIM compared to the regular LIM.

Next, PLIM is used to simulate a large circuit where the partition with the smallest latency is small compared to the rest

V 1 a ( V o l t s ) 0.4 0.3 0.35 0.2 0.25 0.1 0.15 0 −0.05 0.05 −0.1 0 5 10 15 20 Time (ns) (a) 25 30 35 40 V 4 c ( V o l t s ) 0.25 0.2 0.15 0.1 0.05 0 −0.05 −0.1 0 5 10 15 20 Time (ns) (b) 25 30 35 40 LIM PLIM LIM PLIM

Fig. 13. Simulation of circuit in Fig. 12. (a) Voltage at node 1a. (b) Voltage at node 4c.

of the circuit. To construct this circuit, partition 1 is cascaded N times and the simulation time is recorded for PLIM and LIM. The results are summarized in Table I. We observe that 1454 IEEE TRANSACTIONS ON COMPONENTS, PACKAGING AND MANUFACTURING TECHNOLOGY, VOL. 1, NO. 9, SEPTEMBER 2011 TABLE I C OMPARISON OF R UN T IMES N LIM (s) PLIM (s) Speed-up

Table 2 · 4 columns × 7 rows · p.8–8 · CSV
NLIM (s)PLIM (s)Speed-up
10.110.0111.0
100.230.0211.5
1001.400.0346.7
5007.150.0889.4
100013.520.1590.1
200026.210.2893.6
500064.520.6894.9

5000 64.52 0.68 94.9 when the sizes of the partitions are comparable, a small speedup is obtained when using PLIM. On the other hand, when the partition with the smallest latency is small compared to the rest of the circuit, a large speed-up is obtained which approaches the limit of t large /t min where t large is the time step of the largest partition and t min is the smallest time step in the circuit, which also dictates the maximum time step of the regular LIM.

VII. C ONCLUSION

An improved version of the LIM, called PLIM, has been proposed. The PLIM is capable of simulating large circuits with partitions of different latencies significantly faster than the conventional LIM. The LIM method has also been extended to handle dependent sources, and a general stability condition for selecting the time step of the simulation has been shown. The validity of the method has been verified and significant speed-ups were observed when using the new method.

R EFERENCES

[1] J. E. Schutt-Ainé, “Latency insertion method (LIM) for the fast transient

simulation of large networks,” IEEE Trans. Circuits Syst. I: Fundam. Theory Appl., vol. 48, no. 1, pp. 81–89, Jan. 2001. [2] L. W. Nagel, “SPICE2: A computer program to simulate semiconductor

circuits,” Dept. Electr. Eng. Comput. Sci., Univ. California, Berkeley, Tech. Rep. UCB/ERL M520, 1975. [3] S. N. Lalgudi, M. Swaminathan, and Y. Kretchmer, “On-chip power-grid

simulation using latency insertion method,” IEEE Trans. Circuits Syst. I, vol. 55, no. 3, pp. 914–931, Apr. 2008. [4] Z. Deng and J. E. Schutt-Ainé, “LIM-SPICE for the analysis of power

distribution networks,” in Proc. 9th IEEE Workshop Signal Propagat. Interconn., Garmisch-Partenkirchen, Germany, May 2005, pp. 17–20. [5] Y. Inoue, T. Sekine, and H. Asai, “GPGPU-based latency insertion

method: Application to PDN simulations,” in Proc. IEEE Electr. Des. Adv. Packag. Syst. Symp., Shatin, Hong Kong, Dec. 2009, pp. 1–4. [6] T. Watanabe and H. Asai, “Equivalent circuit modeling of multilayered

power/ground planes for fast transient simulation,” in Proc. IEEE Eur. Conf. Exhibit. Des. Autom. Test, Dresden, Germany, Mar. 2010, pp. 1153–1158. [7] D. Klokotov and J. E. Schutt-Ainé, “Latency insertion method for the

analysis of steady state on-chip power distribution networks and transient simulation of lossy interconnects,” in Proc. IEEE Asia-Pacific Microw. Conf., Macau, China, Dec. 2008, pp. 1–4. [8] D. Klokotov and J. E. Schutt-Ainé, “Extensions of the latency insertion

method (LIM) to DC analysis of power supply networks and modeling of circuit interconnects with frequency-dependent parameters,” in Proc. 59th IEEE Electron. Comp. Technol. Conf., San Diego, CA, May 2009, pp. 1624–1629.

[9] T. Sekine and H. Asai, “Block latency insertion method (block-LIM) for

fast transient simulation of tightly coupled transmission lines,” in Proc. IEEE Int. Electromag. Compat., Austin, TX, Aug. 2009, pp. 253–257. [10] Y. Inoue, T. Sekine, and H. Asai, “Parallel-distributed block-LIM-based

fast transient simulation of tightly coupled transmission lines,” in Proc. 60th IEEE Electron. Comp. Technol. Conf., Las Vegas, NV, Jun. 2010, pp. 657–662. [11] D. Klokotov and J. E. Schutt-Ainé, “Transient simulation of lossy

interconnects using the latency insertion method (LIM),” in Proc. IEEE Electr. Perform. Electron. Packag., San Jose, CA, Oct. 2008, pp. 251– 254. [12] Z. Deng, J. E. Schutt-Ainé, J. Tan, C. Kumar, and D. Milosevic, “Latency

insertion method with frequency dependent effect,” in Proc. 1st IEEE Electron. Systemintegr. Technol. Conf., Dresden, Germany, Sep. 2006, pp. 503–506. [13] J. E. Schutt-Ainé, D. Klokotov, P. Goh, J. Tan, F. Al-Hawari, P. Liu,

and W. Dai, “Application of the latency insertion method to circuits with blackbox macromodel representation,” in Proc. 11th IEEE Electron. Packag. Technol. Conf., Singapore, Dec. 2009, pp. 92–95. [14] R. Gao and J. E. Schutt-Ainé, “Improved latency insertion method

for simulation of large networks with low latency,” in Proc. IEEE Electr. Perform. Electron. Packag., Monterey, CA, Oct. 2002, pp. 37–40. [15] H. Asai and N. Tsuboi, “Multi-rate latency insertion method with

RLCG-MNA formulation for fast transient simulation of largescale interconnect and plane networks,” in Proc. 57th IEEE Electron. Comp. Technol. Conf., Reno, NV, May–Jun. 2007, pp. 1667– 1672. [16] N. Tsuboi and H. Asai, “Multi-rate latency insertion method for the

fast transient simulation of large networks with nonlinear termination,” in Proc. IEEE Electr. Perform. Electron. Packag., Scottsdale, AZ, Oct. 2006, pp. 137–140. [17] Z. Deng and J. E. Schutt-Ainé, “Stability analysis of latency insertion

method (LIM),” in Proc. 13th IEEE Electr. Perform. Electron. Packag., Portland, OR, Oct. 2004, pp. 167–170. [18] K. Yee, “Numerical solution of initial boundary value problems involv-

ing Maxwell’s equations in isotropic media,” IEEE Trans. Antennas Propagat., vol. 14, no. 3, pp. 302–307, May 1966. [19] S. N. Lalgudi and M. Swaminathan, “Analytical stability condition of

the latency insertion method for nonuniform GLC circuits,” IEEE Trans. Circuits Syst. II, vol. 55, no. 9, pp. 937–941, Sep. 2008. [20] J. E. Schutt-Ainé, “Stability analysis of the latency insertion method

using a block matrix formulation,” in Proc. IEEE Electr. Des. Adv. Packag. Syst. Symp., Seoul, Korea, Dec. 2008, pp. 155–158. [21] J. P. Hespanha, Linear Systems Theory. Princeton, NJ: Princeton Univ.

Press, 2009. [22] Virtuoso Advanced Analysis Tools User Guide, Cadence 5.1.41 Spectre

Guide Documents. (2008). Cadence, Berksire, U.K. [Online]. Available: http://www.cadence.com

Patrick Goh received the B.S. and M.S. degrees in electrical engineering from the University of Illinois at Urbana-Champaign (UIUC), Urbana, in 2007 and 2009, respectively, where he is currently pursuing the Ph.D. degree. He has held a Teaching Assistant position with the Department of Electrical and Computer Engineering, UIUC, since August 2007. His current research interests include circuit simulation for high-speed interconnects, modeling, and computer-aided design tools. Mr. Goh is a reviewer for the IEEE TR ANSACTIONS ON AD VANCED PA CKAGING and the IEEE TR ANSACTIONS ON CO MPONENTS, PA CKAGING, AND MA NUFACTURING TE CHNOLOGY.

GOH et al.: PARTITIONED LATENCY INSERTION METHOD

José E. Schutt-Ainé (S’86–M’86–SM’98–F’07) received the B.S. degree in electrical engineering from the Massachusetts Institute of Technology (MIT), Cambridge, in 1981, and the M.S. and Ph.D. degrees from the University of Illinois at Urbana- Champaign (UIUC), Urbana, in 1984 and 1988, respectively. He joined Hewlett-Packard Technology Center, Santa Rosa, CA, as an Application Engineer involved with microwave transistors and high- frequency circuits. In 1983, he joined UIUC, and then joined the Electrical and Computer Engineering Department as a member of the Electromagnetics and Coordinated Science Laboratories where he currently specializes in the study of signal integrity for high-speed digital and high-frequency applications. He has been a Consultant for several corpo- rations. His current interests include spectrum from microwave measurements to the generation of computer-aided design tools for electronic systems. Dr. Schutt-Ainé was the recipient of several research awards including the National Science Foundation (NSF) Major Research Instrumentation Award in 1991, the National Aeronautics and Space Administration Faculty Award for Research in 1992, the NSF Mid-Career Advancement Award in 1996, and the UIUC-National Center for Superconducting Applications Faculty Fellow Award in 2000. He is currently serving as Editor-in-Chief of the IEEE TR ANSACTIONS ON AD VANCED PA CKAGING. Dmitri Klokotov received the B.S. degree in physics from Saratov State University, Saratov, Russia, in 2001, and the M.S. degree in electrical and com- puter engineering from the University of Illinois at Urbana-Champaign, Urbana, in 2007. He is currently pursuing the Ph.D. degree. His current research interests include numeri- cal methods, computational electromagnetics, circuit simulation, interconnect analysis, and signal and power integrity. Ping Liu was born in China, in 1979. She received the B.S. and M.S. degrees in communications engi- neering from Beijing Jiao Tong University, Beijing, China, in 2000 and 2003, respectively, and the Ph.D. degree in electromagnetic fields and microwave engineering from Shanghai Jiao Tong University, Shanghai, China, in 2006. She is now with Silicon Package Board Division, Cadence Design Systems Inc., Shanghai, working on the model extraction and circuit simulation tools research and development in high-speed circuits and systems. Her current research interests include field solver modeling of high- speed interconnects, large-scale circuit system simulation, and power and signal integrity analysis in high-speed circuits. Wenliang Dai received the M.S. degree from the University of Electronic Science and Technology of China, Chengdu, China, in 2001, and the Ph.D. degree in electronic engineering from Shanghai Jiao Tong University, Shanghai, China, in 2004. He was with the Silicon-Package-Board Research and Development Center, Cadence Design Systems Inc., San Jose, CA, from 2004 to 2011, as a Senior Member of the Consulting Staff. He is currently with Xpeedic Technology Inc., Issaquah, WA. He has also published more than 20 journal and confer- ence papers as first author in the IEEE TR ANSACTIONS ON MI CROWAVE TH EORY AND TE CHNIQUES, the IEE PR OCEEDINGS ON MI CROWAVES, AN TENNAS AND PR OPAGATION, the Institute of Electronics Information and Communication Engineers Transactions on Electronics, and the International Journal of Electronics. He had one issued and three pending U.S. patents for high-speed circuit analysis. His current research interests include com- putational electromagnetic fields, microwave and millimeter-wave circuitry design, parameter extraction for on-chip interconnects (complementary metal- oxide-semiconductor process), radio frequency (RF) components, design and measurement of RF-integrated circuits and high-speed integrated circuits, and signal/power integrity analysis for high-speed circuit systems in chip-package- board codesign flow. Dr. Dai is a Reviewer for the IEEE TR ANSCTIONS ON AN TENNAS AND PR OPAGATION, the IEEE TR ANSACTIONS ON MI CROWAVE TH EORY AND TE CHNIQUES, the Institute of Engineering and Technology Proceeding, and the Design Automation Conference.

Feras Al-Hawari received the B.S. degree in elec- trical engineering from Jordan University of Science and Technology, Al Ramtha, Jordan, in 1993, the M.S. degree in computer engineering from Florida Institute of Technology, Melbourne, in 1995, and the Ph.D. degree in electrical engineering from North- eastern University, Boston, MA, in 2007. He joined Cadence Design Systems Inc., Chelms- ford, MA, in 1995. Currently, he is a Senior Member of the Consulting Staff as well as a Technical Lead for the circuit simulation and signal integrity analy- sis technologies in the Allegro Printed Circuit Board (PCB) SI Research and Development Group. Recently, he developed efficient and accurate methods to model and simulate S-parameter black boxes, multiconductor transmission lines, and I/O buffer information specification devices. He also architected the bus analysis flow that is used to design and verify source synchronous memory interfaces such as double data rate type three. He filed six patents in the past two years. His current research interests include signal integrity, PCB design, circuit simulation, modeling of I/O devices and interconnects, and multithreaded and distributed computing.