Lease/Release: Architectural support for scaling contended data structures

S. Haider, W. Hasenplaugh, D.-A. Alistarh, in:, ACM, 2016.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
; ;
Abstract
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.
Publishing Year
Date Published
2016-02-27
Acknowledgement
We would like to thank Richard Black, Miguel Castro, Dave Dice, Aleksandar Dragojevic, Maurice Herlihy, Ant Rowstron, Nir Shavit, and Vasileios Trigonakis, as well as the anonymous reviewers, for helpful suggestions during the development of this paper.
Volume
12-16-March-2016
Conference
PPoPP: Principles and Practice of Parallel Pogramming
IST-REx-ID

Cite this

Haider S, Hasenplaugh W, Alistarh D-A. Lease/Release: Architectural support for scaling contended data structures. In: Vol 12-16-March-2016. ACM; 2016. doi:10.1145/2851141.2851155
Haider, S., Hasenplaugh, W., & Alistarh, D.-A. (2016). Lease/Release: Architectural support for scaling contended data structures (Vol. 12-16-March-2016). Presented at the PPoPP: Principles and Practice of Parallel Pogramming, ACM. https://doi.org/10.1145/2851141.2851155
Haider, Syed, William Hasenplaugh, and Dan-Adrian Alistarh. “Lease/Release: Architectural Support for Scaling Contended Data Structures,” Vol. 12-16-March-2016. ACM, 2016. https://doi.org/10.1145/2851141.2851155.
S. Haider, W. Hasenplaugh, and D.-A. Alistarh, “Lease/Release: Architectural support for scaling contended data structures,” presented at the PPoPP: Principles and Practice of Parallel Pogramming, 2016, vol. 12-16-March-2016.
Haider S, Hasenplaugh W, Alistarh D-A. 2016. Lease/Release: Architectural support for scaling contended data structures. PPoPP: Principles and Practice of Parallel Pogramming vol. 12-16-March-2016.
Haider, Syed, et al. Lease/Release: Architectural Support for Scaling Contended Data Structures. Vol. 12-16-March-2016, ACM, 2016, doi:10.1145/2851141.2851155.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar