Alladi Ramakrishnan Hall

Design and ImplementaTechniques to Achieve Compositionality using Object-based Software Transactional Memory Systems

Archit Somani

Technion, Israel

The rise of multi-core systems has necessitated the need for concurrent programming. However, developing correct, efficient concurrent programs is notoriously difficult. Software Transactional Memory Systems (STMs) are a convenient programming interface for a programmer to access shared memory without worrying about concurrency issues. Another advantage of STMs is that they facilitate compositionality of concurrent programs with great ease. Different concurrent operations that need tobe composed to form a single atomic unit is achieved by encapsulating them in a single transaction.

Most of the STMs proposed in the literature are based on read/write primitive operations on memory buffers. We denote them as Read-Write STMs or RWSTMs. Some read/write primitives result inunnecessary aborts. To ignore unimportant lower-level read/write conflicts and allow better concurrency,we design and implement efficient Object-based STMs (or OSTMs) with concurrent closed addressed hashtable (HT-OSTM) and list (list-OSTM) which export the higher-level operations such as insert, delete,lookup, etc. as transaction interface.

It was observed in databases and RWSTMs that storing multiple versions provide greater concurrency. We combine both of these ideas carefully for harnessing greater concurrency in STMs: multiple versions with objects semantics. We propose the notion of Multi-version Object STMs or MVOSTMs. Specifically, we design and implement MVOSTM for the hash-table and list, denoted asHT-MVOSTM and list-MVOSTM. We prove the correctness of proposed MVOSTMs as opacity and show significant performance gain over state-of-the-art STMs through experimental evaluations.