Fast Timing Analysis of Plane Circuits via Two-Layer
CNN-based Modeling
Yuichi Tanji

Hideki Asai

Masayoshi Oda, Yoshifumi Nishio

Akio Ushida

Kagawa University
tanji@eng.kagawa-u.ac.jp

Shizuoka University
hideasai@sys.eng.shizuoka.ac.jp

Tokushima University
nishio@ee.tokushima-u.ac.jp

Tokushima Bunri University
ushida@fe.bunri-u.ac.jp

Abstract— A fast timing analysis of plane circuits via two-layer CNNbased modeling, which is necessary for the solution of power/signal
integrity problems in printed circuit boards and packages, is presented.
Using the new notation expressed by the two-layer CNN, more than
1500 times faster simulation is achieved, compared with Berkeley SPICE(ngspice). In CNN community, CNNs are generally simulated by explicit
numerical integration algorithms such as the forward Euler and RungeKutta methods. However, since the system of the two-layer CNN becomes
stiff, we cannot analyze the CNN by using an explicit numericalintegration algorithm. Hence, to analyze the two-layer CNN and reducethe computational cost, the leapfrog method is introduced in this paper.
This procedure would open a CNN application up to electronic design
automation area.

I. I NTRODUCTION
VLSI implementations, potential applications for image processing, and nonlinear wave phenomena of CNNs have attracted many
interests in the last two decades. As one of the studies, the nonlinear
wave phenomena have been analyzed via CNNs [1], [2], [3], wherea discrete model of partial differential equation is expressed by
CNN and the CNN universal machine [4] simulates the phenomena
quickly using the features of custom hardware. In viewing the CNN
simulations from engineering application sides, the ability of solving
partial differential equations quickly is very attractive and there may
be various applications.
In this paper, we analyze the plane circuits using CNN, which isnecessary for ensuring power/signal integrity of VLSIs, packages, andprinted circuit boards in the high-speed electronic systems [5], [6].
To address the issue of signal/power integrity, electromagnetic fieldshould be analyzed. Then, the discrete models of the Maxwell’s orHelmholtz’s equations involve the inductance effects, whereas almostof CNNs do not have the inductance effects. Hence, we introduce thetwo-layer CNN [7] to model the plane circuits using the coupling
templates.
The CNN universal machine simulates CNNs by the forward Euler
method. However, the linear passive circuits as a model of VLSI,
package, printed circuit board are stiff, which prohibits the use of
the explicit numerical integration methods such as forward Euler
method. Alternatively, the implicit numerical integration methods
such as backward Euler, backward difference, and Gear methods [8],which are used in SPICE-like simulators, are applicable to solving
the stiff problems, but these methods are computationally inefficientsince they need to solve a set of equations simultaneously at each time
point. To reduce the computational costs, we introduce the leapfrog
method [9], [10], where the state vectors in the first and second layers
are decoupled and updated by turns in the manner as the forward
Euler method. This method is a derivative of FDTD method [11]which is known as a Maxwell’s solver. In the illustrative examples, it
is shown that the proposed procedure via the two-layer CNN-basedmodeling is 1,553 times faster than Berkely SPICE (ngspice). Thismeans that we can expect the further speed up if these computations

0-7803-9390-2/06/$20.00 ©2006 IEEEare carried out on a hardware accelerator as the CNN universal
machine.
II. T WO -L AYER CNN-BASED M ODELING OF P LANE C IRCUITS
Ensuring the signal/power integrity of packages and printed circuit boards in high-speed electronic systems needs the analysis ofplane circuits, where the physical phenomena are governed by theHelmholtz’s equations which are the Maxwell’s equations on Lorentz
or Coulomb gauge. However, since simulating the Helmholtz’s equations requires huge CPU costs, the plane circuits are approximatedby linear passive R, L, C, and G elements shown in Fig. 1 [12]. The
normalized KCL equation at the node and KVL one of the branch
consisting of a resistor R and an inductor L are represented as follows,  
                          




(1)

(2)

where



 



(3)



and  and  show the actual and normalized times, respectively.
Let us consider expressing (1) and (2) by the two-layer CNN shownin Fig. 2. The state equations of the two-layer CNN are written by                                   









 

     

(4)  



 



      

(5)

where    is -neighborhood of cell  as     .   ,   , and   
are the internal state, the output, the input of a cell   in thefirst layer CNN, respectively.   ,   , and    are theinternal state, the output, the input of a cell   in the second layer.
  ,    , and     are the feedback,



3738







 





ISCAS 2006

j-1

jvi-1, j

j+1
i-1
L
R

L

vi, j-1

R

L

vi, j

R vi, j+1

i

ii, j
L
C

G

R

vi+1, jFig. 1.

i+1Circuit model of plane circuit.

Fig. 2.

M  





 










  

    













 


N

control, coupling templates in the -th layer CNN, respectively [7].
The output functions of the two-layer CNN are described by  

Two-Layer CNN.

(6)
(a)

(7)

Comparing the circuit equations (1) and (2) with the CNN ones (4)and (5), we can describe the cloning templates for the plane circuits
as





  ¼



 

 





  ¼  
 
 











 

Port1

(b)
(8)
Fig. 3.
circuit.

 



 

 





(9)






    

(10)
(11)

III. L EAPFROG M ETHOD
In the CNN universal machine [4], the dynamics of CNN issimulated by using the forward Euler method. However, if the circuit
is stiff, the forward Euler method may diverge during the transient
analysis. For example, consider an RLC series circuit. The admittance  of the circuit is given by      



(12)

.
The poles of (12) are approximated by    and,    Using the typical parameters     for the package [6], we obtain , and   Modeling of plane circuit. (a)Example plane circuit. (b)Equivalentwhere the matrices,, andare the matrix representation  ,    , and    , respectively. Sinceofthe plane circuit shown in Fig. 1 is linear, the output functions (6)and (7) are redefined by the linear ones as    

Rout





the approximated poles and    , which implies
the RLC series circuit is stiff and the forward Euler method used in
the CNN universal machine is not sufficient for solving this problem.
We simulated the two-Layer CNN corresponding to the plane circuit
cells andshown in Fig. 3(a), where the circuit is modeled byapproximated by the RLC circuit shown in Fig. 3(b). Figure 4(a)shows the transient voltage waveform on the output resister  
in Fig. 3(b) when a pulse waveform is given at “Port1”, where thetransient waveform was calculated by the forward Euler method. For acomparison, the result is compared with one obtained from Berkeley
SPICE. The response obtained from the forward Euler method isvibrated violently and the simulation will break down obviously.
Although the nonlinear wave propagation phenomena of CNNs are
one of the attractive fields of CNN [2], the conventional forward Euler
method or the Runge Kutta method is not necessarily applicable to all
the cases as shown in this section. Instead of the explicit method, we
can use an implicit numerical integration method such as backward
Euler, backward difference, and Gear methods [8]. However, thesemethods need to solve a set of linear equations simultaneously, which
prohibits the application of these methods to the large scale problems.
To analyze the large scale and stiff circuits, we use the leapfrog
method [10] which is a derivative of FDTD method [11] for circuit
simulation [9].
From (10) and (11), a state in the first and second layer is equal
to the output itself. As shown in Fig. 2, the first and second layers
 ofinteract each other through the coupling templates    of (5). Therefore, the first and second layers(4) and   

3739



[volt]0.3

Forward Euler Method
1st Layer
2nd Layer
time

0.2

Leapfrog Method

0.1

1st Layer
2nd Layer

0

time

Euler
SPICE
0

1

2
[seconds]−9[1×10 ]

Fig. 5. Updated Timing of the state vectors in the forward Euler and leapfrog
methods.

(a)[volt]
0.3

0.2



0.1

0

CNN
SPICE
0

1

2
[seconds]−9[1×10 ](b)
Fig. 4.
Timing analysis results obtained by (a)forward Euler method(b)leapfrog method.

