Published by
###
humboldt-universitat_zu_berlin

See more
See less

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. Steﬀen 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 signiﬁcantly 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 diﬀerential algebraic equations (DAEs). Typically these equations

suﬀer 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 stiﬀ 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 modiﬁed nodal analysis the diﬀerential alge-

braic equations describing electrical circuits are derived. Classical methods for

solving these equations are brieﬂy 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: Generallinearmethodsareappliedtodiﬀerentialalgebraicequations.

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 coeﬃcients 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 diﬀerent

design decisions are possible, the emphasise is on comparing two families of

methods: the ﬁrst 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 ﬁlls students with enthusiasm about the numerical

analysis of diﬀerential 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 ﬁnishing 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 inﬂuential 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 diﬀerential 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 oﬀered 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 inﬂuencing 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 ﬁnancial support of the Matheon Research

Center and the German Research Foundation (Deutsche Forschungsgemein-

schaft). I thank my colleagues at the Inﬁneon 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 ﬁnishing 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

Steﬀen Voigtmann

Ottobrunn, 20.08.2006.Contents

Part I Introduction

1 Circuit Simulation and DAEs 15

1.1 Basic Circuit Modelling. . . . . . . . . . . . . . . . . . . . . . . 15

1.2 Diﬀerential 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 Diﬀerential Algebraic Equations

3 Linear Diﬀerential Algebraic Equations 51

3.1 Index Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.2 Linear DAEs with Properly Stated Leading Terms . . . . . . . . 55

3.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4 Nonlinear Diﬀerential 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 Artiﬁcial 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 Simpliﬁcation 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 ampliﬁer 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

Share this publication