Waveform relaxation (WR) has been shown to be an effective algorithm to simulate large digital circuits. In this paper, we explore parallel WR methods to further improve the performance. The parallel processing issues under investigation include partitioning, task granularity, scheduling and allocation. The difficulty of addressing these issues is that circuit simulation problems tend to have highly irregular computational structures. The use of high-level waveforms generated from logic or timing simulators is introduced as a way of improving speed. The speed improvements for circuit partitioning, window selection and task allocation using high-level information are presented.

Describes methods of increasing parallelism, thereby improving the performance, of waveform relaxation-based parallel circuit simulators. The key contribution is the use of parallel nonlinear relaxation and parallel model evaluation to solve large subcircuits that may lead to load balancing problems. These large subcircuits are further partitioned and solved on clusters of tightly-coupled multiprocessors. This paper describes a general hybrid/hierarchical approach for waveform relaxation, and then focuses on the implementation issues regarding parallel nonlinear relaxation and parallel model evaluation. A number of benchmark circuits are used to demonstrate the improved performance of this approach and its range of applicability in parallel circuit simulation.>

The implementation of asynchronous waveform relaxation on parallel processors is discussed. Three different approaches, all based on event-driven scheduling techniques, are compared to the standard data-flow scheme. Issues involving the use of priority queues and preemptive scheduling are described. Circuit examples are used to demonstrate that good speedup can be achieved by using the event-driven method. The results indicate that the combination of data-flow and event-driven scheduling, together with a suitable preemptive scheme, provides a speed improvement of 1.5 to 2.5 over standard data-flow scheduling on eight processors.>

This paper describes a class of parallel algorithms for circuit simulation based on hierarchical relaxation that has been implemented on the Cedar multiprocessor. The Cedar machine is a reconfigurable, general-purpose supercomputer that was designed and implemented at the University of Illinois. A hierarchical circuit simulation scheme was developed to exploit the hierarchical organization of Cedar. The new algorithm and a number of key issues, such as multilevel circuit partitioning, data partitioning, cluster algorithm selection, and cluster algorithm implementation are described in this paper. Performance results on a variety of different configurations of Cedar are also presented that illustrate the benefits of the hierarchical approach over the non-hierarchical approach.