Pipelined computing is a promising paradigm for embedded system design. Designing a power management policy to reduce the power consumption of a pipelined system with nondeterministic workload is, however, nontrivial. In this article, we study the problem of energy minimization for coarse-grained pipelined systems under hard real-time constraints and propose new approaches based on an inverse use of the pay-burst-only-once principle. We formulate the problem by means of the resource demands of individual pipeline stages and propose two new approaches, a quadratic programming-based approach and fast heuristic, to solve the problem. In the quadratic programming approach, the problem is transformed into a standard quadratic programming with box constraint and then solved by a standard quadratic programming solver. Observing the problem is NP-hard, the fast heuristic is designed to solve the problem more efficiently. Our approach is scalable with respect to the numbers of pipeline stages. Simulation results using real-life applications are presented to demonstrate the effectiveness of our methods.

Pipelined computing is a promising paradigm for embedded system design. Designing the scheduling policy for a pipelined system is however more involved. In this paper, we study the problem of the energy minimization for coarse-grained pipelined systems under hard real-time constraints and propose a method based on an inverse use of the pay-burst-only-once principle. We formulate the problem by means of the resource demands of individual pipeline stages and solve it by quadratic programming. Our approach is scalable w.r.t the number of the pipeline stages. Simulation results using real-life applications as well as commercialized processors are presented to demonstrate the effectiveness of our method.

Effective power management is an important design concern for modern embedded systems. In this paper, we present an effective framework to integrate both DVS and DPM to optimize the overall energy consumption. We propose an online algorithm to determine the optimal operating frequency and mode transition of a processor based on the runtime workload. Our algorithm runs in O(n) time, where n is the number of the events stored in the system buffer. A feasibility analysis is also presented, which serves as a criteria for setting the system buffer as well as runtime schedulabilty check. The evaluations with specifications of two commercial processors show that our algorithm is more energy-efficient compared to existing schemes in the literature.

This paper presents a new multiple vehicle cooperative localization approach based on Random Finite Set (RFS) theory. Assuming vehicles are equipped with proprioceptive and exteroceptive sensors to localize the positions, a solution based on RFS statistics is therefore proposed to consider the whole group behavior instead of each vehicle. For this, we rely on Probability Hypothesis Density (PHD) filtering. Compared to other methods, our approach presents a recursive filtering algorithm that provides dynamic estimation of multiple vehicle states. The proposed method addresses the current challenges in multiple vehicle cooperative localization domain such as communication bandwidth issue, data association uncertainty and the over-convergence problem. A comparative study based on simulations demonstrates the reliability and the feasibility of the proposed approach in large scale environments.

Within the past few years, lane detection technology has become of high interest in the field of intelligent vehicles; however, robustness is still an issue. The challenge is to extract the lane markings effectively from the complex urban environment. In this paper, we present a novel approach based on Random Finite Set Statistics for estimating the position of lane markings. We rely on Probability Hypothesis Density (PHD) filtering and apply this technique to lane marking extraction in urban environment. Our method is based on two phases: an image preprocessing phase to extract pixels that potentially represent lanes and a tracking phase to identify lane markings. Compared to other approaches, our method presents a recursive filtering algorithm which extracts lane markings in the presence of clutter and non-lane markings. The experimental results exhibit the high performance of the proposed approach under various scenarios.

Timing is an important concern when designing an embedded system. While lots of researches on hard real-time systems focus on design-time analysis, monitoring the corresponding runtime behaviors are seldom investigated. In this paper, we investigate the conformity problem for runtime inputs of a hard real-time system. We adopt the widely used arrival curve model which captures the worst/best-cases event arrivals in the time interval domain and propose an algorithm to on-the-fly evaluate the conformity of the system input w.r.t. given arrival curves. The developed algorithm is lightweight in terms of both computation and memory overheads, which is particularly suitable for resource-constrained embedded systems. We also provide proofs and an Fpga implementation to demonstrate the effectiveness of our approach.

Many state-of-the-art approaches on fault-tolerant system design make the simplifying assumption that all faults are detected within a certain time interval. However, based on a detailed experimental analysis, we observe that perfect fault detection is not only an impractical assumption but even if implementable also a suboptimal design decision. This paper presents an approach that takes imperfect fault detection into account. Novel analysis and optimization techniques are developed, which distinguish detectable and undetectable faults in the overall workflow. Besides synthesizing the task schedules, our approach also decides which of the available fault detectors is selected for each task instance. Experimental results show that our approach finds solutions with several orders of magnitude higher reliability than current approaches.

