Refine
Document Type
- conference proceeding (article) (8)
- Article (2)
- Part of Periodical (2)
Is part of the Bibliography
- no (12)
Keywords
- Forschung (2)
- Forschungsbericht (2)
- Parallel programming (2)
- Real-time (2)
- Work-stealing (2)
- Real-time systems (1)
- Task model (1)
- Thread pool (1)
- directed acyclic graph (1)
- parallel task (1)
Institute
Begutachtungsstatus
- begutachtet (4)
- peer-reviewed (3)
Forschung 2018
(2018)
Forschungsbericht 2017
(2017)
Modern compute architectures often consist of multiple CPU cores to achieve their performance, as physical properties put a limit on the execution speed of a single processor. This trend is also visible in the embedded and real-time domain, where programmers are forced to parallelize their software to keep deadlines. Additionally, embedded systems rely increasingly on modular applications, that can easily be adapted to different system loads and hardware configurations.
To parallelize applications under these dynamic conditions, often dispatching frameworks like Threading Building Blocks (TBB) are used in the desktop and server segment. More recently, Embedded Multicore Building Blocks (EMB2) was developed as a task-based programming solution designed with the constraints of embedded systems in mind.
In this paper, we discuss how task-based programming fits such systems by analyzing scheduler implementation variants, with a focus on classic work-stealing and the libraries TBB and EMB2. Based on the state of the art we introduce a novel resource-trading concept that allows static memory allocation in a work-stealing runtime holding strict space and time bounds. We conduct benchmarks between an early prototype of the concept, TBB and EMB2, showing that resource-trading does not introduce additional runtime overheads, while unfortunately also not improving on execution time variances.
The enormous amounts of data modern real-time systems have to process lead to expensive, long-lasting calculations. In order to manage those computations in a timely manner, parallel task models have gained a lot of popularity lately. However, parallel programming can be very cumbersome and verbose. Other computationally intensive sectors have dealt with parallel computing for decades and have accumulated their experience in the development of parallel frameworks. Examples of well known parallel runtime systems are OpenMP, Intel Threading Building Blocks (TBB) and Microsoft Parallel Pattern Library (PPL). These runtime systems allow developers to enhance parallelism in their applications in a straightforward fashion. However, those parallel frameworks and the patternbased interfaces they provide might not be easily applicable in real-time systems. In this paper, we investigate the use of parallel programming frameworks in time-critical systems. On that account, we discuss considerations for the design of real-time applications that make use of such parallel runtime systems. Furthermore, we evaluate three library-based frameworks from different computing sectors, namely Intel Threading Building Blocks, Embedded Multicore Building Blocks (EMBB) and High Performance ParalleX (HPX), by conducting benchmarks of various parallel algorithms on an embedded multicore architecture.
With parallel applications becoming more and more popular even in real-time systems, the demand for safe and easyto- use software libraries and frameworks for parallel and concurrent computations is growing immensely. These frameworks usually provide an implementation for different sets of software patterns. A very well known software pattern for concurrency is the Active Object pattern, that allows various threads to have synchronized access to an object in question. This paper presents the Parallel Active Object pattern, which extends the common Active Object pattern to support the use of objects, whose computations are profoundly enhanced by a parallel execution. Furthermore, a C++ software framework is introduced, which implements the Parallel Active Object pattern and thus provides the possibility of using task or data parallel patterns, for example Map, Reduce and Divide-and-Conquer, on the active object's calculations. The proposed framework is evaluated against two other popular libraries, namely OpenMP and Intel Threading Building Blocks. Through utilization of the C++11 standard and template classes a simple user interface is provided, which abstracts the distribution of workloads among the worker threads. By making use of the C++ Standard Template Library the framework can easily be ported to embedded systems and by extending the pattern through real-time capabilities, which ensure a timely and reliable execution of the method requests, the intention of providing the framework for time critical environments is also targeted in the future.
Today, due to the rapidly evolving technology within the automotive industry, the automation level of cars is continuously increasing. As a consequence, the software code base implementing the automated driving functionality is growing in both, complexity and size. Simultaneously, the semiconductor industry continues with structure and voltage downscaling due to diminishing design margins and stringent power constraints. This trend leads to highly integrated hardware on the one hand, whilst provoking an increase in sensitivity against external causes for hardware faults, e.g., radiation effects or electromagnetic interference. Among the available dependability assessment techniques, fault injection (FI) is widely adopted and ISO 26262 strongly recommends applying it to validate, that functional and technical safety mechanisms are implemented correctly and effectively. We present PyFI (Python backend for Fault Injection), a fault injection backend for the Infineon Aurix TriCore which utilizes an iSystem On-chip Analyzer to inject faults into the application data or instructions that are visible at the assembly level. PyFI allows the injection of bit flips and stuck-at faults in memory and register cells of the hardware which trigger our error symptoms on application level. Furthermore, it implements fault collapsing algorithms to reduce the number of faults and the duration for single experiments by gathering statistics about the static and dynamic application execution.
Modern high-end embedded systems nowadays have to process enormous amounts of data. In order to speed up the computations and fully exploit the resources of the underlying hardware architectures, software developers can avail parallelism frameworks such as Intel Threading Building Blocks or compiler extensions as OpenMP. They ease the development of parallel applications by providing interfaces for common parallel design patterns and by internally distributing the work among the workers of a thread pool. However, such frameworks and compiler extensions do not yet support the stringent timing requirements of real-time systems and therefore, an adaption of their computation model to the sector of real-time systems needs to be conducted.
In this paper, we address the problem of scheduling parallel real-time directed acyclic graphs tasks on multiprocessor architectures where the subtasks are dispatched among and executed by the workers of a thread pool. In contrast to existing work in the state-of-the-art, we limit the maximum parallelism of real-time tasks not by the number of processors in the system, but by the number of worker threads used in the thread pool of each real-time application. For this model, we derive a worst-case response time analysis for task sets scheduled by a preemptive global fixed-priority scheduler. In order to evaluate the performance of our response time analysis, we further perform schedulability tests on generated task sets and compare the results to existing feasibility analyses in the current state-of-the-art.
Lately, parallel task models have received much attention in the development of real-time multiprocessor systems, as they allow highly compute-intensive tasks to have shorter deadlines which is very much required in modern reactive systems. However, missing modularity and portability can make parallel programming a cumbersome endeavor. As a consequence, compute-intensive sectors in the desktop and server segment have relied on parallelism frameworks such as Intel Threading Building Blocks, Cilk and OpenMP. These parallelism frameworks, however, are optimized for decent average case performance and consequently, do not meet the strict requirements imposed by real-time systems.
In this paper, we present a proof-of-concept parallelism framework which was implemented in particular for soft real-time systems and having tight timing and safety requirements of such critical systems in mind. The proposed runtime system implements static memory allocation in a work-stealing environment that conforms to the strict space and tight probabilistic time bounds of work-stealing schedulers. Furthermore, we evaluate the performance of this framework by conducting multiprogrammed benchmarks on a real-time embedded multicore architecture.
In the real-time systems sector, various task models and corresponding tests exist to model and verify the schedulability of task sets on the system at hand. While those models and schedulability tests have intensively been studied from a theoretical point of view, it is hard to ma e use of them to compare the actual execution behavior of scheduling algorithms on a real system. In contrast to schedulability tests, simulators can help to investigate the performance of specific scheduling algorithms. One of the most generalized task models to describe parallel tasks is the Directed Acyclic Graph model that allows to represent tasks as a series of subtasks that depict the potentially parallel computations and precedence constraints that denote the order in which the subtasks are allowed to execute.
In this paper, we investigate various scheduling algorithms for the Directed Acyclic Graph model. For that, we first recapitulate the examined scheduling algorithms in detail and point out relevant differences. Subsequently, we present the evaluation of different global and federated scheduling algorithms using fine-grained parallel tasks. To this end, we generate random Directed Acyclic Graph tasks and simulate their execution on multiprocessor systems using scheduling algorithms such as global rate-monotonic and semi-federated scheduling as well as global scheduling policies using the thread pool model.
Sharing data across multiple tasks in multiprocessor systems has intensively been studied in the past decades. Various synchronization protocols, the most well-known being the Priority Inheritance Protocol or the Priority Ceiling Protocol, have been established and analyzed so that blocking times of tasks waiting to access a shared resource can be upper bounded. To the best of our knowledge, all of these protocols share one commonality: Tasks that want to enter a critical section, that is already being executed by another task, immediately get blocked. In this paper, we introduce the Asynchronous Priority Ceiling Protocol (A-PCP), which makes use of aperiodic servers to execute the critical sections asynchronously, while the calling task can continue its work on non-critical section code. For this protocol, we provide a worst-case response time analysis of the asynchronous computations, as well as necessary and sufficient conditions for a feasibility analysis of a set of periodic tasks using the proposed synchronization model on a system that preemptively schedules the tasks under the rate-monotonic priority assignment.