Stochastic Simulation of Integrated Circuits with Nonlinear Black-Box Components via Augmented Deterministic Equivalents.

I. INTRODUCTION

The ever increasing miniaturization and integration experienced in the modern electronic industry is giving rise to a non-negligible impact of manufacturing tolerances and corresponding variability, which must be suitably accounted for in the design and verification of integrated circuits (ICs) and their interconnects [1],[2]. Virtually all available commercial (e.g. SPICE-type) circuit simulators offer Monte Carlo (MC)-like tools to account for random circuit parameters [3]. However, when accurate statistical information is desired, a large number of instances needs to be considered, thus making this approach computationally-intractable and unfeasible. Alternative approaches were therefore investigated to speed-up the design phase [4]-[7].

Smart and efficient solutions based on the so-called polynomial chaos (PC) framework [8] were proposed in the literature for statistical circuit analysis [9]-[11], with specific emphasis on the simulation of digital interconnects [12]-[15]. According to PC, voltages and currents (no matter whether in frequency or time domain) are expanded in series of orthogonal polynomials, whose coefficients directly provide statistical information on the circuit response. To retrieve these unknown coefficients, the usual strategy is to replace the PC expansions in the elements' constitutive equations and apply a stochastic Galerkin method (SGM) [16]. The result is an augmented set of deterministic and coupled equations that relate the voltage and current coefficients, which is then solved through a single system simulation via a customized program.

The PC-based approaches received a great boost thanks to their recent extension to nonlinear circuits [17]-[20]. Specifically, in [20] the derivation of an equivalent circuit representation of the resulting equations allows to create a deterministic augmented network from circuit inspection. The circuit interpretation is fully SPICE-compatible and the equivalent network can be simulated with standard circuit solvers to calculate the PC coefficients. This allows to perform the analysis directly in standard commercial circuit-analysis software, without the need for re-developing library models for each nonlinear device, but rather taking full advantage of the available ones.

However, the above approaches only apply to circuits consisting of classical electrical elements, ranging from linear passive components to standard nonlinear elements like diodes and transistors. In the practical simulation of realistic IC designs, it is common to deal with generic, nonlinear multiport subcircuits, for which a physical description is often unavailable. This is the case, for example, of the models provided by the vendors for building blocks like memory drivers and receivers. These are usually given as compact behavioral macromodels [21] or encrypted transistor-level descriptions, and the methods in [17]-[20] cannot cope with them. Secondly, the model dimension for nonlinear elements does not scale favorably with the number of random variables considered. While the first limitation also affects the modeling technique in [17]-[19], in [18] a more efficient method than SGM, i.e. the stochastic testing (ST), is used to generate the deterministic equations for the PC coefficients.

In this paper, a far more general framework is outlined, where a generic nonlinear subcircuit with an arbitrary number of terminals can be included as a black-box component, no matter its internal description. Furthermore, the model complexity and therefore the simulation efficiency are improved by using the ST in place of the SGM to construct the deterministic equations and the corresponding circuit models. As shown by the applications and numerical results, this choice provides a further and remarkable simulation speed-up.

II. POLYNOMIAL CHAOS-BASED CIRCUIT SIMULATION

This section briefly outlines the PC-based simulation of the stochastic response of a circuit affected by random parameters. For the sake of illustration, the discussion is based on the interconnect of Fig. 1a, which provides an oversimplification of a point-to-point communication link, yet collecting a representative set of electrical elements that are found in complex and realistic structures: nonlinear ICs (e.g., drivers and receivers), classical linear lumped elements (e.g., loads and/or parasitics) and distributed interconnects (transmission lines).

First of all, it is assumed that the circuit (no matter its complexity) is affected by d random parameters [x.sub.i] (i=1,...,d). A typical example is provided by package parasitics, which often have an associated uncertainty bound. Without loss of generality, we assume these parameters to be uncorrelated. Suitable techniques exist to account for correlation among the variables [8]. In addition, each random parameter [x.sub.i] is written in terms of a standardized (or normalized) random variable (RV) [[xi].sub.i], i.e. x=X+[increment of x][[xi].sub.i], with X its average value and [increment of x] its deviation from the mean. For example, for Gaussian random parameters, [[xi].sub.i] has a standard normal distribution and [increment of x] corresponds to the standard deviation.

