More Web Proxy on the site http://driver.im/

research-article

BQ: A Lock-Free Queue with Batching

Authors:

Victor Luchangco,

Erez PetrankAuthors Info & Claims

SPAA '18: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures

Pages 99 - 109

https://doi.org/10.1145/3210377.3210388

Published: 11 July 2018 Publication History

Abstract

Concurrent data structures provide fundamental building blocks for concurrent programming. Standard concurrent data structures may be extended by allowing a sequence of operations to be submitted as a batch for later execution. A sequence of such operations can then be executed more efficiently than the standard execution of one operation at a time. In this paper we develop a novel algorithmic extension to the prevalent FIFO queue data structure that exploits such batching scenarios. An implementation in C++ on a multicore demonstrates a significant performance improvement of up to 16x (depending on batch lengths), compared to previous queue implementations.

References

[1]

Dmitry Basin, Rui Fan, Idit Keidar, Ofer Kiselov, and Dmitri Perelman . 2011. Café: Scalable task pools with adjustable fairness and contention DISC.

Digital Library

[2]

Nachshon Cohen and Erez Petrank . 2015. Efficient memory management for lock-free data structures with optimistic access SPAA.

Digital Library

[3]

Robert Colvin and Lindsay Groves . 2005. Formal verification of an array-based nonblocking queue ICECCS.

Digital Library

[4]

Panagiota Fatourou and Nikolaos D. Kallimanis . 2011. A highly-efficient wait-free universal construction SPAA.

Digital Library

[5]

Panagiota Fatourou and Nikolaos D. Kallimanis . 2012. Revisiting the combining synchronization technique PPoPP.

Digital Library

[6]

John Giacomoni, Tipp Moseley, and Manish Vachharajani . 2008. FastForward for efficient pipeline parallelism: a cache-optimized concurrent lock-free queue. In PPoPP.

Digital Library

[7]

Anders Gidenstam, Håkan Sundell, and Philippas Tsigas . 2010. Cache-aware lock-free queues for multiple producers/consumers and weak memory consistency. In OPODIS.

Digital Library

[8]

James R. Goodman, Mary K. Vernon, and Philip J. Woest . 1989. Efficient synchronization primitives for large-scale cache-coherent multiprocessors. In ASPLOS.

Digital Library

[9]

Allan Gottlieb, Boris D. Lubachevsky, and Larry Rudolph . 1983. Basic techniques for the efficient coordination of very large numbers of cooperating sequential processors. TOPLAS Vol. 5, 2 (1983).

Digital Library

[10]

Andreas Haas, Michael Lippautz, Thomas A. Henzinger, Hannes Payer, Ana Sokolova, Christoph M. Kirsch, and Ali Sezgin . 2013. Distributed queues in shared memory: multicore performance and scalability through quantitative relaxation. In CF.

Digital Library

[11]

Danny Hendler, Itai Incze, Nir Shavit, and Moran Tzafrir . 2010. Flat combining and the synchronization-parallelism tradeoff SPAA.

Digital Library

[12]

Maurice Herlihy . 1991. Wait-free synchronization. TOPLAS Vol. 13, 1 (1991).

Digital Library

[13]

Maurice Herlihy, Beng-Hong Lim, and Nir Shavit . 1995. Scalable concurrent counting. TOCS Vol. 13, 4 (1995).

Digital Library

[14]

Maurice Herlihy and Jeannette M. Wing . 1990. Linearizability: a correctness condition for concurrent objects. TOPLAS Vol. 12, 3 (1990).

Digital Library

[15]

Moshe Hoffman, Ori Shalev, and Nir Shavit . 2007. The baskets queue. OPODIS (2007).

Digital Library

[16]

Christoph M. Kirsch, Michael Lippautz, and Hannes Payer . 2013. Fast and scalable, lock-free k-FIFO queues. In PaCT.

Digital Library

[17]

Alex Kogan and Maurice Herlihy . 2014. The future(s) of shared data structures. In PODC.

Digital Library

[18]

Alex Kogan and Yossi Lev . 2017. Transactional lock elision meets combining. In PODC.

Digital Library

[19]

Edya Ladan-Mozes and Nir Shavit . 2008. An optimistic approach to lock-free FIFO queues. Distributed Computing Vol. 20, 5 (2008).

[20]

Doug Lea . 2009. The java concurrency package (JSR-166).

[21]

Maged M. Michael . 2004. Hazard pointers: safe memory reclamation for lock-free objects. TPDS Vol. 15, 6 (2004).

Digital Library

[22]

Maged M. Michael and Michael L. Scott . 1996. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms PODC.

Digital Library

[23]

Gal Milman, Alex Kogan, Yossi Lev, Victor Luchangco, and Erez Petrank . 2018. BQ: a lock-free queue with batching (full paper). (2018). deftempurl%http://www.cs.technion.ac.il/ erez/Papers/bq-full.pdf tempurl

[24]

Mark Moir, Daniel Nussbaum, Ori Shalev, and Nir Shavit . 2005. Using elimination to implement scalable and lock-free FIFO queues SPAA.

Digital Library

[25]

Adam Morrison and Yehuda Afek . 2013. Fast concurrent queues for x86 processors. In PPoPP.

Digital Library

[26]

