Design and Implementation of Efficient Techniques to Achieve Compositionality using Object-based Software Transactional Memory Systems

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 such as priority-inversion, deadlock, livelock, etc. Another advantage of STMs is that they facilitate compositionality of concurrent programs with great ease. Different concurrent operations that need to be composed to form a single atomic unit is achieved by encapsulating them in a single transaction (a piece of code). Most of the STMs proposed in the literature are based on read/write primitive operations on memory buffers. We represent them as Read-Write STMs (RWSTMs). These read/write primitives result in unnecessary aborts. Instead, semantically rich higher-level methods such as hash table lookup, insert or delete, etc. aid in ignoring unimportant lower-level read/write conflicts and allow better concurrency. We call them Object-based STMs (OSTMs). In this thesis, we adapt the transaction tree model from databases to propose OSTM which enables efficient composition. We extend the traditional notion of conflicts and legality to higher-level methods using STMs and lay down detailed correctness proof to show that it is conflict-opacity or co-opaque. We implemented an efficient OSTM for two Concurrent Data Structures (CDS), hash table and list as HT-OSTM and list-OSTM respectively. Both the OSTMs export the higher-level operations as transaction interface but it is generic to other data structures as well. Experimental analysis of HT-OSTM outperforms state-of-the-art hash table based STMs (ESTM, RWSTM) by a factor of 3.8, 2.2 for lookup intensive workload (70% lookup, 10% insert, 20% delete) and by a factor of 6.7, 5.3 for update intensive workload (50% lookup, 25% insert, 25% delete) respectively. Similarly, list-OSTM outperforms state-of-the-art list based STMs, Trans-list, NOrec-list, and Boostinglist by a factor of 1.76, 1.89, 1.33 for lookup intensive workload and by a factor of 1.77, 1.77, 2.54 for update intensive workload respectively. Along with this, HT-OSTM and list-OSTM incurred negligible aborts as compared to state-of-the-art STMs considered in this thesis. It has been shown in the literature of databases and RWSTMs that storing multiple versions corresponding to each key provides greater concurrency. So, to achieve greater concurrency than OSTM, we combine multiple versions with object semantics idea for harnessing greater concurrency in STMs. We propose the new and efficient notion of Multi-Version Object-based STMs or MVOSTMs. Specifically, we introduce and implement MVOSTM for two efficient CDS, hash table and list object, represented as HT-MVOSTM and list-MVOSTM respectively but it is generic for other data structures as well. Initially, HT-MVOSTM and list-MVOSTM use an unbounded number of versions for each key that suffers from memory consumption. To address this issue, we developed two variants for both hash table and list data structures: (1) A Garbage Collection (GC) method in MVOSTM to delete the unwanted versions of a key, denoted as MVOSTM-GC . (2) Finite version MVOSTM (or KOSTM ) which maintains at most K-versions corresponding to each key by replacing the oldest version when (K + 1)th version is created by the current transaction. Experimental results show that hash table based KOSTM (HT-KOSTM) performs best among its variants (HT-MVOSTM and HT-MVOSTM-GC) and outperforms state-of-the-art hash table based STMs (HT-OSTM proposed by us, ESTM, RWSTM, HT-MVTO, HT-KSTM) by a factor of 3.5, 3.8, 3.1, 2.6, 1.8 for workload W1 (90% lookup, 5% insert, and 5% delete), by a factor of 1.4, 3, 4.85, 10.1, 7.8 for workload W2 (50% lookup, 25% insert, and 25% delete), and by a factor of 2, 4.25, 19, 69, 59 for workload W3 (10% lookup, 45% insert, and 45% delete) respectively. Similarly, list based KOSTM (list-KOSTM) performs best among its variants (listMVOSTM and list-MVOSTM-GC) and outperforms state-of-the-art list based STMs (list-OSTM proposed by us, Trans-list, Boosting-list, NOrec-list, list-MVTO, listKSTM) by a factor of 2.2, 20, 22, 24, 12, 6 for workload W1, by a factor of 1.58, 20.9, 25.9, 29.4, 26.8, 19.68 for workload W2, and by a factor of 2, 35, 41, 47, 148, 112 for workload W3 respectively. We proved that MVOSTM s satisfy opacity and ensure that the transaction with lookup only methods does not abort if unbounded versions are used. To the best of our knowledge, this is the first work to explore the idea of using multiple versions in OSTMs to achieve greater concurrency. To the MVOSTMs explained above, we performed a few more optimizations to harness greater concurrency further. We proposed the notion of Optimized MultiVersion OSTMs (OPT-MVOSTMs). We propose the OPT-MVOSTMs for two efficient CDS, hash table and list objects as OPT-HT-MVOSTM and OPT-list-MVOSTM respectively but it is generic for other data structures as well. For memory utilization, we propose two variants of both the algorithms as OPT-HT-MVOSTM-GC (garbage collection on unwanted versions), OPT-HT-KOSTM (finite K-versions) and OPTlist-MVOSTM-GC , OPT-list-KOSTM . Experimental analysis shows that OPT-HT-KOSTM performs best among its variants (OPT-HT-MVOSTM and OPT-HT-MVOSTM-GC) and outperforms all the state-of-the-art hash table based STMs (HT-KOSTM proposed by us, HT-OSTM proposed by us, ESTM, RWSTM, HT-MVTO, HT-KSTM) by a factor of 1.05, 3.62, 3.95, 3.44, 2.75, 1.85 for workload W1, by a factor of 1.07, 1.44, 3.36, 5.45, 10.84, 8.42 for workload W2, and by a factor of 1.07, 2.11, 5.1, 19.8, 70.3, 60.23 for workload W3 respectively. Similarly, OPT-list-KOSTM performs best among its variants (OPT-list-MVOSTM and OPT-list-MVOSTM-GC) and outperforms state-of-the-art list based STMs (listKOSTM proposed by us, list-OSTM proposed by us, Trans-list, Boosting-list, NOreclist, list-MVTO, list-KSTM) by a factor of 1.2, 2.56, 25.38, 23.57, 27.44, 13.1, 6.8 for W1, by a factor of 1.12, 2.11, 21.54, 26.27, 30.1, 27.89, 20.1 for W2, and by a factor of 1.11, 2.91, 36.1, 42.2, 48.89, 149.92, 114.89 for W3 respectively. We rigorously proved that OPT-MVOSTM s satisfy opacity. In this thesis, we proposed multiple Object-based STM systems (OSTM, MVOSTM, OPT-MVOSTM). We proved that all the proposed OSTMs satisfy the popular correctness criteria as opacity. Experimental evaluation shows that all the proposed OSTMs achieved significant performance gain while reducing the number of aborts as compare to state-of-the-art STMs