The circuit voltages v and currents i (see e.g. the capacitor current in Fig. 1a) are inherently [xi]-dependent because they are affected by the random parameters which render them stochastic as well. The underlying idea of the PC-based circuit simulation is to express these stochastic voltages and currents as expansions of multivariate polynomials that are orthonormal with respect to the joint probability density function (PDF) of [xi]=[[[xi].sub.1],...,[[xi].sub.d]] [22]:

v(t,[xi]) [approximately equal to] [P.summation over (k=0)] [v.sub.k](t)[[phi].sub.k]([xi]), i(t,[xi]) [approximately equal to] [P.summation over (k=0)][i.sub.k](t)[[phi].sub.k]([xi]), (1)

where {[[phi].sub.k]}, k=0,...,P is the polynomial basis. Typically, to provide satisfactory modeling accuracy, multivariate polynomials of total degree less or equal to 2 are used, thus leading to a total number of expansion terms K=P+1=(2+d)!/(2d!) [20]. Once the (deterministic) voltage and current coefficients [v.sub.k] and [i.sub.k] are calculated, pertinent statistical information is readily extracted via analytical formulae or by numerically evaluating (1).

To solve for these unknown voltage and current coefficients, deterministic, though augmented, equivalent circuit models are generated for the stochastic and non-stochastic elements based on their governing equations [15], [20]. An equivalent network is created by expanding each original node into K nodes. Each node is associated to the PC coefficients of the corresponding node voltage. The new nodes are then connected using the pertinent models in accordance with the original circuit topology. The currents flowing in the augmented network coincide with the PC coefficients of the original stochastic currents. This procedure is illustrated in Fig. 1b and allows for the simulation of an arbitrary electrical network. The compatibility with standard simulators further enables to take advantage of available device libraries and solution algorithms.

Nevertheless, only classical electrical elements were modeled so far. Specifically, models for distributed elements were provided in [15], whilst the modeling of lumped linear elements as well as of diodes and transistors was addressed in [20]. Moreover, the circuit equivalents for these nonlinear elements become inefficient when many RVs are considered, as discussed in the next session. Hence, more efficient models that apply to generic nonlinear multiport subcircuits, as required by the simulation of complex and realistic IC designs, are proposed in this paper.

III. MODELING OF MULTI-TERMINAL BLACK-BOX COMPONENTS

Let us now consider a subcircuit with N terminals plus a reference terminal, as shown in Fig. 2. Without loss of generality, the subcircuit is assumed to be fully voltage-controlled and the current entering the nth terminal (n=1,...,N) is expressed as a (possibly dynamical) function of all the terminal voltages, i.e.

[i.sub.n] (t) = [F.sub.n] ([v.sub.1](t),..., [v.sub.n](t), t, d / dt), (2)

where [F.sub.n] represents the current-to-voltage response of the nth terminal of the subcircuit. Following the reasoning outlined in the previous paragraph, the N terminal nodes are expanded into KN nodes. Hence, an equivalent KN-terminal model must be derived, as shown in Fig. 3a. This model must enforce a relationship between the terminal voltages and currents, which correspond to the PC coefficients of the original variables.

Assuming the voltages and currents to be stochastic and replacing their PC expansions (1) into (2), produces

[P.summation over (k=0)][i.sub.nk](t)[[phi].sub.k]([xi]) = [F.sub.n]([[??].sub.1](t,[xi]),...,[[??].sub.N](t,[xi])), (3)

having defined

[[??].sub.n](t,[xi]) = [[SIGMA].sup.P.sub.k=0] [v.sub.nk] (t)[[phi].sub.k] ([xi]). (4)

Then, (3) is forced to be satisfied at a discrete set of K points {[[xi].sub.m]}, m=1,...,K, generated via an orthogonal space-filling approach [18]. This procedure is referred to as ST and allows to find K deterministic equations relating the voltage and current coefficients. These are cast as

[i.sub.nk] (t) = [K.summation over (m=1)][b.sub.km][j.sub.nm](t), (5)

