Canonical abstraction is a static analysis technique that represents states as 3-valued logical structures, and is able to construct finite representations of systems with infinite statespaces for verification. The gr...
详细信息
ISBN:
(纸本)9781921770302
Canonical abstraction is a static analysis technique that represents states as 3-valued logical structures, and is able to construct finite representations of systems with infinite statespaces for verification. The granularity of the abstraction can be altered by the definition of instrumentation predicates, which derive their meaning from other predicates. We introduce shape predicates for preserving certain structures of the state during abstraction. We show that shape predicates allow linearizability to be verified for concurrent data structures using canonical abstraction alone, and use the approach to verify a stack and two queue algorithms. This contrasts with previous efforts to verify linearizability with canonical abstraction, which have had to employ other techniques as well.
We present the first lock-free implementation of an extensible hash table running on current architectures. It provides concurrent insert, delete, and search operations with an expected O(1) cost. It consists of very ...
详细信息
ISBN:
(纸本)9781581137088
We present the first lock-free implementation of an extensible hash table running on current architectures. It provides concurrent insert, delete, and search operations with an expected O(1) cost. It consists of very simple code, easily implementable using only load, store, and compare-and-swap operations. The new mathematical structure at the core of our algorithm is recursive split-ordering, a way of ordering elements in a linked list so that they can be repeatedly "split" using a single compare-and-swap operation. Empirical tests conducted on a large shared memory multiprocessor show that even in non-multiprogrammed environments, the new algorithm significantly outperforms the most efficient known lock-based algorithm at all concurrency levels, exhibiting up to four times higher throughput at peak load. The incremental nature of our algorithm makes it well suited for real-time applications, as it offers predictable performance without unexpected breaks for resizing.
This paper presents a fast concurrent binary search tree algorithm. To achieve high performance under contention, the algorithm divides update operations within an eager abstract access that returns rapidly for effici...
详细信息
This paper presents a fast concurrent binary search tree algorithm. To achieve high performance under contention, the algorithm divides update operations within an eager abstract access that returns rapidly for efficiency reason and a lazy structural adaptation that may be postponed to diminish contention. To achieve high performance under read-only workloads, it features a rebalancing mechanism and guarantees that read-only operations searching for an element execute lock-free. We evaluate the contention-friendly binary search tree using Synchrobench, a benchmark suite to compare synchronization techniques. More specifically, we compare its performance against five state-of-the-art binary search trees that use locks, transactions or compare-and-swap for synchronization on Intel Xeon, AMD Opteron and Oracle SPARC, Our results show that our tree is more efficient than other trees and double the throughput of existing lock-based trees under high contention.
暂无评论