Friday, January 25, 2008
2:00 PM
703
Michael F. Spear
Computer Science @ University of Rochester
4th year Graduate Student
Mike will will present work on a new STM algorithm that I developed with Maged Michael and Christoph von Praun while interning at IBM last summer. The new algorithm, "RingSTM", has a fundamentally different approach to transactions; we eschew the use of per-location metadata, instead representing each committed transactions by a Bloom filter approximating its write set, and publishing these filters to a single global ring data structure. RingSTM has a number of novel attributes, briefly outlined below:

1 - no read bookkeeping overhead (the state of the art is that every read is logged)

2 - read validation overhead is not linear in the number of reads but in the number of committing writers, with the possibility for strong guarantees on total validation overhead

3 - only one atomic operation (the state of the art is one atomic operation per location written)

4 - livelock freedom

5 - short critical sections favorable to thread-level speculation

6 - simplified contention management requirements

7 - strong linearization guarantees

8 - low memory ordering requirements

9 - privatization safety

In addition to being a novel design with good performance and strong theoretical properties, RingSTM has important implications for hardware design, fine-grained implicit parallelism (like Chen's BOP), and transactions in the operating system.