A Lock-Free O(1) Event Pool and its Application to Share-Everything PDES Platforms
Romolo Marotta, Mauro Ianni, Alessandro Pellegrini, and Francesco Quaglia
Published in: Proceedings of the 20th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications
Download PDF
Abstract:
The large diffusion of highly-parallel shared-memory multi-core machines has led Parallel Discrete Event Simulation (PDES) platforms to a shift towards a share-everything model. This model is based on loose coupling between simulation objects and threads, lasting (as an extreme) no more than the lifetime of individual events. Concurrent threads can therefore CPU-dispatch events destined to any object at any point in time, thus fully sharing the workload of events to be processed on a fine grain basis. This demands for efficient mechanisms to share the overall pool of pending events by enabling parallelism in insertion and extraction operations. In this article we present a lock-free event pool which also provides amortized O(1) time complexity for both insertions and extractions. It can sustain highly concurrent accesses, while not leading to noticeable performance degradation when scaling up the thread count. Experimental results demonstrate that our solution stands as a core facility capable of further raising up the pragmatical impact of such an emerging share-everything PDES paradigm.
BibTeX Entry:
author = {Marotta, Romolo and Ianni, Mauro and Pellegrini, Alessandro and Quaglia, Francesco},
booktitle = {Proceedings of the 20th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications},
title = {A Lock-Free O(1) Event Pool and its Application to Share-Everything PDES Platforms},
year = {2016},
month = sep,
note = {Winner of the Best Paper Award},
publisher = {IEEE Computer Society},
series = {DS-RT},
doi = {10.1109/DS-RT.2016.33},
location = {London, UK}
}