RTOS-Aware Refinement for TLM2.0-based HW/SW Design - Becker, Markus; Di Guglielmo, Giuseppe; Fummi, Franco; Müller, Wolfgang; Pravadelli, Graziano; Xie, Tao (Proceedings of DATE’10)
Refinement of untimed TLM models into a timed HW/SW platform is a step by step design process which is a trade-off between timing accuracy of the used models and correct estimation of the final timing performance. The use of an RTOS on the target platform is mandatory in the case real-time properties must be guaranteed. Thus, the question is when the RTOS must be introduced in this step by step refinement process. This paper proposes a four-level RTOS-aware refinement methodology that, starting from an untimed TLM SystemC description of the whole system, progressively introduce HW/SW partitioning, timing, device driver and RTOS functionalities, till to obtain an accurate model of the final platform, where SW tasks run upon an RTOS hosted by QEMU and HW components are modeled by cycle accurate TLM descriptions. Each refinement level allows the designer to estimate more and more accurate timing properties, thus anticipating design decisions without being constrained to leave timing analysis to the final step of the refinement. The effectiveness of the methodology has been evaluated in the design of two complex platforms.
Keywords: Timing; Hardware; Operating systems; Process design; Accuracy; Standards development; Context modeling; Real time systems; Communication channels; Microprogramming

A Mixed Level Simulation Environment for Stepwise RTOS Software Refinement - Becker, Markus; Zabel, Henning; Müller, Wolfgang
In this article, we present a flexible simulation environment for embedded real-time software refinement by a mixed level cosimulation. For this, we combine the native speed of an abstract real-time operating system (RTOS) model in SystemC with dynamic binary translation for fast Instruction Set Simulation (ISS) by QEMU. In order to support stepwise RTOS software refinement from system level to the target software, each task can be separately migrated between the native execution and the ISS. By adapting the dynamic binary translation approach to an efficient but yet very accurate synchronization scheme the overhead of QEMU user mode execution is only factor two compared to native SystemC. Furthermore, the simulation speed increases almost linearly according to the utilization of the task set abstracted by the native execution. Hereby, the simulation time can be considerably reduced by cosimulating just a subset of tasks on QEMU.
Keywords: Application Programming Interface User Mode Kernel Space System Level Design Mixed Level

Task Migration for Fault-Tolerant FlexRay Networks - Klobedanz, Kay; Defo, Gilles B.; Zabel, Henning; Müller, Wolfgang; Zhi, Yuan
In this paper we present new concepts to resolve ECU (Electronic Control Unit) failures in FlexRay networks. Our approach extends the FlexRay bus schedule by redundant slots with modifications in the communication and slot assignment. We introduce additional backup nodes to replace faulty nodes. To reduce the required memory resources of the backup nodes, we distribute redundant tasks over different nodes and propose the migration of tasks to the backup node at runtime. We investigate different solutions to migrate the redundant tasks to the backup node by time-triggered and event-triggered transmissions.
Keywords: Faulty Node Static Segment Slot Assignment Task Migration Communication Controller

A UML Profile for SysML-Based Comodeling for Embedded Systems Simulation and Synthesis - Mischkalla, Fabian; Müller, Wolfgang; He, Da (Proceedings of the M-BED Workshop)
It's wide application in the area of software engineering, UML is still not fully accepted for other engineering domains like for electronic systems design. The main obstacle is due to a major gap in the design flow between UML-based modeling and verification. To overcome this gap, we introduce a UML profile for synthesizable SystemC and C and present its implementation in the context of the advanced SysML modeling environment of ARTiSAN Studio. We demonstrate how to customize Studio for SystemC/C comodeling so that it can serve as a verification and synthesis front-end.

Eine strukturierte Methode zur Generierung von SystemVerilog-Testumgebungen aus textuellen Anforderungsbeschreibungen - Bol, Alexander; Müller, Wolfgang; Krupp, Alexander (Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen (MBMV))

