Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

4.2 WHAT IS PARALLEL SIMULATION?

In this section, we introduce the basic terminology and major issues pertaining to parallel simulation that should provide exactly the same solution to a problem as a sequential simulation. Thus, in specifying and developing a parallel simulator, it is important to understand the sequential nature of the simulation.

In a discrete-event simulation, the model evolution is defined by instantaneous events. Each event corresponds to a transition in a portion of the model state, composed of state variables, each describing a characteristic of the model. Each event also has a simulation time associated with it, called time stamp, which defines its occurrence time. Each event may in turn generate new future events.

The generation of new events and the dependency of their transitions on state variables that previous events may have updated, define a relation of causal order (namely, a partial order) among events. Related events are said to be causally dependent, whereas unrelated ones are called concurrent. In order to guarantee the correctness, concurrent events can be safely processed in any order in a simulation, whereas causally dependent events must be processed according to the causal order. Thus, to ensure the strict chronological order, events are processed one at a time, resulting in an (apparently) sequential program. A typical template for a sequential simulation is given in Fig. 4.1.

Only by eliminating the event list in its traditional form ...