of the CNN are coupled through the state vectors in both layers.
These relations appear in    and   of (4) or   and    of (5).
In the leapfrog method, two coupled state vectors are alternately
solved. Hence, the updated timing of the first layer is being shiftedwith half time step to the second layer. On the other hand, when
the forward Euler method is used for simulating the CNN, the statevectors in both layers are updated simultaneously as shown in Fig.
5.
The update rules of the leapfrog method for the two-layer CNN
are described by    









   










                                        

a set of linear equations at each time point, differently from the caseof applying an implicit numerical integration method. As a result,the leapfrog method is much faster than the SPICE simulation whichuses an implicit numerical integration method for timing analysis.
cells using the leapfrog method.
We simulated the example of
Figure 4(b) shows the transient voltage waveform on the output
resister   shown in Fig. 3(b). To obtain the result, the time step
size is taken as 100 times larger than the forward Euler method in
the case of Fig. 4(a), which means that the leapfrog method is robust
for a stiff problem, though any implicit method is not used.
It should be noted that the leapfrog method is restricted by the
Courant condition which gives us the allowable largest time step size in order to ensure the stability. The Courant condition is obtained
as [9]

  
 







                      

 



  

 



      









Since the state vectors are alternately updated, we do not have to solve

IV. E XAMPLES
To show the performance of the proposed method via two-layer
CNN-based modeling, the plane circuit shown in Fig. 3(a) was simulated. The plane circuit is divided into identical cells (hexahedrons)
which are modeled by an RLC  -model [6], and the equivalent circuit
is obtained as Fig. 3(b). Based on the electromagnetic theory, theparameters of the RLC  -model corresponding to the VLSI package,     , andare determined as        [6].
We calculated the transient responses of the CNN by the leapfrog
method and compared with Berkeley SPICE (ngspice) from thecomputational cost point of view. The CNN simulations were carriedout by Matlab 7 on Federa Core 3. The CPU times of CNN and
SPICE simulations were measured on Pentium 4 with 3 GHz clockand 1 GByte memory.
The linear circuit shown in Fig. 3(b) was driven by a current
source of 0.1 [ns] fall/rise time, 0.4 [ns] pulse width, 0.2 [ns] delaytime, 1.0 [ns] period, and 5 [mA] amplitude at “Port1”. The transient
analysis was carried out for the time interval from 0 [ns] to 2.0[ns] using 1 [ps] time step size. Table I shows the comparison ofcells, the proposed method via the twoCPU times. For
layer CNN-based modeling is 1,553 times faster than ngspice. To
investigate the accuracy of the simulation results, we calculated the cells using ngspice withtransient waveforms for the case of a variety of time step sizes. Figures 6(a) and 6(b) are the transient







(14)

(15)



where   and   are minimum inductance and capacitance,
respectively. If the normalized time of (3) is        ,. Therefore, putting thethe Courant condition becomes  time step size as     , we can obtain the discrete time model,
which is equivalent to the Discrete Time CNN (DT-CNN) [13], [14],of the two-layer CNN by (13) and (14).



(13)
 



3740



TABLE IC OMPARISON OF CPU TIMES FOR A PLANE CIRCUIT.
cells
10
10
20
20
40
40
80
80
160
160
320
320

elements
341
1281
4961
19521
77441
308481








CNN
0.53
0.74
1.79
6.25
32.68
152.09[V]
0.3

Speed-up
4.4
26.44
86.90
224.02505.991553.03equations of plane circuits are expressed by the two-layer CNN andthe dynamics of the two-layer CNN are alternately calculated by theleapfrog method. We can assume that these computations are carriedout on a hardware accelerator as the CNN universal machine. Since
the proposed method is sufficiently fast on a single processor, theCNN simulations on the hardware accelerator might be extremely
fast. The leapfrog method is based on the FDTD method [11].
Therefore, the hardware accelerator would be extended to full wave
analysis of electromagnetic field.

0.2

0.1

R EFERENCES

SPICE

0

CNN
0

1

−9

2

[×10 ]

2[×10 ][seconds]

(a)
[V]
0.3

0.2

0.1

SPICE

0

CNN
0

1
[seconds]−9(b)Fig. 6.
(b)withngspice2.33
19.567155.56
1400.1016535.75
236199.93