The SATURN Approach to SysML-based HW/SW Codesign - Müller, Wolfgang; He, Da; Mischkalla, Fabian; Wegele, Arthur; Larkham, Adrian; Whiston, Paul; Penil, Pablo; Villar, Eugenio; Mitas, Nikolaos; Kritharidis, Dimitros; Azcarate, Florent; Carballeda, Manuel (Proceedings of the IEEE Computer Society Annual Symposium on VLSI)
The main obstacle for the wide acceptance of UML and SysML in the design of electronic systems is due to a major gap in the design flow between UML-based modeling and SystemC-based verification. To overcome this gap, we present an approach developed in the SATURN project which introduces UML profiles for the co-modeling of SystemC and C with code generation support in the context of the SysML tool suite ARTiSAN Studio®. We finally discuss the evaluation of the approach by two case studies.
Keywords: Communicate Sequential Process Virtual Platform Smart Camera Synchronous Data Flow Artisan Studio

Generation of Executable Testbenches from Natural Language Requirement Specifications for Embedded Real-Time Systems - Müller, Wolfgang; Bol, Alexander; Krupp, Alexander; Lundkvist, Ola
We introduce a structured methodology for the generation of executable test environments from textual requirement specifications via UML class diagrams and the application of the classification tree methodology for embedded systems. The first phase is a stepwise transformation from unstructured English text into a textual normal form (TNF), which is automatically translated into UML class diagrams. After annotations of the class diagrams and the definition of test cases by sequence diagrams, both are converted into classification trees. From the classification trees we can finally generate SystemVerilog code. The methodology is introduced and evaluated by the example of an Adaptive Cruise Controller.
Keywords: Natural Language UML SystemVerilog Testbenches

Mutation-Analysis Directed Constrained Random Verification - Xie, Tao; Letombe, Florian; Müller, Wolfgang

An Eclipse-based Framework for the IP-XACT-enabled Assembly of Mixed-Level IPs - Xie, Tao; Defo, Gilles B.; Müller, Wolfgang

Verification of a CAN Bus Model in SystemC with Functional Coverage - Defo, Gilles B.; Müller, Wolfgang; Kuznik, Christoph (Proceedings of SIES 2010)
Many heterogeneous embedded systems, for example industrial automation and automotive applications, require hard-real time constraints to be exhaustively verified - which is a challenging task for the verification engineer. To cope with complexity, verification techniques working on different abstraction levels are best practice. SystemC is a versatile C++ based design and verification language, offering various mechanisms and constructs required for embedded systems modeling. Using the add-on SystemC Verification Library (SCV) elemental constrained-random stimuli techniques may be used for verification. However, SCV has several drawbacks such as lack of functional coverage. In this paper we present a functional coverage library that implements parts of the IEEE 1800-2005 SystemVerilog standard and allows capturing functional coverage throughout the design and verification process with SystemC. Moreover, we will demonstrate the usability of the approach with a case study working on a CAN bus model written in SystemC.
Keywords: Libraries; Generators; Transfer functions; Monitoring; Computational modeling; Driver circuits; Adaptation model

Distributed Coordination of Task Migration for Fault-Tolerant FlexRay Networks - Klobedanz, Kay; Defo, Gilles B.; Müller, Wolfgang; Kerstan, Timo (Proceedings of SIES 2010)
In this paper we present an approach to increase the fault tolerance in FlexRay networks by introducing backup nodes to replace defect ECUs (Electronic Control Units). In order to reduce the memory requirements of such backup nodes, we distribute redundant tasks over different nodes and propose the distributed coordinated migration of tasks of the defect ECU to the backup node at runtime. This approach enhances our former work in, where we extended the FlexRay bus schedule by redundant slots to consider changes in the communication/slot assignment and investigated and evaluated different solutions to migrate the redundant tasks to the backup node using the static and/or dynamic segment of the communication cycle for transmissions. We present the approach of distributed coordination for migration and communication instead of additional dedicated coordinator nodes to further increase the fault tolerance. With this approach we improve the safety of FlexRay networks by avoiding a possible single point of failure due to a dedicated coordinator node also minimizing the necessary time needed for a reconfiguration after an ECU failure. Furthermore, we reduce the overhead within the communication and the demand for additional hardware components.
Keywords: Fault tolerant systems; Protocols; Redundancy; Runtime; Payloads; Schedules

