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.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.