| 1. |
- Gidenstam, Anders, 1977, et al.
(author)
-
Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting
- 2009
-
In: IEEE Transactions on Parallel and Distributed Systems. - : IEEE. - 1558-2183 .- 1045-9219. ; 20:8, s. 1173-1187
-
Journal article (peer-reviewed)abstract
- We present an efficient and practical lock-free method for semiautomatic (application-guided) memory reclamation based on reference counting, aimed for use with arbitrary lock-free dynamic data structures. The method guarantees the safety of local as well as global references, supports arbitrary memory reuse, uses atomic primitives that are available in modern computer systems, and provides an upper bound on the amount of memory waiting to be reclaimed. To the best of our knowledge, this is the first lock-free method that provides all of these properties. We provide analytical and experimental study of the method. The experiments conducted have shown that the method can also provide significant performance improvements for lock-free algorithms of dynamic data structures that require strong memory management.
|
|
| 2. |
- Sundell, Håkan, 1968, et al.
(author)
-
Brushing the Locks out of the Fur: A Lock-Free Work Stealing Library
- 2009
-
In: econd Swedish Workshop on Multi-Core Computing, (MCC '09).
-
Conference paper (peer-reviewed)abstract
- We present a lock-free version of the light-weight userleveltask management library called Wool, in an aim toshow that even extremely well tuned, in terms of synchronization,applications can benefit from lock-free programming.Explicit multi-threading is an efficient way to exploitthe offered parallelism of multi-core and multi-processorbased systems. However, it can sometimes be hard to expressthe inherited parallelism in programs using a limitednumber of long lived threads. Often it can be more straightforwardto dynamically create a large number of small tasksthat in turn automatically execute on the available threads.Wool is a promising and efficient library and frameworkthat allows the programmer to create user tasks in C witha very low overhead. The library automatically executestasks and balances the load evenly on a given number ofthreads by utilizing work stealing techniques. However, thesynchronization for stealing tasks is based on mutual exclusionwhich is known to limit parallelism and efficiency. Wehave designed and implemented a new lock-free algorithmfor synchronization of stealing tasks in Wool. Experimentsshow similar or significantly improved performance on a setof benchmarks executed on a multi-core platform.
|
|
| 3. |
- Sundell, Håkan, 1968, et al.
(author)
-
Lock-Free Deques and Doubly Linked Lists
- 2008
-
In: Journal of Parallel and Distributed Computing. - : Elsevier BV. - 1096-0848 .- 0743-7315. ; 68:7, s. 1008-1020
-
Journal article (peer-reviewed)abstract
- We present a practical lock-free shared data structure that efficiently implements the operations of a concurrent deque as well as a general doubly linked list. The implementation supports parallelism for disjoint accesses and uses atomic primitives which are available in modern computer systems. Previously known lock-free algorithms of doubly linked lists are either based on non-available atomic synchronization primitives, only implement a subset of the functionality, or are not designed for disjoint accesses. Our algorithm only requires single-word compare-and-swap atomic primitives, supports fully dynamic list sizes, and allows traversal also through deleted nodes and thus avoids unnecessary operation retries. We have performed an empirical study of our new algorithm on two different multiprocessor platforms. Results of the experiments performed under high contention show that the performance of our implementation scales linearly with increasing number of processors. Considering deque implementations and systems with low concurrency, the algorithm by Michael shows the best performance. However, as our algorithm is designed for disjoint accesses, it performs significantly better on systems with high concurrency and non-uniform memory architecture.
|
|
| 4. |
- Sundell, Håkan, 1968, et al.
(author)
-
NOBLE: non-blocking programming support via lock-free shared abstract data types
- 2009
-
In: SIGARCH Computer Architecture News. - : ACM, Association for Computing Machinery, Inc.. - 0163-5964 .- 1943-5851. ; 36:5, s. 80-87
-
Journal article (peer-reviewed)abstract
- An essential part of programming for multi-core and multi-processor includes ef cient and reliable means for sharing data. Lock-free data structures are known as very suitable for this purpose, although experienced to be very complex to design. In this paper, we present a software library of non-blocking abstract data types that have been designed to facilitate lock-free programming for non-experts. The system provides: i) ef cient implementations of the most commonly used data types in concurrent and sequential software design, ii) a lock-free memory management system, and iii) a run time-system. The library provides clear semantics that are at least as strong as those of corresponding lock-based implementations of the respective data types. Our software library can be used for facilitating lockfree programming; its design enables the programmer to: i) replace lock-based components of sequential or parallel code easily and ef ciently , ii) use well-tuned concurrent algorithms inside a software or hardware transactional system. In the paper we describe the design and functionality of the system. We also provide experimental results that show that the library can considerably improve the performance of software systems.
|
|
