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

High memory contention is generally agreed to be a worst-case scenario for concurrent data structures. There has been a significant amount of research effort spent investigating designs which minimize contention, and several programming techniques have been proposed to mitigate its effects. However, there are currently few architectural mechanisms to allow scaling contended data structures at high thread counts.

In this paper, we investigate hardware support for scalable contended data structures. We propose Lease/Release, a simple addition to standard directory-based MSI cache coherence protocols, allowing participants to lease memory, at the granularity of cache lines, by delaying coherence messages for a short, bounded period of time. Our analysis shows that Lease/Release can significantly reduce the overheads of contention for both non-blocking (lock-free) and lock-based data structure implementations, while ensuring that no deadlocks are introduced. We validate Lease/Release empirically on the Graphite multiprocessor simulator, on a range of data structures, including queue, stack, and priority queue implementations, as well as on transactional applications. Results show that Lease/Release consistently improves both throughput and energy usage, by up to 5x, both for lock-free and lock-based data structure designs.

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