KIT | KIT-Bibliothek | Impressum | Datenschutz

Engineering MultiQueues: Fast relaxed concurrent priority queues

Williams, Marvin; Sanders, Peter; Dementiev, Roman


Priority queues with parallel access are an attractive data structure for applications like prioritized online scheduling, discrete event simulation, or greedy algorithms. However, a classical priority queue constitutes a severe bottleneck in this context, leading to very small throughput. Hence, there has been significant interest in concurrent priority queues with relaxed semantics. We investigate the complementary quality criteria rank error (how close are deleted elements to the global minimum) and delay (for each element x, how many elements with lower priority are deleted before x). In this paper, we introduce MultiQueues as a natural approach to relaxed priority queues based on multiple sequential priority queues. Their naturally high theoretical scalability is further enhanced by using three orthogonal ways of batching operations on the sequential queues. Experiments indicate that MultiQueues present a very good performance-quality tradeoff and considerably outperform competing approaches in at least one of these aspects.
We employ a seemingly paradoxical technique of "wait-free locking" that might be of more general interest to convert sequential data structures to relaxed concurrent data structures.

Verlagsausgabe §
DOI: 10.5445/IR/1000138387
Veröffentlicht am 01.10.2021
DOI: 10.4230/LIPIcs.ESA.2021.81
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2021
Sprache Englisch
Identifikator ISBN: 978-3-9597720-4-4
ISSN: 1868-8969
KITopen-ID: 1000138387
Erschienen in 29th Annual European Symposium on Algorithms (ESA 2021): 6-8 September 2021, online. Ed.: P. Mutzel
Veranstaltung 29th Annual European Symposium on Algorithms (ESA 2021), Online, 06.09.2021 – 08.09.2021
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH (LZI)
Seiten Art.-Nr.: 81
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 204
Nachgewiesen in Scopus
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page