Benchmarking Parallel Discrete Event Simulations

Abstract

The single core performance of hardware processors have seen only modest increase over the past decade. Yet simulation needs are growing in both simulation size, and complexity. The Parallel Discrete Event Simulation (PDES) field, is concerned with executing a single simulation run using multiple threads. Executing such a simulation in parallel is non-trivial and requires synchronization algorithms to ensure correctness. To compare performance between synchronization algorithm, the PHOLD benchmark is commonly used. In the PDES field, threads (or 'Logical Processes') can only communicate via messages. The allowed sending pattern can be formulated as a directed graph, where tail nodes are allowed to send messages to the head node. We will present the EPHOLD benchmark algorithm, a more generalized version of the PHOLD benchmark, and a mathematical model to predict the amount of parallelism that a given EPHOLD benchmark will attain when a specific PDES synchronization algorithm (i.e. YAWNS) is used. We will experimentally evaluate the predictive capabilities of this mathematical model, and show bottlenecks that emerge when using EPHOLD yet remain hidden with PHOLD. The EPHOLD and PHOLD benchmarks will be experimentally examined for Scale Free and Complete graphs using three synchronization algorithms commonly used in the PDES field.