Rochester Software Transactional Memory

The Rochester Synchronization Group is pleased to announce the fourth release of our Rochester Software Transactional Memory (RSTM) system. RSTM is a C++ library for multithreaded, nonblocking transaction-based code. RSTM is a research prototype, but has been successfully tested on a variety of benchmarks and applications.

Patches

SPARC Delaunay Mesh Patch (for v4): This patch addresses a compilation problem with the Delaunay mesh code (in /mesh) under the v4 release. To apply this patch simply download it to the root directory of the extracted release, and run patch -p1 < mesh_sparc_ifdef.patch.
Retry Mechanisms for RSTM (for v4): This patch provides two alternative implementations of retry() that yield the processor pending wakeup by concurrent writer threads. To apply this patch simply download it to the root directory of the extracted release, and run patch -p0 < rstm_retry.patch.

What's New in Release 4?

The fourth release of RSTM contains a new word-based STM back-end, wider support for different operating systems and CPUs, a refined API, new features (retry, subsumption, inevitability), a new application (swarm), and a new build system. These features are outlined below.

OpenGL 3D Rendering: Our new OpenGL application, swarm, uses transactions to update and render a 3D scene graph. It also demonstrates how to use inevitability in RSTM.
Patches: We've tried our best to incorporate your suggestions, code, and patches into this release. Please let us know if we missed anything.
Inevitability: We now provide support for inevitable transactions via a try_inevitable call, that returns a bool on failure. Inevitability allows transactions to perform I/O, call precompiled libraries, and make system calls.
Subsumption and Retry: Subsumption (flat) nesting is now supported, as is simple API support for retry.
The LLT Library: LLT is a lazy versioning, lazy acquire, blocking, word-based STM based on the TL2 algorithm. Our C++ implementation of this algorithm is fully compatible with the RSTM API, and serves as a reference for how to integrate other word-based backends with existing code written for the RSTM API.
New API: To support privatization in word-based STMs like LLT, we had to refine the v3 API to differentiate between shared and privatized writes from within setters. Setters now take an extra parameter (either an wr_ptr or un_ptr) to indicate whether any write instrumentation is needed.
New Architecture Support: All libraries in this release are compatible with 32-bit x86 and systems running Windows, Linux, and Mac OS X, as well as SPARC systems running Solaris. The mesh application is now supported on Linux, Solaris, and Mac OS X, and swarm is fully supported on Windows and Linux, with partial support on Max OS X. Furthermore, there is some experimental code for running RSTM on Itanuim, as well as support for OpenBSD and FreeBSD.
Cleaner Implementation: There is no longer a need for clone/deactivate/redo methods within your transactional objects. When these features are needed, they are provided automatically via memcpy() calls.

What's New in Release 3?

The third release of RSTM includes new optimizations, as well as a new API, support for privatization, a mesh application, and a new stm backend. These new features are outlined briefly below. Over the next few days we will update this website to provide more information about these new features and how to use them.

