Toward High Performance Nonblocking Software Transactional Memory

Substantial advances in STM performance in recent years have mostly focused on blocking systems. We describe our work integrating the most important techniques and optimizations emerging from the recent work on blocking STMs into several variants of a nonblocking STM. In particular, our design is based on the philosophy of keeping the common, contention free execution path as simple (consequently fast) as possible, while resorting to the more expensive data displacement and metadata management only in situations where transactions have problems making forward progress. We employ novel ownership "stealing" and metadata management techniques in our nonblocking STM to enable several recent blocking STM optimizations such as timestamp-based validation and ownership release via store instructions, all leading to a more streamlined and efficient fast path. We present an undo log (eager versioning) variant of our STM, as well as two redo log (lazy versioning) variants, the latter of which are based on the two ownership acquisition techniques (namely eager and lazy) for writes made by transactions. Experimental results show that our efforts have improved the performance of nonblocking STMs up to the level of being competitive with the state-of-the-art blocking STMs such as TL2.