R. Rajwar, and J. Goodman. Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, page 294--305. Washington, DC, USA, IEEE Computer Society, (2001)
Abstract
Serialization of threads due to critical sections is a fundamental bottleneck to achieving high performance in multithreaded programs. Dynamically, such serialization may be unnecessary because these critical sections could have safely executed concurrently without locks. Current processors cannot fully exploit such parallelism because they do not have mechanisms to dynamically detect such false inter-thread dependences.We propose <i>Speculative Lock Elision (SLE),</i> a novel micro-architectural technique to remove dynamically unnecessary lock-induced serialization and enable highly concurrent multithreaded execution. The key insight is that locks do not always have to be acquired for a correct execution. Synchronization instructions are predicted as being unnecessary and elided. This allows multiple threads to concurrently execute critical sections protected by the same lock. Misspeculation due to inter-thread data conflicts is detected using existing cache mechanisms and rollback is used for recovery. Successful speculative elision is validated and committed without acquiring the lock.SLE can be implemented entirely in microarchitecture without instruction set support and without system-level modifications, is transparent to programmers, and requires only trivial additional hardware support. SLE can provide programmers a fast path to writing correct high-performance multithreaded programs.
%0 Conference Paper
%1 Rajwar:2001:SLE:563998.564036
%A Rajwar, Ravi
%A Goodman, James R.
%B Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture
%C Washington, DC, USA
%D 2001
%I IEEE Computer Society
%K Elision LL/SC LoadLinked Lock VM
%P 294--305
%T Speculative Lock Elision: Enabling Highly Concurrent Multithreaded Execution
%U http://dl.acm.org/citation.cfm?id=563998.564036
%X Serialization of threads due to critical sections is a fundamental bottleneck to achieving high performance in multithreaded programs. Dynamically, such serialization may be unnecessary because these critical sections could have safely executed concurrently without locks. Current processors cannot fully exploit such parallelism because they do not have mechanisms to dynamically detect such false inter-thread dependences.We propose <i>Speculative Lock Elision (SLE),</i> a novel micro-architectural technique to remove dynamically unnecessary lock-induced serialization and enable highly concurrent multithreaded execution. The key insight is that locks do not always have to be acquired for a correct execution. Synchronization instructions are predicted as being unnecessary and elided. This allows multiple threads to concurrently execute critical sections protected by the same lock. Misspeculation due to inter-thread data conflicts is detected using existing cache mechanisms and rollback is used for recovery. Successful speculative elision is validated and committed without acquiring the lock.SLE can be implemented entirely in microarchitecture without instruction set support and without system-level modifications, is transparent to programmers, and requires only trivial additional hardware support. SLE can provide programmers a fast path to writing correct high-performance multithreaded programs.
%@ 0-7695-1369-7
@inproceedings{Rajwar:2001:SLE:563998.564036,
abstract = {Serialization of threads due to critical sections is a fundamental bottleneck to achieving high performance in multithreaded programs. Dynamically, such serialization may be unnecessary because these critical sections could have safely executed concurrently without locks. Current processors cannot fully exploit such parallelism because they do not have mechanisms to dynamically detect such false inter-thread dependences.We propose <i>Speculative Lock Elision (SLE),</i> a novel micro-architectural technique to remove dynamically unnecessary lock-induced serialization and enable highly concurrent multithreaded execution. The key insight is that locks do not always have to be acquired for a correct execution. Synchronization instructions are predicted as being unnecessary and elided. This allows multiple threads to concurrently execute critical sections protected by the same lock. Misspeculation due to inter-thread data conflicts is detected using existing cache mechanisms and rollback is used for recovery. Successful speculative elision is validated and committed without acquiring the lock.SLE can be implemented entirely in microarchitecture without instruction set support and without system-level modifications, is transparent to programmers, and requires only trivial additional hardware support. SLE can provide programmers a fast path to writing correct high-performance multithreaded programs.},
acmid = {564036},
added-at = {2012-10-14T23:33:53.000+0200},
address = {Washington, DC, USA},
author = {Rajwar, Ravi and Goodman, James R.},
biburl = {https://www.bibsonomy.org/bibtex/2cb8413014d4d0798bd1e24d3399f7bee/gron},
booktitle = {Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture},
description = {Speculative lock elision},
interhash = {563f4b271481619eee597327bef762c7},
intrahash = {cb8413014d4d0798bd1e24d3399f7bee},
isbn = {0-7695-1369-7},
keywords = {Elision LL/SC LoadLinked Lock VM},
location = {Austin, Texas},
numpages = {12},
pages = {294--305},
publisher = {IEEE Computer Society},
series = {MICRO 34},
timestamp = {2012-10-14T23:34:29.000+0200},
title = {Speculative Lock Elision: Enabling Highly Concurrent Multithreaded Execution},
url = {http://dl.acm.org/citation.cfm?id=563998.564036},
year = 2001
}