Browse Theses

This thesis contains two parts. In the first part, we focus on the performance analysis of existing parallel simulation protocols. In the second part, we develop the parallel simulation protocols based on time-space division.

For chronological parallel simulations, we prove that all logical processes of the simulated system have the same simulation speeds. This result is called conservation principle. Several equivalent statements of the principle are derived for analyzing the performances of chronological simulations. We compare several most popular asynchronous parallel simulation protocols. Our results show that if the synchronizing overheads are ignored, then Time Warp simulations are faster than Chandy-Misra ones. For Time Warp simulation, the trade-off between the simulation speed and amount of memory used in the simulation is studied. We show that the Time Warp simulation with limited memory may reach the same performance as that with unlimited memory. A model for Time Warp simulation is developed. The model is suitable for assessing the performance of a broad class of queueing network simulations using heterogeneous processors.

Two parallel simulation protocols based on time-space division are proposed. The first one is for a simulation that can be formulated as a network flow problem. The latter is solved by using multiple processors in parallel. We apply this protocol to the simulations of feedforward queueing networks with finite or infinite buffers. The second protocol is for batch mean steady state simulations. Here a simulator generates a sample path tree. All paths in the tree have the same root, and each arc between two nodes is a sub-path, and simulated by a processor.