Verification of Real-Time Properties for Hardware-Dependant Software - Müller, Wolfgang; da S. Oliveira, Marcio F.; Zabel, Henning; Becker, Markus (Proceedings of HLDVT2010)
Seamless HW/SW codesign flows support early verification of hardware and Hardware-dependent Software (HdS) like drivers, operating systems, and firmware. For early estimation and verification, the application of SystemC in combination with Instruction Set Simulators and Software Emulators like QEMU is widely accepted. In this article, we present an advanced design flow for HW, (RT)OS and HdS refinement and verification with focus on the transition from abstract RTOS verification to full system RTOS/HdS emulation. In the context of assertion-based verification, we introduce a set of generic real-time properties which can be reused and verified at different abstraction levels and discuss their application. The properties are presented by the means of IEEE standard PSL assertions which are applied for mixed SystemC/HdS models.
Keywords: Hardware; Microprogramming; Application software; Timing; Protocols; Virtual prototyping; Real time systems; Sampling methods; Operating systems; Emulation

Design Space Abstraction and Metamodeling for Embedded Systems Design Space Exploration - Oliveira, Marcio F. S.; do Nascimento, Francisco Assis M.; Müller, Wolfgang (Proceedings of MoMPES 2010)

Strong NP-hardness of the quantum separability problem - Gharibian, Sevag (Quantum Information & Computation)
Given the density matrix rho of a bipartite quantum state, the quantum separability problem asks whether rho is entangled or separable. In 2003, Gurvits showed that this problem is NP-hard if rho is located within an inverse exponential (with respect to dimension) distance from the border of the set of separable quantum states. In this paper, we extend this NP-hardness to an inverse polynomial distance from the separable set. The result follows from a simple combination of works by Gurvits, Ioannou, and Liu. We apply our result to show (1) an immediate lower bound on the maximum distance between a bound entangled state and the separable set (assuming P != NP), and (2) NP-hardness for the problem of determining whether a completely positive trace-preserving linear map is entanglement-breaking.

Towards Adaptive Networking for Embedded Devices based on Reconfigurable Hardware - Lübbers, Enno; Platzner, Marco; Plessl, Christian; Keller, Ariane; Plattner, Bernhard (Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA))

Pruning the Design Space for Just-In-Time Processor Customization - Grad, Mariusz; Plessl, Christian (Proc. Int. Conf. on ReConFigurable Computing and FPGAs (ReConFig))

An Open Source Circuit Library with Benchmarking Facilities - Grad, Mariusz; Plessl, Christian (Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA))

Configurable Processor Architectures: History and Trends - Andrews, David; Plessl, Christian (Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA))

Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA)

Using Shared Library Interposing for Transparent Acceleration in Systems with Heterogeneous Hardware Accelerators - Beisel, Tobias; Niekamp, Manuel; Plessl, Christian (Proc. Int. Conf. on Application-Specific Systems, Architectures, and Processors (ASAP))

Reconfigurable Nodes for Future Networks - Keller, Ariane; Plattner, Bernhard; Lübbers, Enno; Platzner, Marco; Plessl, Christian (Proc. IEEE Globecom Workshop on Network of the Future (FutureNet))

Rupeas: Ruby Powered Event Analysis DSL - Woehrle, Matthias; Plessl, Christian; Thiele, Lothar (Proc. Int. Conf. Networked Sensing Systems (INSS))

Performance Estimation for the Exploration of CPU-Accelerator Architectures - Kenter, Tobias; Platzner, Marco; Plessl, Christian; Kauschke, Michael (Proc. Workshop on Architectural Research Prototyping (WARP), International Symposium on Computer Architecture (ISCA))

Smart Card basierte Berechnung einer Gruppensignatur als Teil einer biometrischen Authentisierung - Postler, Tim
Keywords: Diplomarbeit

Preference-Based Multi-Objective Particle Swarm Optimization Using Desirabilities - Mostaghim, Sanaz; Trautmann, Heike; Mersmann, Olaf (Parallel Problem Solving from Nature, PPSN XI)
The integration of experts’ preferences is an important aspect in multi-objective optimization. Usually, one out of a set of Pareto optimal solutions has to be chosen based on expert knowledge. A combination of multi-objective particle swarm optimization (MOPSO) with the desirability concept is introduced to efficiently focus on desired and relevant regions of the true Pareto front of the optimization problem which facilitates the solution selection process. Desirability functions of the objectives are optimized, and the desirability index is used for selecting the global best particle in each iteration. The resulting MOPSO variant DF-MOPSO in most cases exclusively generates solutions in the desired area of the Pareto front. Approximations of the whole Pareto front result in cases of misspecified desired regions.

Benchmarking Evolutionary Algorithms: Towards Exploratory Landscape Analysis - Mersmann, Olaf; Preuss, Mike; Trautmann, Heike (Proceedings of the 11th International Conference on Parallel Problem Solving from Nature: Part I)
We present methods to answer two basic questions that arise when benchmarking optimization algorithms. The first one is: which algorithm is the ’best’ one? and the second one: which algorithm should I use for my real world problem? Both are connected and neither is easy to answer. We present methods which can be used to analyse the raw data of a benchmark experiment and derive some insight regarding the answers to these questions. We employ the presented methods to analyse the BBOB’09 benchmark results and present some initial findings.
Keywords: benchmarking; multidimensional scaling; consensus ranking; evolutionary optimization; BBOB test set

On the Distribution of EMOA Hypervolumes - Mersmann, O; Trautmann, Heike; Naujoks, B; Weihs, C (Learning and Intelligent Optimization, 4$^th$ International Conference, LION 4, Venice, Italy)
We present methods to answer two basic questions that arise when benchmarking optimization algorithms. The first one is: which algorithm is the 'best' one? and the second one: which algorithm should I use for my real world problem? Both are connected and neither is easy to answer. We present methods which can be used to analyse the raw data of a benchmark experiment and derive some insight regarding the answers to these questions. We employ the presented methods to analyse the BBOB'09 benchmark results and present some initial findings.

Benchmarking evolutionary multiobjective optimization algorithms - Mersmann, Olaf; Trautmann, Heike; Naujoks, Boris; Weihs, Claus (IEEE Congress on Evolutionary Computation)
Choosing and tuning an optimization procedure for a given class of nonlinear optimization problems is not an easy task. One way to proceed is to consider this as a tournament, where each procedure will compete in different ‘disciplines’. Here, disciplines could either be different functions, which we want to optimize, or specific performance measures of the optimization procedure. We would then be interested in the algorithm that performs best in a majority of cases or whose average performance is maximal. We will focus on evolutionary multiobjective optimization algorithms (EMOA), and will present a novel approach to the design and analysis of evolutionary multiobjective benchmark experiments based on similar work from the context of machine learning. We focus on deriving a consensus among several benchmarks over different test problems and illustrate the methodology by reanalyzing the results of the CEC 2007 EMOA competition.

Sequential Parameter Optimisation for Multi-Objective Evolutionary Optimisation of Additive Layer Manufacturing - Ding, J; Wessing, S; Trautmann, Heike; Mehnen, J; Naujoks, B (Proceedings of the 7$^th$ CIRP International Seminar on Intelligent Computation in Manufacturing Engineering (CIRP ICME ’10))

New Uncertainty Handling Strategies in Multi-objective Evolutionary Optimization - Voß, Thomas; Trautmann, Heike; Igel, Christian (Parallel Problem Solving from Nature, PPSN XI)
Since many real-world optimization problems are noisy, vector optimization algorithms that can cope with noise and uncertainty are required. We propose new, robust selection strategies for evolutionary multi-objective optimization in the presence of noise. We apply new measures of uncertainty for estimating the recently introduced Pareto-dominance for uncertain and noisy environments (PDU). The first measure is the inter-quartile range of the outcomes of repeated function evaluations. The second is based on axis-aligned bounding boxes around the upper and lower quantiles of the sampled fitness values in objective space. Experiments on real and artificial problems show promising results.

