Parallel discrete event simulation: a shared memory approach

Distributed simulation has been the subject of several simulated performance studies; little or no experimental data have heretofore been available. Obtaining such data was the primary goal of this work. Using queueing networks as the simulation application, we simulated a variety of such networks with varying workloads using several variations of the Chandy-Misra algorithm on a shared memory machine. These experiments show that, with rare exception, the Chandy-Misra approach to distributed simulation is not a viable approach to parallel simulation of queueing network models. There are two primary reasons for this. First, a single processor implementation of the Chandy-Misra algorithm is sometimes slower than the equivalent sequential, event-driven simulation. Thus, multiple processors are needed just to recoup the loss due to the inefficiency. Second, networks with cycles require deadlock avoidance or recovery techniques. These techniques are extremely costly, and there is little prospect that they can be reduced to acceptable levels.