In this paper, we study the question whether techniques employed, in a conventional system, by state-of-the-art concurrent algorithms to avoid contended hot spots are still efficient for recoverable computing in setti...
详细信息
ISBN:
(纸本)9783031606021;9783031606038
In this paper, we study the question whether techniques employed, in a conventional system, by state-of-the-art concurrent algorithms to avoid contended hot spots are still efficient for recoverable computing in settings with Non-Volatile Memory (nvm). We focus on concurrent FIFO queues that have two end-points, head and tail, which are highly contended. We present a persistent FIFO queue implementation that performs a pair of persistence instructions per operation (enqueue or dequeue). The algorithm achieves to perform these instructions on variables of low contention by employing Fetch&Increment and using the state-of-the-art queue implementation by Afek and Morrison (PPoPP'13). These result in performance that is up to 2x faster than state-of-the-art persistent FIFO queue implementations.
This paper presents a generic approach for deriving detectably recoverable implementations of many widely-used concurrent data structures. Such implementations are appealing for emerging systems featuring byte-address...
详细信息
ISBN:
(纸本)9781450392044
This paper presents a generic approach for deriving detectably recoverable implementations of many widely-used concurrent data structures. Such implementations are appealing for emerging systems featuring byte-addressable non-volatile main memory (nvmM), whose persistence allows to efficiently resurrect failed threads after crashes. Detectable recovery ensures that after a crash, every executed operation is able to recover and return a correct response, and that the state of the data structure is not corrupted. Our approach, called Tracking, amends descriptor objects used in existing lock-free helping schemes with additional fields that track an operation's progress towards completion and persists these fields in order to ensure detectable recovery. Tracking avoids full-fledged logging and tracks the progress of concurrent operations in a per-thread manner, thus reducing the cost of ensuring detectable recovery. We have applied Tracking to derive detectably recoverable implementations of a linked list, a binary search tree, and an exchanger. Our experimental analysis introduces a new way of analyzing the cost of persistence instructions, not by simply counting them but by separating them into categories based on the impact they have on the performance. The analysis reveals that understanding the actual persistence cost of an algorithm in machines with real nvmM, is more complicated than previously thought, and requires a thorough evaluation, since the impact of different persistence instructions on performance may greatly vary. We consider this analysis to be one of the major contributions of the paper.
The availability of Non-Volatile Main Memory (known as nvmM) enables the design of recoverable concurrent algorithms. We study the power of software combining in achieving recoverable synchronization and designing per...
详细信息
ISBN:
(纸本)9781450392044
The availability of Non-Volatile Main Memory (known as nvmM) enables the design of recoverable concurrent algorithms. We study the power of software combining in achieving recoverable synchronization and designing persistent data structures. Software combining is a general synchronization approach, which attempts to simulate the ideal world when executing synchronization requests (i.e., requests that must be executed in mutual exclusion). A single thread, called the combiner, executes all active requests, while the rest of the threads are waiting for the combiner to notify them that their requests have been applied. Software combining significantly decreases the synchronization cost and outperforms many other synchronization techniques in various cases. We identify three persistence principles, crucial for performance, that an algorithm's designer has to take into consideration when designing highly-efficient recoverable synchronization protocols or data structures. We illustrate how to make the appropriate design decisions in all stages of devising recoverable combining protocols to respect these principles. Specifically, we present two recoverable software combining protocols, satisfying different progress properties, that are many times faster and have much lower persistence cost than a large collection of existing persistent techniques for achieving scalable synchronization. We build fundamental recoverable data structures, such as stacks and queues, based on these protocols that outperform by far existing recoverable implementations of such data structures. We also provide the first recoverable implementation of a concurrent heap and present experiments to show that it has good performance when the size of the heap is not very large.
暂无评论