Integration of Preferences in Hypervolume-Based Multiobjective Evolutionary Algorithms by Means of Desirability Functions - Wagner, Tobias; Trautmann, Heike (IEEE Transactions on Evolutionary Computation)
In this paper, a concept for efficiently approximating the practically relevant regions of the Pareto front (PF) is introduced. Instead of the original objectives, desirability functions (DFs) of the objectives are optimized, which express the preferences of the decision maker. The original problem formulation and the optimization algorithm do not have to be modified. DFs map an objective to the domain [0, 1] and nonlinearly increase with better objective quality. By means of this mapping, values of different objectives and units become comparable. A biased distribution of the solutions in the PF approximation based on different scalings of the objectives is prevented. Thus, we propose the integration of DFs into the S-metric selection evolutionary multiobjective algorithm. The transformation ensures the meaning of the hypervolumes internally computed. Furthermore, it is shown that the reference point for the hypervolume calculation can be set intuitively. The approach is analyzed using standard test problems. Moreover, a practical validation by means of the optimization of a turning process is performed.

Work roll cooling system design optimisation in presence of uncertainty and constrains - Azene, Y.T.; Roy, R.; Farrugia, D.; Onisa, C.; Mehnen, J.; Trautmann, Heike (CIRP Journal of Manufacturing Science and Technology)
The paper presents a framework to optimise the design of work roll based on the cooling performance. The framework develops meta-models from a set of finite element analyses (FEA) of the roll cooling. A design of experiment technique is used to identify the FEA runs. The research also identifies sources of uncertainties in the design process. A robust evolutionary multi-objective evaluation technique is applied to the design optimisation in constrained problems with real life uncertainty. The approach handles uncertainties associated both with design variables and fitness functions. Constraints violation within the neighbourhood of a design is considered as part of a measurement for degree of feasibility and robustness of a solution.
Keywords: Roll cooling design; Uncertainty; Design optimisation; Multi-objective optimisation; Constraint in design

Online convergence detection for evolutionary multi-objective algorithms revisited - Wagner, Tobias; Trautmann, Heike (IEEE Congress on Evolutionary Computation)
The design and application of termination criteria has become an important aspect in evolutionary multi-objective optimization. Online convergence detection (OCD) determines when further generations are no longer promising based on statistical tests on a set of performance indicators. The behavior of OCD mainly depends on two parameters, the number of preceding generations considered in the statistical tests and the desired variance limit. In this paper, guidelines for selecting appropriate combinations of these parameters are empirically derived based on design-of-experiment methods. Furthermore, a variant of OCD is introduced which directly operates on the hypervolume indicator - the internal measure of the SMS-EMOA. This allows a separated analysis of the variance criterion and reduces the complexity of OCD. Based on the experimental design, a systematic comparison with the classical OCD approach is performed and differences between the appropriate parameterizations of both variants are highlighted.

Mächtigkeit und Komplexität von Berechnungen mit der ganzzahligen Division - Lürwer-Brüggemeier, Katharina

On Fault-Tolerant Data Placement in Storage Networks - Mense, Mario

Size Equivalent Cluster Trees - Rendering CAD Models in Industrial Scenes - Kortenjan, Michael

Versatility of Bulk Synchronous Parallel Computing: From the Heterogeneous Cluster to the System on Chip - Bonorden, Olaf

Complexity and approximation of a geometric local robot assignment problem - Bonorden, Olaf; Degener, Bastian; Pietrzyk, Peter; Kempkes, Barbara

Complexity and Approximation of a Geometric Local Robot Assignment Problem - Bonorden, Olaf; Degener, Bastian; Kempkes, Barbara; Pietrzyk, Peter (Algorithmic Aspects of Wireless Sensor Networks)
We introduce a geometric multi-robot assignment problem. Robots positioned in a Euclidean space have to be assigned to treasures in such a way that their joint strength is sufficient to unearth a treasure with a given weight. The robots have a limited range and thus can only be assigned to treasures in their proximity. The objective is to unearth as many treasures as possible. We investigate the complexity of several variants of this problem and show whether they are in $\classP$ or are $\classNP$-complete. Furthermore, we provide a distributed and local constant-factor approximation algorithm using constant-factor resource augmentation for the two-dimensional setting with $\bigO(\log^*n)$ communication rounds.

