SI2-SSE: TLDS: Transactional Lock-Free Data Structures

The University Of Central Florida Board Of Trustees, Orlando FL

Investigators

Abstract

Exploiting the parallelism in multiprocessor systems is a major challenge in computer science. Multicore programming demands a change in the way we design and use fundamental data structures. Non-blocking data structures allow un-constrained access to shared data; however, care must be taken so that data is not overwritten incorrectly. A main obstacle to the design and use of non-blocking data structures is the lack of a generic methodology for allowing efficient transactional and composable operations. This project, supported by the Office of Advanced Cyberinfrastructure, and the Division of Computing and Communication Foundations, will explore and define the fundamental techniques for the design and use of transactional multiprocessor algorithms. The software elements produced in this work will significantly improve the functionality and reuse of the existing concurrent containers and will accelerate the performance of multiprocessor applications beyond what is possible with current programming libraries. The programming elements created in this project will be disseminated through the open-source release of a software library. The project will also help contribute to a workforce trained in systems programming. To achieve the project's goals, the PI will explore solutions to overcome two key challenges for supporting high-performance data structure transactions: 1) how to efficiently buffer write operations so that their modifications are invisible to operations outside the transaction's scope, and 2) how to minimize the penalty of rollbacks when aborting partially executed transactions. A representative collection of six transactional lock-free containers will be created including: a linked-list, a set, a skiplist, a multi-dimensional list, a priority queue, and a dictionary. This work will substantially advance the knowledge and practice in multiprocessor software design. To the best of the PI's knowledge, lock-free transactional transformation is the first methodology that provides both lock-free progress and semantic conflict detection for data structure transactions. To achieve this, the PI will create new techniques for conflict detection and recovery in the execution of transactions. A node-based conflict detection scheme that does not rely on Software Transactional Memory nor require the use of an additional data structure will be introduced. A new and efficient conflict recovery strategy will be designed, based on the interpretation of the logical status of nodes instead of explicitly revoking executed operations in an aborted transaction. This research will introduce the first approach for the efficient execution of composable non- blocking transactions across multiple data structures. The software components and data structures engineered as part of this work will be significant research artifacts themselves.