State Causality Analysis of Conservative Parallel Network Simulation

Critical path analysis is a traditional way to study the parallelism of conservative parallel simulation. In this paper, we propose a new technique called state causality analysis to accurately model the conservative parallel network simulation. A theorem of simulation time advancement is presented and proved. Different from critical path analysis, our method focuses on the dependency of the logical process states instead of the unpredictable events. The effects of many algorithm-independent factors, such as lookahead, I/O overhead, physical transfer delay, processor speed and event distribution, are all taken into consideration. With this method, the complicated relations between parallel performance and the algorithm-independent factors can be revealed distinctly, which however cannot be revealed by critical path analysis in most cases. The theoretical analyses and experiments show that our method always predict a stricter upper bound on the performance of a given network simulation task than critical path analysis, which may provide a baseline to evaluate the conservative synchronization algorithms excluding the effects of algorithm-independent factors.