1 Search Results for "Dementiev, Roman"

Document
DOI: 10.4230/LIPIcs.ESA.2021.81
Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues

Authors: Marvin Williams, Peter Sanders, and Roman Dementiev

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
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.
Cite as

Marvin Williams, Peter Sanders, and Roman Dementiev. Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 81:1-81:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{williams_et_al:LIPIcs.ESA.2021.81,
  author =	{Williams, Marvin and Sanders, Peter and Dementiev, Roman},
  title =	{{Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{81:1--81:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.81},
  URN =		{urn:nbn:de:0030-drops-146627},
  doi =		{10.4230/LIPIcs.ESA.2021.81},
  annote =	{Keywords: concurrent data structure, priority queues, randomized algorithms, wait-free locking}
}
  • Refine by Author
  • 1 Dementiev, Roman
  • 1 Sanders, Peter
  • 1 Williams, Marvin

  • Refine by Classification
  • 1 Computing methodologies → Concurrent computing methodologies

  • Refine by Keyword
  • 1 concurrent data structure
  • 1 priority queues
  • 1 randomized algorithms
  • 1 wait-free locking

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact