How Good Is A Transactional Memory Implementation?

We evaluate transactional memory (TM) implementations, both on theoretical and experimental ground. We ask:

• What are the inherent limitations and trade-offs of transactional memory,
• How expensive are some of the guarantees a TM implementation may provide, and
• Which algorithms/frameworks perform best.

• Transactional Memory - A Short Introduction
• The Velox project
• The STMBench7 Benchmark for TMs
• Theoretical Evaluation of TMs
• SwissTM
• Microbench
• E-STM
• Student projects
• Related Papers

Transactional memory (TM) is a new computation paradigm in which processes of an application communicate using lightweight, in-memory transactions. Basically, a process that wants to access a shared data structure executes some operations on this structure inside a transaction. When the transaction commits, all these operations appear as if they took place instantaneously, at some single, unique point in time. When the transaction aborts, however, all the operations are roll-backed and their effects are never visible to other transactions.

The TM paradigm is argued to be as easy to use as coarse-grained locking, and nearly as efficient on multi-core systems as hand-crafted, fine-grained locking. It is thus not surprising to see a large body of work dedicated towards implementing the paradigm and exploring its limitations (see, e.g., the TM Bibliography page).

We currently participate in the Velox European Project that aims at providing an integrated Approach to Transactional Memory on Multi- and Many-core Computers. The general objective of Velox is to build an integrated hardware/software TM stack (i) to develop new and convert existing applications into real-world TM-based applications that scale easily with the number of cores, (ii) to optimize software and hardware TM-mechanisms using real-world workloads, and (iii) to address unexpected but potential show stoppers for TM deployment.

We have developed STMBench7: a benchmark for evaluating TM implementations. The benchmark aims at providing a workload that is both realistic and non-trivial to implement in a scalable way. The implementation (in Java and C++) contains a lock-based synchronization strategy that can serve as a baseline for comparison with various TMs. The following paper describes STMBench7 in more detail:

Guerraoui, R., Kapalka, M. and Vitek, J. (2007) STMBench7: A Benchmark for Software Transactional Memory. Proceedings of the Second European Systems Conference EuroSys 2007.

The following paper describes our recent experiments with the benchmark using various available STM implementations:

Dragojevic, A., Guerraoui, R. and Kapalka, M. (2008) Dividing Transactional Memories by Zero. 3rd ACM SIGPLAN Workshop on Transactional Computing (Transact 2008).

Important note: The benchmark is still a work in progress. The code and the specification may still undergo many, maybe significant, changes that should reflect the feedback we will get.

Any suggestions, comments or criticism are more than welcome and should be send to Michal Kapalka.

The new Java version (07.03.2008 Beta) of STMBench7 has been released. The new features and changes from the previous version (27.06.2007) are the following:

1. Added correctness tests (useful for validating whether a given synchronization technique gives correct results):
   • Invariant tests: the implementation checks whether all the invariants of the benchmark data structure are preserved.
   • Sequential replay of a concurrent execution: the implementation can replay a concurrent execution sequentially in order to check for violations of the opacity property.
2. The new version does no longer use AspectJ: the coarse-grained and medium-grained locking methods are now fully implemented in Java, without adding any additional overhead when they are not used.
3. The build procedure now uses Apache Ant instead of make.

Note that the new version of the benchmark has a slightly different API. The new API is cleaner and easier to use with an STM, but may introduce problems when used with implementations using the old version of STMBench7.

1. New version (07.03.2008 Beta) − source code and JAR binary file: stmbench7-07.03.2008-beta.tgz
2. Old version (21.02.2007):
   • Source code: stmbench7-21.02.2007.tgz
   • JAR binary file: stmbench7-21.02.2007.jar

The Java version of STMBench7 is created/maintained by Michal Kapalka

The following files are available for download:

• SwissTM, TinySTM and TinySTM STMBench7 source code: sb7_tt_20090910.tgz

Older versions:

• Source code (with locking and RSTM-based synchronization): stmbench7.cpp-27.06.2007.tgz
• A patch for RSTM that is needed to run the RSTM version of STMBench7: rstm_v3.epfl.2.tgz
• SwissTM-w, TinySTM and TinySTM STMBench7 source code: sb7_tt_20081117.tgz
• SwissTM-o STMBench7 source code: sb7_swisstm_20080825.tgz
• TL2/TinySTM source code: sb7_tt_20080519.tgz

