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.
2017
5th ACM SIGSIM Conference on Principles of Advanced Discrete Simulation, SIGSIM-PADS 2017
Parallel Discrete Event Simulation; Non-Blocking Algorithms; Priority Queue
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
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].
File allegati a questo prodotto
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/974295
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 6
social impact