Analytical performance modeling for null message-based parallel discrete event simulation

Abstract

This paper presents a new analytical performance analysis for null message-based parallel discrete event simulation(PDES). Our analysis builds upon the key operation of selecting simulation events for processing in the null message algorithms. The results not only explain the well-known facts of how the look ahead capability of individual simulation processes (called logical processes, or LPs) affect the simulation performance, but also reveals quantitatively how the look ahead, the communication topology, the computation and communication delays, and the flow control mechanism affect the simulation performance. We first show that all of the LPsin a strongly connected component in the communication topology asymptotically progress at the same speed, regardless of their individual characteristics and their share of computation resource. Second, we derive an analytical upper bound on the simulation performance. The derivation shows that the ratio between the sum of the look ahead and the sum of the event processing and communication delays of LPs in a cycle bounds the simulation speed from the above, and the cycle of LPs imposes the tightest upper bound becomes the bottleneck of the simulation. We conduct a series of simulation experiments to empirically validate our findings. Moreover, we show that by using the derived upper bound as an optimization guidance, we improve the partitioning of a simple parallel simulation example and achieve a four times speedup against the same simulation based on a classic min-cut partitioning strategy. © 2011 IEEE.