In the last two decades, great attention has been devoted to the design of non-blocking and linearizable data structures, which enable exploiting the scaled-up degree of parallelism in off-the-shelf shared-memory multi-core machines. In this context, priority queues are highly challenging. Indeed, concurrent attempts to extract the highest-priority item are prone to create detrimental thread conflicts that lead to abort/retry of the operations. In this article, we present the first priority queue that jointly provides: (i) lock-freedom and linearizability; (ii) conflict resiliency against concurrent extractions; (iii) adaptiveness to different contention profiles; and (iv) amortized constant-time access for both insertions and extractions. Beyond presenting our solution, we also provide proof of its correctness based on an assertional approach. Also, we present an experimental study on a 64-CPU machine, showing that our proposal provides performance improvements over state-of-the-art non-blocking priority queues.

Marotta, R., Ianni, M., Pellegrini, A., Quaglia, F. (2024). A conflict-resilient lock-free linearizable calendar queue. ACM TRANSACTIONS ON PARALLEL COMPUTING, 11(1), 1-32 [10.1145/3635163].

A conflict-resilient lock-free linearizable calendar queue

Marotta, Romolo;Pellegrini, Alessandro;Quaglia, Francesco
2024-01-01

Abstract

In the last two decades, great attention has been devoted to the design of non-blocking and linearizable data structures, which enable exploiting the scaled-up degree of parallelism in off-the-shelf shared-memory multi-core machines. In this context, priority queues are highly challenging. Indeed, concurrent attempts to extract the highest-priority item are prone to create detrimental thread conflicts that lead to abort/retry of the operations. In this article, we present the first priority queue that jointly provides: (i) lock-freedom and linearizability; (ii) conflict resiliency against concurrent extractions; (iii) adaptiveness to different contention profiles; and (iv) amortized constant-time access for both insertions and extractions. Beyond presenting our solution, we also provide proof of its correctness based on an assertional approach. Also, we present an experimental study on a 64-CPU machine, showing that our proposal provides performance improvements over state-of-the-art non-blocking priority queues.
2024
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore ING-INF/05
Settore IINF-05/A - Sistemi di elaborazione delle informazioni
English
Data structures design and analysis
Shared memory algorithms
Concurrent algorithms
Non-blocking priority queue
Pending event set
Marotta, R., Ianni, M., Pellegrini, A., Quaglia, F. (2024). A conflict-resilient lock-free linearizable calendar queue. ACM TRANSACTIONS ON PARALLEL COMPUTING, 11(1), 1-32 [10.1145/3635163].
Marotta, R; Ianni, M; Pellegrini, A; Quaglia, F
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
Mar23b.pdf

solo utenti autorizzati

Tipologia: Documento in Post-print
Licenza: Copyright degli autori
Dimensione 1.1 MB
Formato Adobe PDF
1.1 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
3635163.pdf

solo utenti autorizzati

Tipologia: Versione Editoriale (PDF)
Licenza: Copyright degli autori
Dimensione 2.12 MB
Formato Adobe PDF
2.12 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/2108/363227
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact