Date: 26 Feb 2008
From: jyrki@diku.dk
Subject: M.Sc. thesis defence: adding transactions to C++

Oral defence of M.Sc. thesis: A software transactional memory library
for C++
Defender: Kasper Egdų
Censor: Kim Skak Larsen (Odense)
Supervisor: Jyrki Katajainen

Time:  Thursday, 28 February 2008, 10.15–11.05
Place: N037 at DIKU North

The defence will be held in Danish.

Abstract:

An increasing number of cores (or CPUs) per computer is creating a
need for good programming tools for exploiting these cores. Locks are
traditionally used, but issues with deadlocks and race conditions
easily arise and choosing the correct granularity for locking is often
not trivial. In addition, the use of locks does not generally enable
the programmer to compose existing correct lock-based program pieces
into a new larger correct lock-based piece.

An alternative to locks is Software Transactional Memory (STM) which
is a concurrency approach that does not use locks as its primary
method. Instead STM is an optimistic concurrency control mechanism;
using memory transactions similar to transactions used in database
systems. Programs built with STM avoid deadlocks and race conditions
and enables composition of program pieces from existing pieces.

This work explores design criteria for building an STM system for C++
and for building Standard Template Library containers on top of such a
system. We emphasize correctness over performance, generic programming
and direct reuse of existing algorithms and data types with our
implementation. Using an indirection-based approach for our STM
implementation enables us to guarantee strong exception safety for all
operations on our data structures. We also develop a new method for
nesting STM-based data structures within each other, such that we
avoid unnecessary conflicts and copying.

Using compile-time polymorphism we develop a new method for laying out
shared data in memory, thereby allowing us to reduce the number of
cache misses that are otherwise the primary disadvantage of
indirection-based STM implementations. For large datasets with low
contention the throughput in our benchmarks is increased by up to 33
percent when using our layout technique.


The thesis is available online at
http://www.diku.dk/~jyrki/PE-lab/Kasper/