Supporting efficient aggregation in a task-based STM

  • Jean-Philippe Martin ,
  • Chris Rossbach ,
  • Derek Murray ,
  • Michael Isard

SFMA 2013 |

Published by The 3rd Workshop on Systems for Future Multicore Architectures

Parallel computing resources are ubiquitous; tools that simplify their programming are not. Software Transactional Memory (STM) makes parallel programming more accessible by eliminating locks, using optimistic concurrency to promise scalability for programs with simple synchronization. However, while modern STMs do simplify the task of writing correct code, they often complicate the task of writing efficient code: contention for shared resources can yield performance problems that are difficult for programmers to understand and address. Traditional TMs abort concurrent write-sharing transactions, detecting contention by tracking accesses to memory cells or objects. We argue this is the wrong layer of abstraction at which to perform this operation because many parallel constructs rely on data structures for which write-sharing is the common case such as work-lists and aggregators. In such contexts, the traditional approach is unnecessarily conservative and untenable for performance.

We propose mechanisms that enable the programmer to tell the system how to respond to contention at a higher level of abstraction, eliminating whole classes of contention at minimal additional cost in complexity. Our prototype C# STM, Aggro, implements these mechanisms and provides a task- based programming model, eliminating explicit thread management. We show that Aggro can outperform lock-based implementations and other optimistic systems such as Galois.