k=0,...,P. The procedure is analogous for each terminal n. In the above equation, [b.sub.km] are the entries of the matrix B=[A.sup.-1], where in turn the entries of matrix A are [a.sub.mk]=[[phi].sub.k]([[xi].sub.m]). It is worth mentioning that (5) is deterministic, because [xi] is evaluated at specific points, as such suppressing this dependence in (3). The nonlinear current [j.sub.nm] is instead defined as

[j.sub.nm](t) = [F.sub.n] ([[??].sub.1m] (t, [xi]),..., [[??].sub.Nm](t, [xi])) (6)

with

[[??].sub.nm] (t) = [[??].sub.n] (t, [[xi].sub.m]) = [[SIGMA].sup.P.sub.k=0] [v.sub.nk] (t)[a.sub.mk]. (7)

It is the current flowing in the nth terminal when voltages [[??].sub.1m],...,[[??].sub.Nm] are applied to the subcircuit. These currents are therefore obtained by means of the circuit in Fig. 3b, where [v.sub.nk] (with n=1,...,N and k=0,...,P) are the voltages of the terminals appearing in Fig. 3a. It should be noted that K of these circuits are needed to sample all the currents [j.sub.nm] for m=1,...,K. Finally, these currents are combined via dependent current sources to produce the terminal currents [i.sub.nk] in Fig. 3a, in accordance with (5).

With the implementation discussed above, no information on the internal description of the subcircuit is required. Moreover, using ST, the deterministic augmented model of the original subcircuit involves, as already noticed, K= (2+d)!/(2-d!) replicas of this subcircuit, i.e. exactly the same number as the PC coefficients. By using the strategy in [20] to obtain the equations relating the PC-expansion coefficients, the model would involve Q=[3.sup.d][greater than or equal to]K replicas instead. As an example, for d=2,3,4, the figures would be K=6,10,15 and Q=9,27,81, respectively. It is clear that, thanks to the ST, the implementation is more efficient when the number of RVs d is >1, and this is confirmed by the figures provided in the next section.

IV. APPLICATION EXAMPLES AND NUMERICAL RESULTS

The proposed application examples involve the structure illustrated in Fig. 4. It represents a 16-bit digital transmission channel of a memory chip, consisting of the pertinent buffers, package parasitics, transmission lines with the corresponding terminations, and the power supply rail, represented by cascade connection of series resistors. It is important to remark that the above example provides a simplified picture of a complex design scenario, involving a large number of digital devices that exhibit a nonlinear dynamical behavior and that simultaneously communicate through the PCB data bus with other ICs on the board. The structure of Fig. 4 can be further enhanced and refined, without compromising the effectiveness of the proposed methodology in the stochastic assessment of digital ICs and their signal and power integrity.

To stress the versatility of the approach, two memory technologies are considered as test cases, using the same structure but with different driver models. This simply amounts to changing the call to the proper subcircuit model in the equivalent circuit of Fig. 3. The power supply voltage is [V.sub.DD]=1.8 V, the package is modeled as a RLC section with [R.sub.p]=50 m[OMEGA], [L.sub.p]=2 nH, [C.sub.p]=5.5 pF, whilst the transmission lines have a characteristic impedance of 50 [OMEGA], a delay of 1 ns, and are terminated by a parallel RC load with R=1 k[OMEGA] and C= 10 pF. The resistance r of the power supply rail is varied according to the driver model. The even-bit drivers produce a pulse with a duration of 15 ns and rise/fall times of 0.1 ns. The switching times are slightly misaligned. The odd-bit drivers are kept in the "low" state instead. All the simulations are performed using HSPICE [23] on a HP Compaq dc7700 with an Intel(R) Pentium(R) 4, CPU running at 3.20 GHz and 2 GB of RAM.

A. Test Case #1: low power DDR memory

The first example considers a driver model that is representative of a 133-MHz low power DDR memory. The power rail resistors have a value of r[approximately equal to]0.9 [OMEGA]. The variability is here provided by the power supply voltage [V.sub.DD] and by the rail resistance r, considered as two independent Gaussian RVs with relative standard deviations of 2% and 10%, respectively. The supply voltage deviation is comparable with that of commercial voltage regulators and also affects the driver model.

