APPLICATION OF EXTRAPOLATION ALGORITHMS IN NONLINEAR CIRCUIT SIMULATION AND OPTIMIZATION WITH SPICE OPUS Borut Wagner, Ärpäd Bürmen, Janez Puhan, Sašo Tomažič, Tadej Turna University of Ljubljana, Faculty of Electrical Engineering, Ljubljana, Slovenia Key words: extrapolation algorithms, circuit simulation, circuit optimization, integrated circuit design, SPICE. Abstract: In this paper the extrapolation algorithms for vector sequence acceleration are presented. Four extrapolation algorithms are described and their application to circuit simulation is discussed. Steady state evaluation times are compared for the presented extrapolation algorithms and the direct method on real-world test circuits. Results show/ that the most appropriate extrapolation algorithm for evaluating the steady state of a circuit is the epsilon algorithm. The epsilon algorithm was implemented in SPICE OPUS circuit simulator. The implemented epsilon algorithm was used for optimizing the steady-state response of a test circuit. The accelerated evaluation makes the optimization of steady-state response possible. Uporaba ekstrapolacijskih postopkov pri simulaciji in optimizaciji nelinearnih vezij s programskim paketom SPICE OPUS Kjučne besede: ekstrapolacijski postopki, simulacija električnih vezij, optimizacija električnih vezij, načrtovanje integriranih vezij, SPICE. Izvleček: V članku so predstavljeni ekstrapolacijski postopki, ki se uporabljajo za pospeševanje konvergence zaporedij. Opisani so štirje postopki in njihov način uporabe pri simulaciji električnih vezij. Podana je primerjava časov za računanje stacionarnega stanja testnih električnih vezij brez in z uporabo ekstrapolacijskih postopkov Za implementacijo v programski paket SPICE OPUS je bil izbran epsilon algoritem, ki se je izkazal za najbolj primernega. Postopek je bil uporabljen tudi pri optimizaciji testnega vezja. Zaradi hitrejšega izračuna samega stacionarnega stanja se je pohitril tudi celoten postopek optimizacije stacionarnega stanja in postal primeren za praktično uporabo. 1 Introduction Extrapolation algorithms for vector sequences /1,2,3,4/ are used for accelerating sequences that converge slowly. The limit of a sequence can be calculated efficiently by evaluating only a few terms of the sequence without the explicit knowledge of the sequence generator. Using an extrapolation algorithm and only few terms of the sequence, a new initial term of the sequence can be calculated. With the new initial term, furtherterms of the sequence are evaluated by the sequence generator. The procedure is iterated until the differences between consequent terms of the sequence are small enough to assume that we are close to the limit of the sequence. When computing the steady-state response /5/ of a nonlinear circuit all signals in the circuit are assumed to have the same fundamental frequency/and the period T = l/f. The circuit is simulated starting at some initial condition until steady state is reached. Simulation results x(0, t > 0 represent node voltages and branch currents of the circuit at time t. The sequence {xj," = x(iT)}, i = 0,1,2,3 is convergent if the circuit has a steady-state response with period T. To accelerate the computation of steady state, the circuit is simulated for n periods and the extrapolation method is used on vectors to compute the new in- tial vector Then the circuit is simulated starting with nitial conditions and the new sequence {xj'' = x(zT) = 0,1,2,3 is extracted from the response of the circuit. This is repeated Mimes until x^"' - xf' is small enough to assume the circuit is in steady state. The paper is organized as follows. In Section 2 a brief description of four extrapolation algorithms (epsilon algorithm, rho algorithm, theta algorithm and topological epsilon algorithm) is given. In Section 3 the simulation of electrical circuits with SPICE OPUS is presented. Problems that occur when steady-state response of circuits has to be computed are presented. The acceleration of the steady-state response computation by means of extrapolation algorithms is described. In Section 4 simulation times for the test circuits (Greinacher rectifier, narrow-band filter, switching power supply) are compared for the direct approach (transient analysis until all initial transients die off) and for the accelerated steady-state computation by means of extrapolation algorithms. Section 5 describes the implementation details of the selected extrapolation algorithm in SPICE OPUS. In Section 6, the implemented algorithm is used in the optimization of a test circuit. Section 7 concludes the paper. 2 Extrapolation algorithms Vector sequence {x«}, i = 0,1,2,3... (1) is generated from tlie initial vector using the sequence generator = F(x<''), i = 0,1,2,3... If the sequence {x<"} is convergent, the limit of the sequence is denoted by x. An extrapolation algorithm E generates a new vector sequence {x™,} , k = 0,1,2,3... with the following two steps k = 0,1,2,3... (2) and .(0 _ = F(x^'" 0. i = 1'2.3... for each k = 0,1,2,3... (3) The extrapolation algorithm generates the first term xf^*, of a new sequence {x^'],}, i = 0,1,2... from the +1 terms of sequence {x^'^}, i = 0,1,2...m^. For each k, n^ + \< d, d = dim(xf') has to be satisfied. If n,^+l> d the extrapolation algorithm is overdetermined. .(1) ,(2) '-1 .(«A-) '-1 .(0) .(1) .(2) '0 .("A-'0 .(0) .(1) .(2) .(«a-D '1 .(0) The sequence {x™,}, k = 0,1,2,3... generated by (2) and (3) converges faster than sequence (1) to the same limit x. Figure 1: Two-dimension array for the epsilon algorithm In the following subsections four extrapolation algorithms are described: epsilon algorithm, rho algorithm, theta algorithm and topological epsilon algorithm. The algorithms differ only in the definition of E. 2.1 Epsilon algorithm For each in (2) a two-dimension array depicted in Fig. 1 is formed by (4a) ^ 0 , i = 1,2,3... nA e; =xf,i = 0,l,2... n;< (4b) JO j = 0,1,2... «A--1 where i + j + 1 < «A (4c) The procedure described by (4), is the so-called epsilon algorithm /1 /. The inverse of the vector in (4c) is computed as x-'=- (5) If Ilk is an even number, e™ is the result of the epsilon algorithm, so the extrapolation function (2) is defined as Ü/^CO) „(1) „(2) (6) 2.2 Rho algorithm The rho algorithm /1/ is similar to the epsilon algorithm. For each k in (2) nk has to be even. The result is p™ obtained from p^'/ =0 , i= l,2,3...n, (7a) p; =x['li = 0,l,2...m. (7b) nt, j = 0,1,2... «A--I where 1 + j + 1 < «i (7c) The inverse of the vector in (7c) is calculated in the same manner as in (5). 2.3 Theta algorithm Extrapolation by theta algorithm /1 / (for an even Uk) is computed using the following equations = 0 , i = 1,2,3... Ilk nk , i = 0,1,2... nk, J = 0,1,2... — - 1 where i + 2j + 1 < n/t, 2 i = 0,1,2... nk , J = 0,1,2...'^- 1 where \ + 2] + 2 < nk, 2 The abbreviations in (8c) and (8d) are (8a) (8b) (8c) (8d) (0 (8e) (8f) and the inverses in (8c) and (8d) are calculated by (5). For each k and even nk the theta algorithm extrapolation function E is defined as (9) 2.4 Topological epsilon algorithm If the inverse of a vector x is defined as X = (y,x> (10) the inverse is the so-called inverse of vector x with respect toy. In the topological epsilon algorithm the inverses in odd and even terms are computed with respect to different vectors. For each interation k of the extrapolation algorithm, the topological epsilon algorithm /1/ is defined by £« = 0 , i = 1,2,3... nk .1 = 0,1,2... nk (11a) (11b) „(0 ^ eO'+l) + rik, J = 0,1,2...'^- 1 where i + 2j + 1 Rant .50E Vs .sin/lV/2.4GHz -!lNa -ilNa INI INI ■"'OUTi" .stage i C:0iV12 IN2 Nb 0UT2 stage2 — C:0M2i /-" I load I On A -^INb IN2 0UT2 h Figure 3: (a) Single stage of a Grelnacher rectifier (b) Implementation of a diode with an n-channel MOS. (c) Test circuit: two-stage Grelnacher rectifier. Fig. 3a represents one stage of the Grelnacher rectifier. Diodes in Fig. 3a are implemented as n-channel MOS transistors in O.ISjim TSMC technology (Fig. 3b). Two stages are connected together as depicted In Fig. 3c. At the in- put of the circuit a sinusoidal voltage source Vs with amplitude 1 V and frequency 2.4 GHz is connected in series with resistor = 50 Q. The output of the circuit is loaded with I load = /ö/x4. In Fig. 4 a narrow-band filter is depicted. At the input of the circuit (node 1) a sinusoidal voltage source V-,,, with amplitude 1 V and frequency 32767.41 Hz is connected. The output of the circuit is at node 4. The quartz crystal J/ is modelled with resistor Rs, inductor Lj and capacitors Q and Cp. r ■ 30k 1 5pF ' 1020GH JJ_rVN-Y^_12_ I___Rs_____J,s____Cs III XI >/ln NIV/32.767,41Hz :C2 _ 47nF -207 8 ■l_?OV IC 1,5pF lOpF Figure 4: Narrow-band filter. The circuit in Fig. 5 is a switching power supply. The power source (DC voltage 20 V) is connected to node 1. DC voltage of the Vpuhe is 10 V, amplitude is 20 V, rise and fall times are 10 ns, and the duty-cycle is 9%. At the output (node 4) noad = IkQ. is connected. Ml (^Vdc W20V LI .rw-v-v. 10 uH Vpuise 7>D1 ^^pulse 0 20 0 1 On 1 On 80n 1 j _C1 "lOuF RIoad k Figure 5: Switching power suppiy. 4.2 Results The steady-state response of the Greinacher rectifier is shown in Fig. 6. The circuit reaches the steady state in 100ms or in 240000 periods of the signal Vs. The steady state of the circuit was also computed with extrapolation algorithm. Parameter Figure 6: The steady-state response of the two-stage Greinacher rectifer (loaded with Iioad= IOjjA). (equations (4), (7), (8) and (11)) was set to 6. The extrapolation algorithm was stopped when the relative and the absolute criteria (16) were satisfied (<5a = Iff^ and {5r = Iff^). The number of iterations of the extrapolation algorithm (k) and the number of periods the circuit was simulated before it reached the steady state (+ tddIT)) are listed in t Table 1. Table 1: The number of iterations of the extrapolation algorithm and the number of simulated periods in the computation of the steady-state response. Greinacher rectifier Narrow-band filter Switching power supply Iterations Periods Iterations Periods Iterations Periods Epsilon algorithm 52 330 3 54 4 24 Rho algorithm 37 222 3 87 5 30 Theta algorithm 99 594 9 144 12 72 Topological epsilon algorithm 274 1644 3 54 4 24 Direct transient analysis / 240000 / 65535 / 100000 Using an extrapolation algorithm, the steady-state response of the test circuit was computed more than 140 times faster than with the direct approach (transient analysis until all initial transients die off). The narrow-band filter took 2 s (65535 periods) of the signal Vin before it reached steady state (Fig. 7). Computing the steady state with the epsilon, rho, theta and topological epsilon algorithm took 54, 87, 144 and 54 periods, respectively (Table 1) with & = S.ia'^ and 5r = J./O"«. The steady-state response of the switching power supply is depicted in Fig. 8. Steady state is reached in 100 ms or v(4)[sl 1.9E)3S5? 1,9995,'? 1,99994 1,9999,'j 1 199997 19999? 199999 ? Figure 7: The steady-state response of the narrowband filter. in 100000 periods of the signal Vpuise- With the epsilon, rho, theta and topological epsilon algorithm computing steady state took 24, 30, 72 and 24 periods, respectively (Table 1) with = la"^ and Sr = m^. t[ms) Figure 8: The steady-state response of the switching power suppiy. 5 Implementation of an extrapolation algorithm in SPICE OPUS 5.1 Choice of the extrapolation algorithm The results listed in Table 1 show that for the selected test circuits the best of the extrapolation algorithms is the epsilon algorithm. Therefore we chose it for the implementation in SPICE OPUS. The epsilon algorithm was also chosen due to it's simplicity and good results obtained with other circuits the extrapolation algorithm was tested on /8,9/. 5.2 SSSE analysis The new SSSE (Steady-State Shooting with Extrapolation) analysis was implemented in the SPICE OPUS circuit simulator/6/. The syntax of the ssse analysis is as follows: ssse [step [skip [periods]]] [history] <> ... required parameter [] ... optional parameter freq represents the fundamental frequency (f) of the steady-state response, step represents the basis for the variable time step (same as the first argument for the transient analysis, default value: 10/ freq), sl2V 3 1V Measurement 2 Y ripple load <250pV 1 100 pV Measurements V ' DC noload >3V 1 IV Measurement 4 y ripple iiohad <140pV 1 lOOpV Measurements are defined by "J V, DC load ^OUTl {t))dt Kippk load = . max (0 - Voun (0) - JyouT2(^)-Vounit))\ V. J "tT DC iwload V ripple _noload T iyouTiit)- ^OUTX mt («4-1)7- Ä^OUTlii)- (0) (e[{nj-l)r,njrJ (17a) (17b) (17c) (17d) Measurements 1 and 2 were made with Ihad = lOjjA (Fig. 3c). Measurements 3 and 4 were made with no load {Ihad = 0). The optimization took 2964 iterations. Every iteration of the optimization included two SSSE analyses. On an AMD Athlon XP 2500+ (1.83 GHz clock) computer with 512 MB of RAM, the optimization took 3 hours and 10 minutes. Optimum parameters are shown in Table 5 and the final measurement values in Table 6. Table 5: Optimum parameter values after the optimization. Value Parameter 0 16.60 fjm Parameter 1 21.10 pm Parameter 2 27.76 pm Parameter 3 26.68 pm Parameter 4 300 pF For measurements 2 and 4 the goals were achieved, while Measurements 1 and 3 violated the goals. The final cost function value was 0.6792. Table 6 also lists the measurement values before optimization (at initial values of the parameters in Table 3). Average improvement of the measurements is 16 %. In Sections 4.2 and 5.1 we have demonstrated that the acceleration ratio for the Greinacher rectifier test circuit (in case of the epsilon algorithm) is 727 (240000/330^727, see Table 1). If ordinary transient analysis was used, the optimization would take more than 95 days. This clearly Table 6: Measurement values before arid after the optimization. Before optimization After optimization Improvement Measurement 1 1.624 V i.m V 10.5 % Measurement 2 326.0 ^jV 249.9 IJV 23.3 % Measurement 3 2.670 V 2.911 V 9.0 % Measurement 4 116.6 yN 138.9 ijV 21.3 % demonstrates tiiat if tfie steady-state response of a circuit Inas to be computed in an optimization loop, an efficient extrapolation algoritlim is necessary. 7 Conclusions Four extrapolation algoritiims (epsilon, rlio, theta and topological epsilon algorithm) were described in this paper Using these algorithms the steady-state computation has been accelerated several hundred times. The extrapolation algorithms were tested on three test circuits (Greinacher rectifier, narrow-band filter and switching power supply). The epsilon algorithm was shown to be the most appropriate for the implementation in the SPICE OPUS circuit simulator The steady-state responses of the test circuits were computed several hundred times faster than with the direct approach (transient analysis until all initial transients die off). A new SPICE OPUS analysis utilizing the epsilon algorithm was implemented. The Greinacher rectifier test circuit was optimized using the SSSE analysis. The purpose of the optimization was to show that the optimization of the steady-state response can be accelerated significantly by using extrapolation methods. Optimization with the SSSE analysis (accelerated transient analysis) lasted 3 hours and 10 minutes. It has been estimated that the optimization with the direct approach (direct transient analysis) would take more than 95 days. 8 Acknowledgment The research has been supported by the Slovenian Research Agency within programme P2-0246 - Algorithms and optimization methods in telecommunications. 9 References /1/ A. Sidi, W. F. Ford, D. A. Smith, Acceleration of Convergence of Vector Sequences, SIAM Journal on Numerical Analysis, vol, 23, no. 1, pp. 178-196, February 1986. /2/ P. R. Graves-Morris, Extrapolation methods for vector sequences, Numer. Math. 61, pp. 475-487, 1992. /3/ E.J. Weniger, Nonlinear Sequence Transformations: Computational Tools for the Acceleration of Convergenc and the Sum-mantion of Divergent Series, URL: http://arxivorg/pdf/math.CA/0107080 /4/ X. Gourdon, P. Sebah, Convergence acceleration of series, January 10, 2002, URL: http://numbers.computation.free.fr/Con-stants/Mlscellaneous/seriesacoeleration.html /5/ K. S. Kundert, J. K. White, A. Sangiovanni-Vincentelli, Steady-state methods for simulation analog and microwave circuits, Klu-wer Academic Publishers, 1990. /6/ SPICE OPUS circuit simulator homepage, URL: http://www,fe.uni-lj.si/spice/ Faculty of Electrical Engineering, Electronic Design Automation Laboratory, URL: http://www.fe.uni-lj.si/edalab/ /7/ J, Puhan, T. Tuma, Optimization of analog circuits with SPICE 3f4, Proceedings oftheECCTD'97, vol. 1, pp. 177-180, 1997. /8/ B. Wagner, A. Bürmen, J. Puhan, I, Fajfar, T, Tuma, Computing the steady-state response of nonlinear circuits by means of the i-algo-rithm, Electrotechnical review, vol. 72, no. 6, pp. 297-302, 2005. /9/ B. Wagner, A. Bürmen, J, Puhan, I. Fajfar, T. Tuma, Uporaba ekstrapolacijskih metod pri računanju stacionarnega stanja električnih vezij (Application of extrapolation methods for steady-state computation of electrical circuits). Zbornik štirinajste mednarodne Elektrotehniške in računalniške konference ERK 2005, zv A, str. 82-85. /10/ BÜRMEN, Arpad, STRLE, Drago, BRATKOVIČ, Franc, PUHAN, Janez, FAJFAR, Iztok, TUMA, Tadej, Automated robust design and optimization of integrated circuits by means of penalty functions, AEÜ, Inf, j, electron, commun. 2003, 57, no, 1, str, 47-56, unlv. dipl. ing. el, Borut Wagner University of Ljubljana Faculty of Electrical Engineering Tržaška cesta 25, SI-1000 Ljubljana, Slovenia E-mail: borut. wagner@fe. uni-lj. si Tel: +386 1 4768724, Fax: +386 1 4264630 doc. dr. Arpad Bärmen University of Ljubljana Faculty of Electrical Engineering Tržaška cesta 25, SI-1000 Ljubljana, Slovenia E-mail: arpadb@fides. fe. uni-lj. si Tel: +386 1 4768322, Fax: +386 1 4264630 doc. dr Janez Puhan University of Ljubljana Faculty of Electrical Engineering Tržaška cesta 25, SI-1000 Ljubljana, Slovenia E-mail: janez.puhan@fe. uni-lj.si Tel: +386 1 4768322, Fax: +386 1 4264630 prof, dr Sašo Tomažič University of Ljubljana Faculty of Electrical Engineering Tržaška cesta 25, SI-1000 Ljubljana, Slovenia E-mail: saso. tomazic@fe. uni-lj. si Tel: +386 1 4768432, Fax: +386 1 4264630 prof. dr. Tadej Tuma University of Ljubljana Faculty of Electrical Engineering Tržaška cesta 25, SI-1000 Ljubljana, Slovenia E-mail: tadej.tuma@fe.uni-lj.si Tel: +386 1 4768329, Fax: +386 1 4264630 Prispelo (Arrived): 21. 04. 2006; Sprejeto (Accepted): 08. 09. 2006