The cswec program [WY95] is a parallel implementation of the SWEC program, which performs timing simulation of digital MOS circuits [LMSK91]. The program first partitions the circuit into loosely coupled subcircuits, each of which can be simulated independently within a time step. At the end of a time step, the state of the subcircuit is propagated to its fanout subcircuits, if the state cannot be extrapolated linearly from the old state within some error margin. This communication is referred to as an event. Events occur at unpredicatable times and vary in frequency depending on the non-linearity of the voltage. The time step size used by the subcircuits depend on their states. Smaller timesteps are necessary for subcircuits with more activity to improve accuracy, and larger timesteps can be used for subcircuits with little activity to save computation. There are no global synchronization points, since each subcircuit is simulated with a variable number of timesteps that cannot be predicted in advanced.
The sequential implementation uses a centralized priority queue to schedule subcircuits in strict ascending time order, so that all events are processed before any affected subcircuit computation takes place. The parallel implementation eliminates the centralized scheduling queue and uses a data-flow approach for scheduling subcircuits. The program uses the conservative method of discrete event simulation, scheduling a subcircuit only when all input events have been Simple static load balancing heuristics are used for distributing the subcircuits across processors. The Graph data structure is used to perform event communication, and to bound the memory used for the simulation.
Conservative parallel simulation is primarily useful for combinational circuits (circuits without feedback paths); optimistic scheduling is much more effective for sequential circuits [WY93]. Since cswec targets combinational circuits, the data dependence graph of the circuit is acyclic, and deadlock due to the lack of global information cannot occur. However, because the event graph places an upper bound on the number of outstanding messages, the subcircuits sending new events may have to wait for its fanout subcircuits to release buffer space. This creates cycles in the overall dependence graph. Therefore, deadlock due to storage constraints can still occur. We resolve deadlocks using a combination of null messages and deadlock detection and recovery. A null message is an event that carries only the simulation time. A subcircuit sends a null message if it proceeds for several time steps and blocks without producing any event message. Our heuristics produce enough null messages to eliminate deadlocks in practice.