The top panel of Fig. 5 shows the crosstalk voltage produced at the termination of the 13th (unexcited) channel. The gray area results from the superposition of 100 MC samples of the random response, and provides a qualitative idea of the voltage fluctuation due to the variability. Furthermore, the blue lines indicate the responses that lie [+ or -]3[sigma] (with [sigma] the standard deviation) from the average response, where the average and standard deviation have been estimated from 1000 MC samples. Finally, the red markers indicate the [+ or -]3[sigma] limits obtained with the proposed PC-based simulation. The excellent modeling accuracy can be further appreciated in the bottom panel, where a comparison between MC and PC on the estimation of the standard deviation of the response is provided. In the plot, the dotted and dashed lines are the standard deviation obtained with a subset of 10 and 100 MC samples, respectively, and show that a large number of MC runs, i.e. at least 1000 (see the solid line), is required to achieve the accuracy provided by PC.

A similar analysis is carried out for the voltage transmitted to the termination of the 6th (active) channel. Fig. 6 provides in the top panel random samples (gray area) of the transmitted voltage together with the [+ or -]3 [sigma] limits, again estimated with both MC and PC. The bottom panel displays the PDF of the transmitted voltage at the maximum overshoot, occurring at 19.3 ns (see the dashed vertical line in the top panel). The gray bars are the histogram obtained from the MC samples, whilst the red line is numerically obtained from the PC expansion. The worse resolution of the MC result is due to the limited number of samples considered, whereas PC allows a smoother reproduction of the PDF. As to the simulation times, the 1000-sample MC analysis required 21 h and 8 min, whereas the simulation of the PC-augmented network took 9 min and 10 s. Therefore, a remarkable speed-up of 138x is achieved thanks to the advocated technique.

B. Test Case #2: Flash memory chip

In the second test case, the driver model mimics the response of a 66-MHz Flash memory chip. The power rail resistance is here r[approximately equal to]1.4 [OMEGA], and the variability is provided by the parasitics, i.e. the value of the rail resistance r and of the package elements [R.sub.p], [L.sub.p] and [C.sub.p]. All these parameters are assumed to be Gaussian distributed with independent standard deviations of 10%.

Fig. 7 displays the average voltage responses on the 8 excited channels. The blue lines and red markers are the averages obtained with MC and PC, respectively. A voltage drop is observed in the different channels due to the nonideal on-chip power distribution network.

In addition, Fig. 8 shows the statistical information pertaining to the crosstalk voltage on the most significant bit. In the top panel, the spread of the crosstalk due to the variability in the parasitics is highlighted by the gray area. The [+ or -]3[sigma] bounds capture well this response variation and are estimated with both MC (blue lines) and PC (red markers). As in the previous example, the bottom panel of Fig. 8 establishes the accuracy of PC in reproducing the crosstalk standard deviation, as well as the convergence of the MC analysis. Also in this case, at least 1000 MC samples are necessary to match the PC accuracy.

Finally, Fig. 9 assesses the variability of the power supply voltage of the driver in channel #1. In the top panel, the spread and the [+ or -]3[sigma] limits are reported. The bottom panel displays the PDF of the supply voltage at 33.3 ns (see the dashed line in the top panel). owing to the skewness of the distribution, average and standard deviation are not sufficient to characterize the variability of the supply voltage in this case.

As far as the simulation efficiency is considered, the MC analysis took 2 days, 5 h and 50 min, against the 1 h and 8 min required by the PC-based simulation, which yields a 47x speed-up. The main figures characterizing the efficiency and netlist size of the HSPICE simulations for the two proposed examples are summarized in Table I. Table II reports a comparison between the simulation time when either ST or SGM is used to generate the augmented deterministic equations and the corresponding equivalent circuit models. The number of replicas of the original multiport element required by the two modeling approaches is highlighted in the table. When the number of RVs d increases, ST becomes far more efficient.

V. CONCLUSION

Two major contributions are delivered in this paper. First, the PC-based modeling of stochastic circuits is applied, for the first time, to arbitrary multiport black-box components, for which no physical description is available. This allows to include in the statistical simulation any device model, independently of its number of terminals and/or internal complexity. Secondly, ST is used in place of SGM to generate the SPICE-compatible equivalent circuits for the calculation of the PC coefficients, thus improving the simulation efficiency.

