# Nonlinear Relaxation Algorithms for Circuit Simulation

### Resve A. Saleh

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/ERL M87/21

1987

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/ERL-87-21.pdf

Circuit simulation is an important Computer-Aided Design (CAD) tool in the design of Integrated Circuits (IC). However, the standard techniques used in programs such as SPICE result in very long computer run times when applied to large problems. In order to reduce the overall run time, a number of new approaches to circuit simulation have been developed and are described in this dissertation. These methods are based on nonlinear relaxation techniques and exploit the relative inactivity of large circuits. Simple waveform processing techniques are described to determine the maximum possible speed improvement which can be obtained by exploiting this property of large circuits. Three simulation algorithms are described, two of which are based on the Iterated Timing Analysis (ITA) method and a third based on the Waveform-Relaxation Newton (WRN) method. New programs which incorporate these techniques hake been developed and used to simulate a variety of industrial circuits. The results from these simulations are also provided. The techniques are shown to be much faster than the standard approach. In addition, a number of parallel aspects of these algorithms are described and a general space-time model of parallel task scheduling is developed.

**Advisor:** A. Richard Newton

BibTeX citation:

@phdthesis{Saleh:M87/21, Author = {Saleh, Resve A.}, Title = {Nonlinear Relaxation Algorithms for Circuit Simulation}, School = {EECS Department, University of California, Berkeley}, Year = {1987}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/858.html}, Number = {UCB/ERL M87/21}, Abstract = {Circuit simulation is an important Computer-Aided Design (CAD) tool in the design of Integrated Circuits (IC). However, the standard techniques used in programs such as SPICE result in very long computer run times when applied to large problems. In order to reduce the overall run time, a number of new approaches to circuit simulation have been developed and are described in this dissertation. These methods are based on nonlinear relaxation techniques and exploit the relative inactivity of large circuits. Simple waveform processing techniques are described to determine the maximum possible speed improvement which can be obtained by exploiting this property of large circuits. Three simulation algorithms are described, two of which are based on the Iterated Timing Analysis (ITA) method and a third based on the Waveform-Relaxation Newton (WRN) method. New programs which incorporate these techniques hake been developed and used to simulate a variety of industrial circuits. The results from these simulations are also provided. The techniques are shown to be much faster than the standard approach. In addition, a number of parallel aspects of these algorithms are described and a general space-time model of parallel task scheduling is developed.} }

EndNote citation:

%0 Thesis %A Saleh, Resve A. %T Nonlinear Relaxation Algorithms for Circuit Simulation %I EECS Department, University of California, Berkeley %D 1987 %@ UCB/ERL M87/21 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/858.html %F Saleh:M87/21