Circuit simulation is a significant bottleneck in the design of VLSI circuits and parallel execution offers the potential for considerably reducing the simulation time for large circuits. We have developed MIRSIM, a parallel switch-level circuit simulator. This is a Maisie implementation of IRSIM, an existing event-driven simulator that incorporates a linear model of MOS transistors. The implementation has been used to simulate a number of circuits using both conservative and optimistic protocols on the IBM SP2 using a variety of circuit partitioning techniques.

For parallel execution, the model must first be divided into a number of partitions, each of which may potentially be executed on a processor. The objective of the partitioning algorithm is to generate balanced partitions (to try and achieve a uniform distribution of the computation) such that a minimum number of nets are cut (to minimize the message communication among the corresponding partitions in the simulation).

In addition to the existing iterative partitioning algorithms (K-FM), we also support acyclic algorithms (K-AFM) that impose the constraint that generated partitions do not form cycles. The preceding set of partitioning algorithms can be invoked automatically for a given circuit. A graphical facility has been provided to allow a designer to manually partition the circuit (Figure 1). The hierarchical structure of a circuit is displayed as a tree. Circles represent leaf nodes and rectangles represent higher level functional blocks. A circuit designer can use his/her knowledge about the structure of the circuit to manually partition components into approximately balanced parts with low communication overheads. Manual partitioning method can also be combined with other partitioning algorithms. A designer can assign an initial manual partition to the circuit and apply automatic partitioning algorithms on some of the sub-partitions to obtain a balanced decomposition of the circuit into a larger number of partitions

In order to simulate distributed events in the correct global order, MIRSIM provides the following synchronization algorithms:

• sequential or Global Event List algorithms,
• three parallel conservative algorithms that respectively use null messages, conditional events, and a combination of the preceding two schemes called the accelerated null message protocol (ANP),
• a parallel optimistic algorithm based on space-time simulations, and
• the Ideal Simulation Protocol (or ISP) which is based on the concept of the critical path to predict a realistic lower bound on the execution time of a given parallel model.

A set of circuits used in this performance study are listed in Table 1. For each circuit, we indicate the simulation time using IRSIM and the sequential execution of MIRSIM. As seen from the figure, on average MIRSIM is only 2.1% slower. A major difference between IRSIM and MIRSIM is that the former keeps track of all state transition of all nodes for interactive debugging. However, MIRSIM only keeps the state histories of nodes specified in the command file; this accounts for the few cases where MIRSIM is actually faster. Although it is hard to quantify the performance impact of the additional trace for MIRSIM, preliminary experiments indicate that it is not a significant overhead.

Figure 2 summarizes the results of the simulation study for the VLSI circuits. The experiments were executed on a 32-node IBM SP2 running AIX -- each node is a RS/6000 workstation processor with 256M bytes of main memory and 66.7MHz clock speed. For each circuit in our test suite, we present the best speedup that was obtained using both conservative and optimistic algorithms and the specific partitioning algorithm that yielded the corresponding result. The speedup is measured related to the original IRSIM execution. As can be seen from the figure, no single synchronization or partitioning algorithm dominated. However, where feasible, acyclic partitions appeared to yield the best performance. Acyclic partitions yield better performance as they eliminate circular dependencies in the parallel model. Consider a circuit decomposition that contains two partitions P₁ and P₂. Assume that the output from some transistor in P₁ is an input to another transistor that is in P₂. This requires that a message be sent from P₁ to P₂ whenever the value of this output changes; we say that P₁ is dependent on P₂. In an acyclic partitioning, if a partition, say P_i, is dependent on P_j, then P_j will not be dependent on P_i and vice versa. For conservative algorithms, this significantly improves the lookahead properties of the entities resulting in a dramatic reduction in null messages. For optimistic algorithms, it reduces the number of rollbacks, although the improvements in execution time are not as dramatic.

Where acyclic partitions were not feasible, manual partitioning yielded better performance as the designer could use structural information from the circuits to minimize communication and synchronization overheads. The figure also includes the speedup predicted by the ISP protocol. Interestingly, in many cases, the performance of the simulator is close to the lower bound predicted by ISP, which clearly indicates that further improvements in performance are likely to come from better partitioning algorithms or more efficient IPC implementations than from any improvements in the synchronization mechanism itself.

Publications