Termination and Output Measure Generation in Optimistic and Conservative-Synchronous Parallel Simulations

This paper proposes algorithms to stop parallel discrete event simulations using arbitrary termination conditions and to collect output measures. We show that the time complexity of termination can be higher than that of the underlying simulation; therefore termination can reduce or even preclude speed-up. We propose simulation protocol independent algorithms solving the termination and generation problems. Implementations of the algorithms for conservative-synchronous and optimistic protocols are presented. The predicted and measured increase in real time required to execute a time warp and a bounded lag simulation equipped with our termination algorithms is presented. The chief conclusion is that when the time required for each evaluation of the termination condition exceeds the mean time to execute an event, termination can dominate the simulation running time.