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.
A Conflict-Resilient Lock-Free Calendar Queue for Scalable Share-Everything PDES Platforms / Marotta, Romolo; Ianni, Mauro; Pellegrini, Alessandro; Quaglia, Francesco. - ELETTRONICO. - (2017), pp. 15-26. (Intervento presentato al convegno 5th ACM SIGSIM Conference on Principles of Advanced Discrete Simulation, SIGSIM-PADS 2017 tenutosi a Singapore; Singapore) [10.1145/3064911.3064926].
A Conflict-Resilient Lock-Free Calendar Queue for Scalable Share-Everything PDES Platforms
MAROTTA, ROMOLO
;IANNI, MAURO
;PELLEGRINI, ALESSANDRO
;QUAGLIA, Francesco
2017
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.File | Dimensione | Formato | |
---|---|---|---|
Marotta_Postprint_A-conflict-resilient _2017.pdf
accesso aperto
Note: https://dl.acm.org/citation.cfm?doid=3064911.3064926
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
547.3 kB
Formato
Adobe PDF
|
547.3 kB | Adobe PDF | |
Marotta_A-conflict-resilient _2017.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
697.96 kB
Formato
Adobe PDF
|
697.96 kB | Adobe PDF | Contatta l'autore |
Marotta_Frontespizio-indice_A-conflict-resilient _2017.pdf
solo gestori archivio
Tipologia:
Altro materiale allegato
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
312.01 kB
Formato
Adobe PDF
|
312.01 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.