The technique is validated through the statistical simulation of a 16-bit memory chip driving a data bus. The buffer models for two different memory architectures are considered to stress the versatility of the proposed approach. A thorough comparison against MC simulations in terms of accuracy and simulation time is reported. The efficiency of the ST-based models versus those generated via the SGM is also assessed. The advocated methodology provides significant speed-up with respect to both MC and state-of-the-art SGM-based methods.

REFERENCES

[1] L. Scheffer, L. Lavagno, and G. Martin, EDA for IC Implementation, Circuit Design, and Process Technology. Boca Raton, FL: CRC Press, Taylor & Francis Group, 2006.

[2] T. Mikazuki and N. Matsui, "Statistical design techniques for highspeed circuit boards with correlated structure distributions," IEEE Transactions on Components, Packaging and Manufacturing Technology, Part A, vol. 17, no. 1, pp. 159-165, 1994, http://dx.doi.org/10.1109/IEMT9.1990.115004

[3] R. Spence and R. S. Soin, Tolerance Design of Electronic Circuits. London: Imperial College Press, 1997.

[4] Q. Zhang, J. J. Liou, J. McMacken, J. Thomson, and P. Layman, "Development of robust interconnect model based on design of experiments and multiobjective optimization," IEEE Transactions on Electron Devices, vol. 48, no. 9, pp. 1885-1891, 2001, http://dx.doi.org/10.1109/16.944173

[5] A. H. Zaabab, Qi-Jun Zhang, and M. Nakhla, "A neural network modeling approach to circuit optimization and statistical design," IEEE Transactions on Microwave Theory and Techniques, vol. 43, no. 6, pp. 1349-1358, 1995, http://dx.doi.org/10.1109/22.390193

[6] L. Brancik and E. Kolafova, "Simulation of higher-order electrical circuits with stochastic parameters via SDEs," Advances in Electrical and Computer Engineering, vol. 13, no. 1, pp. 17-22, 2013, http://dx.doi.org/10.4316/aece.2013.01003

[7] L. Brancik and E. Kolafova, "Application of stochastic differential-algebraic equations in hybrid MTL systems analysis," Elektronika Ir Elektrotechnika, vol. 20, no. 5, pp. 41-45, 2014, http://dx.doi.org/10.5755/j01.eee.20.5.7098

[8] D. Xiu, "Fast numerical methods for stochastic computations: a review," Communications in Computational Physics, vol. 5, no. 2-4, pp. 242-272, 2009.

[9] Q. Su and K. Strunz, "Stochastic circuit modelling with Hermite polynomial chaos," IET Electronics Letters, vol. 41, no. 21, pp. 1163-1165, 2005, http://dx.doi.org/10.1049/el:20052415

[10] K. Strunz and Q. Su, "Stochastic formulation of SPICE-type electronic circuit simulation using polynomial chaos," ACM Transactions on Modeling and Computer Simulation, vol. 18, no. 4, pp. 15:1-15:23, 2008, http://dx.doi.org/10.1145/1391978.1391981

[11] N. Mi, S. X.-D. Tan, Y. Cai, and X. Hong, "Fast variational analysis of on-chip power grids by stochastic extended Krylov subspace method," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 11, pp. 1996-2006, 2008, http://dx.doi.org/10.1109/TCAD.2008.2006077

[12] S. Vrudhula, J. M. Wang, and P. Ghanta, "Hermite polynomial based interconnect analysis in the presence of process variations," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 10, pp. 2001-2011, 2006, http://dx.doi.org/10.1109/TCAD.2005.862734

[13] I. S. Stievano, P. Manfredi, and F. G. Canavero, "Parameters variability effects on multiconductor interconnects via Hermite polynomial chaos," IEEE Transactions on Components, Packaging and Manufacturing Technology, vol. 1, no. 8, pp. 1234-1239, 2011, http://dx.doi.org/10.1109/TCPMT.2011.2152403

