| 11. |
- 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.
|
|
| 12. |
- 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.
|
|
| 13. |
|
|
| 14. |
- 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.
|
|
| 15. |
- Bäckström, Karl, 1994, et al.
(författare)
-
Consistent lock-free parallel stochastic gradient descent for fast and stable convergence
- 2021
-
Ingår i: Proceedings - 2021 IEEE 35th International Parallel and Distributed Processing Symposium, IPDPS 2021. ; , s. 423-432
-
Konferensbidrag (refereegranskat)abstract
- Stochastic Gradient Descent (SGD) is an essential element in Machine Learning (ML) algorithms. Asynchronous shared-memory parallel SGD (AsyncSGD), including synchronization-free algorithms, e.g. HOGWILD!, have received interest in certain contexts, due to reduced overhead compared to synchronous parallelization. Despite that they induce staleness and inconsistency, they have shown speedup for problems satisfying smooth, strongly convex targets, and gradient sparsity. Recent works take important steps towards understanding the potential of parallel SGD for problems not conforming to these strong assumptions, in particular for deep learning (DL). There is however a gap in current literature in understanding when AsyncSGD algorithms are useful in practice, and in particular how mechanisms for synchronization and consistency play a role. We contribute with answering questions in this gap by studying a spectrum of parallel algorithmic implementations ofAsyncSGD, aiming to understand how shared-data synchronization influences the convergence properties in fundamental DL applications. We focus on the impact of consistency-preserving non-blocking synchronization in SGD convergence, and in sensitivity to hyper-parameter tuning. We propose Leashed-SGD, an extensible algorithmic framework of consistency-preserving implementations of AsyncSGD, employing lock-free synchronization, effectively balancing throughput and latency. Leashed-SGD features a natural contention-regulating mechanism, as well as dynamic memory management, allocating space only when needed. We argue analytically about the dynamics of the algorithms, memory consumption, the threads' progress over time, and the expected contention. We provide a comprehensive empirical evaluation, validating the analytical claims, benchmarking the proposed Leashed-SGD framework, and comparing to baselines for two prominent deep learning (DL) applications: multilayer perceptrons (MLP) and convolutional neural networks (CNN). We observe the crucial impact of contention, staleness and consistency and show how, thanks to the aforementioned properties, Leashed-SGD provides significant improvements in stability as well as wall-clock time to convergence (from 20-80% up to 4 ×improvements) compared to the standard lock-based AsyncSGD algorithm and HOGWILD!, while reducing the overall memory footprint.
|
|
| 16. |
- Bäckström, Karl, 1994, et al.
(författare)
-
MindTheStep-AsyncPSGD: Adaptive Asynchronous Parallel Stochastic Gradient Descent
- 2019
-
Ingår i: Proceedings - 2019 IEEE International Conference on Big Data, Big Data 2019. ; , s. 16-25
-
Konferensbidrag (refereegranskat)abstract
- Stochastic Gradient Descent (SGD) is very useful in optimization problems with high-dimensional non-convex target functions, and hence constitutes an important component of several Machine Learning and Data Analytics methods. Recently there have been significant works on understanding the parallelism inherent to SGD, and its convergence properties. Asynchronous, parallel SGD (AsyncPSGD) has received particular attention, due to observed performance benefits. On the other hand, asynchrony implies inherent challenges in understanding the execution of the algorithm and its convergence, stemming from the fact that the contribution of a thread might be based on an old (stale) view of the state. In this work we aim to deepen the understanding of AsyncPSGD in order to increase the statistical efficiency in the presence of stale gradients. We propose new models for capturing the nature of the staleness distribution in a practical setting. Using the proposed models, we derive a staleness-adaptive SGD framework, MindTheStep-AsyncPSGD, for adapting the step size in an online-fashion, which provably reduces the negative impact of asynchrony. Moreover, we provide general convergence time bounds for a wide class of staleness-adaptive step size strategies for convex target functions. We also provide a detailed empirical study, showing how our approach implies faster convergence for deep learning applications.
|
|
| 17. |
- Bäckström, Karl, 1994, et al.
(författare)
-
The Impact of Synchronization in Parallel Stochastic Gradient Descent
- 2022
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. ; 13145 LNCS, s. 60-75
-
Konferensbidrag (refereegranskat)abstract
- In this paper, we discuss our and related work in the domain of efficient parallel optimization, using Stochastic Gradient Descent, for fast and stable convergence in prominent machine learning applications. We outline the results in the context of aspects and challenges regarding synchronization, consistency, staleness and parallel-aware adaptiveness, focusing on the impact on the overall convergence.
|
|
| 18. |
- Casado, Lander, 1985, et al.
(författare)
-
ContikiSec: A Secure Network Layer for Wireless Sensor Networks under the Contiki Operating System
- 2009
-
Ingår i: Proceedings of the 14th Nordic Conference on Secure IT Systems (NordSec 2009), Lecture Notes in Computer Science. - 1611-3349. - 9783642047657 ; 5838, s. 133 - 147
-
Konferensbidrag (refereegranskat)abstract
- In this paper we introduce ContikiSec, a secure network layer forwireless sensor networks, designed for the Contiki Operating System. ContikiSechas a configurable design, providing three security modes starting fromconfidentiality and integrity, and expanding to confidentiality, authentication,and integrity. ContikiSec has been designed to balance low energy consumptionand security while conforming to a small memory footprint. Our design wasbased on performance evaluation of existing security primitives and is part ofthe contribution of this paper. Our evaluation was performed in the ModularSensor Board hardware platform for wireless sensor networks, running Contiki.Contiki is an open source, highly portable operating system for wireless sensornetworks (WSN) that is widely used in WSNs.
|
|
| 19. |
- Casimiro, Antonio, et al.
(författare)
-
KARYON: Towards Safety Kernels for Cooperative Vehicular Systems
- 2012
-
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. - 9783642335358 ; 7596, s. 232-235
-
Konferensbidrag (refereegranskat)abstract
- KARYON, a kernel-based architecture for safety-critical control, is a European project that proposes a new perspective to improve performance of smart vehicle coordination focusing on Advanced Driver Assistance Systems (ADASs) and Unmanned Aerial Systems (UAS). The key objective is to provide system solutions for predictable and safe coordination of smart vehicles that autonomously cooperate and interact in an open and inherently uncertain environment. Currently, these systems are not allowed to operate on the public roads or in the air space, as the risk of causing severe damage cannot be excluded with sufficient certainty. The impact of the project is two-fold; it will provide improved vehicle density without driver involvement and increased traffic throughput to maintain mobility without a need to build new traffic infrastructures. The results will improve interaction in cooperation scenarios while preserving safety and assessing it according to standards. The prospective project results include self-stabilizing algorithms for vehicle coordination, communication and synchronization. In addition, we aim at showing that the safety kernel can be designed to be a self-stabilizing one.
|
|
| 20. |
- Cederman, Daniel, 1981, et al.
(författare)
-
A Practical Quicksort Algorithm for Graphics Processors
- 2008
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- In this paper we describe GPU-Quicksort, an efficient Quicksort algorithm suitable for highly parallel multi-core graphics processors. Quicksort has previously been considered an inefficient sorting solution for graphics processors, but we show that in CUDA, NVIDIA's programming platform for general purpose computations on graphical processors, GPU-Quicksort performs better than the fastest known sorting implementations for graphics processors, such as radix and bitonic sort. Quicksort can thus be seen as a viable alternative for sorting large quantities of data on graphics processors.
|
|
