Predicting Runtime Performance Bounds of Expanded Parallel Discrete Event Simulations

Predicting and analyzing runtime performance characteristics is a vital step in the development process of parallel discrete event simulations. For instance, model developers need to identify and eliminate performance bottlenecks within a simulation model in order to derive a model structure that aids parallel execution. Similarly, developers of parallel simulation frameworks require means of assessing the efficiency of the framework. In this paper, we present a performance prediction methodology that computes the best possible performance bound for expanded parallel discrete event simulations in the context of our Horizon simulation framework. The methodology builds upon a linear program which calculates an optimal event execution schedule for a given simulation and a set of CPUs. In order to mitigate the complexity of this NP-complete scheduling problem, we introduce performance optimizations and relaxations of the linear program.