Sökning: id:"swepub:oai:research.chalmers.se:697af10d-c6a6-4529-9148-b5d9920ec395" >
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)
- ISBN 9781509028238
- 2016
- 2016
- Engelska.
-
Ingår i: 45th International Conference on Parallel Processing (ICPP), 2016. - 0190-3918. - 9781509028238 ; 2016 september, s. 360-369
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://research.cha...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Helping is a widely used technique 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 operation step 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. We design the algorithms without using any language/platformspecific mechanism. Specifically, we use neither bit-stealing froma pointer nor runtime type introspection of objects. Thus, our algorithms are language-portable. Further, to optimize the amortized number of steps per operation, if a CAS execution tomodify 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 efficiency 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 optimizedones and in many cases yield 10%-50% higher throughput.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Nyckelord
- Help
- Language-portable
- Concurrent data structure
- Lock-free
- Linearizability
- Binary search tree
- Help-optimal
- Linked-list
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas