Adam Morrison
Yehuda Afek
Abstract
Conventional wisdom in designing concurrent data structures is to use the most powerful synchronization primitive, namely compare-and-swap (CAS), and to avoid contended hot spots. In building concurrent FIFO queues, this reasoning has led researchers to propose combining-based concurrent queues.
This paper takes a different approach, showing how to rely on fetch-and-add (F&A), a less powerful primitive that is available on x86 processors, to construct a nonblocking (lock-free) linearizable concurrent FIFO queue which, despite the F&A being a contended hot spot, outperforms combining-based implementations by 1.5x to 2.5x in all concurrency levels on an x86 server with four multicore processors, in both single-processor and multi-processor executions.
- Power ISA Version 2.06. http://www.power.org/resources/downloads/PowerISA_V2.06B_V2_PUBLIC.pdf, January 2009.Google Scholar
- G. E. Blelloch, P. B. Gibbons, and S. H. Vardhan. Combinable memory-block transactions. In SPAA 2008. Google ScholarDigital Library
- G. E. Blelloch, P. Cheng, and P. B. Gibbons. Scalable room synchronizations. Theory of Computing Systems, 36, 2003.Google Scholar
- R. Colvin and L. Groves. Formal verification of an array-based nonblocking queue. In ICECCS 2005. Google ScholarDigital Library
- D. Dice, V. J. Marathe, and N. Shavit. Lock cohorting: a general technique for designing numa locks. In PPoPP 2012. Google ScholarDigital Library
- J. Evans. Scalable memory allocation using jemalloc. http://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919, 2011.Google Scholar
- P. Fatourou and N. D. Kallimanis. Revisiting the combining synchronization technique. In PPoPP 2012. Google ScholarDigital Library
- P. Fatourou and N. D. Kallimanis. A highly-efficient wait-free universal construction. In SPAA 2011. Google ScholarDigital Library
- E. Freudenthal and A. Gottlieb. Process coordination with fetch-and-increment. In ASPLOS 1991. Google ScholarDigital Library
- A. Gottlieb, B. D. Lubachevsky, and L. Rudolph. Basic techniques for the efficient coordination of very large numbers of cooperating sequential processors. TOPLAS, 5(2), Apr. 1983. Google ScholarDigital Library
- D. Hendler, I. Incze, N. Shavit, and M. Tzafrir. Flat combining and the synchronization-parallelism tradeoff. In SPAA 2010. Google ScholarDigital Library
- M. Herlihy. Wait-free synchronization. TOPLAS, 13:124--149, January 1991. Google ScholarDigital Library
- M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008. Google ScholarDigital Library
- M. P. Herlihy and J. M. Wing. Linearizability: a correctness condition for concurrent objects. TOPLAS, 12:463--492, July 1990. Google ScholarDigital Library
- M. Hoffman, O. Shalev, and N. Shavit. The baskets queue. In OPODIS 2007. Google ScholarDigital Library
- A. Kogan and E. Petrank. Wait-free queues with multiple enqueuers and dequeuers. In PPoPP 2011. Google ScholarDigital Library
- E. Ladan-Mozes and N. Shavit. An optimistic approach to lock-free FIFO queues. In DISC 2004.Google ScholarCross Ref
- M. M. Michael. Hazard pointers: Safe memory reclamation for lockfree objects. IEEE TPDS, 15(6):491--504, June 2004. Google ScholarDigital Library
- M. M. Michael and M. L. Scott. Simple, fast, and practical nonblocking and blocking concurrent queue algorithms. In PODC 1996. Google ScholarDigital Library
- M. Moir, D. Nussbaum, O. Shalev, and N. Shavit. Using elimination to implement scalable and lock-free FIFO queues. In SPAA 2005. Google ScholarDigital Library
- P. Sewell, S. Sarkar, S. Owens, F. Z. Nardelli, and M. O. Myreen. x86-TSO: a rigorous and usable programmer's model for x86 multiprocessors. Communications of the ACM, 53(7):89--97, July 2010. Google ScholarDigital Library
- N. Shafiei. Non-blocking array-based algorithms for stacks and queues. In ICDCN 2009. Google ScholarDigital Library
- P. Tsigas and Y. Zhang. A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems. In SPAA 2001. Google ScholarDigital Library
Index Terms
- Fast concurrent queues for x86 processors
Recommendations
Fast concurrent queues for x86 processors
PPoPP '13: Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programmingConventional wisdom in designing concurrent data structures is to use the most powerful synchronization primitive, namely compare-and-swap (CAS), and to avoid contended hot spots. In building concurrent FIFO queues, this reasoning has led researchers to ...
Practical, Fast and Simple Concurrent FIFO Queues Using Single Word Synchronization Primitives
Ada-Europe '08: Proceedings of the 13th Ada-Europe international conference on Reliable Software TechnologiesWe present an efficient and practical non-blocking implementation of a concurrent array-based FIFO queue that is suitable for preemptive multi threaded systems. It is well known that concurrent FIFO queues relying on mutual exclusion cause blocking, ...
On the Importance of Synchronization Primitives with Low Consensus Numbers
ICDCN '18: Proceedings of the 19th International Conference on Distributed Computing and NetworkingThe consensus number of a synchronization primitive is the maximum number of processes for which the primitive can solve consensus. This has been the traditional measure of power of a synchronization primitive. Thus, the compare-and-swap primitive, ...
Comments