The design of electric vehicles require a complete paradigm shift in terms of embedded systems architectures and software design techniques that are followed within the conventional automotive systems domain. It is increasingly being realized that the evolutionary approach of replacing the engine of a car by an electric engine will not be able to address issues like acceptable vehicle range, battery lifetime performance, battery management techniques, costs and weight, which are the core issues for the success of electric vehicles. While battery technology has crucial importance in the domain of electric vehicles, how these batteries are used and managed pose new problems in the area of embedded systems architecture and software for electric vehicles. At the same time, the communication and computation design challenges in electric vehicles also have to be addressed appropriately. This paper discusses some of these research challenges.

Time-Triggered Network-on-Chip (TTNoC) is a networking concept aiming at providing both predictable and high-throughput communication for modern multiprocessor systems. The message scheduling is one of the major design challenges in TTNoC-based systems. The designers not only need to allocate time slots but also have to assign communication routes for all messages. This paper tackles the TTNoC scheduling problem and presents an approach based on Satisfiability Modulo Theories (SMT) solving. We first formulate the complete problem as an SMT instance, which can always compute a feasible solution if exists. Thereafter, we propose an incremental approach that integrates SMT solving into classical heuristic algorithms. The experimental results show that the heuristic scales significantly better with only minor loss of performance.

An ongoing effort within the community of verification and program analysis is to raise the level of abstraction in programming by automatic synthesis. In this paper, we demonstrate how our synthesis engine GAVS+ achieves this goal by automatically creating control code for the FESTO Modular Production System. The overall approach is model-driven: we reinterpret planning domain definition language (PDDL) as a design contract to model two-player games played between control and environment, such that users can describe (i) basic abilities of hardware components, including sensors (as environment moves) and actuators (as control moves), (ii) topologies how components are interconnected, and (iii) desired specification under a restricted class of linear temporal logic. The model is processed by our game-based synthesis engine, from which intermediate code is generated. By mapping each behavioral-level action to a sequence of low-level PLC control commands, we transform the intermediate code into an executable program. The efficiency of our engine enables to synthesize every scenario presented in this paper within seconds. When the specification evolves, this implies a huge time-gain compared to manual program modification.

This paper presents a novel approach based on Random Finite Set (RFS) Statistics for estimating a vehicle's trajectory in complex urban environments by using a fixed single camera. For this, we extend our earlier works which used Probability Hypothesis Density (PHD) filtering under sensor fusion framework and are among the first to apply this technique to visual odometry in real traffic scenes. We consider features acquired from the camera as a group targets, use the PHD filter to update the overall group state and then estimate the ego-motion vector of the camera. Compared to other approaches, our approach presents a recursive filtering algorithm that provides dynamic estimation of multiple-targets states in the presence of clutter and avoids the association problem. Experimental results show that this method provides good robustness under real traffic scenarios.

This paper presents a novel approach for estimating the vehicle's trajectory in complex urban environments. In previous work, we presented a visual odometry solution that estimates frame-to-frame motion from a single camera based on Random Finite Set (RFS) Statistics. This paper extends that work by combining the stereo cameras and gyroscope sensor. We are among the first to apply RFS statistics to visual odometry in real traffic scenes. The method is based on two phases: a preprocessing phase to extract features from the image and transform the coordinates from the image space to vehicle coordinates; a tracking phase to estimate the egomotion vector of the camera. We consider features as a group target and use the Probability Hypothesis Density (PHD) filter to update the overall group state as the motion vector. Compared to other approaches, our method presents a recursive filtering algorithm that provides dynamic estimation of multiple-targets states in the presence of clutter and high association uncertainty. The experimental results show that this method exhibits good robustness under various scenarios.

Modern Multiprocessor Systems-on-Chips (MPSoCs) are ideal platforms for co-hosting multiple applications, which may have very distinct resource requirements (e.g. data processing intensive or communication intensive) and may start/stop execution independently at time instants unknown at design time. In such systems, the runtime task allocator, which is responsible for assigning appropriate resources to each task, is a key component to achieve high system performance. This paper presents a new task allocation strategy in which self-adaptability is introduced. By dynamically adjusting a set of key parameters at runtime, the optimization criteria of the task allocator adapts itself according to the relative scarcity of different types of resources, so that resource bottlenecks can be effectively mitigated. Compared with traditional task allocators with fixed optimization criteria, experimental results show that our adaptive task allocator achieves significant improvement both in terms of hardware efficiency and stability.

This paper presents an approach for the reliability-aware design optimization of real-time systems on multi-processor platforms. The optimization is based on an extension of well accepted fault- and process-models. We combine utilization of hardware replication and software re-execution techniques to tolerate transient faults. A System Fault Tree (SFT) analysis is proposed, which computes the system-level reliability in presence of the hardware and software redundancy based on component failure probabilities. We integrate the SFT analysis with a Multi-Objective Evolutionary Algorithm (MOEA) based optimization process to perform efficient reliability-aware design space exploration. The solution resulting from our optimization contains the mapping of tasks to processing elements (PEs), the exact task and message schedule and the fault-tolerance policy assignment. The effectiveness of the approach is illustrated using several case studies.

