Speculation-based techniques for transactional lock-free execution of lock-based programs

This thesis is motivated by the difficulty in writing correct high-performance programs. Writing shared-memory multithreaded programs imposes a complex trade-off between programming ease and performance, largely due to subtleties in coordinating access to shared data. To ensure correctness programmers often rely on conservative locking at the expense of performance. The resulting serialization of threads is a performance bottleneck. Locks also interact poorly with scheduling and faults.; We seek to improve multithreaded programming trade-offs by providing architectural support for optimistic lock-free execution. In a lock-free execution, shared objects are never locked when accessed by various threads. We propose two hardware techniques: Speculative Lock Elision and Transactional Lock Removal.; Speculative Lock Elision (SLE) is a micro-architectural technique to remove dynamically-unnecessary lock-induced serialization. The key insight is that locks don't 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 elision is validated and committed without acquiring the lock and non-conflicting critical sections execute and commit concurrently without serialization on the lock. SLE can be implemented entirely in the microarchitecture without instruction-set support and system-level modifications, is transparent to programmers, and requires trivial additional hardware support.; Transactional Lock Removal (TLR) uses SLE as an enabling mechanism but in addition provides successful lock-free execution of lock-based critical sections in the presence of data conflicts if sufficient resources are available for buffering speculative state. TLR elides locks using SLE to construct an optimistic lock-free critical section execution but in addition also uses a timestamp-based conflict resolution scheme to provide lock-free execution even in the presence of data conflicts. By treating lock-free critical sections as lock-free transactions, TLR provides transactional properties to critical sections and by using timestamps also provides starvation freedom.; Benefits of SLE and TLR include improved programmability, stability, and performance. Programmers can obtain benefits of lock-free data structures, such as non-blocking and wait-free behavior, while using lock-protected critical sections for writing programs.