Switch-level simulation using dynamic graph algorithms

A model for MOS transistors that is suitable for logic simulation of VLSI circuits is presented. It is based on the concept of a dynamically directed switch (DDS). As in other switch-level models, the circuit is viewed as a graph whereon transistors are represented by directed edges and circuit nodes are represented by vertices. The problem of finding the steady-state response of the circuit is shown to be reducible to the single-source shortest-path problem in graph theory. A distributed literation process in which each transistor determines its instantaneous direction based on its source and drain vertex labels and updates those labels according to its own resistance is defined. Two types of events in the circuit require the reevaluation of the graph labels: transistors turning on and off. These correspond to edge addition and deletion in the circuit graph. Rather than repeatedly applying a shortest path algorithm to the graph whenever these events occur, the author investigates the possibility of dynamically updating only those labels which were affected by the change. The main result is the development of an algorithm for switch-level simulation based on this incremental-updating technique using only local information. The algorithm is fast and accurate and is extended to deal with timing based on an RC-tree delay model. The implementation of the algorithms presented here within the Lsim mixed-mode analog and digital simulator is described