Transient responses calculated by SPICE with (a) [ps] and [ps], where the time step size in the CNN simulation is fixed [ps].

voltage waveforms at “Port1” using ngspice with 1 [ps] and 0.01[ps]time step sizes, respectively. Although “Port1” is driven by a current
source having a pulse waveform, the voltage waveform at “Port1” islargely degraded. It should be noted that the time step size of the
proposed method via two-layer CNN is fixed by 1 [ps]. We can seethat the simulation results by the proposed method is more accurate
than the ones by SPICE. Therefore, if the CPU times are evaluatedwith the same accuracy, the computational efficiency of the proposed
method becomes more remarkable than that listed in Tab. I. In thisexample, we do not consider any parallelism of CNN. Thus, if a
hardware accelerator for simulating the two-layer CNN is realized,
further speed-up is expected.

[1] T. Roska, L. O. Chua, D. Wolf, T. Kozek, R. Tetzlaff, and F. Puffer,“Simulating nonlinear waves and partial differential equations via cnn–part i,” IEEE Trans. on Circuits Syst., vol. 42, no. 10, pp. 807–815, 10
1995.
[2] L. O. Chua, “Passivity and complexity,” IEEE Trans. Circuits Syst.-I,
vol. 46, pp. 71–82, 1999.
[3] T. Roska, L. O. Chua, D. Wolf, T. Kozek, R. Tetzlaff, and F. Puffer,“Simulating nonlinear waves and partial differential equations via cnn–part ii,” IEEE Trans. on Circuits Syst., vol. 42, no. 10, pp. 816–820,
1995.
[4] L. O. Chua and T. Roska, “The cnn universal machine,” IEEE Trans.
Circuits Syst.-II, vol. 40, pp. 163–173, 1993.
[5] M. W. Beattie and L. T. Pileggi, “Modeling magnetic coupling for onchip interconnect,” Proc. Design Automation Conference 2001, 2001.
[6] T. Watanabe, K. Srinivasan, H. Asai, and M. Swaminathan, “Modelingof power distribution networks with retardation using the transmission
matrix method,” Proc. EPEP’04, 2004.
[7] Z. Yang, Y. Nishio, and A. Ushida, “Generation of various typesof spatio-temporal phenomena in two-layer cellular neural networks,”
IEICE Trans. Fundamentals, vol. E87-A, no. 4, pp. 864–871, 2004.
[8] L. O. Chua and P.-M. Lin, Computer-Aided Analysis of Electrical
Circuits: Algorithms and Computational Techniques. Englewood Cliffs:
Prentice-Hall, Inc., 1975.
[9] J. E. Schutt-Aine, “Latency insertion method (lim) for the fast transient
simulation of large networks,” IEEE Trans. Circuits Syst.-I, vol. 48, pp.
81–89, 2001.
[10] H. Kubota, Y. Tanji, T. Watanabe, and H. Asai, “Generalized method of
the time-domain circuit simulation based on lim with mna formulation,”
Proc. Custom Integrated Circuits Conference, 2005.
[11] K. S. Yee, “Numerical solution of intial boundary value problems involving maxwell’s equations in isotrophic media,” IEEE Trans. Antennas
Propagat., vol. 14, no. 4, pp. 302–307, 1966.
[12] N. Na, J. Choi, S. Chun, and M. Swaminathan, “Modeling and transient
simulation of planes in electromagnetic packages,” IEEE Trans. Comp.,
Packag., Manufact. technol. B, vol. 21, pp. 157–163, 1998.
[13] H. Harrer and J. T. Nossek, “Discrete-time cellular neural networks,”
Int. J. Circuit Theory and Applications, vol. 20, pp. 453–467, 1992.
[14] M. Ikegami and M. Tanaka, “Image coding and decoding by discrete
time cellular neural networks,” IEICE Trans., vol. J77-A, pp. 954–964,
1994.
[15] [Online]. Available: http://ngspice.sourceforge.net/

V. C ONCLUSIONSIn this paper, a fast timing analysis of the plane circuits using
the CNN-based modeling has been presented, where the Maxwell’s3741