Lock-free simulation algorithm to enhance the performance of sequential and parallel DEVS simulators in shared-memory architectures

This paper presents a new algorithm for the Discrete EVent System Specification (DEVS) formalism that improves the performance of simulating complex systems by reducing the number of iterations through the model components in each simulation step. It also minimizes unnecessary visits to model components by propagating simulation routines only when necessary. Additionally, we provide two parallel versions of this new simulation algorithm that use work-stealing scheduling and avoid locking mechanisms without compromising the validity of the execution in shared-memory architectures. We implemented the proposed algorithms in the xDEVS simulator and evaluated their performance using the DEVStone synthetic benchmark. The results show that the proposed algorithms outperform state-of-the-art alternatives. For computationally intensive models, parallel implementations achieve high parallelism efficiency. Furthermore, they are more resilient to model complexity than the sequential algorithm, showing better performance for complex models even without computational overhead in state transition functions. • A new simulation algorithm for DEVS models that significantly reduces execution overhead in each simulation step, enhancing performance. • Two different parallel implementations of this algorithm that achieve high parallelism efficiency. • Parallel algorithms avoid locking mechanisms, reducing thread contention and improving overall simulation speed. • Work-stealing scheduling is used to improve load balance, adapting better to dynamically multi-threaded programs, and allowing for nested parallelism without flattening the DEVS model. • Empirical results demonstrate that the proposed algorithms outperform the fastest state-of-the-art simulators, especially in computationally intensive scenarios. • Parallel implementations show better performance for complex models even without computational overhead in state transition functions. • In models with computation-intensive state transition functions, parallel implementations show parallelism efficiencies above 90%, indicating low thread contention in complex models.