Niloufar Shafiei . 2009. Non-blocking array-based algorithms for stacks and queues ICDCN.

Digital Library

[27]

Philippas Tsigas and Yi Zhang . 2001. A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems. In SPAA.

Digital Library

[28]

Chaoran Yang and John Mellor-Crummey . 2016. A wait-free queue as fast as fetch-and-add. In PPoPP.

Digital Library

Cited By

Wu QEkanayake ALi RBeard JJohn L(2022)SPAMeR: Speculative Push for Anticipated Message Requests in Multi-Core SystemsProceedings of the 51st International Conference on Parallel Processing10.1145/3545008.3545044(1-12)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1145/3545008.3545044
Milman-Sela GKogan ALev YLuchangco VPetrank E(2022)BQ: A Lock-Free Queue with BatchingACM Transactions on Parallel Computing10.1145/35127579:1(1-49)Online publication date: 23-Mar-2022
https://dl.acm.org/doi/10.1145/3512757
Adas DFriedman R(2022)A Fast Wait-Free Multi-Producers Single-Consumer QueueProceedings of the 23rd International Conference on Distributed Computing and Networking10.1145/3491003.3491004(77-86)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1145/3491003.3491004
Show More Cited By

Index Terms

BQ: A Lock-Free Queue with Batching
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent algorithms
  2. Parallel computing methodologies
    1. Parallel algorithms
      1. Shared memory algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Concurrent algorithms
    2. Parallel algorithms
      1. Shared memory algorithms

Recommendations

BQ: A Lock-Free Queue with Batching
Concurrent data structures provide fundamental building blocks for concurrent programming. Standard concurrent data structures may be extended by allowing a sequence of operations to be submitted as a batch for later execution. A sequence of such ...
LOFT: lock-free transactional data structures
PPoPP '19: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming

Concurrent data structures are widely used in modern multicore architectures, providing atomicity (linearizability) for each concurrent operation. However, it is often desirable to execute several operations on multiple data structures atomically. We ...
Concurrent Size (Abstract)
HOPC'24: Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing

The size of a data structure (i.e., the number of elements in it) is a widely used property of a data set. However, for concurrent programs, obtaining a correct size efficiently is non-trivial. In fact, the literature does not offer a mechanism to obtain ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '18: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures

July 2018

437 pages

ISBN:9781450357999

DOI:10.1145/3210377

General Chair:
Christian Scheideler
University of Paderborn, Germany
,
Program Chair:
Jeremy Fineman
Georgetown University, USA

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part 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 components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

the Israel Science Foundation

Conference

SPAA '18

Sponsor:

SPAA '18: 30th ACM Symposium on Parallelism in Algorithms and Architectures

July 16 - 18, 2018

Vienna, Austria

Acceptance Rates

SPAA '18 Paper Acceptance Rate 36 of 120 submissions, 30%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
389
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)6

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu QEkanayake ALi RBeard JJohn L(2022)SPAMeR: Speculative Push for Anticipated Message Requests in Multi-Core SystemsProceedings of the 51st International Conference on Parallel Processing10.1145/3545008.3545044(1-12)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1145/3545008.3545044
Milman-Sela GKogan ALev YLuchangco VPetrank E(2022)BQ: A Lock-Free Queue with BatchingACM Transactions on Parallel Computing10.1145/35127579:1(1-49)Online publication date: 23-Mar-2022
https://dl.acm.org/doi/10.1145/3512757
Adas DFriedman R(2022)A Fast Wait-Free Multi-Producers Single-Consumer QueueProceedings of the 23rd International Conference on Distributed Computing and Networking10.1145/3491003.3491004(77-86)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1145/3491003.3491004
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
https://dl.acm.org/doi/10.1145/3490148.3538572
Giersch ONolte J(2022)Fast and Portable Concurrent FIFO Queues With Deterministic Memory ReclamationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.309790133:3(604-616)Online publication date: 1-Mar-2022
https://doi.org/10.1109/TPDS.2021.3097901
Guo BSekerinski E(2022)Efficient parallel graph trimming by arc-consistencyThe Journal of Supercomputing10.1007/s11227-022-04457-978:13(15269-15313)Online publication date: 16-Apr-2022
https://doi.org/10.1007/s11227-022-04457-9
Nookala PDinda PHale KChard KRaicu I(2021)Enabling Extremely Fine-grained Parallelism via Scalable Concurrent Queues on Modern Many-core Architectures2021 29th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)10.1109/MASCOTS53633.2021.9614292(1-8)Online publication date: 3-Nov-2021
https://doi.org/10.1109/MASCOTS53633.2021.9614292
Liu CWang P(2021)A Concurrent Message Processing Mechanism for Internet of Vehicles2021 IEEE 2nd International Conference on Information Technology, Big Data and Artificial Intelligence (ICIBA)10.1109/ICIBA52610.2021.9687947(778-783)Online publication date: 17-Dec-2021
https://doi.org/10.1109/ICIBA52610.2021.9687947
Blelloch GFineman JGu YSun YScheideler CSpear M(2020)Optimal Parallel Algorithms in the Binary-Forking ModelProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400227(89-102)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400227
Xu YSinger KLee IGupta RShen X(2020)Parallel determinacy race detection for futuresProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3332466.3374536(217-231)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.1145/3332466.3374536
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents