JudoSTM: A Dynamic Binary Rewriting Approach to Software Transactional Memory

Marek Olszewski,  Jeremy Cutler,  J. Gregory Steffan
University of Toronto


With the advent of chip-multiprocessors, we are faced with the challenge of parallelizing all performance-critical software. Transactional memory (TM) has emerged as a promising programming model allowing programmers to focus on parallelism rather than maintaining correctness and avoiding deadlock. Many implementations of hardware, software, and hybrid support for TM have been proposed; of these, software-only implementations (STMs) are especially compelling since they can be used with current commodity hardware. However, in addition to higher overheads, many existing STM systems are limited to using either certain managed languages or intrusive APIs. Furthermore, transactions in STMs cannot normally contain calls to unobservable code such as shared libraries or system calls.

In this paper we present JudoSTM, a novel dynamic binary-rewriting approach to implementing STM that supports C and C++ code and also atomic sections that contain arbitrary calls to shared-libraries. Furthermore, by using value-based conflict-detection JudoSTM additionally supports the transactional execution of both (i) irreversible system calls and (ii) library functions that may contain locks. We significantly lower overheads through several novel optimizations that improve the quality of rewritten code and reduce the cost of conflict detection and write-buffering. We show that our approach performs comparably to Rochester's RSTM library-based implementation---demonstrating that a dynamic binary-rewriting approach to implementing STM is an interesting alternative.