Understanding Tradeoffs in Software Transactional Memory

Understanding Tradeoffs in Software Transactional Memory by Nir Shavit and myself was accepted in CGO-2007. The paper describes the TL1 (Transactional Locking) mechanism. The slides presented at the conference are available as well. (We first described TL1 at Transact'06 in Ottawa). TL1's successor, TL2, authored by mself, Nir Shavit and Ori Shalev, was published in DISC'06.

Briefly, STMs such as TL1 periodically revalidate the read-set during a transaction. This is necessary as a transaction might have read a set of values that are inconsistent and then, based on that inconsistent data, enter an infinite loop, generate traps, or otherwise misbehave. We refer to such a transaction as a zombie: it's observed inconsistent state and could never successfully commit, but it's still running. We could avoid zombie transactions by revalidating the entire read-set after each transactional load. That's sufficient to avoid zombies, but the cost is quadratic with the size of the read-set. Instead, TL1 admits zombies (transiently) and validates periodically. The period of zombie execution is bounded. But the TL1 runtime environment must also provide zombie containment to gracefully tolerate the misbehavior of zombie transactions.

Another way to avoid zombies is to use so-called visible readers. Conceptually each transactional variable maps to a read-write lock. The first time a transaction reads from a location it acquires the read-lock. And of course transactional writes acquire the lock for writing. Visible readers avoid zombie execution but at the cost of considerable read-write coherency traffic on the read-write locks.

TL2 does not admit zombies execution, potentially making it more suitable for C or C++ unmanaged runtime environments. And it manages to avoid zombies with validation costs only proportional to the read-set size and without visible readers.

Comments:

I found your paper a very interesting read. I am particularly excited by your efficient Commit Mode algorithm, which I have a question about. When encountering a previously un-read/written to location, how do you fetch the variable version and the contents of the variable atomically in an efficient manner? I'm guessing you do not acquire the lock as this would no longer make the readers invisible. This was not discussed in the paper.

Posted by Marek Olszewski on April 16, 2007 at 03:01 PM EDT #

Hello Marek. During the speculative execution phase a transactional load will first fetch the lockword (which contains the version#), fetch the variable, and then refetch the lockword to ratify the version# observed by the 1st fetch. In TL1 we'll save the version# and lockword address in the read-set and recheck that it remains unchanged at commit-time. In TL2 we'll compare the version# to the thread's "RV" and save just the lockword address in the read-set. Regards,Dave

Posted by Dave Dice on April 23, 2007 at 07:26 AM EDT #

Hello David,
I have found your paper on TL2 really interesting. I would like to have a look at it, if possible. In the new STAMP TM benchmark suite from Stanford, there is a port (or implementation from scratch from the paper description?) to x86, but I would be interested in the Sparc version you use for the paper.
Is that available, or will it be soon?
Regards, Enrique.

Posted by Enrique Vallejo on May 17, 2007 at 12:28 AM EDT #

Post a Comment:
  • HTML Syntax: NOT allowed
About

Dave is a senior research scientist in the Scalable Synchronization Research Group within Oracle Labs : Google Scholar.

Search

Categories
Archives
« July 2014
SunMonTueWedThuFriSat
  
1
2
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  
       
Today