A Conflict-Resilient Lock-Free Calendar Queue for Scalable Share-Everything PDES Platforms
Romolo Marotta, Mauro Ianni, Alessandro Pellegrini, and Francesco Quaglia
Published in: Proceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation
Download PDF
Abstract:
Emerging share-everything Parallel Discrete Event Simulation (PDES) platforms rely on worker threads fully sharing the workload of events to be processed. These platforms require efficient event pool data structures enabling high concurrency of extraction/insertion operations. Non-blocking event pool algorithms are raising as promising solutions for this problem. However, the classical non-blocking paradigm leads concurrent conflicting operations, acting on a same portion of the event pool data structure, to abort and then retry. In this article we present a conflict-resilient non-blocking calendar queue that enables conflicting dequeue operations, concurrently attempting to extract the minimum element, to survive, thus improving the level of scalability of accesses to the hot portion of the data structure—namely the bucket to which the current locality of the events to be processed is bound. We have integrated our solution within an open source share-everything PDES platform and report the results of an experimental analysis of the proposed concurrent data structure compared to some literature solutions.
BibTeX Entry:
author = {Marotta, Romolo and Ianni, Mauro and Pellegrini, Alessandro and Quaglia, Francesco},
booktitle = {Proceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation},
title = {A Conflict-Resilient Lock-Free Calendar Queue for Scalable Share-Everything PDES Platforms},
year = {2017},
month = may,
pages = {41--52},
publisher = {ACM},
series = {PADS},
doi = {10.1145/3064911.3064927},
location = {Singapore}
}