Background 

Logic simulators are used in order to verify the logical and timing speci-
fication of designed circuits. Since logic simulation is one of the most time-
consuming stages in LSI design, faster simulators are required. In addition, 
flexibility is also needed. 

A parallel logic simulator is one likely way of producing quick and flexible 
simulation. We built a parallel logic simulator on the PIM machine, as a first 
but significant step to the realization of super high performance simulators 
on future hyper-parallel machines. 

Specification of the Simulator 

The simulator simulates combinatorial circuits and sequential circuits that 
have feedback loops. It handles three values: Hi, Lo, and X (unknown). A 
different delay time can be assigned to each gate (non-unit delay model). 
Since this simulator treats gates only, flip-flops and other functional blocks 
should be completely decomposed into gates. 

Parallel Discrete Event Simulation and Time Warp 

Parallel logic simulation is treated as a typical application of parallel dis-
crete event simulation (PDES). PDES can be modeled so that several ob-
jects (corresponding to gates) change their states by communicating with 
each other. A message has information of an event whose occurrence time is 
stamped on the message (time-stamp). Since messages should be received and 
evaluated in the time-stamp order by their destination objects, a time-keeping 
mechanism is needed. 

We adopted the Time Warp mechanism (TW) as the time-keeping mech-
anism. In TW, each object usually acts according to received messages and 
also records the history of messages and states, optimistically assuming that 
messages arrive chronologically. When a message arrives at an object out 
of time-stamp order, however, the object rewinds its history (this process is 
called rollback), and makes adjustments as if the message had arrived in cor-
rect time-stamp order. If there are messages which should not have been sent, 
the object also sends antimessages in order to cancel those messages. 

The rollback process has been suspected to contain large overheads which 
might affect performance adversely. So, we added several devices to reduce 
the overheads so that the simulator can run efficiently on the PIM machine. 


					- 52 -