The Taub Faculty of Computer Science Events and Talks

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 privatization.