The following technical report is available from
http://aib.informatik.rwth-aachen.de: <http://aib.informatik.rwth-aachen.de/>
A Real-time Capable, Open-Source-based Platform for Off-the-Shelf Embedded Devices
Igor Kalkov
AIB 2018-03
Nowadays, software plays a crucial role in the development of embedded products. The product's design and development process can be significantly simplified by relying on reusable software components and modern general-purpose hardware. However, such off-the-shelf components are typically not able to provide real-time support required in the industry. To address this limitation, different approaches were presented in the past to enable the use of high-level software while retaining precise timings during the interaction with the physical environment. For example, real-time capable Linux running on general-purpose hardware is widely used in industrial automation today. Furthermore, Linux-based platforms like Android are continuously gaining popularity in all sectors of the market. Due to its intuitive user interface and a wide range of supported hardware, Android is already broadly deployed in different industrial use cases. However, Android devices used in embedded products are still restricted to serving the purpose of pure data visualization and handling of the user input. To extend Android's field of application to time-critical domains, this work presents a holistic approach for combining the performance of modern general-purpose off-the-shelf hardware with predictability and determinism of a real-time capable operating system. Instead of adopting common methods for limiting the real-time support to the Linux kernel and native applications, it provides a global perspective on Android's architecture including the Linux kernel, main high-level components and their interaction in time-critical scenarios.
The first part of this dissertation covers enhancements for minimizing the process scheduling latency using the PREEMPT_RT patch. Since Android is built upon Linux, introducing a fully preemptible kernel and a high-resolution timer enables a more precise process management. This approach allows Android to achieve bounded scheduling deviations in the same order of magnitude as industrial Linux-based systems. In the second part, it is shown that Android's original memory management may cause unpredictable suspensions of running applications or even automatically terminate long-term background processes. To address this issue, the platform is extended with a real-time capable garbage collector based on reference counting. The new collector operates concurrently to real-time threads in a non-blocking incremental manner, avoiding undesired interferences. Furthermore, the proposed modifications provide additional protection for persistent background services. Finally, this thesis implements enhanced methods for data exchange between separate Android applications. Being seamlessly integrated into the platform, new mechanisms allow predictable communication and bounded delays for delivering arbitrary messages across process boundaries.
A detailed evaluation of the introduced platform changes highlights the effectiveness and scalability of the presented approach. The resulting system performs better in terms of responsiveness and determinism, while staying fully compatible with standard Android components and third-party applications. By combining powerful general-purpose hardware and high-level programming paradigms, Android applications are now able to additionally fulfill strict timing requirements. This allows utilizing the advantages of Android in industrial use cases, which facilitates the development of easily extendable and less complex embedded products with intuitive user interfaces.
The following technical report is available from
http://aib.informatik.rwth-aachen.de: <http://aib.informatik.rwth-aachen.de/>
Fast Estimates of Greeks from American Options: A Case Study in Adjoint Algorithmic Differentiation
Jens Deussen, Viktor Mosenkis, and Uwe Naumann
AIB 2018-02
In this article algorithmic differentiation is applied to compute the sensitivities of the price of an American option, which is computed by the Longstaff-Schwartz algorithm. Adjoint algorithmic differentiation methods speed up the calculation and make the results more accurate and robust compared to a finite difference approximation. However, adjoint computations require more memory due to the storing of intermediate results. One possibility to reduce these memory requirements is to use a technique called checkpointing: Instead of storing all intermediate results the required values are recomputed. Another possibility is to apply a pathwise adjoint approach, which results from an analysis of the Longstaff-Schwartz algorithm and the exploitation of its features. The presented approach is embarrassing parallel and yields the same results as the other adjoint methods, but it reduces the computational effort as well as the memory requirements of the computation to the level of a single pricing calculation.
The following technical report is available from
http://aib.informatik.rwth-aachen.de: <http://aib.informatik.rwth-aachen.de/>
Incremental Integration and Static Analysis of Model-Based Automotive Software Artifacts
Thomas Gerlitz
AIB 2017-08
In recent years, the automotive industry adopted model-based development of software components as an integral part of the automotive software development process. The use of models enables the simulation and testing of system behavior even in early stages of development. They can further serve as input to code generators, allowing the model-based development of firmware for complex systems such as the electronic control units (ECU) of an automobile. As the complexity and size of models continues to grow, a need has arisen for dynamic and static model analysis techniques to keep costs for quality assessment as required by norms and standards such as ISO 26262 in check. While a plethora of tools exists for the analysis of software source-code, the tool landscape for the analysis of software models is still sparsely populated. Due to abstractions used within models and their heterogeneous and often proprietary file formats, the realization of generic model analysis tools cannot be performed to the same extent as for software source-code.
In this thesis, we present a method for the incremental integration and static analysis of model-based software artifacts comprising the extraction, storage, analysis and evolution of model data. The proposed incremental integration approach allows the conversion of supported artifacts into a well-defined representation and subsequent storage in a model repository, enabling seamless access to stored artifacts as well as synchronization with changes made to their source models. We further propose multiple static analysis techniques for MATLAB/Simulink models, a prevalent model-based software artifact in automotive software development. These analyses support various activities during different stages of a model-based development process. We present a signal reconstruction and slicing algorithm that supports debugging, testing and exploration activities of MATLAB/Simulink models. A clone detection procedure allows the automatic identification of cloned model fragments and their subsequent controlled reuse by refactoring into generic library blocks. Further quality and design defects are detected by a model smell analysis, identifying anti-patterns that negatively influence quality properties of MATLAB/Simulink models. Furthermore, we propose an inter-artifact consistency analysis targeting traceability links between artifacts of a product line and its accompanying variability documentation. All proposed techniques are realized in the form of an integrated software framework called artshop.
To show the applicability of the artshop framework, we applied the realized techniques on a set of real-world models taken from academic and industrial case studies to assess the overall scalability and performance of the framework. We show that the integration and analysis capabilities of the artshop framework are already applicable to real-world models.
The following technical report is available from
http://aib.informatik.rwth-aachen.de: <http://aib.informatik.rwth-aachen.de/>
Proceedings of the IDEA League Doctoral School on Transiently Powered Computing
Muhammad Hamad Alizai, Jan Beutel, Jó Ágila Bitsch, Olaf Landsiedel, Luca Mottola, Przemysław Pawełczak, Klaus Wehrle, and Kasım Sinan Yıldırım
AIB 2017-09
Advances in energy harvesting and wireless energy transfer are redefining the scope and extent of the energy constraints in low-power embedded computing. It now becomes conceivable to power not just RFID-scale devices out of harvested or wirelessly-transferred energy, but also more powerful devices operating in applications such as smart buildings, factory automation, and mobile health. However, energy provisioning from ambient energy harvesting or wireless energy transfer is generally erratic. Thus, devices need to cope with highly variable, yet unpredictable energy supplies across both space and time. The challenges arising in this field are generating an entirely new stream of research from the hardware up to the application layers, and novel solutions are being devised to attack these unique problems.
The following technical report is available from
http://aib.informatik.rwth-aachen.de: <http://aib.informatik.rwth-aachen.de/>
Meta Adjoint Programming in C++
Klaus Leppkes, Johannes Lotz, Uwe Naumann, and Jacques du Toit
AIB 2017-07
Adjoint code development for many-core architectures like GPUs is a major challenge. To address issues arising from the parallelization, currently hand-writing the adjoint code is the most promising approach. Unfortunatly, hand-writing has the fundamental drawback of maintainability, i.e. diverging primal and adjoint codes. To overcome this, supporting tools can and should be used. In this report, we present a new approach for generating adjoint C++ codes by algorithmic differentiation. The approach is called meta adjoint programming and based on the template metaprogramming mechanism. We show that with new developments in the C++ language standard, operator and function overloading techniques can be used to achieve efficient and maintainable adjoint codes. Results are shown for a GPU parallel CVA code. An implementation of meta adjoint programming called dco/map is presented and comparisons with hand-written adjoint code are carried out.
The following technical report is available from
http://aib.informatik.rwth-aachen.de: <http://aib.informatik.rwth-aachen.de/>
Derivative Code by Overloading in C++ (dco/c++): Introduction and Summary of Features
Klaus Leppkes, Johannes Lotz, and Uwe Naumann
AIB 2016-08
dco/c++ is a flexible and efficient implementation of first- and higher-order tangent and adjoint Algorithmic Differentiation (AD) by operator overloading in C++. It combines a cache-optimized internal representation based on C++ expression templates with an intuitive and powerful application programmer interface. It also has bindings in Fortran and MATLAB. dco/c++ has been applied successfully to a number of numerical simulations in the context of, for example, large-scale parameter estimation, shape optimization, or computational finance. dco/c++ is under active development. This report provides a basic reference in form of a brief introduction to derivative code resulting from the application of AD to numerical simulation programs, a description of the four fundamental differentiation modes (first- and second-order tangent and adjoint modes, respectively) and a list of all features of the current version of dco/c++. An in-depth discussion of the latter is beyond this document. Further information on the tool can be obtained by contacting info(a)stce.rwth-aachen.de.
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
CD2Alloy: A Translation of Class Diagrams to Alloy
Oliver Kautz, Shahar Maoz, Jan Oliver Ringert, and Bernhard Rumpe
AIB 2017-06
This report presents a translation from UML class diagrams [OMG15, Rum16] to Alloy modules [Jac06] and a translation from Alloy instances back to UML object diagrams. An overview of the translation was first presented in [MRR11a] and applied in [MRR11b] to semantic differencing of class diagrams. It supports an extended list of CD language features, including, e.g., directed associations, composite aggregations, interfaces, multiple inheritance, and enumerations. The translation thus supports essential features of many real-world CDs, UML and EMF metamodels, practically not analyzable before. An important feature of the translation is the ability to analyze multiple class diagrams within one Alloy module, which is not possible with previous translations. This document defines the translations by translation rules that operate on the abstract syntax of a class diagram language and produce concrete syntax of the Alloy language. We give examples showing class diagrams and complete representations in Alloy as well as an Alloy instance and its object diagram representation.
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Complexity Analysis for Term Rewriting by Integer Transition Systems
Matthias Naaf, Florian Frohn, Marc Brockschmidt, Carsten Fuhs, and Jürgen Giesl
AIB 2017-05
We present a new method to infer upper bounds on the innermost runtime complexity of term rewrite systems (TRSs), which benefits from recent advances on complexity analysis of integer transition systems (ITSs). To this end, we develop a transformation from TRSs to a generalized notion of ITSs with (possibly non-tail) recursion. To analyze their complexity, we introduce a modular technique which allows us to use existing tools for standard ITSs in order to infer complexity bounds for our generalized ITSs. The key idea of our technique is a summarization method that allows us to analyze components of the transition system independently. We implemented our contributions in the tool AProVE, and our experiments show that one can now infer bounds for significantly more TRSs than with previous state-of-the-art tools for term rewriting.
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Complexity Analysis for Java with AProVE
Florian Frohn and Jürgen Giesl
AIB 2017-04
While AProVE is one of the most powerful tools for termination analysis of Java since many years, we now extend our approach in order to analyze the complexity of Java programs as well. Based on a symbolic execution of the program, we develop a novel transformation of (possibly heap-manipulating) Java programs to integer transition systems (ITSs). This allows us to use existing complexity analyzers for ITSs to infer runtime bounds for Java programs. We demonstrate the power of our implementation on an established standard benchmark set.
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Analyzing Runtime Complexity via Innermost Runtime Complexity
Florian Frohn and Jürgen Giesl
AIB 2017-02
There exist powerful techniques to infer upper bounds on the innermost
runtime complexity of term rewrite systems (TRSs), i.e., on the lengths
of rewrite sequences that follow an innermost evaluation strategy.
However, the techniques to analyze the (full) runtime complexity of TRSs
are substantially weaker. In this paper, we present a sufficient
criterion to ensure that the runtime complexity of a TRS coincides with
its innermost runtime complexity. This criterion can easily be checked
automatically and it allows us to use all techniques and tools for
innermost runtime complexity in order to analyze (full) runtime
complexity. By extensive experiments with an implementation of our
results in the tool AProVE, we show that this improves the state of the
art of automated complexity analysis significantly.