Singh, Ajay and Peri, Sathya
(2018)
Efficient means of Achieving Composability using
Transactional Memory.
Masters thesis, Indian Institute of Technology Hyderabad.
Abstract
The major focus of software transaction memory systems (STMs) has been to facilitate the multiprocessor
programming and provide parallel programmers with an abstraction for fast development of the concurrent
and parallel applications. Thus, STMs allow the parallel programmers to focus on the logic of parallel
programs rather than worrying about synchronization.
Heart of such applications is the underlying concurrent data-structure. The design of the underlying
concurrent data-structure is the deciding factor whether the software application would be efficient, scalable
and composable. However, achieving composition in concurrent data structures such that they are efficient as
well as easy to program poses many consistency and design challenges.
We say a concurrent data structure compose when multiple operations from same or different object
instances of the concurrent data structure can be glued together such that the new operation also behaves
atomically. For example, assume we have a linked-list as the concurrent data structure with lookup, insert
and delete as the atomic operations. Now, we want to implement the new move operation, which would delete
a node from one position of the list and would insert into the another or same list. Such a move operation
may not be atomic(transactional) as it may result in an execution where another process may access the
inconsistent state of the linked-list where the node is deleted but not yet inserted into the list. Thus, this
inability of composition in the concurrent data structures may hinder their practical use.
In this context, the property of compositionality provided by the transactions in STMs can be handy.
STMs provide easy to program and compose transactional interface which can be used to develop concurrent
data structures thus the parallel software applications. However, whether this can be achieved efficiently is a
question we would try to answer in this thesis.
Most of the STMs proposed in the literature are based on read/write primitive operations(or methods)
on memory buffers and hence denoted RWSTMs. These lower level read/write primitive operations do not
provide any other useful information except that a write operation always needs to be ordered with any
other read or write. Thus limiting the number of possible concurrent executions. In this thesis, we consider
Object-based STMs or OSTMs which operate on higher level objects rather than read/write operations on
memory locations. The main advantage of considering OSTMs is that with the greater semantic information
provided by the methods of the object, the conflicts among the transactions can be reduced and as a result,
the number of aborts will also be less. This allows for larger number of permissive concurrent executions
leading to more concurrency. Hence, OSTMs could be an efficient means of achieving composability of
higher-level operations in the software applications using the concurrent data structures. This would allow
parallel programmers to leverage underlying multi-core architecture.
To design the OSTM, we have adopted the transactional tree model developed for databases. We extend
the traditional notion of conflicts and legality to higher level operations in STMs which allows efficient
composability. Using these notions we define the standard STM correctness notion of Conflict-Opacity. The
OSTM model can be easily extended to implement concurrent lists, sets, queues or other concurrent data
structures.
We use the proposed theoretical OSTM model to design HT-OSTM - an OSTM with underlying hash table
object. We noticed that major concurrency hot-spot is the chaining data structure within the hash table. So,
we have used Lazyskip-list approach which is time efficient compared to normal lists in terms of traversal
overhead. At the transactional level, we use timestamp ordering protocol to ensure that the executions are
conflict-opaque. We provide a detailed handcrafted proof of correctness starting from operational level to the
transactional level. At the operational level we show that HT-OSTM generates legal sequential history. At
vi
transactional level we show that every such sequential history would be opaque thus co-opaque.
The HT-OSTM exports STM insert, STM lookup and STM delete methods to the programmer
along-with STM begin and STM trycommit. Using these higher level operations user may easily and
efficiently program any parallel software application involving concurrent hash table. To demonstrate the
efficiency of composition we build a test application which executes the number of hash-tab methods (generated
with a given probability) atomically in a transaction. Finally, we evaluate HT-OSTM against ESTM
based hash table of synchrobench and the hash-table designed for RWSTM based on basic time stamp ordering
protocol. We observe that HT-OSTM outperforms ESTM by the average magnitude of 106 transactions
per second(throughput) for both lookup intensive and update intensive work load. HT-OSTM outperforms
RWSTM by 3% & 3.4% update intensive and lookup intensive workload respectively
Actions (login required)
 |
View Item |
Altmetric
Altmetric