Energy-efficiency is becoming one of the most critical issues in embedded system design. In Network-on-Chip (NoC) based heterogeneous Multiprocessor Systems, the energy consumption is influenced dramatically by task allocation schemes. Although various approaches are proposed to allocate tasks in an energy-efficient way, existing work does not well explore the tradeoff between the two major power consumers, namely the processors and network links, resulting in sub optimal mappings from a system point of view. In this paper, we first extend the existing Integer Linear Programming (ILP) formulation to take both processing and communication energy into account. Thereafter, we propose a Simulated Annealing with Timing Adjustment (SA-TA) heuristic to accelerate the optimization process. While the SA-TA algorithm achieves performance very close to the global optimum, significant improvement in computation speed is observed.

In the past, model-based development focused mainly on functional and structural aspects of the system to be developed. Recently, several approaches to include timing aspects have been suggested. However, these approaches are typically applied in later development phases. Models specifying the requirements with respect to timing without focusing on a specific solution are missing. For example, few models support the specification of the allowed jitter of a system. In this paper, we identify requirements on languages for modeling the desired timing behavior of hard and soft real-time systems by analyzing different application domains. Based on these results, we evaluate existing approaches with respect to their suitability and present a suitable approach. Finally, this paper describes the application of the suggested approach in the context of an example from the automation domain.

The design of fault-tolerant automation systems is a complex task. These systems must not only satisfy real-time requirements but they must also deliver the specified functionality in the presence of both software and hardware faults. To achieve fault-tolerance, systems have to use redundancy. This redundancy is usually achieved by replicating hardware units and executing the application within a distributed system. Model-based design tools promise to reduce the complexity of the design process by raising the abstraction level. However, most of the existing tools focus only on functional aspects. Code realizing extra-functional requirements such as fault-tolerance mechanisms, communication, and scheduling is not targeted. However, this type of code makes up the majority of the code of a fault-tolerant real-time system. This paper presents FTOS, a model-based development tool for the design of fault-tolerant automation systems that focuses on code generation of extra-functional requirements and therefore complements existing tools.

In all areas of industrial production and construction, companies have to implement processes with increasing complexity to satisfy their customer's needs in respect of product quality and continuity. To fulfil these requirements, a continuous process monitoring and documentation is required to assure the process quality but without increasing production cost significantly. In our project we develop an intelligent sensor cable which can be easily integrated into industrial processes using industrial communication standards like ProfiBus. To support an easy installation process of our sensor cable, it needs to be self contained; in our case the sensors and the processing unit, required for pre-processing and sensor management, are integrated in the cable. To increase usability, the cable can also be tailored by the customer to the required length. The key application of our sensor cable is the documentation of the concrete curing processes using the integrated temperature sensors for safety critical constructions.

The increasing use of model-based tools enables further use of formal verification techniques in the context of distributed real-time systems. To avoid state explosion, it is necessary to construct verification models that focus on the aspects under consideration.In this paper, we discuss how we construct a verification model for timing analysis in distributed real-time systems.We (1) give observations concerning restrictions of timed automata to model these systems,(2) formulate mathematical representations on how to perform model-to-model transformation to derive verification models from system models, and (3) propose some theoretical criteria how to reduce the model size. The latter is in particular important, as for the verification of complex systems, an efficient model reflecting the properties of the system under consideration is equally important to the verification algorithm itself.Finally, we present an extension of the model-based development tool FTOS, designed to develop fault-tolerant systems, to demonstrate our approach.

Wireless sensor networks (WSNs) have drawn a lot of attention and a lot of work has been done to provide an efficient communication infrastructure for these systems. This paper focuses on another -not so well studied- class of embedded networks: embedded networks used for control and automation purposes. In contrast to WSNs, these networks have a comparably stable infrastructure, with a low probability of node or link failure. The main challenge for the communication in control oriented networks is the heterogeneity of the underlying infrastructure and the resource constraints already known from WSNs. We propose an adaptable communication layer that leverages existing network protocols and at the same time provides a seamless communication over heterogeneous networks and an efficient and scalable network stack for individual nodes. We show the feasibility of this approach with a demonstrator for the smart energy management in a future home automation scenario.