New API: Our new API uses templates to mediate access to shared objects. These templates, which implement smart pointers, hide the old open_RO() and open_RW() methods. We believe the resulting code is more natural, and the smart pointers provide a clean interface for privatization and new STM backends. All of our benchmarks are updated to support this new API; until we update the "Using" link, please refer to the LinkedListRelease.cpp file for an example of the basic API.
Privatization: Using the new API, RSTM now permits applications to operate on shared data outside of a transaction. We provide build options for privatization using the transactional fence, validation fence, obstruction-free privatization and consensus (barrier) privatization. Details of these mechanisms are available in Technical Report 915. The PrivList.h file gives a very simple code example that uses the new API to privatize a linked list.
Delaunay Triangulation: Using the new API and its support for privatization, we were able to build a significant application using RSTM. The new application, Delaunay Triangulation, is built by default in the new release as mesh. It demonstrates a number of useful idioms for sharing code between transactional and nontransactional phases, and performs extensive privatization. Delaunay Triangulation is currently only supported under SPARC/Solaris.
New STM Backend: If you are willing to sacrifice nonblocking guarantees, it is possible to eliminate the level of indirection that RSTM introduces. While we aren't the first STM to provide this option, we are pleased nonetheless to offer our RedoLock library as a backend that is API-compatible with RSTM. RedoLock currently is only supported under SPARC/Solaris.
Accessors: To support RedoLock and obstruction-free privatization, we require the use of accessor methods (getters and setters) when reading fields of an object from inside a transaction. We provide preprocessor macros to simplify the creation of these accessors, and all of our code demonstrates their correct use.
New File Layout: We've merged all of the STM backend code into a single folder, stm. This makes it a little more confusing to modify RSTM itself, but it makes it far simpler to build applications that depend on RSTM: All of the dependencies are in a single folder, and to use RSTM you need only include stm/stm_api.h and #define the STM library you wish to use (valid options are rstm, redo_lock, and cgl).
Optimizations: A number of optimizations to the new library result in significantly faster code. Of particular interest, there is now a compile flag TLS with which you can choose optimized interfaces to thread-local storage. Using this and other optimizations, we have observed single-thread speedups of up to 20%.
Debugging: We've introduced several new assertions to help you write correct code. These assertions detect alias errors and API violations, such as the creation and use of transactional pointers (rd_ptr and wr_ptr) outside of transactions. These (and all other) assertions can be disabled with the PROFILE=fast compilation option.

What's New in Release 2?

The second release of RSTM includes a number of optimizations, bug fixes, and new features.

Memory Management: RSTM no longer relies on our garbage collector for correctness; you can now use any allocator, so long as you adhere to a straightforward interface. Using malloc or compile-time malloc replacements is straightforward.
Validation Heuristics: We are now including our global commit counter heuristic as a compile-time optimization. This heuristic improves the performance of some benchmarks by an order of magnitude.
Simpler Code: several key methods are noticably simpler and easier to understand, most notably open_RW().
Contention Management: You can avoid the overhead of virtual method calls by fixing the contention manager at compile time.
Simplified Build: the new RSTM build process is simpler and provides easy access to conflict profiling, timing, heuristics, and other features.
Faster: We've added some aggressive inlining and optimizations to speed the overall system.
RSTM now compiles and runs on the x86 architecture. The latest release is designed to build under x86/Linux as well as SPARC V8+/Solaris.
Justin Gottschlich (Draco Research Group, University of Colorado at Boulder) has ported RSTM release 2 to Microsoft Windows. This port is also available from the download page.

Why Transactions?

Transactions promise the simplicity of coarse-grain locks with the performance of fine-grain locks; if a block of code needs to execute atomically, the programmer simply labels it as transactional, and the runtime executes it in parallel with other transactions whenever possible.

Why Nonblocking?

Nonblocking data structures avoid many of the principal problems with locks, including deadlock, convoying, priority inversion, and performance anomalies due to preemption and page faults.

Why C++?

Most other STM systems require managed langauges (Java, C#, Haskell), or a nonstandard threading package. Our goal with RSTM is to encourage more widespread use of transactions by making them available to the large body of existing multithreaded code, much of which is written with pthreads in C and C++. (We hope in a future release to include an API for C.)

License

RSTM is released under the modified BSD license. We request, as a courtesy, that you register with us in order to access the download directory. This will allow us to alert you to future releases. (We will not use your name for any other purpose.) In addition, we ask that you adhere to the following requests if you download and use this software:

If your use of this software contributes to a published paper, please (1) cite our summary paper, which appears on this website, and (2) e-mail a citation for your published paper to .
If you redistribute derivatives of this software, please let us know, and either (1) ask people to register with us at this website or (2) collect registration information and periodically send it to us.

More Information

For more information about RSTM, you might want to view the Rochester Synchronization Group Publications List, which includes recent publications on RSTM, our RTM hardware proposal, our Java Adaptive STM (ASTM) system, and Contention Management research.

Acknowledgments

This material is based upon work supported by National Science Foundation grants CCR-0204344, CNS-0411127, CNS-0615139, CCF-0702505, and CSR-0720796; and by donations from Sun Microsystems, IBM, Intel, and Microsoft. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation or any other sponsor.