General linear methods for integrated circuit design [Elektronische Ressource] / von Steffen Voigtmann

Voigtmann Steffen

Sujets

• Mathematics

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2006
• Nombre de lectures: 18
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

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 . . .