Out-of-Order Discrete Event Simulation: Fighting Memory Boundedness while Running DES Models

In this article we present Out-of-order Discrete Event Simulation (ODES), a solution for sequential style execution of DES models not following timestamp order. ODES ensures anyway the same identical simulation results as timestamp ordered execution, thanks to fully correct maintenance of the simulation model data flow. At the same time, it drastically reduces the memory boundedness—namely, the impact of cache misses and of stale CPU cycles—on the simulation model execution speed. Beyond presenting foundational concepts, we also discuss our ODES-engine implementation, based on the c programming language. Additionally, we report experimental data for comparing ODES with the classical timestamp ordered execution of simulation models according to conventional sequential simulation. The relevance of ODES compared to classical timestamp ordered sequential DES not only stands in its benefits on performance, rather ODES can also assume the role of new reference for determining the speedup achievable via parallel/distributed discrete event simulation systems, compared to the single thread execution. Also, thanks to its improvements in the interaction with RAM, ODES constitutes a new framework for effective parallel replication of simulation experiments on multi-processor/multi-core machines.