Sökning: id:"swepub:oai:research.chalmers.se:8ada3acd-fdde-45cb-8771-11ecaf8dd0b4" >
Help-optimal and La...
Help-optimal and Language-portable Lock-free Concurrent Data Structures
-
- Chatterjee, Bapi, 1982 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
- Walulya, Ivan, 1985 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
- Tsigas, Philippas, 1967 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
(creator_code:org_t)
- 2016
- Engelska.
- Relaterad länk:
-
http://publications.... (primary) (free)
-
visa fler...
-
https://research.cha...
-
visa färre...
Abstract
Ämnesord
Stäng
- Helping is the most common mechanism to guarantee lock-freedom in many concurrent data structures. An optimized helping strategy improves the overall performance of a lock-free algorithm. In this paper, we propose help-optimality, which essentially implies that no operationstep is accounted for exclusive helping in the lock-free synchronization of concurrent operations. To describe the concept, we revisit the designs of a lock-free linked-list and a lock-free binary search tree and present improved algorithms. Our algorithms employ atomic single-word compare-and-swap (CAS) primitives and are linearizable.Additionally, we do not use a language/platform speci?c mechanism to modulate helping, speci?cally, we use neither bit-stealing from a pointer nor runtime type introspection of objects, making the algorithms language-portable. Further, to optimize the amortized numberof steps per operation, if a CAS execution to modify a shared pointer fails, we obtain a fresh set of thread-local variables without restarting an operation from scratch.We use several micro-benchmarks in both C/C++ and Java to validate the e?ciency of our algorithms against existing state-of-the-art. The experiments show that the algorithms are scalable. Our implementations perform on a par with highly optimized ones and in manycases yield 10%-50% higher throughput.
Ämnesord
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Datorsystem (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Computer Systems (hsv//eng)
Nyckelord
- language-portable
- concurrent data structure
- lock-free
- linearizability
- help
- binary search tree
- linked-list
Publikations- och innehållstyp
- rap (ämneskategori)
- vet (ämneskategori)