Eshcar Hilel, Ph.D. Thesis Seminar
As multi-core and multiprocessing architectures are becoming common, modern
applications require concurrent data structures for their computations.
Designing concurrent data structures and ensuring their correctness
is a difficult task; significantly more challenging than doing so
for their sequential counterparts.
Transactional memory (TM), a programming model in
which concurrent processes synchronize via in-memory transactions,
is one prominent approach for alleviating the difficulty of programming
concurrent data structures for multi-core and multiprocessing systems.
TM is seriously considered as part of software solutions and as a basis for
novel hardware designs. It is therefore imperative to understand inherent
tradeoffs in the design and implementation of transactional memory.
In the talk, we present two inherent limitations on implementations
of transactional memory. First, we discuss TMs avoiding
interference between transactions with disjoint data. We prove that
in these implementations, read-only transactions that always terminate
successfully, not only have to write to the memort, but the number of writes is
linear in the number of items the transaction is reading.
Allowing to access the same memory locations from inside and outside
a transaction is crucial both for interoperability with legacy code
and in order to improve the performance of the TM. Supporting privatization,
allows to isolate some items making them private to a process; the process
can thereafter access them nontransactionally, without interference
by other processes. We show privatization has an inherent cost, linear
in the number of privatized items. The assumptions needed to prove the
bounds indicate that limiting the parallelism of the TM or tracking the
items of other transactions are the price to pay for efficient