Refereed Publications: Abstract and Full paper


Title: Parallel Optimistic Logic Simulation with Event Lookahead
Gate-level logic simulation is a low-granularity application that is very challenging for parallel processing. Parallel discrete event simulation (PDES) on general-purpose machines can reduce the logic simulation time for large circuits considerably.  However, it generates more events than necessary for certain high activity circuits and produces inconsistent speedup over different circuits. This paper presents an optimistic parallel discrete event simulation technique that can reduce unnecessary events and produce more consistent speedup when circuit glitches are not considered. This is possible because, even though glitches contribute to a sizable portion of events during a simulation, they can be ignored most of the times.

The proposed Event-lookahead Time Warp (ETW) algorithm can look ahead, combine and execute multiple events at each gate optimistically, and recover from an error by using a rollback mechanism as used in the original Time Warp algorithm.  To reduce the rollback cost of the algorithm and to support efficient run-time scheduling, a new data structure, called a governor heap, was proposed and implemented.  The governor heap contains a heap structure and multiple linked lists, one for each gate or flip-flop.  By separating events into short linked lists, the governor heap is very efficient and scalable in inserting, deleting, and combining events for large-scale simulations.
PostScript (jpdc98.ps)


Title: Concurrency Preserving Partitioning Algorithm
 for Parallel Logic Simulation
A partitioning algorithm for parallel discrete event gate-level logic simulations is proposed in this paper. Unlike most other partitioning algorithms, the proposed algorithm preserves computation 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 better 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 algorithm consists of three phases and three conflicting goals can be separately considered so to reduce computational complexity.

To evaluate the quality of partitioning algorithms in terms of preserving concurrency, a concurrency metric that requires neither sequential nor parallel simulation is proposed.  A levelization technique is used in computing the metric so to determine gates which can be evaluated at about the same time.  A parallel gate-level logic simulator is implemented on an INTEL Paragon and an IBM SP2 to evaluate the performance of the iCPP algorithm.  The results are compared with several other partitioning algorithms to show that the iCPP algorithm does preserve concurrency pretty well and reasonable speedup may be achieved with the algorithm.
PostScript (vlsidesign.ps)



Title: Parallel Optimistic Logic Simulation with Event Lookahead
Parallel discrete event simulation (PDES) on general-purpose machines can reduce the logic simulation time for large circuits considerably.  However, it generates more events than necessary for certain high activity circuits and produces inconsistent execution times over different circuits. This is because glitches contribute to a sizable portion of events during a simulation.The proposed Event-lookahead Time Warp (ETW) algorithm can look ahead, combine and execute multiple events at each gate  optimistically, and recover from an error by using a rollback mechanism as used in the original Time Warp algorithm. As a result, it reduces unnecessary events and produces  more consistent execution times and reasonable speedups.
PostScript (icpp98.ps)


Title: Concurrency Preserving Partitioning (CPP) for Parallel Logic Simulation
Based on a linear ordering of vertices in a directed graph, a linear-time partitioning algorithm for parallel logic simulation is presented.  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 concurrency preserving partitioning (CPP) algorithm can provide better 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 algorithm consists of three phases, and three conflicting goals can be separately considered in each phase so to reduce computational complexity.  A parallel gate-level circuit simulator is implemented on an Intel Paragon machine to evaluate the performance of the CPP algorithm.  The results are compared with two other partitioning algorithms to show that reasonable speedup may be achieved with the algorithm.
Postscript (pads96.ps)
PDF format (pads96.pdf)
 



Title: Parallel Logic Simulation Using Time Warp  on Shared-Memory Multiprocessors
   This paper presents an efficient parallel logic-circuit simulation scheme based on the Time Warp optimistic algorithm. The Time Warp algorithm is integrated with a new Global Virtual Time (GVT) computation scheme for fossil collection. The new GVT computation is based on a token ring passing method, so that global chronization is not required in a shared-memory multiprocessor system. This allows us to process large logic simulation problems, where the GVT computation is executed frequently for fossil collection due to limited memory space.  We also presented how to reduce the frequency of the GVT computation and the rollback ratio by scheduling the process with the smallest timestamp first. We implemented the parallel logic-circuit simulator using the Time Warp on BBN Butterfly machines, and the experimental results show that our algorithm provides a significant speedup in processing time even for very large circuits.
Postscript (ipps94.ps)