| 1. |
- Gidenstam, Anders, et al.
(författare)
-
Cache-Aware Lock-Free Queues for Multiple Producers/Consumers and Weak Memory Consistency
- 2010
-
Ingår i: Proceedings of the 14th International Conference on Principles of Distributed Systems (OPODIS) 2010. - Berlin, Heidelberg : Springer. - 9783642176524 - 3642176526 ; 6490, s. 302-317
-
Konferensbidrag (refereegranskat)abstract
- A lock-free FIFO queue data structure is presented in this paper. The algorithm supports multiple producers and multiple consumers and weak memory models. It has been designed to be cache-aware and work directly on weak memory models. It utilizes the cache behavior in concert with lazy updates of shared data, and a dynamic lock-free memory management scheme to decrease unnecessary synchronization and increase performance. Experiments on an 8-way multi-core platform show significantly better performance for the new algorithm compared to previous fast lock-free algorithms.
|
|
| 2. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting
- 2009
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : IEEE. - 1558-2183 .- 1045-9219. ; 20:8, s. 1173-1187
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 3. |
- Nguyen, Dang Nhan, 1983, et al.
(författare)
-
Brief Announcement: ParMarkSplit: A Parallel Mark-Split Garbage Collector Based on a Lock-Free Skip-List
- 2013
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - : Springer. - 1611-3349 .- 0302-9743. - 9783642415265 ; 8205, s. 557-558
-
Konferensbidrag (refereegranskat)abstract
- This brief announcement provides a high level overview of a parallel mark-split garbage collector. Our parallel design introduces and makes use of an efficient concurrency control mechanism based on a lock-free skip-list design for handling the list of free memory intervals. We have implemented the parallel mark-split garbage collector in OpenJDK HotSpot as a parallel and concurrent garbage collector for the old generation. We experimentally evaluate the collector and compare it with the default concurrent mark-sweep garbage collector in OpenJDK HotSpot, using the DaCapo benchmarks.
|
|
| 4. |
- Nguyen, Dang Nhan, 1983, et al.
(författare)
-
CoMarkSplit: A Concurrent Mark-Split Garbage Collector
- 2012
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Garbage collectors are important components of many modern programming languages and runtime systems. Mark-split is a garbage collection algorithm that combines advantages of both mark-sweep and copying collection algorithms. With the switch to multi-core and many-core microprocessors, parallelism becomes a core issue in the design of any algorithm or software system. In this paper, we present a concurrent design of the mark-split garbage collector. Our concurrent design algorithmically introduces and makes use of an efficient concurrency control mechanism for handling the list of free intervals. This mechanism is based on a lock-free skip-list design and supports an extended set of operations that allows, atomically and in a lock-free manner, to search and remove and also to insert two intervals at the same time. We have implemented the concurrent mark-split garbage collector in OpenJDK HotSpot as a garbage collector for the tenured generation. We present experimental evaluation of our concurrent collector and compare it with the default concurrent marks-sweep garbage collector present in OpenJDK HotSpot, using the Dacapo benchmarks. The evaluation shows that our concurrent mark-split performs better than the concurrent mark-sweep garbage collector in some applications.
|
|
| 5. |
- Nguyen, Dang Nhan, 1983, et al.
(författare)
-
ParMarkSplit : A Parallel Mark-Split Garbage Collector Based on a Lock-Free Skip-List
- 2014
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer. - 1611-3349 .- 0302-9743. - 9783319144719 - 9783319144726 ; 8878, s. 372-387
-
Konferensbidrag (refereegranskat)abstract
- Mark-split is a garbage collection algorithm that combines advantages of both the mark-sweep and the copying collection algorithms. In this paper, we present a parallel mark-split garbage collector (GC). Our parallel design introduces and makes use of an efficient concurrency control mechanism for handling the list of free memory intervals. This mechanism is based on a lock-free skip-list design which supports an extended set of operations. Beside basic operations, it can perform a composite one that can search and remove and also insert two elements atomically. We have implemented the parallel mark-split GC in OpenJDK’s HotSpot virtual machine. We experimentally evaluate our collector and compare it with the default concurrent mark-sweep GC in HotSpot, using the DaCapo benchmarks, on two contemporary multiprocessor systems; one has 12 Intel Nehalem cores with HyperThreading and the other has 48 AMD Bulldozer cores. The evaluation shows that our parallel mark-split keeps the characteristics of the sequential mark-split, that it performs better than the concurrent mark-sweep in applications that have low live/garbage ratio, and have live objects locating contiguously, therefore being marked consecutively. Our parallel mark-split performs significantly better than a trivial parallelization based on locks in terms of both collection time and scalability.
|
|
| 6. |
- Sundell, Håkan, 1968, et al.
(författare)
-
A Lock-Free Algorithm for Concurrent Bags
- 2011
-
Ingår i: 23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'11.San Jose, 4-6 June 2011. - New York, NY, USA : ACM. - 9781450307437 ; , s. 335-344
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- A lock-free bag data structure supporting unordered buffering is presented in this paper. The algorithmsupports multiple producers and multiple consumers, as well as dynamic collection sizes. To handle concurrencyefficiently, the algorithm was designed to thrive for disjoint-access-parallelism for the supportedsemantics. Therefore, the algorithm exploits a distributed design combined with novel techniques for handlingconcurrent modifications of linked lists using double marks, detection of total emptiness, and efficientmemory management. Experiments on a 24-way multi-core platform show significantly better performancefor the new algorithm compared to previous algorithms of relevance.Keywords: concurrent; data structure; non-blocking; shared memory;
|
|
| 7. |
- Sundell, Håkan, 1968, et al.
(författare)
-
Brushing the Locks out of the Fur: A Lock-Free Work Stealing Library
- 2009
-
Ingår i: econd Swedish Workshop on Multi-Core Computing, (MCC '09).
-
Konferensbidrag (refereegranskat)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.
|
|
| 8. |
- Sundell, Håkan, 1968, et al.
(författare)
-
Lock-Free Deques and Doubly Linked Lists
- 2008
-
Ingår i: Journal of Parallel and Distributed Computing. - : Elsevier BV. - 1096-0848 .- 0743-7315. ; 68:7, s. 1008-1020
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 9. |
- Sundell, Håkan, 1968, et al.
(författare)
-
NOBLE: non-blocking programming support via lock-free shared abstract data types
- 2009
-
Ingår i: SIGARCH Computer Architecture News. - : ACM, Association for Computing Machinery, Inc.. - 0163-5964 .- 1943-5851. ; 36:5, s. 80-87
-
Tidskriftsartikel (refereegranskat)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.
|
|
