| 1. |
- Klaftenegger, David, et al.
(författare)
-
Brief announcement : queue delegation locking
- 2014
-
Ingår i: Proc. 26th ACM Symposium on Parallelism in Algorithms and Architectures. - New York : ACM Press. - 9781450328210 ; , s. 70-72
-
Konferensbidrag (refereegranskat)
|
|
| 2. |
|
|
| 3. |
- Klaftenegger, David, et al.
(författare)
-
On the scalability of the Erlang term storage
- 2013
-
Ingår i: Proc. 12th ACM SIGPLAN Workshop on Erlang. - New York : ACM Press. - 9781450323857 ; , s. 15-26
-
Konferensbidrag (refereegranskat)
|
|
| 4. |
- Klaftenegger, David, et al.
(författare)
-
Queue Delegation Locking
- 2018
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : IEEE COMPUTER SOC. - 1045-9219 .- 1558-2183. ; 29:3, s. 687-704
-
Tidskriftsartikel (refereegranskat)abstract
- The scalability of parallel programs is often bounded by the performance of synchronization mechanisms used to protect critical sections. The performance of these mechanisms is in turn determined by their sequential execution time, efficient use of hardware, and ability to avoid waiting. In this article, we describe queue delegation (QD) locking, a family of locks that both delegate critical sections and enable detaching execution. Threads delegate work to the thread currently holding the lock and are able to detach, i.e., immediately continue their execution until they need a result from a previously delegated critical section. We show how to use queue delegation to build synchronization algorithms with lower overhead and higher throughput than existing algorithms, even when critical sections need to communicate results back immediately. Experiments when using up to 64 threads to access a shared priority queue show that QD locking provides 10 times higher throughput than Pthreads mutex locks and outperforms leading delegation algorithms. Also, when mixing parallel reads with delegated write operations, QD locking outperforms competing algorithms with an advantage ranging from 9.5 up to 207 percent increased throughput. Last but not least, continuing execution instead of waiting for the execution of critical sections leads to increased parallelism and better scalability. As we will see, queue delegation locking uses simple building blocks whose overhead is low even in uncontended use. All these make the technique useful in a wide variety of applications.
|
|
| 5. |
- Sagonas, Konstantinos, et al.
(författare)
-
A contention adapting approach to concurrent ordered sets
- 2018
-
Ingår i: Journal of Parallel and Distributed Computing. - : ACADEMIC PRESS INC ELSEVIER SCIENCE. - 0743-7315 .- 1096-0848. ; 115, s. 1-19
-
Tidskriftsartikel (refereegranskat)abstract
- With multicores being ubiquitous, concurrent data structures are increasingly important. This article proposes a novel approach to concurrent data structure design where the data structure dynamically adapts its synchronization granularity based on the detected contention and the amount of data that operations are accessing. This approach not only has the potential to reduce overheads associated with synchronization in uncontended scenarios, but can also be beneficial when the amount of data that operations are accessing atomically is unknown. Using this adaptive approach we create a contention adapting search tree (CA tree) that can be used to implement concurrent ordered sets and maps with support for range queries and bulk operations. We provide detailed proof sketches for the linearizability as well as deadlock and livelock freedom of CA tree operations. We experimentally compare CA trees to state-of-the-art concurrent data structures and show that CA trees beat the best of the data structures that we compare against by over 50% in scenarios that contain basic set operations and range queries, outperform them by more than 1200% in scenarios that also contain range updates, and offer performance and scalability that is better than many of them on workloads that only contain basic set operations.
|
|
| 6. |
- Sagonas, Konstantinos, et al.
(författare)
-
Contention adapting search trees
- 2015
-
Ingår i: Proc. 14th International Symposium on Parallel and Distributed Computing. - : IEEE conference proceedings. - 9781467371476 ; , s. 215-224
-
Konferensbidrag (refereegranskat)abstract
- With multicores being ubiquitous, concurrent data structures are becoming increasingly important. This paper proposes a novel approach to concurrent data structure design where the data structure collects statistics about contention and adapts dynamically according to this statistics. We use this approach to create a contention adapting binary search tree (CA tree) that can be used to implement concurrent ordered sets and maps. Our experimental evaluation shows that CA trees scale similar to recently proposed algorithms on a big multicore machine on various scenarios with a larger set size, and outperform the same data structures in more contended scenarios and in sequential performance. We also show that CA trees are well suited for optimization with hardware lock elision. In short, we propose a practically useful and easy to implement and show correct concurrent search tree that naturally adapts to the level of contention.
|
|
| 7. |
|
|
| 8. |
|
|
| 9. |
- Winblad, Kjell, 1985-
(författare)
-
Dynamic Adaptations of Synchronization Granularity in Concurrent Data Structures
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The multicore revolution means that programmers have many cores at their disposal in everything from phones to large server systems. Concurrent data structures are needed to make good use of all the cores. Designing a concurrent data structure that performs well across many different scenarios is a difficult task. The reason for this is that the best synchronization granularity and data organization vary between scenarios. Furthermore, the number of parallel threads and the types of operations that are accessing a data structure may even change over time.This dissertation tackles the problem mentioned above by proposing concurrent data structures that dynamically adapt their synchronization granularity and organization based on usage statistics collected at run-time. Two of these data structures (one lock-free and one lock-based) implement concurrent sets with support for range queries and other multi-item operations. These data structures adapt their synchronization granularity based on detected contention and the number of items that are involved in multi-item operations such as range queries. This dissertation also proposes a concurrent priority queue that dynamically changes its precision based on detected contention.Experimental evaluations of the proposed data structures indicate that they outperform non-adaptive data structures over a wide range of scenarios because they adapt their synchronization based on usage statistics. Possible practical consequences of the work described in this dissertation are faster parallel programs and a reduced need to manually tune the synchronization granularities of concurrent data structures.
|
|
| 10. |
- Winblad, Kjell, et al.
(författare)
-
Lock-free Contention Adapting Search Trees
- 2018
-
Ingår i: The 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018. - New York, NY, USA : ACM. - 9781450357999
-
Konferensbidrag (refereegranskat)
|
|
