Department of Computer Science
University of Rochester
Users unfamiliar with transactional memory may want to read this introductory information on TM implementations first.
The number of libraries that we now provide can make chosing one a difficult task.
Object-based software transactional memories map data to metadata in a per-object fashion. The primary advantage of this arrangement is that metadata can be allocated on-demand, in the same location as the data that it protects. This is good for data locality and because we only allocate as much metadata as we need to protect the data actually being used by the application.
Object-based STMs suffer from object level false conflicts, e.g., if a transaction writes an object field, a concurrent transaction that reads a different field from the object will assume that there is a conflict, when in fact there is not one.
The primary difficulty with an object-based STM is that it can be difficult to generate code for, and it is not obvious how to map metadata for non-object types. RSTM deals with this using its object-based smart pointer interface.
This is the original nonblocking object-based implementation, as described in our TRANSACT, 2006 paper. It uses shallow object cloning and one level of indirection in order to be non-blocking.
Features
The redo-lock framework takes the basic RSTM algorithm and modifies it to eliminate the one level of indirection, in the common case. It does this by using a lazy versioning system for writes, and giving up its non-blocking guarantees. More details on the algorithm, and an analysis of simple hardware support to make the algorithm non-blocking, can be found in our SPAA, 2007 paper proposing the Alert-On-Update mechanism.
Features
Word-based software transactional memory maps data to metadata on a per-word basis. The mapping is typically, but not always, a many-to-one mapping between addresses and their associated metadata. So-called single-lock variants map all locations to the same metadata. Many hash-based schemes map addresses to a fixed table of metadata.
These implementations protect atomic regions by acquiring and releasing a single global lock. These have very low single-threaded overhead, but limited scalability. They are mostly useful for baseline performance testing of other TMs, however the TML and TML + Lazy implementations scale well when writing transactions are rare. Note that these implementations do not support retry-based condition synchronization.
The CGL (Coarse Grained Lock) library acquires and releases a single global lock on entrance to an atomic section. This provides no concurrency, and thus no scalability, but has very low overhead. This library is mostly useful for debugging and baseline benchmark testing.
Features
The TML (Transactional Mutex Lock) runtime uses a single global sequence lock to 1) allow concurrent read-only transactions with no logging overhead, 2) reduce locking overhead for read-only transactions, and 3) allow a single in-place writer with no logging overhead.
On some architectures, TML has lower overhead than CGL, since readers don't need atomic operations to acquire a mutex lock. TML also scales better than CGL, because multiple readers may work in parallel. Because of this we recommend that TML be used as the baseline in performance testing.
More information is available in our TRANSACT, 2009 paper on TML.
Features
As its name indicates, TML + Lazy uses the same single global sequence lock as TML, but uses a lazy acquire/lazy versioning policy for writers. This adds writer overhead, but allows for more concurrency amongst readers who can continue to work, even when a writer is active. Transactions still do not log enough information for validation, so a committing writer excludes all other transactions. The Precise library adds the required read logging for validation.
Features
Hashed implementations use a global table of ownership records (orecs) in order to control access to data. Normal addresses are mapped to an orec using a hash. Before committing, a writer must acquire all of the orecs corresponding to locations that it has written, and make sure that all of the locations that it read are stil valid.
Hashed implementations typically have low overhead and high scalability. In addition, they are easy to generate code for. They suffer from false conflicts when different addresses collide under the hash function. They also usually allocate the orec table statically. This can be a large structure, sometimes on the order of millions of locations. Finally, data and metadata have no locality, so a single access typically requires two cache lines to satisfy.
The LLT (Lazy-Lazy-Timestamp) library is a canonical lazy versioning implementation patterned after TL2. There is a global clock that transactions read when they start. Orecs contain the last time that a location was modified. If a transaction encounters a location that was written after it starts, it assumes it is inconsistent and aborts and retries. At commit time, the transaction acquires all of the orecs associated with locations it is modifying, checks to make sure that all of the locations it read still have a timestamp earlier than its start time, increments the global time, and then writes out all of its updates and modifies the associated orecs to be the new time.
Features
fence()
interface for privatization)The ET (Extendable-Timestamps) library starts with the basic LLT infrastructure, adds the ability to operate in both eager-acquire/eager-versioning and eager-acquire/lazy-versioning mode, and adds extendable timestamps as in Reigel et al.'s SPAA, 2007 paper.
Extendable timestamps simply means that a transaction encountering a location that was written after its start time validates rather than aborts. If validation succeeds, the transaction is still consistent and it updates its timestamp to the current global time. This allows it to continue processing, and avoids wasting the work it has already done.
Features
fence()
interface for privatization)-Vee in
the benchmarks), or-Vel in the benchmarks), or-Vll in
the benchmarks)SGLA extends the lazy-lazy variant of ET with the start time linearization proposed by Menon et al. in SPAA, 2008 to provide single lock atomicity in Java. Start linearization reduces scalability, so LLT (or ET) should be preferred in non-Java environments when stronger semantics are not required.
Features
The Fair runtime extends the lazy-lazy variant of ET with support for transactional priorities. A transaction with a lower priority will yield to a transaction with a higher priority. More information about this runtime can be found in our PPOPP, 2009 paper. The Fair runtime uses the "Patient" contention management policy to avoid livelock in practice, and can be configured to avoid starvation by elevating transaction priority after a number of consecutive aborts.
Features
fence()
interface for privatization)The Strict runtime is based on the lazy-lazy variant of our ET runtime, with added support for the acquire and release fences required by the SSS transactional memory model. More details can be found in our paper on transactional memory models at OPODIS, 2008.
Features
The Flow runtime adds implicit privatization safety to our LLT runtime, as well as optional support for the SFS transactional memory model found in our paper on transactional memory models at OPODIS, 2008.
Features
While word-based implementations with global orec tables are the most common form of word-based TM, there are other options. We provide two in RSTM.
RingSW implements the single-writer variant of RingSTM presented at SPAA, 2008. Rather than using a global shared table of orecs, transactions in RingSTM use Bloom filters to approximate read and write sets. Committing transaction publish their Bloom filters in a global ring, and transactions can validate by fast intersections of their read set with published write sets.
Features
The precise algorithm takes TML + Lazy and adds value-based conflict detection, pioneered in Olszewski et al.'s JudoSTM published in PACT, 2007, in order to support rollback.
Value-based conflict detection does not require any per-location metadata. Transactions simply record the values that they have read, and check their consistency by making sure that all of the values are still correct. The TML lock is used to serialize transactional commit.
Features