| 1. |
- Almgren, Magnus, 1972, et al.
(författare)
-
Mapping Systems Security Research at Chalmers
- 2011
-
Ingår i: First SysSec Workshop (SysSec 2011). - 9780769545301 ; , s. 67-70
-
Konferensbidrag (refereegranskat)abstract
- The department of Computer Science and Engineering at Chalmers University has a long tradition of research in systems security, including security metrics, attack detection, and mitigation. We focus on security issues arising in four specific environments: (1) backbone links, (2) sensor networks, (3) the connected car, and (4) the smart grid. In this short summary we describe recent results as well as open research questions we are exploring.
|
|
| 2. |
- Assarsson, Ulf, 1972, et al.
(författare)
-
Image-Space Dynamic Transparency for Improved Object Discovery in 3D Environments
- 2006
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We present an image-space algorithm for dynamic transparency with the purpose of supporting object discovery and access in information-rich 3D visualization environments. The algorithm is based on multiple rendering passes and detects instances of object occlusion in the image-space using the fragment shader capabilities of modern programmable graphics hardware, creating alpha maps of opacity gradients around the occluded objects. In essence, the effect is somewhat similar to X-ray vision of a superhero. We have implemented a prototype version of our algorithm with real-time rendering performance using a number of optimizations and speedups on current graphics hardware. To evaluate its use, we have also implemented three different example applications portraying different scenarios, including abstract visualization, virtual walkthrough, and gaming. Preliminary results from an empirical user study comparing our technique to standard viewpoint controls indicate that our technique is superior in regards to object discovery efficiency. These results hold over both completion times as well as correctness of a visual search task.
|
|
| 3. |
- 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)
|
|
| 4. |
- Atalar, Aras, 1985, et al.
(författare)
-
How lock-free data structures perform in dynamic environments: Models and analyses
- 2017
-
Ingår i: Leibniz International Proceedings in Informatics, LIPIcs. - 1868-8969. - 9783959770316 ; 70, s. 23.1-23.17
-
Konferensbidrag (refereegranskat)abstract
- © Aras Atalar, Paul Renaud-Goud, and Philippas Tsigas.In this paper we present two analytical frameworks for calculating the performance of lock-free data structures. Lock-free data structures are based on retry loops and are called by application-specific routines. In contrast to previous work, we consider in this paper lock-free data structures in dynamic environments. The size of each of the retry loops, and the size of the application routines invoked in between, are not constant but may change dynamically. The new frameworks follow two different approaches. The first framework, the simplest one, is based on queuing theory. It introduces an average-based approach that facilitates a more coarse-grained analysis, with the benefit of being ignorant of size distributions. Because of this independence from the distribution nature it covers a set of complicated designs. The second approach, instantiated with an exponential distribution for the size of the application routines, uses Markov chains, and is tighter because it constructs stochastically the execution, step by step. Both frameworks provide a performance estimate which is close to what we observe in practice. We have validated our analysis on (i) several fundamental lock-free data structures such as stacks, queues, deques and counters, some of them employing helping mechanisms, and (ii) synthetic tests covering a wide range of possible lock-free designs. We show the applicability of our results by introducing new back-off mechanisms, tested in application contexts, and by designing an efficient memory management scheme that typical lock-free algorithms can utilize.
|
|
| 5. |
- 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.
|
|
| 6. |
- 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.
|
|
| 7. |
- 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.
|
|
| 8. |
- Bader, D.A., et al.
(författare)
-
ACM Journal on Experimental Algorithmics Special Issue on Multicore Algorithms
- 2012
-
Ingår i: Journal of Experimental Algorithmics. - : Association for Computing Machinery (ACM). - 1084-6654. ; 17, s. 4.1-4.1
-
Tidskriftsartikel (refereegranskat)abstract
- The recent switch to multicore processors brought a dramatic change that affects a large spectrum of systems from embedded and general-purpose to high-end computing systems. Parallelism is forcing major changes in software development. The aim of this issue is to discuss the challenges that parallelism brings to the design and implementation of algorithms and data structures. This special issue arose out of discussions held at the Dagstuhl Seminar 10261, on Algorithm Engineering held June 27–July 2, 2010, in Germany, and organized by Giuseppe F. Italiano (Università di Roma “Tor Vergata,” Italy), David S. Johnson (AT & T Research, Florham Park, NJ), Petra Mutzel (Technical University of Dortmund, Germany), and Peter Sanders (Karlsruhe Institute of Technology, Germany). We conceived a special issue of the ACM Journal on Experimental Algorithmics with a call for original submissions that address implementation and performance issues of multicore algorithms and data structures for any multicore processor, for example, Intel Nehalem, Single-Chip Cloud, NVIDIA and AMD GPUs. An experimental study typically includes an implementation, a series of experiments designed to understand the behavior of the algorithm(s) under study, and a critical discussion of the experiments and their results. We welcomed experimental submissions and encouraged authors to include test data from previously published studies to enable critical comparisons. A total of nine submissions were received, and four were accepted for this special issue. All manuscripts had at least three extensive reviews, and most received five to six reviews. We thank all of the authors for their submissions, and especially the 16 reviewers of these manuscripts.
|
|
| 9. |
- Benkner, Siegfried, et al.
(författare)
-
PEPPHER : Efficient and Productive Usage of Hybrid Computing Systems
- 2011
-
Ingår i: IEEE Micro. - : IEEE Institute of Electrical and Electronics. - 0272-1732 .- 1937-4143. ; 31:5, s. 28-41
-
Tidskriftsartikel (refereegranskat)abstract
- PEPPHER, a three-year European FP7 project, addresses efficient utilization of hybrid (heterogeneous) computer systems consisting of multicore CPUs with GPU-type accelerators. This article outlines the PEPPHER performance-aware component model, performance prediction means, runtime system, and other aspects of the project. A larger example demonstrates performance portability with the PEPPHER approach across hybrid systems with one to four GPUs.
|
|
| 10. |
- Benkner, S., et al.
(författare)
-
Peppher: Performance Portability and Programmability for Heterogeneous Many-Core Architectures
- 2017
-
Ingår i: Programming Multicore and Many-Core Computing Systems. - Hoboken, NJ, USA : John Wiley & Sons, Inc.. - 9781119332015 - 9780470936900 ; , s. 241-260
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- © 2017 by John Wiley & Sons, Inc. All rights reserved. PEPPHER takes a pluralistic and parallelization agnostic approach to programmability and performance portability for heterogeneous many-core architectures. The PEPPHER framework is in principle language independent but focuses on supporting C++ code with PEPPHER-specific annotations as pragmas or external annotations. The framework is open and extensible; the PEPPHER methodology details how new architectures are incorporated. The PEPPHER methodology consists of rules for how to extend the framework for new architectures. This mainly concerns adaptivity and autotuning for algorithm libraries, the necessary hooks and extensions for the run-time system and any supporting algorithms and data structures that this relies on. Offloading is a specific technique for programming heterogeneous platforms that can sometimes be applied with high efficiency. Offload as developed by the PEPPHER partner Codeplay is a particular, nonintrusive C++ extension allowing portable C++ code to support diverse heterogeneous multicore architectures in a single code base.
|
|