3nuts: A Locality-Aware Peer-to-Peer Network Combining Random Networks, Search Trees, and DHTs - Schindelhauer, Christian; Mahlmann, Peter; Janson, Thomas
Categorizing peer-to-peer networks from an algorithmic point of view the two extremes of the spectrum are unstructured networks and networks based on plain distributed hash tables (DHT). Unstructured networks stand out with their simplicity, robustness, and support for complex queries. Though, they lack efficient query algorithms providing guarantees. On the other hand, DHT based networks feature efficient lookup algorithms with typically logarithmic hop distance and provide simple and efficient load balancing. Yet, they are limited to exact match queries and in many cases hard to maintain under churn.

Minimal Energy Path Planning for Wireless Robots - Ooi, Chia Ching; Schindelhauer, Christian (Mobile Networks and Applications (MONET))

Utilizing detours for energy conservation in mobile wireless networks - Ooi, Chia Ching; Schindelhauer, Christian (Telecommunication Systems)

Colouring Non-sparse Random Intersection Graphs - Raptopoulos, Christoforos L.; Nikoletseas, Sotiris E.; Spirakis, Paul G. (34st International Symposium on Mathematical Foundations of Computer Science)

Combinatorial Properties for Efficient Communication in Distributed Networks with Local Interactions - Nikoletseas, Sotiris E.; Raptopoulos, Christoforos L.; Spirakis, Paul G. (Proceedings of IPDPS - IEEE International Parallel & Distributed Processing Symposium)

Distributed Heterogeneous Hashing and Deterministic Dynamical Decompositions - Deveci, Deniz; Kortenjan, Michael; Schomaker, Gunnar (Parallel and Distributed Computing and Systems, Nr. 21)

Analysis and implementation of an Artificial Homeostatic Hormone System: A first case study in robotic hardware - Stradner, Jürgen; Hamann, Heiko; Schmickl, Thomas; Crailsheim, Karl (2009 IEEE/RSJ International Conference on Intelligent Robots and Systems)
One of the prominent challenges in mobile robotics is to develop control methodologies that allow the adaptation to dynamic and unforeseen environments. The classic approach of hand-coded controllers is very efficient for well-defined tasks and specific environments but poor in adapting to changing environmental conditions. One alternative approach is the application of evolutionary algorithms which need, in turn, easily evolvable representations of controllers. In this paper, we investigate one promising approach of an artificial hormone system as a control paradigm which is believed to be easily optimized by evolutionary processes. In a first step of this research, we focus on the simple task of collision avoidance. We present a brief mathematical analysis of this controller approach and an implementation of the controller on a mobile robot to check the feasibility in principle of our approach. The task is successfully accomplished and we conclude with a discussion of the hormone dynamics in the robot.

Two different approaches to a macroscopic model of a bio-inspired robotic swarm - Schmickl, Thomas; Hamann, Heiko; Wörn, Heinz; Crailsheim, Karl (Robotics and Autonomous Systems)
By compiling macroscopic models we analyze the adaptive behavior in a swarm of autonomous robots generated by a bio-inspired, distributed control algorithm. We developed two macroscopic models by taking two different perspectives: A Stock & Flow model, which is simple to implement and fast to simulate, and a spatially resolved model based on diffusion processes. These two models were compared concerning their prediction quality and their analytical power: One model allowed easy identification of the major feedback loops governing the swarm behavior. The other model allowed analysis of the expected shapes and positions of observable robot clusters. We found a high correlation in the challenges posed by both modeling techniques and we highlighted the inherent problems of inferring emergent macroscopic rules from a microscopic description of swarm behavior.

Pattern Formation as a Transient Phenomenon in the Nonlinear Dynamics of a Multi-Agent System - Hamann, Heiko; Troch, Inge; Breitenecker, F. (MATHMOD 2009 - 6th Vienna International Conference on Mathematical Modelling)

Compositional CSP Traces Refinement Checking - Wehrheim, Heike; Wonisch, Daniel (Electr. Notes Theor. Comput. Sci.)

Static Class Elements for Object-Z - Ruhroth, Thomas; Wehrheim, Heike (Electr. Notes Theor. Comput. Sci.)