A PRACTICAL EFFICIENCY CRITERION FOR THE NULL MESSAGE ALGORITHM

This paper presents a quantitative criterion for efficient execution of the Null Message Protocol, the bestknown conservative parallel discrete event simulation (PDES) protocol. By using the criterion, a model designer can use lookahead and communication latency as input and improve the efficiency of parallelization. Earlier works consider lookahead in relation to model properties like timestamp increment and in isolation from the capabilities of the underlying hardware/software simulation environment, and have not been able to provide quantitative criteria for performance prediction. Our results suggest that the performance impact of lookahead can only be quantified when linked to other performance factors such as communication latency and throughput between partitions of a parallelized simulation model. The latency and throughput issues are becoming of increasing importance as clusters gain popularity as PDES platforms. The criterion is based on a novel concept of the coupling factor, and allows one to use intuitive and easy-to-measure input parameters. The criterion can be used to assess simulation models ’ potential for parallel execution as well as the maximum partitioning that may still potentially yield good performance. This paper is also novel in that it uses the Ideal Simulation Protocol as a benchmark