STM _ BEGIN() read global version number /* gv# */

(a) Pseudo-code for stm begin

STM _ READ(A) if already written goto written path read metadata of A if metadata is locked goto conflict path log A and its metadata in the read set read value at A if STM _ VALIDATE() goto conflict path return val

STM _ VALIDATE() read global version number /* gv# */ if global version number changed /* gv# */ for each read set entry if metadata changed return FALSE return TRUE

(b) Pseudo-code for stm validate

STM _ END() lock metadata for write set if already locked goto conflict path if STM _ VALIDATE() goto conflict path /* Success guaranteed */ increment global version number /* gv# */ execute writes update/unlock metadata for write set

(d) Pseudo-code for stm end

 

tion decisions, there are transactional semantics issues that break the ideal transactional programming model for which the community had hoped. TM introduces a variety of programming issues that are not present in lock-based mutual exclusion. For example, semantics are muddled by:

˲ Interaction with non-transactional codes, including access to shared data from outside of a transaction (tolerating weak atomicity) and the use of locks inside a transaction (breaking isolation to make locking operations visible outside transactions);

˲ Exceptions and serializability: how to handle exceptions and propagate consistent exception information from within a transactional context, and how to guarantee that transactional execution respects a correct ordering of operations;

˲ Interaction with code that cannot be transactionalized, due to either communication with other threads or a requirement barring speculation;

˲ Livelock, or the system guarantee that all transactions make progress even in the presence of conflicts.

In addition to the intrinsic semantic issues, there are also implementation-specific optimizations motivated by high transactional overheads, such as programmer annotations for exclud-

ing private data. Furthermore, the nondeterminism introduced by aborting transactions complicates debugging— transactional code may be executed and aborted on conflicts, which makes it difficult for the programmer to find deterministic paths with repeatable behavior. Both of these dilute the productivity argument for transactions, especially software-only TM implementations.

Given all these issues, we conclude that TM has not yet matured to the point where it presents a compelling value proposition that will trigger its widespread adoption. While TM can be a useful tool in the parallel programmer’s portfolio, it is our view that it is not going to solve the parallel programming dilemma by itself. There is evidence that it helps with building certain concurrent data structures, such as hash tables and binary trees. In addition, there are anecdotal claims that it helps with workloads; however, despite several years of active research and publication in the area, we are disappointed to find no mentions in the research literature of large-scale applications that make use of TM. The STAMP³⁰ and Lonestar¹⁷ benchmark suites are promising starts, but have a long way to go to be representative of full applications.

We base these conclusions on our work over the past two years building a

state of the art STM runtime system and compiler framework, the freely available IBM STM. ³¹ Here, we describe this experience, starting with a discussion of STM algorithms and design decisions. We then compare the performance of this STM with two other state of the art implementations (the Intel STM¹⁴ and the Sun TL2 STM⁷) as well as dissect the operations executed by the IBM STM and provide a detailed analysis of the performance hotspots of the STM.

software transactional memory

STM implements all the transactional semantics in software. That includes conflict detection, guaranteeing the consistency of transactional reads, preservation of atomicity and isolation ( preventing other threads from observing speculative writes before the transaction succeeds), and conflict resolution (transaction arbitration). The pseudo-code for the main operations executed by a typical STM is illustrated in Figure 1. We show two STM algorithms, one that performs full validation and one that uses a global version number (the additional statements marked with the gv# comment).

The advantage of an STM for system programmers is that it offers flexibility in implementing different mechanisms and policies for these operations. For