4.0 Parallel Discrete Event Simulation

As the size and complexity of simulations grow, the amount of time required to complete them grows. If we attempt to validate complex simulations by making multiple runs, the time to complete a simulation test may become prohibitive. Fortunately, computer scientists have developed Parallel Discrete Event Simulation (PDES) to address this problem. PDES speeds up simulation execution by distributing the simulation across a number of processors.

To distribute the simulation, we need to decompose the problem we are simulating. The decomposition of ecological simulations is spatially based. That is, we divide up the ecosystems geographical region and allow the simulation entities to associate themselves with these regions. The association between entities and regions is made by having the regions responsible for processing and scheduling the entities events. In PDES terms, the regions are Logical Processors (LP).

Ideally, if we have 10 processors and distribute 10 LPs across these processors, the simulation should run 10 times faster. Unfortunately, this is does not happen in practice. The fact that we have decomposed and distributed the problem forces communication between processors. For example, when an animal moves from on region to another, both regions have to be aware of the movement. This means that the two processors associated with the regions have to exchange the information before the necessary variables are set. The information exchange involves sending messages across some sort of network which is always slower than direct memory access. Perhaps the most insidious problem associated with parallel simulations is synchronization.

To illustrate the synchronization problem, consider a simulation running on two LPs, LPA and LPB. Since each LP can schedule and process events, there is no reason to assume that the simulation time, the Local Virtual Time (LVT) on LPA is the same as the LVT on LPB--remember that LVT is dependent on the timestamp of the event being processed. Assume that LPA has an LVT of 100 and LPB has an LVT of 90. Next assume that LPB wants to communicate with LPA by sending a message with a time stamp of 95. In effect, LPB is trying to affect LPA's present, by altering its past. This error is called a local causality constraint (lcc) violation.

To correct lcc violation error, computer scientists have developed a number of approaches which are broadly categorized as conservative or optimistic. The conservative approach involves preventing lcc violations and the optimistic approach fixes any errors that occur.