The C++ version of STMBench7 is created/maintained by Aleksandar Dragojevic.

We argue that verifying TM protocols requires a new correctness criterion and existing ones such as serializability or linearizability are not adequate. We defined a correctness criterion for TM implementations which we call opacity.This criterion captures the intuitive safety requirements that have been (implicitly) identified by many authors. In the following paper, we present opacity, together with its graph-theoretical interpretation, and derive the first complexity lower bound for TM implementations:

Guerraoui, R. and Kapalka, M. (2008) On the Correctness of Transactional Memory. Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2008).

We have developed SwissTM: an STM that has the goal of performing particularly well with realistic workloads, with various transaction sizes and mixed access pattern, while still achieving good performance in more traditional microbenchmarks.

The following files are available for download:

• 2009-09-10

Older versions:

• 2008-11-19 wlpdstm_20081119.tgz
• 2008-11-17 swisstm-w-20081117.tgz
• Object based source: swisstm_20080531.tgz
• Word based source: wlpdstm_20080611.tgz

Lee-TM is an STM benchmark that offers longer, realistic workloads and is based on Lee’s circuit routing algorithm. The algorithm takes pairs of points (e.g. on an integraged circuit) as its input and produces a non-intersecting routes between them. We helped with development of RSTM, TL2 and TinySTM versions of Lee-TM benchmark.

The following files are available for download:

• 2009-09-10

Older versions:

• 2008-11-17 lee_tm_20081117.tgz
• Object based SwissTM Lee-TM source: lee_tm_swisstm_20080611.tgz
• Word based SwissTM Lee-TM source: lee_tm_wlpdstm_20060611.tgz

Other versions can be downloaded from here.

STAMP is an STM benchmark suite that consists of several realistic workloads. We modified the original version to support SwissTM.

The following files are available for download:

• 2009-09-10

The original version can be downloaded from here.

Transactional memories are typically speculative and rely on contention managers to cure conflicts. This work explores a complementary approach that prevents conflicts by scheduling transactions according to predictions on their access sets. We developed Shrink, a scheduler that (a) bases its prediction on the access patterns of the past transactions from the same threads, and (b) uses a novel heuristic, which we call serialization affinity, to schedule transactions with a probability proportional to the current amount of contention.

The following files are available for download:

• Shrink for SwissTM swisstm_shrink.tar.gz
• Shrink for TinySTM tinystm_shrink.tar.gz

Microbench aims at comparing STM performance against performance of lock-based and lock-free alternatives. It comprises common data structures: linked list, skip list, hashtable... Microbench derives from the stm-based linked list test of TinySTM and the current release includes the SUN stm-based red-black tree benchmark. It also features fine-grained locking algorithms (e.g., lazy linked list, optimistic skip list) and lock-free algorithms (e.g., harris-michael, fraser’s lock-free skip-list).
Microbench has been successfully used with E-STM, SwissTM, TinySTM and runs on x86, x86-64 and SPARC.

The current version can be downloaded here.

E-STM is a software transactional memory that supports 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. Elastic transactions can be safely composed with normal ones, but significantly improve performance if used instead.

The current version can be downloaded here.

We offer master, semester and internship student projects:

• Transactional File System
• Irrevocable Transactions
• Transactional Boosting
• Transactional Visible Reads
• Transactional Closed Nesting
• SwissTM C#
• SwissTM Java
• STAMP C#
• STAMP Java
• Concurrent Applications using Elastic Transactions
• Elasticity and Boosting
• Large-Scale Distributed Transactions

Dragojevic A., Felber P., Gramoli P., Guerraoui R. (2010) Why STM can be more than a Research Toy. Communications of the ACM (CACM).

Barreto J., Dragojevic A., Ferreira P., Guerraoui R., Kapalka M. (2010) Leveraging Parallel Nesting in Transactional Memory. Proceedings of the 15th Symposium on Principles and Practice of Parallel Computing (PPoPP).