[14] D. Vande Ginste, D. De Zutter, D. Deschrijver, T. Dhaene, P. Manfredi, and F. Canavero, "Stochastic modeling-based variability analysis of on-chip interconnects," IEEE Transactions on Components, Packaging and Manufacturing Technology, vol. 2, no. 7, pp. 1182-1192, 2012, http://dx.doi.org/10.1109/TCPMT.2012.2192274

[15] P. Manfredi, D. Vande Ginste, D. De Zutter, and F. G. Canavero, "Uncertainty assessment of lossy and dispersive lines in SPICE-type environments," IEEE Transactions on Components, Packaging and Manufacturing Technology, vol. 3, no. 7, pp. 1252-1258, 2013, http://dx.doi.org/10.1109/TCPMT.2013.2259295

[16] R. G. Ghanem and P. D. Spanos, Stochastic Finite Elements. A Spectral Approach. New York: Springer-Verlag, 1991.

[17] A. Biondi, D. Vande Ginste, D. De Zutter, P. Manfredi, and F. G. Canavero, "Variability analysis of interconnects terminated by general nonlinear loads," IEEE Transactions on Components, Packaging and Manufacturing Technology, vol. 3, no. 7, pp. 1244-1251, 2013, http://dx.doi.org/10.1109/TCPMT.2013.2259896

[18] Z. Zhang, T. A. El-Moselhy, I. M. Elfadel, and L. Daniel, "Stochastic testing method for transistor-level uncertainty quantification based on generalized polynomial chaos," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 32, no. 10, pp. 1533-1545, 2013, http://dx.doi.org/10.1109/TCAD.2013.2263039

[19] M. R. Rufuie, E. Gad, M. Nakhla, and R. Achar, "Generalized Hermite polynomial chaos for variability analysis of macromodels embedded in nonlinear circuits," IEEE Transactions on Components, Packaging and Manufacturing Technology, vol. 4, no. 4, pp. 673-684, 2014, http://dx.doi.org/10.1109/TCPMT.2013.2285877

[20] P. Manfredi, D. Vande Ginste, D. De Zutter, and F. G. Canavero, "Stochastic modeling of nonlinear circuits via SPICE-compatible spectral equivalents," IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 61, no. 7, pp. 2057-2065, 2014, http://dx.doi.org/10.1109/TCSI.2014.2304667

[21] I. S. Stievano, L. Rigazio, F. G. Canavero, T. R. Cunha, J. C. Pedro, H. M. Teixeira, A. Girardi, R. Izzi, and F. Vitale, "Behavioral modeling of IC memories from measured data," IEEE Transactions on Instrumentation and Measurement, vol. 60, no. 10, pp. 3471-3479, 2011, http://dx.doi.org/10.1109/TIM.2011.2128570

[22] D. Xiu and G. E. Karniadakis, "The Wiener-Askey polynomial chaos for stochastic differential equations," SIAM Journal on Scientific Computing, vol. 24, no. 2, pp. 619-622, 2002, http://dx.doi.org/10.1137/S1064827501387826

[23] HSPICE User Guide, Version B-2008.09, Synopsys, Inc., Mountain View, CA, USA, 2008.

Paolo MANFREDI, Igor S. STIEVANO, Flavio G. CANAVERO

Dept. of Electronics and Telecommunications, Politecnico di Torino, 10129 Torino, Italy

paolo.manfredi@polito.it

Digital Object Identifier 10.4316/AECE.2014.04001
```TABLE I. MAIN FIGURES CHARACTERIZING THE MC AND PC SIMULATIONS

MC analysis                                 PC-based
simulation
test case   nodes   elements   memory used   CPU time   K    nodes

#1          1480    3289        5663 kb       76059 s    6    9461
#2          2807    6888       11549 kb      193826 s   15   43693

PC-based simulation
test case   elements   memory used   CPU time   speed-up

#1           21056      32597 kb      550 s      138 x
#2          109032     187629 kb     4091 s       47 x

ST-based              SGM-based
test case   RVs   replicas   CPU time   replicas   CPU time   speed-up

#1          2      6          550 s      9           871 s    1.6 x
#2          4     15         4091 s     81         32046 s    7.8 x
```
COPYRIGHT 2014 Stefan cel Mare University of Suceava
No portion of this article can be reproduced without the express written permission from the copyright holder.