Comparing Speculative Synchronization Algorithms for Continuous-Time Agent-Based Simulations

Philipp Andelfinger, Andrea Piccione, Alessandro Pellegrini, and Adelinde Uhrmacher

Abstract:
Continuous-Time agent-based models often represent tightly-coupled systems where agents’ state transitions occur in close interaction with neighbouring agents. Without artificial discretization, the potential for near-instantaneous propagation of effects across the model challenges their parallel execution. Although existing algorithms can tackle the largely unpredictable nature of such simulations through speculative execution, they are subject to trade-offs concerning the degree of optimism, the probability and cost of rollbacks, and locality exploitation. This paper aims to understand the suitability of asynchronous and synchronous parallel simulation algorithms when executing continuous-time agent-based models with rate-driven stochastic transitions. We present extensive measurement results comparing optimized implementations under various configurations of a parametrizable simulation model of the epidemic spread of disease. Our results show that the amount of locality in the agent interactions is the decisive factor for the relative performance of the approaches. We identify remaining hurdles for higher simulation performance with the two classes of algorithms and outline potential refinements based on profiling results.

BibTeX Entry: