Search

Deriving the Worst-Case Execution Time (WCET) of a task is a challenging process, especially for processor architectures that use caches, out-of-order pipelines, and speculative execution. Despite existing contributions to WCET analysis for these complex architectures, there are open problems. The single-path code generation overcomes these problems by generating time-predictable code that has a single execution trace. However, the simplicity of this approach comes at the cost of longer execution times. This paper addresses performance improvements for single-path code. We propose a time-predictable memory hierarchy with a prefetcher that exploits the predictability of execution traces in single-path code to speed up code execution. The new memory hierarchy reduces both the cache-miss penalty time and the cache-miss rate on the instruction cache. The benefit of the approach is demonstrated through benchmarks that are executed on an FPGA implementation.

This paper presents the Platform Specific Time Triggered Model (PS-TTM), a SystemC based modeling and simulation framework for time-triggered safety-critical embedded systems. The approach facilitates the modeling of Time-Triggered Architecture (TTA) based embedded systems, following a strict separation between the designs of functionality and platform. The PS-TTM provides a value and time domain deterministic simulation environment for an early functional and temporal assessment of the systems. Moreover, the framework includes a time-triggered automatic test executor that enables to perform non-intrusive simulated fault injection (SFI) to the models. The SFI makes an early dependability assessment possible, what reduces the risk of late and expensive discovery of safety related pitfalls. The feasibility of the proposed framework is illustrated with a case study, based on the modeling, simulation and validation of a simplified railway on-board signaling system.

The development and certification of safety critical embedded systems require the implementation of fault-tolerance mechanisms to ensure the safe operation of the system even in the presence of faults. These mechanisms need to be verified and validated by means of fault injection. Simulated fault injection enables an early dependability assessment that validates the correct implementation of fault-tolerance mechanisms and reduces the risk of late and expensive discovery of safety related pitfalls. This paper presents a novel modeling and simulation framework for time-triggered safety critical embedded systems. Our approach supports simulated fault injection at different abstraction levels (platform independent and platform specific models) and integrates a time-triggered automatic test executor for the early verification and validation of the systems. The feasibility of the proposed framework is illustrated with a case study where a simplified railway signaling system is modeled and simulated at different levels of abstraction.

The design of fault-tolerant real-time systems is characterized by a trade-off between performance considerations and fault-tolerance aspects. This paper presents a design approach that provides three strategies for time-redundant execution of the tasks of an application. The three execution strategies differ in their faulttolerance and performance properties such that a software designer can tailor the structure of the application software to the performance and fault-tolerance needs of an application. The paper describes the three time-redundant execution strategies and compares them with respect to fault tolerance, CPU-time requirements, and schedulability.

This paper presents a testing and simulated fault injection framework for time-triggered safety-critical embedded systems. Our approach facilitates the validation of fault-tolerance mechanisms by performing non-intrusive (SFI) on models of the system at different stages of the development, from the (PIM) to the (PSM). The SFI enables exercising the intended fault tolerance mechanisms by injecting faults in a simulated model of a system. The main benefit of this work is that it enables an early detection of design flaws in fault-tolerant systems, what reduces the possibility of late discovery of design pitfalls that might require an expensive redesign of the system. We examine the feasibility of the proposed approach in a case study, where SFI is used to assess the fault tolerance mechanisms designed in a simplified railway signaling system.

In mixed-criticality systems, applications with different levels of criticality are integrated on the same computational platform. Without a proper isolation of the different applications of such a mixed-criticality system certification gets expensive, because it has to be shown that application components of lower criticality do not hamper the correct operation of the critical applications. Therefore, all components — even the less critical ones — have to be certified for the highest criticality level. For single core platforms the use of hypervisors promises to shield applications of different criticality from each other. Timing problems may emerge when the hypervisor is ported to a multicore platform where different cores access the global memory concurrently. We show, that full temporal isolation of applications executing on different cores is only achievable if the hypervisor is run on appropriate hardware. The presented dual-layer bus arbiter enables critical applications to preserve isolation properties and also improves the execution performance of noncritical applications.

A good worst-case performance and the availability of high-quality bounds on the worst-case execution time (WCET) of tasks are central for the construction of hard realtime computer systems for safety-critical applications. Timing-predictability of the whole software/hardware system is a necessary prerequisite to achieve this. We show that a predictable architecture and the tight and seamless integration of compilation and WCET analysis is beneficial to achieve the initial two goals of good worst-case performance and the availability of high-quality bounds on the WCET of computation tasks. Information generated by the compiler improves the WCET analysis. Detailed timing feedback from the WCET analysis helps the compiler to reduce the worst case execution time. The paper describes the interface and the interaction between the industrial strength WCET analysis tool and the compiler as developed in the EU FP7 T-CREST project, and demonstrates the cooperation of these tools with an illustrative example.

Summary form only given. Multi-core processors promise a number of benefits for development of dependable embedded systems. They offer higher performance than single-core processors and consume less energy than high-speed single cores of equivalent computational power, reducing this way a number of computational nodes and wiring in a system and increasing the system robustness. Moreover, the cores of the heterogeneous multi-core processors can be tailored to match the specific functionalities of the embedded computer system. Despite these promises, multi-cores are not automatically well-suited for safety-critical and mixed-criticality embedded systems. If not carefully designed, the lack of adequate spatial and temporal partitioning and the barely analyzable worst-case timing behavior of their performance-enhancing features render the validation of claims about the dependability and correct timing behavior of applications on today's powerful multicores to be impossible. Therefore, this tutorial discusses the key architectural principles that must be followed when constructing embedded multi-core systems for safety-critical and mixed-criticality applications. Moreover, it introduces and discusses a new design methodology suitable for the implementation of such applications on the top of the multi-core systems that follow these principles.

Summary form only given. The hardware and software architectures of time-critical embedded systems are becoming too complex. As a consequence, the timing of these systems is difficult to understand and proofs about temporal correctness are hard if not impossible to obtain. We argue that we should not follow the current trends and make computers more and more complex. Instead we should design and use hardware and software architectures that are as simple as possible. When using these architectures, one should take as many decisions as possible before runtime, thus minimizing the number of scenarios in which the timing of the computer system is situation-dependent. We introduce hardware and software strategies that are smart enough to eliminate dynamic run-time decisions, thus improving the time-predictability of embedded computer systems. Using these strategies makes the timing behavior of computer systems easy to understand. Thus proofs for temporal correctness become almost trivial.

A prototype development environment for the Mars maintainable real-time system is described. The Mars design environment supports the implementation of critical real-time tasks with time editing. It uses an experimental real-time language, Modula-R, which is based on Modula-2. The Mars real-time architecture, which is the target architecture of the Mars environment, is described. To illustrate the environment, the development of a simple real-time algorithm that implements insertion sort for an array is presented. >

The tough competition among automotive companies creates a high cost pressure on the OEMs. Combined with shorter innovation cycles, testing new safety-critical functions becomes an increasingly difficult issue [4]. In the automotive industry about 55% of breakdowns can be traced back to problems in electronic systems. About 30% of these incidents are estimated to be caused by timing problems [7]. It is necessary to develop new approaches for testing the timing behavior on embedded and real-time systems. This work describes the integration of runtime measurements using an external measurement device into a framework for measurement-based worst-case execution time calculations. We show that especially for small platforms using an external measurement device is a reasonable way to perform execution time measurements. Such platforms can be identified by the lack of a time source, limited memory, and the lack of an external interface. The presented device uses two pins on the target to perform run-time measurements. It works cycle accurate for frequencies up to 200MHz, which should be sufficient for most embedded devices.

Modern processors used in embedded systems are becoming increasingly powerful, having features like caches and pipelines to speedup execution. While execution speed of embedded software is generally increasing, it becomes more and more complex to verify the correct temporal behavior of software, running on this high-end embedded computer systems. To achieve time-predictability the authors introduced a very rigid software execution model with distribution being realized based on the time-triggered communication model. In this paper we analyze the time-predictability of a preempting task-activation, running on a hardware with direct-mapped instruction caches. As one result we analyze why a task-preemption driven by a clock interrupt is not suitable to guarantee time-predictability. As a second result, we present a time-predictable task-preemption driven by an instruction counter.

In this paper, we introduce an approach for automated verification and testing of ANSI C programs for embedded systems. We automatically extract an automaton model from the C code of the SUT (system under test). This automaton model is on the one hand used for formal verification of the requirements defined in the system specification, on the other hand, we can derive test cases from this model, for both methods we use a model checker. We describe our techniques for test case generation, based on producing counterexamples with a model checker by formulating trap properties. The resulting test cases can then be applied to the SUT on different test levels. An important issue for model checking C-source code, is the correct modeling of the semantics of a C program for an embedded system. We focus on challenges and possible restrictions that appear, when model checking is used for the verification of C-source code. We specifically show how to deal with arithmetic expressions in the model checker NuSMV and how to preserve the numerical results in case of modeling the platform-specific semantics of C

With the increased use of powerful, performance-optimized hardware components in embedded systems, timing prediction is getting more and more complex. Thus while the execution speed of software is generally increasing, it is getting more and more difficult (if not infeasible) to perform an accurate and safe timing analysis of software that runs on those high-end embedded computer systems.

In this paper we introduce the development of a framework for testing safety-critical embedded systems based on the concepts of model-based testing. In model-based testing the test cases are derived from a model of the system under test. In our approach the model is an automaton model that is automatically extracted from the C-source code of the system under test. Beside random test data generation the test case generation uses formal methods, in detail model checking techniques. To find appropriate test cases we use the requirements defined in the system specification. To cover further execution paths we developed an additional, to our best knowledge, novel method based on special structural coverage criteria. We present preliminary results on the model extraction using a concrete industrial case study from the automotive domain.

In this paper we present a test framework for specifying, executing, and evaluating function (black-box) tests for I/O control blocks that are part of a Matlab/Simulink based rapid-prototyping (RP) development environment for distributed control applications for the time-triggered network protocol TTP/C. The framework uses the RP environment to create embedded test applications which are then executed in a physical test network. In doing so the test application itself acts as a test driver for the required I/O operations. Results from this application are then compared to reference results that are created by the framework from the simulation and from the test specification. Tests are specified independently of the programming language using a format that was designed for ease-of-use and extensive reuse of components in mind. Concluding we present an implementation of this framework in a resource constrained real-world corporate environment, discussing problems, design decisions, and experiences gained during its development and use

In today's technical world (e.g., in the automotive industry), more and more purely mechanical components get replaced by electro-mechanical ones. Thus the size and complexity of embedded systems steadily increases. To cope with this development, comfortable software engineering tools are being developed that allow a more functionality-oriented development of applications. The paper demonstrates how worst-case execution time (WCET) analysis is integrated into such a high-level application design and simulation tool MATLAB/Simulink-thus providing a higher-level interface to WCET analysis. The MATLAB/Simulink extensions compute and display worst-case timing data for all blocks of a MATLAB/Simulink simulation, which gives the developer of an application valuable feedback about the correct timing of the application being developed. The solution facilitates a fully-automated WCET analysis, i.e., in contrast to existing approaches the programmer does not have to provide path information.

The systematic development of fault-tolerant real-time systems with guaranteed timeliness requires an appropriate system architecture and a rigorous design methodology. Those services of the architecture that help to simplify the work of the real-time programmer are described, taking the MARS architecture as an example. Programming in the large activities, i.e., the systematic derivation of task timing parameters from the requirements specification, are then addressed. Programming to meet a time budget is discussed, and the programming interface, the programming environment, and the testing and support tools are presented. The architecture and most of the tools have been implemented and can be demonstrated on a fault-tolerant prototype application. >

Many innovations in the automotive sector involve complex electronics and embedded software systems. Testing techniques are one of the key methodologies for detecting faults in such embedded systems. In this paper, a novel cross-platform verification framework including automated test-case generation by model checking is introduced. Comparing the execution behavior of a program instance running on a certain platform to the execution behavior of the same program running on a different platform we denote cross-platform verification. The framework supports various types of coverage criteria. It turned out that end-to-end testing is of high importance due to defects occurring on the actual target platform for the first time. Additionally, formal verification can be applied for checking requirements resulting from the specification using the same model generation mechanism that is used for test data generation. Due to a novel self-assessment mechanism, the confidence into the formal models is increased significantly. We provide a case study for the Motorola embedded controller HCS12 that is heavily used by the automotive industry. We perform structural tests on industrial code patterns using a wide-spread industrial compiler. Using our technique, we found two severe compiler defects that have been corrected in subsequent releases.

To guarantee timeliness in hard real-time systems the knowledge of the worst-case execution time (WCET) for its time-critical tasks is mandatory. Accurate and correct WCET analysis for modern processor is a quite complex problem. Path analysis is required to identify a minimal set of possible execution paths. Further, the modeling of a processor’s internal states for features like caches or pipelines requires to consider possible interferences of these features.

To communicate between heterogeneous computer systems, mechanisms for data conversion are necessary. In this paper we present a portable, asymmetric data conversion method that is suitable for remote testing frameworks in embedded systems development. The described method takes the resource limitations of embedded systems into account by doing the data conversion at the testing host. The method can be implemented as platform-independent source code and it avoids the need of recompiling the code of a communication partner if the code of the other communication partner is migrated to a different platform.

The increase in the amount of functionalities provided by safety-critical systems in the last years has lead to a complexity growth in these systems. Several techniques have been developed in order to tackle this issue, including simplification strategies and the definition of time-deterministic models of computation (MoCs) and architectures, such as the Logical Execution Time MoC (LET) and the Time-Triggered Architecture (TTA) respectively. Although TTA based systems relying on the LET MoC have already been successfully applied to safety-critical systems, SystemC, the nowadays de-facto standard in HW/SW system development, does not provide a LET-based simulation engine for the modeling and assessment of these systems. With the aim to fill this gap, this paper presents the PI-TTM, a novel SystemC extension for the modeling and simulation of LET based safety-critical embedded systems.

International audience; EMWF (Embedded Workflow Framework) is an open source middleware for flexible (i.e., configurable, customizable and adaptable), user-centric automation and assistive devices and systems. EMWF 1.0 provides a light-weight workflow manager and engines on Windows CE, Windows XP Embedded, and Linux. It is for small embedded automation devices. EMWF 2.0 also provides basic message passing and real-time scheduling mechanisms and workflow communication facility. This paper describes EMWF 1.0 and extensions in EMWF 2.0, as well as case studies on workflow-based design and implementation as motivations for EMWF and the extensions.

International audience; The development of embedded systems challenges software engineers with timely delivery of optimised code that is both safe and resource-aware. Within this context, we focus on distributed systems with small, specialised node hardware, specifically, wireless sensor network (WSN) systems. Model-driven software development (MDSD) promises to reduce errors and efforts needed for complex software projects by automated code generation from abstract software models. We present an approach for MDSD based on the data-centric OMG middleware standard DDS. In this paper, we argue that the combination of DDS features and MDSD can successfully be applied to WSN systems, and we present the design of an appropriate approach, describing an architecture, metamodels and the design workflow. Finally, we present a prototypical implementation of our approach using a WSN-enabled DDS implementation and a set of modelling and transformation tools from the Eclipse Modeling Framework.

International audience; The analysis of worst-case execution times has become mandatory in the design of hard real-time systems: it is absolutely necessary to know an upper bound of the execution time of each task to determine a task schedule that insures that deadlines will all be met. The OTAWA toolbox presented in this paper has been designed to host algorithms resulting from research in the domain of WCET analysis so that they can be combined to compute tight WCET estimates. It features an abstraction layer that decouples the analyses from the target hardware and from the instruction set architecture, as well as a set of functionalities that facilitate the implementation of new approaches.

