La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

General Linear Methods
for Integrated Circuit Design
DISSERTATION
zur Erlangung des akademischen Grades
doctor rerum naturalium
(Dr. rer. nat.)
im Fach Mathematik
eingereicht an der
Mathematisch-Naturwissenschaftlichen Fakultat¨ II
Humboldt-Universit¨at zu Berlin
von
Herr Dipl.-Math. Steffen Voigtmann
geboren am 12.07.1976 in Berlin
Pr¨asident der Humboldt-Universit¨at zu Berlin:
Prof. Dr. Christoph Markschies
Dekan der Mathematisch-Naturwissenschaftlichen Fakult¨at II:
Prof. Dr. Uwe Kuc¨ hler
Gutachter:
(a) Prof. Dr. John Butcher
(b) Prof. Dr. Roswitha Ma¨rz
(c) Prof. Dr. Caren Tischendorf
eingereicht am: 30. Januar 2006
Tag der mundlic¨ hen Prufung:¨ 26. Juni 2006Preface
Today electronic devices play an important part in everybody’s life. In par-
ticular, there is an ongoing trend towards using mobile devices such as cell
phones, laptops or PDAs. Integrated circuits for these kind of applications
are mainly produced in CMOS technology (complementary metal-oxide semi-
conductor). CMOS circuits use almost no power when they are not active and
thus, combiningnegativelyandpositivelychargedtransistors, theydrawpower
only when switching polarity. Furthermore, advanced CMOS technology is ex-
pected to dominate in the future since it allows to manufacture transistors in
the nanoscale regime.
Circuit simulation is one of the key technologies enabling a further increase
in performance and memory density. A mathematical model is used in order
to assess the circuit’s behaviour before actually producing it. Thus production
startswithanalreadyoptimisedlayoutandproductioncostsbutalsothetime-
to-market is significantly reduced.
One important analysis type in circuit simulation is the transient analysis of
layouts on varying input signals. Based on schematics or netlist descriptions of
electrical circuits the corresponding model equations are automatically gener-
ated. This network approach preserves the topological structure of the circuit
but does not lead to a minimal set of unknowns. Hence the resulting model
consists of differential algebraic equations (DAEs). Typically these equations
suffer from poor smoothness properties due to the model equations of modern
transistorsbutalsoduetoe.g. piecewiselinearinputfunctions. Similarly, time
constants of several orders of magnitudes give rise to stiff equations and low
order A-stable methods need to be used.
The further miniaturisation of electrical devices drives simulation methods for
circuit DAEs to their limits. Due to the reduced signal/noise ratio, stability
questions become more and more important for modern circuits. Thus there
is a strong need to improve stability properties of existing methods such as
the combination of BDF and trapezoidal rule. There are fully implicit Runge-
Kutta methods that exhibit much better stability properties. However, theseiv Preface
methods are currently not attractive for industrial circuit simulators due to
their high computational costs.
General linear methods (GLMs) provide a framework covering, among others,
bothlinearmultistepandRunge-Kuttamethods. Theyenabletheconstruction
ofnewmethodswithimprovedconvergenceandstabilityproperties. Uptonow
little is known about solving DAEs using general linear methods. In particular
theapplicationofgenerallinearmethodsinelectricalcircuitsimulationhasnot
yet been addressed. Hence the object of this thesis is to study general linear
methods for integrated circuit design.
The work is organised as follows:
Part I: Using the charge oriented modified nodal analysis the differential alge-
braic equations describing electrical circuits are derived. Classical methods for
solving these equations are briefly addressed and their limitations are investi-
gated. As a means to overcome these shortcomings general linear methods are
introduced.
Part II: Linear and nonlinear DAEs of increasing complexity are investigated
indetail. Usingtheconceptofthetractabilityindexadecouplingprocedurefor
nonlinearDAEsisderived. Thisdecouplingprocedureisthekeytoolforgiving
conditions for the existence and uniqueness of solutions but also for studying
numerical integration schemes.
Part III: Generallinearmethodsareappliedtodifferentialalgebraicequations.
In order to prove convergence for index-2 DAEs it is seminal to investigate
GLMs for implicit index-1 equations. Order conditions and further additional
requirements on the method’s coefficients are derived such that convergence
is ensured. Using the decoupling procedure from Part II these results are
transferred to the case of index-2 equations.
Part IV: Methods with order p are constructed for 1 ≤ p ≤ 3. As different
design decisions are possible, the emphasise is on comparing two families of
methods: the first one havingp+1 internal stages while the other one employs
just p stages. While the former type of methods allows better stability prop-
erties and highly accurate error estimators, the latter family reduces the work
per step and is capable of reacting more rapidly to changes of the numerical
solution. ImplementationissuessuchasNewtoniteration, errorestimationand
order control are addressed for both families of methods. Extensive numerical
tests indicate high potential for general linear methods in integrated circuit
design.Acknowledgement
This work is one result of the close friendship between the numerical anal-
ysis group of Prof. Roswitha M¨arz and the ’Runge-Kutta Club’ headed by
Prof. John Butcher.
Roswitha M¨arz not only teaches numerical analysis at the Humboldt Univer-
sity in Berlin but she also fills students with enthusiasm about the numerical
analysis of differential algebraic equations. I am one of these students and I
want to thank her for the motivating, encouraging and supportive atmosphere
that I enjoyed at Humboldt University.
After finishing my Master’s degree I was fortunate to get the chance to visit
Prof. John Butcher at The University of Auckland. This stay in New Zealand
was most influential for my future work. I thank John Butcher for letting me
become part of the Runge-Kutta Club and teaching me so many things (not
only about mathematics and general linear methods). I am honoured that he
consented to review this thesis.
Towards the end of my stay in New Zealand a project developed that aimed
at combining the two mathematical worlds I lived in so far: the application
of general linear methods to differential algebraic equations. My supervisor
Prof. Caren Tischendorf (Technical University Berlin) was enthusiastic about
this idea from the very beginning. I thank her for realising a project within the
Research CenterMatheon. Throughout working on this project I was free to
explore my own ideas but Caren offered most valuable help whenever needed.
I always trusted her guidance but she never forced me into a certain direction.
While working on this thesis I was fortunate to meet many colleagues and
friends influencing my work. I thank Claus Fuhrer¨ (Lund University, Sweden)
for many fruitful discussions on DAEs. He not only invited me to Lund but
also arranged a visit with Anne Kværnø (NTNU Trondheim, Norway). I thank
her for helping me with the convergence proof for general linear methods.vi Acknowledgement
IlearnedalotfromHelmutPodhaisky(Martin-LutherUniversityHalle-Witten-
berg), in particular about the construction of methods and implementation is-
sues. HisMatlab codes formed the basis for developing my own DAE solver.
Stepsize prediction and order control were discussed with Gustaf S¨oderlind
(Lund University, Sweden). I thank him for taking interest in my work. Ren´e
Lamour (Humboldt University Berlin) was always available for discussion and
I thank Andreas Bartel (University of Wuppertal) for sending me a copy of his
PhD thesis.
I am pleased to acknowledge the financial support of the Matheon Research
Center and the German Research Foundation (Deutsche Forschungsgemein-
schaft). I thank my colleagues at the Infineon Technologies AG / Qimonda AG
for supporting me in many ways. Special thanks go to Sabine Bergmann and
to Sieglinde J¨anicke from the Humboldt University for extraordinary support
when submitting the thesis.
After all, writing and finishing this work would not have been possible without
the loving support of my wife, Sabine. I am lucky to have such a wonderful
woman at my side.
Kei mai koe ki au
He aha te mea nui te no?
Makue ki atu -
He tangata, he tangata, he tangata.
Maori proverb
Steffen Voigtmann
Ottobrunn, 20.08.2006.Contents
Part I Introduction
1 Circuit Simulation and DAEs 15
1.1 Basic Circuit Modelling. . . . . . . . . . . . . . . . . . . . . . . 15
1.2 Differential Algebraic Equations . . . . . . . . . . . . . . . . . . 19
2 Numerical integration schemes 25
2.1 Linear Multistep Methods . . . . . . . . . . . . . . . . . . . . . 26
2.2 Runge-Kutta Methods . . . . . . . . . . . . . . . . . . . . . . . 33
2.3 General Linear Methods . . . . . . . . . . . . . . . . . . . . . . 42
Part II Differential Algebraic Equations
3 Linear Differential Algebraic Equations 51
3.1 Index Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.2 Linear DAEs with Properly Stated Leading Terms . . . . . . . . 55
3.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4 Nonlinear Differential Algebraic Equations 67
4.1 The Index of Nonlinear DAEs . . . . . . . . . . . . . . . . . . . 69
4.2 Index-1 Equations . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5 Exploiting the Structure of DAEs in Circuit Simulation 77
5.1 Decoupling Charge-Oriented MNA Equations . . . . . . . . . . 78
6 Properly Stated Index-2 DAEs 87
6.1 A Decoupling Procedure for Index-2 DAEs . . . . . . . . . . . . 89
6.2 Application to Hessenberg DAEs . . . . . . . . . . . . . . . . . 102
6.3 Proofs of the Results . . . . . . . . . . . . . . . . . . . . . . . . 104viii Contents
Part III General Linear Methods for DAEs
7 General Linear Methods 113
7.1 Consistency, Order and Convergence . . . . . . . . . . . . . . . 114
7.2 Stability Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8 Implicit Index-1 DAEs 125
8.1 Order Conditions for the Local Error . . . . . . . . . . . . . . . 126
8.2 Convergence for Implicit Index-1 DAEs . . . . . . . . . . . . . . 147
8.3 The Accuracy of Stages and Stage Derivatives . . . . . . . . . . 157
9 Properly Stated Index-2 DAEs 165
9.1 Discretisation and Decoupling . . . . . . . . . . . . . . . . . . . 165
9.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
Part IV Practical General Linear Methods
10 Construction of Methods 179
10.1 Methods with s=p+1 Stages . . . . . . . . . . . . . . . . . . . . 183
10.2 Methods with s=p Stages . . . . . . . . . . . . . . . . . . . . . 193
10.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
11 Implementation Issues 209
11.1 Newton Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . 211
11.2 Error Estimation and Stepsize Prediction . . . . . . . . . . . . . 213
11.3 Changing the Order . . . . . . . . . . . . . . . . . . . . . . . . . 223
12 Numerical Experiments 227
12.1 Glimda++: Methods with s=p+1 Stages . . . . . . . . . . . . 229
12.2 Glimda vs. Glimda++ . . . . . . . . . . . . . . . . . . . . . . 232
12.3 Glimda vs. Standard Solvers . . . . . . . . . . . . . . . . . . . 237
Part V Summary
Bibliography 247List of Figures
1.1 The Miller Integrator circuit . . . . . . . . . . . . . . . . . . . . 16
1.2 Two simple VRC circuits . . . . . . . . . . . . . . . . . . . . . . 20
1.3 Analytical solution of the circuit from Figure 1.2(b) . . . . . . . 21
1.4 Impact of topology and technical parameters on the index . . . 23
2.1 Damping behaviour of the BDF method for an RLC circuit . . 282
2.2 Artificial oscillations of the trapezoidal rule. . . . . . . . . . . . 29
2.3 Stability properties of BDF methods and the trapezoidal rule . . 31
2.4 Stability properties of some Runge-Kutta methods . . . . . . . . 36
2.5 Circuit diagram for the Ring Modulator . . . . . . . . . . . . . 37
2.6 The Ring Modulator’s output signal . . . . . . . . . . . . . . . . 38
2.7 Comparison of Dassl andRadau for the Ring Modulator . . . 39
2.8 Order reduction for Gauss and SDIRK methods . . . . . . . . . 41
2.9 Stability behaviour of the GLM (2.12) and order of convergence 46
3.1 Numerical solution of Example 3.9 (standard formulation) . . . 64
3.2n of Example 3.9 (properly stated) . . . . . . . 64
4.1 The NAND gate model . . . . . . . . . . . . . . . . . . . . . . . 68
4.2 A nonlinear circuit with a current-controlled current source . . . 73
5.1 The NAND gate with the equivalent circuit from Figure 4.1(b). 78
6.1 The relation between u, z, w and the solution x . . . . . . . . . 92∗
6.2 The components of the solution x for Example 6.8 . . . . . . . . 99
6.3 The roadmap to the proofs . . . . . . . . . . . . . . . . . . . . . 104
7.1 The local and global error for general linear methods . . . . . . 117
8.1 A simple RCL circuit . . . . . . . . . . . . . . . . . . . . . . . . 126
8.2 One step taken by a GLMM for the problem (8.1). . . . . . . . 135
8.3 Simplification of trees. . . . . . . . . . . . . . . . . . . . . . . . 142
8.4 The global error for general linear methods . . . . . . . . . . . . 148x List of Figures
8.5 Example 8.28 – Accuracy of stages and stage derivatives . . . . 158
9.1 The relationship between discretisation and decoupling . . . . . 166
10.1 Choosing λ for the method (10.12) . . . . . . . . . . . . . . . . 187
10.2 Choosing λ for the method (10.13) . . . . . . . . . . . . . . . . 189
10.3 Choosing λ for the order 3 method . . . . . . . . . . . . . . . . 191
∗10.4 The parameter a controls the damping behaviour ofM . . . 19622 2
10.5 Controlling the damping bahaviour for Example 10.1 . . . . . . 197
10.6 Choosing λ for the methodM from Table 10.3 . . . . . . . . . 2033
10.7 Stability regions for the three families of methods . . . . . . . . 206
11.1 Accuracy of the estimators from Table 11.1 . . . . . . . . . . . . 219
11.2 of thetors from Table 11.2 . . . . . . . . . . . . 222
11.3 Order selection strategy for the methods from Table 10.1 . . . . 224
11.4 Order selection strategy for theds from Table 10.4 . . . . 226
12.1 Comparing the methods of Table 10.1 and 10.2 (Glimda++) . 230
12.2 The transistor amplifier circuit . . . . . . . . . . . . . . . . . . . 231
12.3 Comparison of Glimda andGlimda++ . . . . . . . . . . . . . 233
12.4rison of Glimda andGlimda++. 2nd set of problems . 234
12.5 Numerical results for the Two Bit Adding Unit . . . . . . . . . 236
12.6 Comparison of Glimda andDassl, Radau, Mebdfi . . . . . 239

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin