Abstract
In this work, two techniques were proposed to greatly improve the performance
of parallel logic simulation. One is a partitioning algorithm and the other
is a hybrid parallel simulation algorithm. In addition, a new concurrency
metric is proposed to evaluate partitioning algorithms before the execution
of parallel simulation. Experiments were performed to demonstrate that
the two proposed techniques together provide significant reduction in parallel
simulation time.
Unlike most other partitioning algorithms, the proposed algorithm preserves
circuit concurrency by assigning to processors circuit gates that can be
evaluated at about the same time. As a result, the
improved concurrency preserving partitioning (iCPP) algorithm can provide
instantaneous load balancing, not aggregated load balancing, throughout
the period of a parallel simulation. This is especially important when
the algorithm is used together with a Time Warp simulation where a high
degree of concurrency can lead to fewer rollbacks and better performance.
The results are compared with several partitioning algorithms to show that
reasonable speedup may be achieved with the algorithm.
A hybrid parallel gate-level logic simulator that integrates an event lookahead
technique and the Time Warp optimistic protocol is proposed and was implemented
on an IBM SP2 and an Intel Paragon machine. Without using global synchronization,
the Event-lookahead Time Warp (ETW) protocol reduces
multiple evaluations and the number of erroneous events caused by the Time
Warp event-driven simulation. As a result, its performance is expected
to be good on different circuits.