Felber, P., Gramoli, V., Guerraoui, R. (2009) Elastic Transactions. Proceedings of the 23rd International Symposum on Distributed Computing (DISC).

Guerraoui, R., Henzinger, T. A., Singh, V. (2009) Software Transactional Memory on Relaxed Memory Models. Proceedings of the 21st International Conference on Computer Aided Verification (CAV).

Guerraoui, R., Kapalka, M. (2009) Transactional Memory: Glimmer of a Theory (Invited Paper). Proceedings of the 21st International Conference on Computer Aided Verification (CAV).

Dragojevic A., Yang N., Adl-Tabatabai A.-R. (2009) Optimizing Transactions for Captured Memory.. Proceedings of the 21st Annual Symposium on Parallelism in Algorithms and Architectures (SPAA).

Dragojevic A., Singh A., Guerraoui, R. Singh V. (2009) Preventing versus Curing: Avoiding Conflicts in Transactional Memories. Proceedings of the 28th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC).

Guerraoui, R., Kapalka, M. (2009) The Theory of Transactional Memory. Bulletin of the EATCS, 97.

Dragojevic A., Guerraoui, R., and Kapalka, M.. (2009) Stretching Transactional Memory. Proceedings of the ACM SIGPLAN 2009 Conference on Programming Languages Design and Implementation (PLDI).

Guerraoui, R., and Kapalka, M.. (2009) The Semantics of Progress in Lock-Based Transactional Memory. Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL).

Harmanci, D., and Felber, P., Gramoli V. and Fetzer, C. (2009) TMunit: Testing Transactional Memories. 4th ACM SIGPLAN Workshop on Transactional Computing.

Gramoli, V., Harmanci, D. and Felber P. (2008) Toward a Theory of Input Acceptance for Transactional Memories. Proceedings of the 12th International Conference on Principles of Distributed Systems.

Guerraoui, R., Henzinger, T.A. and Singh, V. (2008) Permissiveness in Transactional Memories. Proceedings of the 22nd International Symposium on Distributed Computing.

Guerraoui, R., Henzinger, T.A. and Singh, V. (2008) Completeness and Nondeterminism in Model Checking Transactional Memories. Proceedings of the 19th International Conference on Concurrency Theory.

Guerraoui, R. and Kapalka, M. (2008) On Obstruction-Free Transactions. 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).

Dragojevic, A., Guerraoui, R., Kapalka, M. (2008) Stretching Transactional Memory. Technical Report.

Guerraoui, R., Henzinger, T. and Singh, V. (2008) Model Checking Transactional Memories. Proceedings of the ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation (PLDI).

Guerraoui, R. and Kapalka, M. (2008) On the Correctness of Transactional Memory. Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP’08).

Dragojevic, A., Guerraoui, R. and Kapalka, M. (2008) Dividing Transactional Memories by Zero. 3rd ACM SIGPLAN Workshop on Transactional Computing (Transact 2008).

Guerraoui, R., Kapalka, M. and Kouznetsov, P. (2007) The Weakest Failure Detectors to Boost Obstruction-Freedom. Distributed Computing, 20(6).

Guerraoui, R. (2007) A Smooth Concurrency Revolution with Free Objects. Internet Computing, 11(4).

Black, A.P., Cremet, V., Guerraoui, R. and Odersky, M. (2003) An Equational Theory for Transactions. Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2003).

Frølund, S. and Guerraoui, R. (2002) e-Transactions: End-to-End Reliability for Three-Tier Architectures. IEEE Trans. Software Eng. 28(4):378−395.

Frølund, S. and Guerraoui, R. (2001) Implementing E-Transactions with Asynchronous Replication. IEEE Trans. Parallel Distrib. Syst. 12(2):133−146.

Guerraoui, R., Capobianchi, R., Lanusse, A. and Roux, P. (1992) Nesting Actions through Asynchronous Message Passing. Proceedings of the European Conference on Object-Oriented Programming (ECOOP 1992).

Guerraoui, R. (1994) Atomic Object Composition. Proceedings of the 8th European Conference on Object-Oriented Programming (ECOOP 1994).

Guerraoui, R. (1995) Nested transactions: Reviewing the coherence contract. Information Sciences.