| 1. |
- Atalar, Aras, 1985, et al.
(författare)
-
Analyzing the Performance of Lock-Free Data Structures: A Conflict-Based Model
- 2015
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783662486535 ; 9363, s. 341-355
-
Konferensbidrag (refereegranskat)abstract
- This paper considers the modeling and the analysis of the performance of lock-free concurrent data structures that can be represented as linear combinations of fixed size retry loops. Our main contribution is a new way of modeling and analyzing a general class of lock-free algorithms, achieving predictions of throughput that are close to what we observe in practice. We emphasize two kinds of conflicts that shape the performance: (i) hardware conflicts, due to concurrent calls to atomic primitives; (ii) logical conflicts, caused by concurrent operations on the shared data structure. We propose also a common framework that enables a fair comparison between lock-free implementations by covering the whole contention domain, and comes with a method for calculating a good back-off strategy. Our experimental results, based on a set of widely used concurrent data structures and on abstract lock-free designs, show that our analysis follows closely the actual code behavior.(1)
|
|
| 2. |
- Atalar, Aras, 1985, et al.
(författare)
-
Lock-Free Search Data Structures: Throughput Modeling with Poisson Processes
- 2019
-
Ingår i: Leibniz International Proceedings in Informatics, LIPIcs. - 1868-8969. ; 125
-
Konferensbidrag (refereegranskat)abstract
- This paper considers the modeling and the analysis of the performance of lock-free concurrent search data structures. Our analysis considers such lock-free data structures that are utilized through a sequence of operations which are generated with a memoryless and stationary access pattern. Our main contribution is a new way of analyzing lock-free concurrent search data structures: our execution model matches with the behavior that we observe in practice and achieves good throughput predictions. Search data structures are formed of basic blocks, usually referred to as nodes, which can be accessed by two kinds of events, characterized by their latencies; (i) CAS events originated as a result of modifications of the search data structure (ii) Read events that occur during traversals. An operation triggers a set of events, and the running time of an operation is computed as the sum of the latencies of these events. We identify the factors that impact the latency of such events on a multi-core shared memory system. The main challenge (though not the only one) is that the latency of each event mainly depends on the state of the caches at the time when it is triggered, and the state of caches is changing due to events that are triggered by the operations of any thread in the system. Accordingly, the latency of an event is determined by the ordering of the events on the timeline. Search data structures are usually designed to accommodate a large number of nodes, which makes the occurrence of an event on a given node rare at any given time. In this context, we model the events on each node as Poisson processes from which we can extract the frequency and probabilistic ordering of events that are used to estimate the expected latency of an operation, and in turn the throughput. We have validated our analysis on several fundamental lock-free search data structures such as linked lists, hash tables, skip lists and binary trees.
|
|
| 3. |
- Atalar, Aras, 1985, et al.
(författare)
-
Modeling and Analyzing the Performance of Lock-Free Data Structures
- 2014
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- This paper considers the modeling and the analysis of the performance of lock-free concurrent datastructures. Lock-free designs employ an optimistic conflict control approach, allowing several processesto access the shared data object at the same time. The operations on these data structures are typicallydesigned as compositions of retry loops.Our main contribution is a new way of modeling and analyzing a general class of lock-free algorithms,achieving predictions of throughput that are close to what we observe in practice. In our model weintroduce two key metrics that shape the performance of lock-free algorithms: (i) expansion in executiontime of a retry due to memory congestion and (ii) number of wasted retries. We show how to computethese two metrics, and how to combine them, to calculate the throughput of an arguably large class oflock-free algorithms. Our analysis also captures the throughput performance of a lock-free algorithm whenexecuted as part of a larger parallel application. This part of our analysis leads to an analytical methodfor calculating a good back-off strategy to finely tune the performance of a lock-free application. Ourexperimental results, based on a set of widely used concurrent data structures and on abstract lock-freedesigns, show that our analysis follows closely the actual code behavior.To the best of our knowledge, this is the first attempt to make ends meet between theoretical boundson performance and actual measured throughput.
|
|
| 4. |
- Atalar, Aras, 1985, et al.
(författare)
-
Modeling Energy Consumption of Lock-Free Queue Implementations
- 2015
-
Ingår i: 29th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015, Hyderabad, India, 25-29 May. - : IEEE Computer Society. - 1530-2075. - 9781479986484 ; , s. 229-238
-
Konferensbidrag (refereegranskat)abstract
- This paper considers the problem of modeling the energy behavior of lock-free concurrent queue data structures. Our main contribution is a way to model the energy behavior of lock-free queue implementations and parallel applications that use them. Focusing on steady state behavior we decompose energy behavior into throughput and power dissipation which can be modeled separately and later recombined into several useful metrics, such as energy per operation. Based on our models, instantiated from synthetic benchmark data, and using only a small amount of additional application specific information, energy and throughput predictions can be made for parallel applications that use the respective data structure implementation. To model throughput we propose a generic model for lock-free queue throughput behavior, based on a combination of the dequeuers' throughput and enqueuers' throughput. To model power dissipation we commonly split the contributions from the various computer components into static, activation and dynamic parts, where only the dynamic part depends on the actual instructions being executed. To instantiate the models a synthetic benchmark explores each queue implementation over the dimensions of processor frequency and number of threads. Finally, we show how to make predictions of application throughput and power dissipation for a parallel application using a lock-free queue requiring only a limited amount of information about the application work done between queue operations. Our case study on a Mandelbrot application shows convincing prediction results.
|
|
| 5. |
- Aupy, G., et al.
(författare)
-
Energy-aware algorithms for task graph scheduling, replica placement and checkpoint strategies
- 2015
-
Ingår i: Handbook on Data Centers. - New York, NY : Springer New York. - 9781493920921 ; , s. 37-80
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- The energy consumption of computational platforms has recently become a critical problem, both for economic and environmental reasons. To reduce energy consumption, processors can run at different speeds. Faster speeds allow for a faster execution, but they also lead to a much higher (superlinear) power consumption. Energy-aware scheduling aims at minimizing the energy consumed during the execution of the target application, both for computations and for communications. The price to pay for a lower energy consumption usually is a much larger execution time, so the energy-aware approach makes better sense when coupled with some prescribed performance bound. In other words, we have a bi-criteria optimization problem, with one objective being energy minimization, and the other being performance-related.
|
|
| 6. |
- Papadopoulos, L., et al.
(författare)
-
Performance and power consumption evaluation of concurrent queue implementations in embedded systems
- 2015
-
Ingår i: Computer Science - Research and Development. - : Springer Science and Business Media LLC. - 1865-2034 .- 1865-2042. ; 30:2, s. 165-175
-
Tidskriftsartikel (refereegranskat)abstract
- Embedded and high performance computing (HPC) systems face many common challenges. One of them is the synchronization of the memory accesses in shared data. Concurrent queues have been extensively studied in the HPC domain and they are used in a wide variety of HPC applications. In this work, we evaluate a set of concurrent queue implementations in an embedded platform, in terms of execution time and power consumption. Our results show that by taking advantage of the embedded platform specifications, we achieve up to 28.2 % lower execution time and 6.8 % less power dissipation in comparison with the conventional lock-based queue implementation. We show that HPC applications utilizing concurrent queues can be efficiently implemented in embedded systems and that synchronization algorithms from the HPC domain can lead to optimal resource utilization of embedded platforms.
|
|
