Login
Computer Science @ Rochester
Tuesday, June 16, 2009
2:00 PM
CSB 601
Michael Spear
University of Rochester
Fast Software Transactions
Mainstream programmers typically use explicit locks to write parallel programs. The resulting code is prone to deadlock, and still often fails to perform well. Transactional Memory (TM) is a promising alternative to lock-based critical sections, in which the programmer specifies regions of code that require atomicity, and a run-time system executes those regions safely while exploiting available parallelism.

In this dissertation, we present mechanisms that make software TM fast while increasing its value as an end-user programming abstraction. To lower latency, we introduce a heuristic to avoid in-flight consistency checks, compiler optimizations to reduce the cost of memory ordering, and a new TM algorithm that uses Bloom filters to eliminate read-modify-write instructions. To improve scalability, we introduce a comprehensive strategy for livelock and starvation avoidance. To increase generality, we propose scalable mechanisms for I/O within transactions, and we introduce a language-level semantics for TM based on ordering rather than locks.

This talk describes RingSTM, the TM based on Bloom filters. Evaluation shows performance on par with other TM algorithms for a wide variety of workloads. Additionally, RingSTM guarantees progress and provides stronger semantics than most TM algorithms. Furthermore, it offers promising opportunities for hardware acceleration, increasing the likelihood that TM will achieve widespread use.