English

The simulation of integrated circuits enables the verification of the correct functioning and provides important performance values prior to their fabrication. In particular the accurate but time-consuming circuit-level simulation plays a central role in the design process. Due to the ever increasing complexity of integrated circuits and the associated rise in computing time, there is a continuing need in efficient numerical methods for the solution of the resulting high-dimensional systems of differential and algebraic equations.

The standard approach to solve these systems can be split into two main steps: the computation of consistent initial conditions and the numerical integration with implicit one-step or multi-step methods. In this thesis, we develop different models of the signal flow of integrated circuits and propose graph-based methods to speed up the simulation exploiting information on the underlying network structure.

The determination of consistent initial values necessitates the solution of a system of nonlinear equations. In order to improve the convergence of the Newton-Raphson method, which is usually used to solve the system of equations, and thus to reduce the simulation time, we compute an appropriate starting point using an event-driven switch-level algorithm in combination with a model of the logic signal flow that is based on the partitioning into channel-connected and strongly connected components.

Another possibility to reduce the runtime is to exploit subsystems that are temporarily inactive during the transient simulation. We introduce a dependency graph which enables the prediction of the influence of signal changes and a splitting of the system into active and inactive subsystems. Based on this decomposition, we define signal-flow based Runge-Kutta methods which automatically identify inactive subsystems and skip the recomputation of these regions. This leads to a significantly reduced number of time-consuming function evaluations.

Deutsch

Durch die Simulation integrierter Schaltkreise lassen sich schon vor der Fertigung detaillierte Aussagen über die Funktionalität und das Leistungsverhalten treffen. Insbesondere die präzise aber rechenintensive Simulation auf Schaltkreisebene spielt dabei eine zentrale Rolle. Aufgrund der stetig steigenden Komplexität integrierter Schaltkreise und der damit verbundenen zunehmenden Simulationsdauer besteht weiterhin ein Bedarf an effizienten numerischen Verfahren zur Lösung der resultierenden hochdimensionalen differential-algebraischen Gleichungssysteme.

Die Standardvorgehensweise, diese Systeme zu lösen, kann in zwei wesentliche Schritte unterteilt werden: die Berechnung konsistenter Anfangsbedingungen und die anschließende numerische Integration mithilfe impliziter Einschritt- oder Mehrschrittverfahren. In der vorliegenden Arbeit werden unterschiedliche Modelle zur Beschreibung des Signalflusses integrierter Schaltkreise vorgestellt. Darauf aufbauend werden graphbasierte Verfahren entwickelt, die Simulation unter Ausnutzung der zugrundeliegenden Netzwerkstruktur zu beschleunigen.

Die Bestimmung konsistenter Anfangswerte erfordert die Lösung eines nichtlinearen Gleichungssystems. Dazu wird in der Regel das Newton-Raphson-Verfahren verwendet. Um die Konvergenz dieses Verfahrens zu beschleunigen und somit die Simulationsdauer zu reduzieren, wird ein Algorithmus präsentiert, der es ermöglicht, einen geeigneten Startwert für die Iteration zu berechnen. Zu diesem Zweck wird ein eventgesteuertes Verfahren zur Simulation auf Schalterebene mit einem Modell des logischen Signalflusses kombiniert, das auf der Zerlegung des Schaltkreises in kanalverbundene und stark zusammenhängende Komponenten basiert.

Eine weitere Möglichkeit, die Simulationsdauer zu reduzieren, besteht darin, die während der Transientenanalyse temporär inaktiven Bereiche auszunutzen. Dazu wird ein Abhängigkeitsgraph generiert, der Aussagen über den Verlauf von Signaländerungen und eine Partitionierung in aktive und inaktive Teilbereiche ermöglicht. Es werden dann signalflussbasierte Runge-Kutta-Verfahren definiert, die inaktive Teilsysteme automatisch erkennen und die Neuberechnung dieser Bereiche vermeiden. Somit lässt sich die Anzahl der benötigten Funktionsauswertungen signifikant verringern.