Abstracts
(Listed alphabetically by the speaker's name)
View the abstracts in order of presentation
Parallel Flexible Iterative Solvers
for Sparse Equation Systems from Circuit Simulation
A. Basermann (1), M. Nordhausen (2), U. Jaekel (1), K. Hachiya (3 )
(1) NEC Europe Ltd, C&C Research Laboratories
(2) Christian-Albrechts University of Kiel, Faculty of Engineering
(3) NEC Electronics Corp., High-End Design Technology Development Group
The performance of iterative Krylov subspace solvers for sparse linear systems in circuit simulation depends crucially on the quality of the preconditioners used, in particular on parallel computer systems. We compare combinations of parallel flexible solvers with various preconditioners, and describe measures to improve the efficiency of the methods. Numerical experiments on transient simulation with NEC's parallel circuit simulator MUSASI are shown, comparing the performance of parallelized direct and iterative methods for real circuit problems.
Homotopy
Method for Finding the Steady States of Oscillators
Speaker: Dr. Hans Georg Brachtendorf
Fraunhofer Institute
R. Melville, R. Laur
Shooting, finite difference or Harmonic Balance techniques in conjunction with Newton's method are widely employed for the numerical calculation of limit cycles of oscillators. The resulting set of nonlinear equations are usually solved by damped Newton's method. In some cases however, non-convergence occurs when the initial estimate of the solution is not close enough to the exact one. A two-dimensional homotopy method is presented in this paper that overcomes this problem. The resulting linear set of equations employing Newton's method is underdetermined by rank 2 and is solved in a least squares sense for which a rigorous mathematical basis can be derived. Because continuation methods are only employed for obtaining a sufficient initial guess of the limit cycle, a coarse grid is enough to make the method run-time efficient.
Initial
Condition Strategies for Multiple-time Partial Differential Equations
Speaker: Todd Coffey
Sandia National Laboratories
Many
highly oscillatory circuits have a wide separation of time scales between
the underlying oscillation and the behavior of interest. This is particularly
true of communication circuits. Multiple-time Partial Differential Equation
(MPDE) methods offer substantial speed-up for these circuits by introducing
a periodic artificial time variable that represents the highly oscillatory
behavior. This leaves just the slowly changing behavior of interest,
which can be integrated with much larger steps. One problem of particular
interest is the larger initial condition that must be specified for
this periodic artificial time variable. One possible solution is to
formulate an optimization problem in the hopes of increasing the step
sizes taken in the slow time direction. This talk will discuss one possible
unconstrained optimization problem for determining this initial condition.
Numerical results and comparisons to several other initial condition
strategies will be presented in addition to MPDE background research
and implementation issues.
Sparse
LU Factorization for Matrices Arising in Circuit Simulation
Speaker: Tim Davis
University of Florida
A sparse LU factorization algorithm 2 to 1000 times faster than the method commonly used in SPICE is presented. Although circuit matrices are unsymmetric, a mix of unsymmetric and symmetric strategies is used. The algorithm unsymmetrically permutes the matrix into upper block triangular form, orders each block using symmetric minimum degree, and factorizes each block with a left-looking sparse LU method and numerical partial pivoting (with a strong diagonal preference). Parallel extensions will be discussed.
Explicit Integration Methods for Stiff Equations
Speaker: C. W. Gear
NEC Research Institute
Conventional wisdom says that for stiff systems one must either use implicit methods, a very small step size,or make use of the Jacobian in some fashion. Recently we have introduced projective integration methods that combine different step sizes in a way that can generate stability regions adapted to the problem. A projective method starts with a conventional explicit inner integrator using a step size commensurate with the fastest components. Each step damps these components by a factor, say ?, so that after k steps there is a damping of ?k – exponential in k. Then the projective step. which is a polynomial extrapolation through some of the points. is performed over a step M times larger that the inner step. It’s error amplification is polynomial in M so that M/k can, in principle be arbitrarily large. Since the average step size is (M+k)/k times the inner step, we can, in principle have large step-size explicit methods. The real picture is more complex than this simple summary suggests. This talk will discuss the potential application of these methods to transient analysis. Since there are typically components of many different speeds, it is often necessary to deal with each. This is currently handled by the use of telescopic projective methods which make note of the fact that the projective integration method can be used as the inner integrator in a further layer of projective integration, and so on. Each successively larger step size can be used to damp another (set of) components (or just that subpart of the system responsible for the particular eigenvalues can be integrated with that step size). If the eigenvalues are approximately known, telescopic integration can be used to deal with each annoyance separately. If they are not known, there are versions of telescopic integration that provide large regions of stability while remaining explicit.
Advanced
and Practical Approaches to Semi-conductor Device CAD
Neil Goldsman
University of Maryland
The
design of deep submicron and nanoscale electronics requires the use
of sophisticated computer aided design (CAD) tools. We have developed
a number of semiconductor device simulators to facilitate the CAD of
transistors with characteristic geometries of 100 nanometers and below.
These new simulators are based on various approaches to device analysis
including the Numerical Boltzmann Spherical Harmonic, Drift Diffusion,
Hydrodynamic, and Monte Carlo methods. An overview of the mathematics
and physics underlying these simulation methods will be presented. Quantum
effects in nanoscale devices will be described, and methodologies used
to
analyze these phenomena will be discussed. Special emphasis will be
paid to the Numerical Boltzmann Spherical Harmonic device simulation
method.
Multiparameter
Continuation
Michael E. Henderson
IBM Research
Previous attempts at computing solution manifolds of dimension two or more (Brodzik & Rheinboldt, Melville & Mackey, ...) have used variants of advancing fronts to generate a mesh on the manifold. This leads to several difficult mesh generation problems, chiefly dealing with self intersection of the front. There is a dual approach which finds a covering of the manifold instead of a tiling (i.e. the mesh). This yields a very simple method which uses polyhedra and spherical balls in the tangent space of the manifold to find a set of well distributed points on the manifold, for which the projection of the spherical balls covers the manifold. I will describe the basic geometric results and show some examples of computations using this approach, including branch switching at bifurcations and an adaptation for computing unstable manifolds of hyperbolic fixed points.
Calculation
of the Electron Distribution Function During Breakdown
W N G Hitchon
University of Wisconsin - Madison
The
electron distribution function is calculated self-consistently with
the electric field, by means of
a Green's function (or propagator) method which we refer to as the Convective
Scheme (CS). The method explicitly conserves particles and energy, locally
in phase space; and by a variety of methods is made to minimize numerical
diffusion. Applications to breakdown are presented. We also discuss
the matching of the kinetic model to a propagator-based fluid model
which permits simulation of much longer discharges than are practical
for the kinetic simulation.
Linear
Solution of Circuits in the Xyce Simulator
Speaker: Rob Hoekstra
Sandia National Laboratories
Analog circuit simulators rely on robust and accurate solution of linear systems. These linear problems are, in general, sparse and non-symmetric and often highly ill-conditioned. Analysis has shown that this class of problems have some unusual attributes requiring specialized solver technology. Results will be shown exhibiting some of these characteristics and our approach including block upper triangular form, incomplete factorization preconditioning, and hypergraph partitioning to achieve robust solution as well as scalability for large distributed memory platforms.
Opening
Remarks
Speaker: Eric Keiter
Sandia National Laboratories
Welcome to NACDM 2004! This is a companion workshop to one that was held two years ago, which (from Sandia's perspective) was a very interesting and fruitful exercise. Sandia National Laboratories has developed a distributed memory parallel circuit simulator (Xyce), and an overview of this simulator will be given, with some important developments and results. The objectives and organization of this workshop will also be described.
Simulating
Resonant Tunneling Diodes with the Wigner-Poisson Equations
Speaker: Andrew Lasater
North Carolina State University
Resonant tunneling diodes (RTDs) are quantum sized semiconductor devices, which both theory and numerical simulation predict can sustain terahertz current oscillations. The electron transport in these devices are modeled by the Wigner-Poisson Equations: a nonlinear PDE which describes the time-evolution of the electrons coupled with Poisson's equation to incorporate the potential effects of the electrons. Ongoing research with an RTD involve removing it from a circuit and searching for a voltage drop across the RTD that creates these high frequency current oscillations within the device. To accomplish this, we connected our simulator to LOCA (Library of Continuation Algorithms), a software library developed at Sandia National Laboratories. These algorithms enables us to trace-out the steady-state solutions to the PDE as the voltage drop across the device is varied. An eigenvalue analysis performed by LOCA allows us to predict the development of current oscillations from just steady-state calculations. Numerical results will be presented.
Scheduling
Optimization on the Simbus Backplane
Speaker: Dale Martin
Clifton Labs, Inc.
Continuous system models are becoming increasingly more important in the modeling and analysis of complex systems. Unfortunately, the runtime simulation costs required to support continuous modeling can be prohibitive to their use. One technique to decrease simulation runtime costs is mixed-domain simulation where the system is modeled by a mixture of discrete and continuous elements. In those regions where highly detailed information is required, continuous models can be used, and discrete models can be used otherwise. In this paper, we present a simulation backplane and its scheduling algorithm that can be used to integrate existing discrete and continuous simulators to form a single unified mixed-domain simulation environment.
Large-signal
Frequency Domain Coupled Device and Circuit Simulation
Speaker: Karti Mayaram
Oregon State University
The frequency-domain harmonic balance method is popular for the simulation of RF circuits. A coupling of circuit and device simulators allows analysis of RF circuits with accurate models for the semiconductor devices. Three approaches for the harmonic balance method in a coupled device and circuit simulator, CODECS, are explored. These are the non-quasi-static (NQS), quasi-static (QS), and modified Volterra series (MVS) approaches. The NQS approach is accurate but requires significant computing resources and extensive modifications to the device-level simulator. The quasi-static approach is efficient but the accuracy is limited by the unity-gain frequency of devices. The modified Volterra series approach has improved accuracy over the quasi-static approach for high frequency and small amplitude signals.
Is
It Time for SPICE 4?
Speaker: Larry Nagel
Omega Enterprises
SPICE originally was released into the public domain in 1971 by the University of California, Berkeley. The program enjoyed almost instant acceptance, with universities all over the world employing the program in integrated circuit design courses as well as computer-aided design research. SPICE2 was released into the public domain in 1975, again by the University of California, Berkeley. SPICE2 also enjoyed wide acceptance, and after SPICE 2G.6, work on SPICE at Berkeley waned. Not until 1989, almost 15 years later, was SPICE3 released into the public domain by Berkeley. The latest public domain SPICE3 simulator was released around 1993, about ten years ago. This talk will chronicle the crucial role SPICE had in launching a cottage industry of alphabet SPICE programs as well as hundreds of university research projects in various areas of circuit simulation. Paramount in this role was the fact that SPICE has always been in the public domain, available to all at a very nominal cost. SPICE-like programs, notably SPECTRE and ELDO, have been written since SPICE3 was released, but these follow-on programs are notably not in the public domain. The talk concludes by pondering the question of whether a more recent, public-domain circuit simulation program is necessary at this point.
Who is in Control? (Enhancing Your Simulator Using
an Extension Language)
Speaker: Sani R. Nassif
IBM Austin Research Labs
Simulators are generally written with much focus on algorithms, efficiency, and accuracy. This often results in tools which are monolithic in nature, with rigid control structures and somewhat inflexible sequencing. This flys in the face of a world where graphical user interfaces (GUIs) and highly interactive applications are the norm. Often, simulators are covered with a thin veneer of GUI code and re-badged as interactive, in spite of the fact that the overall control structure of the simulator remains one of (1) read the input, (2) perform the simulation, then (3) return the output. In this talk, the author describes an alternative model for building simulators where the tool is turned inside out and exposed to an extension language (in this case Tcl) to generate a completely different type of tool. In addition to the usual simulation tasks, the tool becomes immensely useful as a true design aid by allowing it to (a) be easily integrated into an interactive schematic-driven simulation paradigm, (b) incorporating modeling and optimization algorithms to allow design tuning, and (c) radically simplifying and standardizing the netlist and command language for the simulator.
Nonlinear
Solution Algorithms for Circuit Simulation
Speaker: Roger P. Pawlowski
Roger
P. Pawlowski, Eric R. Keiter, Robert J. Hoekstra, Tom V. Russo, Scott
A. Hutchinson, Jaijeet Roychowdhury, and Tamara Kolda
Sandia National Laboratories
Large-scale circuit simulation presents many challenges to the underlying solver algorithms. Difficulties typically center around obtaining a steady-state solution for the DC operating point. This talk will focus on current efforts to develop robust nonlinear solver technology specific to the DC operating point calculation. We will present results comparing nonlinear globalization techniques including line search, trust region, and homotopy algorithms. We will discuss the development of MOSFET specific multi-parameter homotopy algorithms. Comparisons of solver algorithms will be presented for a set of representative circuits.
Error Estimation for Reduced Order Models of
Dynamical Systems
Speaker: Linda Petzold
C. Homescu and L. Petzold
University of California Santa Barbara
R. Serban
Lawrence Livermore National Laboratory
The use of reduced order models to describe a dynamical system is pervasive in science and engineering. Often these models are used without an estimate of their error or range of validity. In this lecture we consider dynamical systems and reduced models built using proper orthogonal decomposition. We show how to compute estimates and bounds for these errors, by a combination of small sample statistical condition estimation and error estimation using the adjoint method. Most importantly, the proposed approach allows the assessment of regions of validity for reduced models. Numerical examples validate our approach.
Oscillator Macromodelling and Applications
Jaijeet Roychowdhury
University of Minnesota
Oscillators abound in engineering and in nature; indeed, they are critical components of most analog and digital systems. For many applications, it is advantageous to use good macromodels (or behavioral models) in place of more detailed SPICE-level descriptions of oscillators, as direct numerical simulation of even simple oscillators presents unique challenges. In this talk, we will describe recent algorithmic techniques for abstracting nonlinear macromodels of oscillators. The push-button-generated macromodels capture a variety of phase and amplitude-related phenomena (including injection locking dynamics, slow beats, timing jitter and phase noise) orders of magnitude faster than simulating the original SPICE-level oscillator descriptions.
Using Circuit Modeling to Simulate Large
Scale, Multi-Cellular, Biological Pathways
Speaker: Richard L. Schiek
Richard
L. Schiek & Elebeoba E. May
Sandia National Laboratories
To tackle large genetic and metabolic pathway problems, the massively-parallel, electronic circuit simulator, Xyce (TM), has been adapted to address biological circuits. Unique to this bio-circuit simulator is the ability to simulate not just one or a set of genetic circuits in a cell, but many cells and their internal circuits interacting through a common environment. Currently, electric circuit analogs for common biological and chemical machinery have been created. Using such analogs, one can construct expression, regulation and reaction networks. Individual species can be connected to other networks or cells via non-diffusive or diffusive channels (i.e. regions where species diffusion limits mass transport). Within any cell, a hierarchy of networks may exist operating at different time-scales so that no internal or external clock is forced on the system. To understand and model cellular differentiation, we have simulated the Drosophila sp. segment polarity gene network for a 2D array of cells connected through a common diffusion limited environment. In such an environment, cells experience local concentrations of differentiation stimuli determined by neighboring cells' production and consumption rates. These local stimuli effect the genetic and metabolic regulatory networks within the cell directing the cells eventual development. For this model problem, we will present functionality and parameter sensitivity studies. Additionally, we will show how parameter sensitivity and stability relate to morphological differentiation patterns.
Large-Scale
Nonlinear Optimization in Circuit Tuning
Andreas Waechter
IBM Watson Research Center
Circuit tuning is an essential step in the design of digital circuits. The central task is to find the optimal widths of transistors in order to minimize signal delay or area requirement. This problem can be formulated as a large-scale nonlinearly constrained nonlinear optimization problem, where function evaluations are obtained by simulation of gates (small subcircuits). We will describe an implementation of this approach, where the subcircuit simulations are performed by SPECS, an event-driven circuit simulator. The numerical optimization engine is IPOPT, a primal-dual interior point method for nonlinear programming, which uses a line search filter approach to ensure global convergence. Numerical results will be presented.
Applications
of Krylov Subspace Methods in Large-Scale Continuation
Speaker: Homer Walker
Homer
Walker
Worcester Polytechnic Institute
Roger Pawlowski and Eric Phipps
Sandia National Labs
We
consider the application of Krylov subspace methods to continuation
problems, in which the object is to track a solution curve as a continuation
parameter varies. Continuation methods are typically of predictor-corrector
form, in which, at each step along the curve, Newton-like corrector
iterations are used to return to the curve from an initial "predicted''
point. The analogue of the Newton equation is underdetermined, and the
additional linear condition necessary to determine each corrector step
uniquely is typically a requirement that the step be orthogonal to an
approximate tangent direction. Augmenting the underdetermined system
with this orthogonality condition in a straightforward way usually works
well if direct linear algebra methods are used but may be problematic
with Krylov subspace methods. We outline an alternative approach in
which the orthogonality condition is imposed directly as a constraint
on the corrector step in a certain way. The means of doing this preserves
problem conditioning, allows the use of preconditioners constructed
for the fixed-parameter case, and has certain other advantages. We conclude
with numerical experiments on large-scale problems
using LOCA and other Sandia application codes.
A
Parallel Direct Search Algorithm
Layne T. Watson
Virginia Polytechnic Institute and State University
Often
in applications a search or sweep of parameter space is desired, with
the goal of finding points where some derived quantity is optimal. Also
typically the presence of spurious local optima precludes
standard gradient based optimization, leaving deterministic or nondeterministic
search algorithms as the only plausible options. If function evaluations
are expensive, nondeterministic approaches
(simulated annealing, evolutionary optimization, etc.) are unappealing
since they tend to require a large number of function evaluations. D.
Jones' DIRECT algorithm is a deterministic direct search algorithm that
makes very efficient use of acquired function values, but is not easily
parallelized. This talk describes the DIRECT global optimization algorithm,
issues in its serial and parallel implementations, and some significant
applications.
