Rochester Software Transactional Memory

• Google Code Site
• Main
• License
• Download
• Building RSTM
• Programming with RSTM
• Applications
• STM Implementations
• STM Primer

Google Code Site

The RSTM package is now available as a Google code project. We welcome your comments, suggestions, and contributions. Future releases will occur through the Google code mechanism.

The information hosted here is accurate with respect to the fifth release, and the initial Google code release. The STM Implementations and STM Primer pages will continue to be relevant, but we expect the RSTM-specific information hosted at the University of Rochester to become rapidly out-of-date.

Applications Included With RSTM

Data Structure Microbenchmarks

The default build allows you to run 8 microbenchmarks by typing

          bench/obj/Bench_[libname] -B <benchmark>
        

• Counter - Shared Counter
• HashTable - 256 Bucket HashTable
• LFUCache - Web Cache Simulation
• LinkedList - Sorted Linked List
• LinkedListRelease - Sorted Linked List with Early Release
• RandomGraph - Graph Benchmark (default 4 neighbors)
• RBTree - Red-Black Tree (default)
• RBTreeLarge - Red-Black Tree with 4KB nodes
• DList - Doubly-linked list
• WWPathology - benchmark with lots of write-write conflicts
• RWPathology - benchmark with lots of read-write conflicts
• StridePathology - another benchmark with read-write conflicts
• PrivList - benchmark to privatize linked lists
• PrivTree - benchmark to privatize RBTrees
• CoarseGrainHash - nontransactional hash benchmark
• FineGrainHash - nontransactional hash benchmark

Since RSTM and RedoLock are obstruction-free, we provide a number of contention managers that can be run with

          bench/obj/Bench_rstm -C <contention manager>
        

Note: These options have no effect when invoked with the word-based backends.

• Aggressive - always abort competitor
• Polite - exponential backoff waiting
• Karma - whoever has opened more objects wins
• Killblocked - abort if the competitor seems to be stalled
• Eruption - donate karma when you wait
• Timestamp - oldest always wins
• Polka - combination of polite and karma (default)
• Polkaruption - combination of Polka and Eruption
• Polkavis - Polka, with code to handle visible readers
• Highlander - when A kills B, A takes B's karma
• Whpolka - Polka, with different karma for reads and writes
• Justice - yet another parameterization of reads and writes for Polka
• Greedy - blocking, time-based priority like that described in Guerraoui et al.'s DISC 2005 paper on Polymorphic Contention Management. Works best with visible readers.
• Serializer - blocking time-based priority. Like Greedy except that on abort, transactions get a new priority.
• Reincarnate - nonblocking (via timeouts) version of Serializer
• Timid - blocking, always aborts on conflict. Similar to "responder wins" policy in hardware TM

When configured with the RSTM backend, this release supports conflict detection based on visible or invisible readers, and eager or lazy acquire. The appropriate command-line options are:

• -V invis-eager (invisible readers, eager acquire)
• -V invis-lazy (visible readers, eager acquire)
• -V vis-eager (visible readers, eager acquire)
• -V vis-lazy (visible readers, lazy acquire)

Note that visible readers have no meaning in other backends.

For blocking, word-based STMs based on ET we support three write acquisition and versioning pairs.

• -Vee (eager, eager)
• -Vel (eager, lazy)
• -Vll (lazy, lazy)

There are many other parameters as well, for varying the benchmark time, the range of elements in the data set, the number of threads, the read/write mix, and much more. Type

bench/obj/Bench_rstm -h

for the full list.

Delaunay Triangulation

The mesh/ folder contains code that computes the unique Delaunay Triangulation for a set of points. Invoking

mesh/mesh -h

will enumerate the command-line options. Please note that the validation strategy and contention management policies for the mesh application are hard-coded. You will need to change the parameters to stm::init() in mesh.cpp and my_thread.cpp to use different policies.

Please note that the mesh application is currently not supported on Win32.

Extensible Hashing

This is the extensible hashing benchmark that we used to test contention manager implementations in our PPOPP 2009 paper.

Swarm: OpenGL Rendering

The swarm/ folder contains code for an OpenGL 3-D Rendering benchmark. The current release of swarm consists of an engine that computes animation and physics (velocity, collisions) for a set of animated tripods that are being drawn into large gravity-emitting planets. Swarm uses inevitability, when available, to accelerate rendering and updating transactions.

Swarm requires OpenGL and GLUT. If necessary, you may need to download OpenGL and GLUT to the alt-license/ folder. Our tests use the implementation available from OpenGL.org. As in the mesh, swarm requires you to manually change the contention management and validation policies in the code. The files my_thread.cpp and Game.cpp contain calls to stm::init().

Please note that on Mac OS X, swarm will not handle user input (such as clicking on the graphics window or pressing 'esc' to terminate the benchmark) during execution. This OS X specific bug will be addressed in a future release. Swarm can be terminated in this case with a [ctrl-C] on the command line, and can be run with the -t field to specify the number of seconds to run for.

Basic Nesting, Retry, and Word-Based Microbenchmarks

If you are interested in developing new runtime libraries, the VerifyRetry, VerifyNesting, and TypeTest code (part of the bench/ folder) may be of interest. This code consists of simple tests to ensure that each library implements retry and subsumption correctly. These tests also verify that word-based stms (such as LLT) handle all primitive types correctly.