The field of computer science is ever evolving. Not long ago, software developers were able to get "free" performance upgrades with every bit of advancement in CPU architectures. Frequency boost, cache capacity increase, and more sophisticated pipeline all brought significant performance improvements in sequential execution. Now computing has hit the power wall and the performance of a single core has been pushed past the point of diminishing returns. The hardware design begins to shift towards massive parallelism on both chip level. Exploiting thread level parallelism is thus essential for software developers. C++ provides the capability to operate on powerful hardware synchronization primitives such as compare_and_swap, which is indispensable for building concurrent libraries to facilitate the development of high-performance parallel applications.
With the growing availability of concurrent libraries such Boost.Lockfree, Intel TBB, and LibCDS, more and more programmers embrace the concept of lock-free programming. Lock-free data structures provides scalable thread-safe concurrent accesses and guarantee that at any moment at least one thread will make progress. Compared with traditional lock-based approaches, lock-free algorithms utilize fine-grained synchronizations and tolerate thread faults. However, none of the existing lock-free data structures supports transactions yet, which require that a sequence of method calls on the data structures appears to complete in an atomic step and in isolation with regards to other ongoing transactions. Because of this, the users of lock-free libraries who need transaction executions often are forced to fall back to coarse-grained locking which has a negative impact on performance and annihilates the non-blocking progress guarantee provided by the libraries. We propose a holistic approach for developing future non-blocking transactional data structures — an open source library of transactional data structures based on existing non-blocking data structures.
This library will be built on three of the presenters' research works: 1) multi-resource lock (MRLock), which is a scalable lock manager with efficient FIFO conflict revolve scheme; 2) lock-free transactional transformation (LFTT), which is a methodology for transforming high-performance lock-free base data structures into high-performance lock-free transactional data structures; and 3) multi-dimensional linked list (MDList), which is a novel logarithmic search data structure optimized for concurrent accesses.
In the session, we will discuss two strategies for implementing scalable transactional data structures using both locks and lock-free synchronizations. The locking strategy employs MRLock, which is a novel shared-memory resource allocation lock for multi-core processors. It uses a lock-free FIFO queue to manage locking requests in batches, which minimizes memory contention among threads. It is fast and designed as a drop-in replacement for the two-phase locking methods in C++11 and Boost library (std::lock() and boost::lock()). When combined with existing lock-based transaction synchronization techniques such as semantic locking and transaction boosting, it can be used by programmers who prefer lock-based code to implement high-performance transactional data structures on familiar grounds. The lock-free strategy is based on lock-free transactional transformation (LFTT), which uses transaction descriptor object to announce the transaction globally so that delayed threads can be helped. It is applicable to linked data structures such as linked lists and skip lists. The logical status of any node in the data structure depends on the status of the transaction descriptor that was embedded in it. Conflict transactions do not need to revert their operations as required in some of the existing methodologies. We will demonstrate the application of this strategy to existing lock-free lists and skip lists.
We will also introduce a lock-free logarithmic search data structure based on multi-dimensional linked list. This brand new data structure is designed from ground up to achieve full potential for concurrent accesses. It has a distributed memory layout which alleviates contention. Write operations modify at most two nodes so interference among operations are brought down to a minimum. This data structure implements the collection/dictionary abstract data type, which is ubiquitous in modern applications. When combined with the above mentioned transactional strategies, this work could greatly benefit application developers who deal with data intensive scenarios such as in memory databases.
Preliminary version of source code can be accessed from
https://ucf-cs.github.io/tlds/. The research work mentioned in this presentation can be accessed from
http://cse.eecs.ucf.edu/bios/delizhang.html.
