Circuit simulation has been a topic of great interest to the integrated circuit design community for many years. It is a difficult, and interesting, problem be cause circuit simulators are very heavily used, consuming thousands of computer hours every year, and therefore the algorithms must be very efficient. In addi tion, circuit simulators are heavily relied upon, with millions of dollars being gambled on their accuracy, and therefore the algorithms must be very robust. At the University of California, Berkeley, a great deal of research has been devoted to the study of both the numerical properties and the efficient imple mentation of circuit simulation algorithms. Research efforts have led to several programs, starting with CANCER in the 1960's and the enormously successful SPICE program in the early 1970's, to MOTIS-C, SPLICE, and RELAX in the late 1970's, and finally to SPLICE2 and RELAX2 in the 1980's. Our primary goal in writing this book was to present some of the results of our current research on the application of relaxation algorithms to circuit simu lation. As we began, we realized that a large body of mathematical and exper imental results had been amassed over the past twenty years by graduate students, professors, and industry researchers working on circuit simulation. It became a secondary goal to try to find an organization of this mass of material that was mathematically rigorous, had practical relevance, and still retained the natural intuitive simplicity of the circuit simulation subject.

Inhalt
1 Introduction.- Section 1.1 Simulation For IC Design.- Section 1.2 Circuit Simulation.- Section 1.3 Standard Circuit Simulators.- Section 1.4 Relaxation-Based Circuit Simulators.- Section 1.5 Notation.- 2 The Circuit Simulation Problem.- Section 2.1 Formulation of the Equations.- Section2.1.1 Branch Equations.- Section 2.1.2 KCL and KVL.- Section 2.1.3 Nodal Analysis.- Section 2.1.4 Extending The Nodal Analysis Technique.- Section 2.2 Mathematical Properties of the Equations.- Section 2.2.1 Existence of Solutions.- Section 2.2.2 Diagonal Dominance and the Capacitance Matrix.- Section 2.2.3 Resistor-and-Grounded-Capacitor (RGC) Networks.- Section 2.3 Numerical Integration Properties.- Section 2.3.1 Consistency, Stability, and Convergence.- Section 2.3.2 Stiffness and A-Stability.- Section 2.3.3 Charge Conservation.- Section 2.3.4 Domain of Dependence.- 3 Numerical Techniques.- Section 3.1 Numerical Integration in General-Purpose Simulators.- Section 3.2 Properties of Multistep Integration Methods.- Section 3.3 Relaxation Decomposition.- Section 3.4 Semi-Implicit Numerical Integration Methods.- Section 3.5 Relaxation Versus Semi-Implicit Integration.- 4 Waveform Relaxation.- Section 4.1 The Basic WR Algorithm.- Section 4.2 Convergence Proof for the Basic WR Algorithm.- Section 4.3 Waveform Relaxation-Newton Methods.- Section 4.4 Nonstationary WR Algorithms.- 5 Accelerating WR Convergence.- Section 5.1 Uniformity of WR Convergence.- Section 5.2 Partitioning Large Systems.- Section 5.3 Ordering the Equations.- 6 Discretized WR Algorithms.- Section 6.1 The Global-Timestep Case.- Section 6.2 Fixed Global-Timestep WRConvergence Theorem.- Section 6.3 The Multirate WR Convergence Theorem.- 7 The Implementation of WR.- Section 7.1 Partitioning Mos Circuits.- Section 7.2 Ordering the Subsystem Computation.- Section 7.3 Computation of the Subsystem Waveforms.- Section 7.4 Window Size Determination.- Section 7.5 Partial Waveform Convergence.- Section 7.6 Experimental Results.- 8 Parallel WR Algorithms.- Section 8.1 An Overview of the Shared-Memory Computer.- Section 8.2 Mixed Seidel/Jacobi Parallel WR Algorithm.- Section 8.3 Timepoint-Pipelining WR Algorithm.- Section 8.4 Parallel Algorithm Test Results.- References.