Lock-Free Transactional Transformation For Linked Data Structures

Keywords

Lock-free; Transactional boosting; Transactional data structure; Transactional memory

Abstract

Nonblocking data structures allow scalable and thread-safe access to shared data. They provide individual operations that appear to execute atomically. However, it is often desirable to execute multiple operations atomically in a transactional manner. Previous solutions, such as Software Transactional Memory (STM) and transactional boosting, manage transaction synchronization separately from the underlying data structure's thread synchronization. Although this reduces programming effort, it leads to overhead associated with additional synchronization and the need to rollback aborted transactions. In this work, we present a newmethodology for transforming high-performance lock-free linked data structures into high-performance lock-free transactional linked data structures without revamping the data structures' original synchronization design. Our approach leverages the semantic knowledge of the data structure to eliminate the overhead of false conflicts and rollbacks. We encapsulate all operations, operands, and transaction status in a transaction descriptor, which is shared among the nodes accessed by the same transaction.We coordinate threads to help finish the remaining operations of delayed transactions based on their transaction descriptors. When a transaction fails,we recover the correct abstract state by reversely interpreting the logical status of a node.We also present an obstruction-free version of our algorithm that can be applied to dynamic execution scenarios and an example of our approach applied to a hash map. In our experimental evaluation using transactions with randomly generated operations, our lock-free transactional data structures outperform the transactional boosted ones by 70% on average. They also outperform the alternative STM-based approaches by a factor of 2 to 13 across all scenarios. More importantly, we achieve 4,700 to 915,000 times fewer spurious aborts than the alternatives.

Publication Date

9-1-2018

Publication Title

ACM Transactions on Parallel Computing

Volume

5

Issue

1

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1145/3209690

Socpus ID

85056310796 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85056310796

This document is currently not available here.

Share

COinS