The development of embedded networks poses several challenges: complexity and size of the network, heterogeneity of nodes, and infrastructure dynamics. From other IT domains it is known that many of these challenges can be met by a Service Oriented Architecture (SOA). In the context of embedded networks, an application can be interpreted as a set of interacting services that produce, consume or manipulate data. However, the hard boundary conditions of embedded networks, such as limited resources and real time requirements, have to be taken into account. This paper discusses an embedded SOA (eSOA) concept based on the definition of an embedded service (eService) term and the differences to traditional Web services based SOAs. The paper describes a middleware platform that supports the execution and development of embedded network applications by employing model based code generation and a pattern based service composition model. The advantages of the approach are showcased using an application from the building automation sector, focusing on the energy management of smart buildings.

Recently, a move from traditional, network specific multimedia services to IP-based solutions could be observed. Although many of these applications have similar requirements and address the same issues, individual solutions based on specialized protocols are commonly used. This specialization prohibits the extraction and reuse of common services and hinders the interoperability between services and the integration with external components.

Model-based development has become state of the art in software engineering. A number of tools, like Mat-lab/Simulink or SCADE, are available for the automatic generation of application code on basis of models. Unfortunately, system aspects like process management, communication or fault-tolerance mechanisms are not covered by these tools. One main reason is the non-existence of appropriate models with an explicit semantic to allow the automatic code generation. In addition, there is a great need to have the possibility to extend both the model and the code generation abilities to allow a high coverage of the used platforms, since such code is platform dependent. In this paper, we will present an approach applying meta code generators using template-based code generation to achieve this extensibility and will discuss the properties of models required for the use in model-based development of system aspects for safety-critical real-time systems

Model-based development has become state of the art in software engineering. Unfortunately, the used code generators often focus on the pure application functionality. Features like automatic generation of fault-tolerance mechanisms are not covered. One main reason is the inadequacy of the used models. An adequate model must have amongst others explicit execution semantics and must be suited to support replica determinism and automatic state synchronization. These requirements are fulfilled when using the concept of logical execution time, a time-triggered approach. This approach hides the implementation details like the physical execution from the user, In contrast to other time-triggered paradigms. Within this paper, we present a solution to exploit this concept to realize major fault-tolerance mechanisms in a generic way.

Model-based development is state of the art in software engineering, due to its potential regarding automatic code synthesis. Nevertheless for embedded systems, where there exists a huge heterogeneity of used platforms, it is obvious that it is impossible to design a code generator that supports a priori all required platforms. Instead a code generator architecture is needed that is suited for an easy extensibility of the code generation ability. One possible solution is the use of template-based approaches. In this paper, we describe an approach1to develop safety-critical realtime systems by using open architecture ware, a modular MDA/MDD generator framework. We will present the tool-chain and discuss two lab applications.

Currently there are different approaches to develop fault-tolerant embedded software: implementing the system from scratch or using libraries respectively specialized hardware. By implementing from scratch the developer has all options concerning system design, the used programming language and hardware. But on the other hand the implementation is errorprone and time- and cost-intensive. The usage of libraries or specialized hardware reduces the design possibilities, while increasing the quality of the developed system and accelerating the development. We present a new technique for developing fault-tolerant systems that combines the advantages of these approaches. We suggest the implementation of reusable templates that solve different aspects of fault-tolerant systems, for example temporal synchronization. In addition we introduce a code generator that realizes a mapping of these templates into application-dependent source code.

Model based development has become the state of the art in software engineering. Unfortunately there are only few model-based tools available for the design of fault- tolerant embedded software: while there exist many different code generators for application code, the generation of system aspects like process management, communication in a distributed system and fault-tolerance mechanisms is very complex due to the heterogeneity of the embedded systems. We think that the design of an all-embracing code generator, that supports a priori all platforms (the combination of hardware, operating system and programming language) is impossible. Rather it is necessary to concentrate on a code generator architecture that allows an easy extension of the code generation ability. In this paper we present one possible solution: generating the code on the basis of templates, that solve different recurring aspects of safety-critical embedded software. By the use of a technique similar to preprocessor macros, these templates can be implemented in an application independent fashion. The code generator can then adapt these templates to the application by extracting the necessary information out of the model provided by the application developer. A first realization of this approach is also mentioned in this paper.

Although the main fault-tolerance techniques are known for a long time, there exists no consistent approach for implementing dependable applications in the sense that the fault-tolerance mechanisms are generated automatically by development tools. With the Zerberus system we developed such a tool. The main concept of Zerberus is the platform independent specification of the functional model (application tasks, interaction with environment, temporal constraints) by the developer using the Zerberus language. Based on this functional model the code for the fault-tolerance mechanisms is generated automatically for the desired platform using pre-implemented templates. Due to this automatic code generation the development process is accelerated and the developers are enabled to implement dependable application without expert knowledge of fault-tolerance techniques. Our approach offers also the possibility to accelerate the certification process by using certified templates for the fault-tolerance mechanisms.