Cited By
View all- Nikolaev RRavindran BAgrawal KLee I(2022)wCQProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538572(307-319)Online publication date: 11-Jul-2022
A lock-free relaxed concurrent queue for fast work distribution
Pages 454 - 456
Abstract
The operation of modern systems requires the low latency and high throughput of producer-consumer communication over shared memory. In order to achieve fast communication at high concurrency, we define a relaxed ordering model that splits the queue operations into two stages, the sequential assignment to queue slots and their subsequent concurrent execution. Based on this model, we design and implement the linearizable and lock-free algorithm called Relaxed Concurrent Queue Single (RCQS). We experimentally show that RCQS achieves factors to orders of magnitude advantage over the state-of-the-art queue algorithms in operation latency and item transfer speed.
References
[1]
David Dice and Oleksandr Otenko. 2011. Brief Announcement: Multilane - a Concurrent Blocking Multiset. In Symp. Parallelism in Algorithms and Architectures (San Jose, CA). ACM, New York, NY, 313--314.
[2]
Maurice Herlihy and Nir Shavit. 2012. The Art of Multiprocessor Programming. Morgan Kaufmann, Waltham, MA, Chapter 3, 54--61.
[3]
Giorgos Kappes and Stergios V. Anastasiadis. 2020. A User-Level Toolkit for Storage I/O Isolation on Multitenant Hosts. In Symp. Cloud Computing (Virtual Event, USA). ACM, New York, NY, 74--89.
[4]
Bernhard Kerbl, Michael Kenzel, Joerg H. Mueller, Dieter Schmalstieg, and Markus Steinberger. 2018. The Broker Queue: A Fast, Linearizable FIFO Queue for Fine-Granular Work Distribution on the GPU. In Intl. Conf. Supercomputing (Beijing, China). ACM, New York, NY, 76--85.
[5]
Justin Kopinsky. 2018. Relaxed Concurrent Ordering Structures. Ph.D. Dissertation. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA.
[6]
Maged M. Michael and Michael L. Scott. 1996. Simple, Fast and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. In Symposium on Principles of Distributed Computing (Philadelphia, PA). ACM, New York, NY, 267--275.
[7]
Adam Morrison and Yehuda Afek. 2013. Fast Concurrent Queues for x86 Processors. In Symposium on Principles and Practice of Parallel Programming (Shenzhen, China). ACM, New York, NY, 103--112.
[8]
Hamza Rihani, Peter Sanders, and Roman Dementiev. 2015. Brief Announcement: MultiQueues: Simple Relaxed Concurrent Priority Queues. In Symposium on Parallelism in Algorithms and Architectures (Portland, OR). ACM, New York, NY, 80--82.
[9]
William N. Scherer and Michael L. Scott. 2004. Nonblocking Concurrent Data Structures with Condition Synchronization. In Intl. Conf. Distributed Computing (Amsterdam, Netherlands). Springer, Berlin, Heidelberg, 174--187.
[10]
Chaoran Yang and John Mellor-Crummey. 2016. A Wait-free Queue as Fast as Fetch-and-Add. In Symp. Principles and Practice of Parallel Programming (Barcelona, Spain). ACM, New York, NY, 16:1--16:13.
Index Terms
- A lock-free relaxed concurrent queue for fast work distribution
Recommendations
A Family of Relaxed Concurrent Queues for Low-Latency Operations and Item Transfers
The producer-consumer communication over shared memory is a critical function of current scalable systems. Queues that provide low latency and high throughput on highly utilized systems can improve the overall performance perceived by the end users. In ...
Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems
IPDPS '03: Proceedings of the 17th International Symposium on Parallel and Distributed ProcessingWe present an efficient and practical lock-free implementation of a concurrent priority queue that is suitable for both fully concurrent (large multi-processor) systems as well as pre-emptive (multi-process) systems. Many algorithms for concurrent ...
Fast and lock-free concurrent priority queues for multi-thread systems
We present an efficient and practical lock-free implementation of a concurrent priority queue that is suitable for both fully concurrent (large multi-processor) systems as well as pre-emptive (multi-process) systems. Many algorithms for concurrent ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2021
507 pages
Copyright © 2021 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 February 2021
Check for updates
Author Tags
Qualifiers
- Poster
Conference
PPoPP '21: 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
February 27, 2021
Virtual Event, Republic of Korea
Acceptance Rates
PPoPP '21 Paper Acceptance Rate 31 of 150 submissions, 21%;
Overall Acceptance Rate 230 of 1,014 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 418Total Downloads
- Downloads (Last 12 months)92
- Downloads (Last 6 weeks)11
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
Cited By
View all- Nikolaev RRavindran BAgrawal KLee I(2022)wCQProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538572(307-319)Online publication date: 11-Jul-2022
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in