Detail

Leveraging Parallel Nesting in Transactional Memory

Exploiting the emerging reality of affordable multi-core architectures
goes through providing programmers with simple abstractions
that would enable them to easily turn their sequential programs into
concurrent ones that expose as much parallelism as possible.While
transactional memory promises to make concurrent programming
easy to a wide programmer community, current implementations
either disallow nested transactions to run in parallel or do not scale
to arbitrary parallel nesting depths. This is an important obstacle to
the central goal of transactional memory, as programmers can only
start parallel threads in restricted parts of their code.
This paper addresses the intrinsic difficulty behind the support
for parallel nesting in transactional memory, and proposes a novel
solution that, to the best of our knowledge, is the first practical
solution to meet the lowest theoretical upper bound known for the
problem.
Using a synthetic workload configured to test parallel transactions
on a multi-core machine, a practical implementation of our
algorithm yields substantial speed-ups (up to 22x with 33 threads)
relatively to serial nesting, and shows that the time to start and commit
transactions, as well as to detect conflicts, is independent of
nesting depth.