Back to Search
Start Over
Fast Wait-Free Construction for Pool-Like Objects with Weakened Internal Order: Stacks as an Example
- Source :
- IEEE Transactions on Parallel and Distributed Systems. 30:1596-1612
- Publication Year :
- 2019
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2019.
-
Abstract
- This paper focuses on a large class of concurrent data structures that we call pool-like objects (e.g., stack, double-ended queue, and queue). Performance and progress guarantee are two important characteristics for concurrent data structures. In the aspect of performance, weakening the internal order in a pool-like object is an effective technique to reduce the synchronization cost among threads accessing the object, but no objects with weakened internal order provide a progress guarantee as strong as wait-freedom. Meanwhile, wait-free algorithms tend to be inefficient, which is mainly attributed to the helping mechanisms. Based on the philosophy of existing helping mechanisms, a wait-free pool-like object with weakened internal order would suffer from unnecessary process of getting the latest object state and synchronization. This paper takes a state-of-the-art implementation of stacks with weakened internal order as an example, and transforms it into a highly-efficient wait-free stack named WF-TS-Stack. The transformation method includes a helping mechanism with state reuse and a relaxed removal scheme. In addition, we use a simple and effective scheme to further improve the performance of WF-TS-Stack in Non-Uniform Memory Access (NUMA) architectures. Our evaluation with representative benchmarks shows that WF-TS-Stack outperforms its original building blocks by up to 1.45× at maximum concurrency. We also discuss how to yield an efficient double-ended queue (deque) variant of WF-TS-Stack, because deque is a more generalized pool-like object.
- Subjects :
- 020203 distributed computing
Concurrent data structure
Computer science
Concurrency
Distributed computing
Process (computing)
02 engineering and technology
Thread (computing)
Object (computer science)
Data structure
Computational Theory and Mathematics
Stack (abstract data type)
Hardware and Architecture
Signal Processing
Synchronization (computer science)
0202 electrical engineering, electronic engineering, information engineering
Concurrent computing
Queue
Subjects
Details
- ISSN :
- 21619883 and 10459219
- Volume :
- 30
- Database :
- OpenAIRE
- Journal :
- IEEE Transactions on Parallel and Distributed Systems
- Accession number :
- edsair.doi...........3c472c347d22ff421086a40c27782685