The standard approach to simulation of a program that consists of a number of asynchronous message-passing processes is to use a sequential discrete-event simulator. When viewed as a discrete-event model, each process of the compiled program contains only three types of events: local code blocks, or code that does not involve communication with another process, send events, and receive events. Although it is possible to simulate local code blocks, most simulators use direct execution[CMM88,MF88] as this has been shown to be more efficient. In direct execution, the time to execute the local code block is either measured using the physical processor clock and scaled appropriately to model the target processor, or it is computed by counting the number of instruction cycles that will be needed to execute the local code block. The cycle count may then be directly translated to a time measure depending on the clock and statistical cache characteristics of the target processor. Send and receive events are typically simulated by estimating the transmission time for each message and including the (simulation) timestamp at which the corresponding message will be received with each message. A separate logical clock is maintained for each process that indicates the (simulation) time at which each event occurs in the corresponding process.
Thus the basic simulation methodology is as follows: the compiler that generates the SPMD program from the data parallel program is modified to instrument the resulting compiled code such that accurate timestamps for each event can be generated by the simulator:
, and on completion of the local code block, the logical clock for
this thread is advanced by 
.
Once the timestamps have been generated for each event in the simulation model, the model can be executed using either sequential or parallel algorithms. Model execution using a sequential algorithm is straightforward: events scheduled by all processes are stored in increasing order of their timestamps in a global event list. At each step, the event with the smallest timestamp is removed from the global list and executed; any additional events (e.g. send events) generated by the execution of this event are inserted in the global list.
However, parallel execution of the preceding model is considerably more complex. Each processor of the simulation simulates one or more processes from the target program. Although the processor can determine the earliest events among the processes that are mapped on it, it is harder for a processor to deduce whether its (locally) earliest event is in fact, globally the earliest. In general, a global synchronization may be required in the parallel simulator before simulation of each event (Note: simulation of an event may generate and schedule events at other processors, requiring that the globally earliest event be recomputed after each event!).
Two primary solutions have been suggested to eliminate this global periodic synchronization: conservative and optimistic. Conservative algorithms do not permit any causality error: a simulation object (also called an LP) cannot process an event until the system can guarantee that it will not subsequently receive a message (event) with an earlier timestamp. This constraint may introduce deadlocks, which are typically handled by incorporating deadlock detection[Mis86b] or deadlock avoidance[Mis86b,Cha89a] mechanisms into the simulation algorithm. Optimistic algorithms[Jef85,Cha89b] allow an LP to process messages out of order; causality errors are corrected by using rollbacks and recomputations. Implementations of optimistic algorithms are usually more difficult because they require complex mechanisms for detection and handling of causality errors, termination detection, exception handling, and memory management. A comprehensive discussion of parallel discrete-event simulations may be found in [Fuj90,Mis86b]. A simulation language called Maisie[Bag94] has been designed at UCLA to support the execution of parallel discrete-event models. Maisie is a C-based discrete-event simulation language that was designed to cleanly separate a simulation model from the underlying algorithm (sequential or parallel) used for the execution of the model. With few modifications, a Maisie program may be executed using a sequential simulation algorithm, a parallel conservative algorithm or a parallel optimistic algorithm. The parallel simulation engine described in this chapter has been written in Maisie. Some optimizations, described in the next section, have been implemented to reduce the synchronization overheads. These optimizations have resulted in significant improvement to the performance of the parallel simulation engine as reported in Section 3.5.