Brief Announcement: Jiffy: A Fast, Memory Efficient, Wait-Free Multi-Producers Single-Consumer Queue

Authors Dolev Adas, Roy Friedman



PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.50.pdf
  • Filesize: 263 kB
  • 3 pages

Document Identifiers

Author Details

Dolev Adas
  • Technion - Israel Institute of Technology, Haifa, Israel
Roy Friedman
  • Technion - Israel Institute of Technology, Haifa, Israel

Cite AsGet BibTex

Dolev Adas and Roy Friedman. Brief Announcement: Jiffy: A Fast, Memory Efficient, Wait-Free Multi-Producers Single-Consumer Queue. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 50:1-50:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.50

Abstract

In applications such as sharded data processing systems, data flow programming and load sharing applications, multiple concurrent data producers are feeding requests into the same data consumer. This can be naturally realized through concurrent queues, where each consumer pulls its tasks from its dedicated queue. For scalability, wait-free queues are often preferred over lock based structures. The vast majority of wait-free queue implementations, and even lock-free ones, support the multi-producer multi-consumer model. Yet, this comes at a premium, since implementing wait-free multi-producer multi-consumer queues requires utilizing complex helper data structures. The latter increases the memory consumption of such queues and limits their performance and scalability. Additionally, many such designs employ (hardware) cache unfriendly memory access patterns. In this work we study the implementation of wait-free multi-producer single-consumer queues. Specifically, we propose Jiffy, an efficient memory frugal novel wait-free multi-producer single-consumer queue and formally prove its correctness. We then compare the performance and memory requirements of Jiffy with other state of the art lock-free and wait-free queues. We show that indeed Jiffy can maintain good performance with up to 128 threads, delivers better throughput than other constructions we compared against, and consumes less memory.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Concurrency control
  • Theory of computation → Concurrency
Keywords
  • Wait-freedom
  • MPSC Queues
  • Concurrent data-structures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Keren Censor-Hillel, Erez Petrank, and Shahar Timnat. Help! In ACM Symposium on Principles of Distributed Computing (PODC), pages 241-250, 2015. Google Scholar
  2. Panagiota Fatourou and Nikolaos D Kallimanis. Revisiting the Combining Synchronization Technique. In Proc. of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), volume 47 (8), pages 257-266, 2012. Google Scholar
  3. Maurice Herlihy. Wait-Free Synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(1):124-149, 1991. Google Scholar
  4. Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2011. Google Scholar
  5. Edya Ladan-Mozes and Nir Shavit. An Optimistic Approach to Lock-Free FIFO Queues. In Distributed Computing, 18th International Conference (DISC), pages 117-131, 2004. Google Scholar
  6. Nhat Minh Lê, Adrien Guatto, Albert Cohen, and Antoniu Pop. Correct and Efficient Bounded FIFO Queues. In 25th International Symposium on Computer Architecture and High Performance Computing, pages 144-151. IEEE, 2013. Google Scholar
  7. Maged M. Michael and Michael L. Scott. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. In Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 267-275, 1996. Google Scholar
  8. Nicholas Nethercote and Julian Seward. Valgrind: A Program Supervision Framework. Electronic notes in theoretical computer science, 89(2):44-66, 2003. Google Scholar
  9. William N. Scherer, Doug Lea, and Michael L. Scott. Scalable Synchronous Queues. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP), pages 147-156, 2006. Google Scholar
  10. Michael L. Scott. Non-Blocking Timeout in Scalable Queue-Based Spin Locks. In Proc. of the 21st ACM Symposium on Principles of Distributed Computing, (PODC), pages 31-40, 2002. Google Scholar
  11. Michael L. Scott and William N. Scherer. Scalable Queue-Based Spin Locks with Timeout. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP), pages 44-52, 2001. Google Scholar
  12. Nir Shavit and Asaph Zemach. Scalable Concurrent Priority Queue Algorithms. In Proc. of the 18th ACM Symp. on Principles of Distributed Computing (PODC), pages 113-122, 1999. Google Scholar
  13. Chaoran Yang and John Mellor-Crummey. A Wait-Free Queue as Fast as Fetch-and-Add. Proc. of the ACM Symp. on Principles and Practice of Parallel Programming (PPoPP), 2016. Google Scholar
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