In many engineering disciplines, large systems are built from prefabricated components with known and validated properties. Components are connected via stable, understandable, and standardized interfaces. The system engineer has knowledge about the global properties of the components-as they relate to the system functions-and of the detailed specification of the component interfaces. Knowledge about the internal design and implementation of the components is neither needed, nor available in many cases. A prerequisite for such a constructive approach to system building is that the validated properties of the components are not affected by the system integration. This composability requirement is an important constraint for the selection of a platform for the component-based design of large distributed embedded systems. Component-based design is a meet-in-the middle design method. On one side the functional and temporal requirements on the components are derived top-down from the desired application functions. On the other side, the functional and temporal capabilities of the components are contained in the specifications of the available components (bottom up). During the design process a proper match between component requirements and component capabilities must be established. If there is no component available that meets the requirements, a new component must be developed. A prerequisite of any component-based design is a crystal clear component concept that supports the precise specification of the services that are delivered and acquired across the component interfaces. In real-time systems, where the temporal properties of component services are as important as the value properties, the proper notion of a component is a hardware software unit. In the first part of this presentation the different interfaces of an embedded system component will be introduced. The services of the component are provided by the linking interface (LIF) that must be precisely specified in the domains of value and time. The technology independent interface TII is used to parameterize a component to the given application environment. While a component provider must assure that the component works properly in all configurations that are covered by the parameter space, the component user is primarily interested in the correct operation of the concrete component configuration. The following parts will be concerned with the composition of components and the notion of emerging properties in systems of components.

International audience; As embedded systems take more important roles at many places, it is more important for them to be able to show the evidences of system failures. Providing such evidences makes it easier to investigate the root causes of the failures and to prove the responsible parties. This paper proposes simultaneous logging and replaying of a system that enables recording evidences of system failures. The proposed system employs two virtual machines, one for the primary execution and the other for the backup execution. The backup virtual machine maintains the past state of the primary virtual machine along with the log to make the backup the same state as the primary. When a system failure occurs on the primary virtual machine, the VMM saves the backup state and the log. The saved backup state and the log can be used as an evidence. By replaying the backup virtual machine from the saved state following the saved log, the execution path to the failure can be completely analyzed. We developed such a logging and replaying feature in a VMM. It can log and replay the execution of the Linux operating system. The experiment results show the overhead of the primary execution is only fractional.

International audience; Ubiquitous Systems are expected in the near future to have much more impact on our daily tasks thanks to advances in embedded systems, "Plug-n-Play" protocols and software architectures. Such protocols target home devices and enables automatic discovery and interaction among them. Consequently, smart applications are shaping the home into a smart one by orchestrating devices in an elegant manner. Currently, several protocols coexist in smart homes but interactions between devices cannot be put into action unless devices are supporting the same protocol. Furthermore, smart applications must know in advance names of services and devices to interact with them. However, such names are semantically equivalent but syntactically different needing translation mechanisms. In order to reduce human efforts for achieving interoperability, we introduce an approach combining ontology alignment techniques with those of Model Driven Engineering domain to reach a dynamic service adaptation.

International audience; Dynamic Quality-of-Service (QoS) management has been shown to be an effective way to make an efficient use of systems resources, such as computing, communication or energy. This is particularly important in resource-contrained embedded systems, such as vehicles, multimedia devices, etc.. Deploying dynamic QoS management requires using an appropriate schedulability test that is fast enough and ensures continued schedulability while the system adapts its configuration. In this paper we consider four utilization-based tests with release jitter, a particularly relevant feature in distributed systems, three of which were recently proposed and one is added in this work. We carry out an extensive comparison using random task sets to characterize their relative merits and we show a case study where multiple video streams are dynamically managed in a fictitious automotive application using such schedulability bounds.

International audience; Future space systems require innovative computing system architectures, on account of their size, weight, power consumption, cost, safety and maintainability requisites. The AIR (ARINC 653 in Space Real-Time Operating System) architecture answers the interest of the space industry, especially the European Space Agency, in transitioning to the flexible and safe approach of having onboard functions of different criticalities share hardware resources, while being functionally separated in logical containers (partitions). Partitions are separated in the time and space domains. In this paper we present the evolution of the AIR architecture, from its initial ideas to the current state of the art. We describe the research we are currently performing on AIR, which aims to obtain an industrial-grade product for future space systems, and lay the foundations for further work.