| 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. |
- 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)
|
|
| 3. |
- 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.
|
|
| 4. |
- 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.
|
|
| 5. |
- 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.
|
|
| 6. |
- 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.
|
|
| 7. |
- 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.
|
|
| 8. |
- Benkner, S., et al.
(författare)
-
The PEPPHER approach to programmability and performance portability for heterogeneous many-core architectures
- 2012
-
Ingår i: Advances in Parallel Computing. - : IOS Press. - 1879-808X .- 0927-5452. ; 22, s. 361-368, s. 361-368
-
Konferensbidrag (refereegranskat)abstract
- The European FP7 project PEPPHER is addressing programmability and performance portability for current and emerging heterogeneous many-core architectures. As its main idea, the project proposes a multi-level parallel execution model comprised of potentially parallelized components existing in variants suitable for different types of cores, memory configurations, input characteristics, optimization criteria, and couples this with dynamic and static resource and architecture aware scheduling mechanisms. Crucial to PEPPHER is that components can be made performance aware, allowing for more efficient dynamic and static scheduling on the concrete, available resources. The flexibility provided in the software model, combined with a customizable, heterogeneous, memory and topology aware run-time system is key to efficiently exploiting the resources of each concrete hardware configuration. The project takes a holistic approach, relying on existing paradigms, interfaces, and languages for the parallelization of components, and develops a prototype framework, a methodology for extending the framework, and guidelines for constructing performance portable software and systems-including paths to migration of existing software-for heterogeneous many-core processors. This paper gives a high-level project overview, and presents a specific example showing how the PEPPHER component variant model and resource-aware run-time system enable performance portability of a numerical kernel. © 2012 The authors and IOS Press. All rights reserved.
|
|
| 9. |
- Berger, Christian, 1980, et al.
(författare)
-
Bridging Physical and Digital Traffic System Simulations with the Gulliver Test-Bed
- 2013
-
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. - 9783642379734 ; 7865 LNCS, s. 169-184
-
Konferensbidrag (refereegranskat)abstract
- We propose a cyber-physical platform that combines road traffic simulation, network simulation, and physically simulated vehicles to facilitate extensive testing on various levels of vehicular systems. Our design integrates physical and digital vehicle simulation into a common development and testing environment. This paper describes the platform design and presents prototypical implementations that use Simulator of Urban Mobility (SUMO), TinyOS Simulator (TOSSIM), a 3D sensor simulation environment, and a test-bed of miniature vehicles called Gulliver. As a prototypical implementation, we demonstrate the development of cooperative applications, and by that we achieve: (a) a cyber-physical system that provides a common environment for physically and digitally simulated vehicles, (b) a platform to interface communication between physically and digitally simulated vehicles, and (c) the ability to tailor testing scenarios in which some system components are simulated digitally and some physically. The suggested design provides flexibility, cost efficiency, and scalable testing opportunities for future vehicular systems. Furthermore, the proposed system is able to support novel steps towards intelligent transportation systems for smart cities. © 2013 Springer-Verlag.
|
|
| 10. |
- Bäckström, Karl, 1994, et al.
(författare)
-
ASAP.SGD: Instance-based Adaptiveness to Staleness in Asynchronous SGD
- 2022
-
Ingår i: Proceedings of Machine Learning Research. - 2640-3498. ; PMLR 162, s. 1261-1271
-
Konferensbidrag (refereegranskat)abstract
- Concurrent algorithmic implementations of Stochastic Gradient Descent (SGD) give rise to critical questions for compute-intensive Machine Learning (ML). Asynchrony implies speedup in some contexts, and challenges in others, as stale updates may lead to slower, or non-converging executions. While previous works showed asynchrony-adaptiveness can improve stability and speedup by reducing the step size for stale updates according to static rules, there is no one-size-fits-all adaptation rule, since the optimal strategy depends on several factors. We introduce (i) ASAP.SGD, an analytical framework capturing necessary and desired properties of staleness-adaptive step size functions and (ii) TAIL-T, a method for utilizing key properties of the execution instance, generating a tailored strategy that not only dampens the impact of stale updates, but also leverages fresh ones. We recover convergence bounds for adaptiveness functions satisfying the ASAP.SGD conditions, for general, convex and non-convex problems, and establish novel bounds for ones satisfying the Polyak-Lojasiewicz property. We evaluate TAIL-T with representative AsyncSGD concurrent algorithms, for Deep Learning problems, showing TAIL-T is a vital complement to AsyncSGD, with (i) persistent speedup in wall-clock convergence time in the parallelism spectrum, (ii) considerably lower risk of non-convergence, as well as (iii) precision levels for which original SGD implementations fail.
|
|
