PPoPP 2016
Sat 12 - Wed 16 March 2016 Barcelona, Spain
Tue 15 Mar 2016 10:25 - 10:50 at Mallorca+Menorca - Shared-memory data structures Chair(s): Yossi Lev

Concurrent data structures that have fast and predictable performance are of critical importance for harnessing the power of multicore processors, which are now ubiquitous. Although wait-free objects, whose operations complete in a bounded number of steps, were devised more than two decades ago, wait-free objects that can deliver scalable high performance are still rare.

In this paper, we present the first wait-free FIFO queue based on fetch-and-add (FAA). While compare-and-swap (CAS) based non-blocking algorithms may perform poorly due to work wasted by CAS failures, algorithms that coordinate using FAA, which is guaranteed to succeed, can in principle perform better under high contention. Along with FAA, our queue uses a custom epoch-based scheme to reclaim memory; on x86 architectures, it requires no extra memory fences on our algorithm’s typical execution path. An empirical study of our new FAA-based wait-free FIFO queue under high contention on four different architectures with many hardware threads shows that it outperforms prior queue designs that lack a wait-free progress guarantee. Surprisingly, at the highest level of contention, the throughput of our queue is often as high as that of a microbenchmark that only performs FAA. As a result, our fast wait-free queue implementation is useful in practice on most multi-core systems today. We believe that our design can serve as an example of how to construct other fast wait-free objects.

Tue 15 Mar
Times are displayed in time zone: (GMT+01:00) Greenwich Mean Time : Belfast change

10:00 - 11:15: Main conference - Shared-memory data structures at Mallorca+Menorca
Chair(s): Yossi LevOracle Labs
PPoPP-2016-papers10:00 - 10:25
Link to publication DOI
PPoPP-2016-papers10:25 - 10:50
Chaoran YangRice University, John Mellor-CrummeyRice University
Link to publication DOI
PPoPP-2016-papers10:50 - 11:15
Syed Kamran HaiderUniversity of Connecticut, William HasenplaughMIT, Dan AlistarhMicrosoft Research
Link to publication DOI