ε-STM

A Software Transactional Memory that supports elastic transactions

estm

ε-STM is the first software transactional memory supporting elastic transactions. Elastic transactions are a variant of the transactional model. Upon conflict detection, an elastic transaction might drop what it did so far within a separate transaction that immediately commits, and initiate a new transaction which might itself be elastic.

Elastic transactions are a complementary alternative to traditional transactions, particularly appealing when implementing search structures. Both forms of transactions can safely be combined within the same application. ε-STM implementation is faster than a state-of-the-art software transactional memory in various workloads and with a speedup of 36% on average. It also presents a speedup over lock-based solutions of 89% on average.

The figure on the right-hand side shows that ε-STM multiplies regular STM peak performance by a factor of 4 on an 8-core machine for searching and modifying a 216-sized linked list, but, more importantly, tolerates contention. Indeed it scales better as the ratio of updating transactions grows and the level of parallelism grows.

Here is the simple API, ε-STM provides to the user: The simplicity of using ε-STM comes from the very few information the programmer has to provide. The programmer has to indicate whether his(her) transaction is normal or elastic and no extra-information (i.e., release action, or on-abort-action) is necessary.

Related Papers and Talks

Releases

Graphs

Experiments
Comparison of ESTM (java version) against state-of-the-art STM libraries (LSA, TL2, NOrec, SwissTM, LSA-CM, TL2-CM).

Settings
UltraSPARC T2, 2048 elements, 10% insert, 10% remove, 80% contains. Probability of operation success: 1/2 (i.e., 10% effective update operations, 90% read-only operations). Each point results from average throughput of 5 runs of 5 seconds each with 5 seconds JVM warmup.

For further information please contact Vincent.Gramoli@epfl.ch.