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 -