Rochester Software Transactional Memory

Last update: 03/14/08
  • Main
  • License
  • Download
  • Building RSTM
  • Programming with RSTM
  • Applications

Data Structure Microbenchmarks

The default build allows you to run 8 microbenchmarks by typing

bench/obj/Bench_rstm -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
Note that when the library is configured to use RedoLock, LLT, or CGL, the executable name will change accordingly.

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 LLT and CGL back-ends.
  • 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
This release of RSTM 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 RedoLock, and that the -V parameter has no meaning for the LLT and CGL backends. 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.

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 FeatureTest 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.

Questions? contact webmaster
Department of Computer Science
University of Rochester