Single-path code aims to make WCET analysis easier by eliminating data-dependent control flow. To completely negate the need for WCET analysis, single-path code must also eliminate execution-time variability from memory accesses. To be practically useful, single-path code must be optimized to be competitive with traditional WCET-analyzed code. This paper summarizes the work in Emad Jacob Maroun's PhD dissertation titled”Compiling for Time-Predictability and Performance“. Memory access compensation ensures that singlepath code exhibits constant execution time. The generated code is optimized using an improved transformation that uses generic allocators for general-purpose and predicate registers. The repetition dominance relation is used to reduce unnecessary code execution. Lastly, a heuristic list scheduler enables single-path code to utilize the second issue slot of a dual-issue processor. In addition to achieving constant execution times on a timepredictable processor, the results show varying but significant improvements of up to 145 % in performance and a reduced code size of up to 28 %. Compared to WCET-analyzed traditional code, single-path code is mostly competitive while outright superior in several cases. However, pathological cases of poor performance are still observed.

Register allocation is a crucial step in the compilation pipeline that decides what program values occupy which physical registers. Single-path code’s use of predicated instructions instead of branching control-flow means register allocation must also allocate predicate registers. In this paper, we improve the original single-path transformation to allow generic register allocators to allocate predicate registers. Our improved transformation splits register allocation into two. First, the general-purpose registers are allocated as usual using a generic register allocator. Then, the main steps of the single-path transformation are performed while still using virtual predicate registers. Lastly, register allocation is rerun using the generic allocator to allocate the predicate registers. Our results show the improved single-path transformation increasing performance by up to 80 % and reducing code size by up to 43 % compared to the original transformation that uses a custom predicate allocator.

Single-path code is a code generation technique for real-time systems that reduces execution time variability. However, doing so can incur significant execution-time overhead and does not guarantee constant execution times. In this paper, we address the performance challenges of single-path code and solve the variability issue. We present the repetition dominance relation to identify and optimize code blocks that are always executed a fixed number of times. We show that single-path code’s instructions are uniquely easy to schedule, and we explore an extension to the Patmos architecture that allows additional instruction types in the second issue slot. Lastly, we present two techniques for ensuring that functions always perform the same number of accesses to memory, resulting in programs with constant execution time. We compare the performance of single-path code to that of statically analyzed traditional code. Our results show that single-path code’s performance is mostly competitive while outright superior in several cases. However, pathological cases of poor performance are still observed.

Time predictability is a central requirement for real-time systems. The correct behavior of such a system can only be achieved if the results of programs are ready in time to affect the environment. Execution times of modern systems can vary for many reasons, meaning complex analyses must be performed to ensure that the execution time is bounded and that a task always finishes before its deadline. Care must also be taken to ensure that nefarious actors do not exploit the varying execution time to compromise the system’s integrity. Avoiding variable execution times can greatly simplify systems, is inherently more secure, and eliminates the need for complex analyses. In this paper, we first argue for the value of having programs with constant execution times. We then show how the memory system around a processing core can affect execution times even on systems without intermediate storage like caches or scratch-pads. We present automatic compiler techniques for generating constant execution time programs and evaluate their implementation on the Patmos architecture. We show that combining our two compensation techniques is generally superior to either on their own. We compare the performance of our implementation to the estimates produced by the Platin worst-case execution time analyzer. While our implementation significantly impacts performance, it is generally manageable and has the potential for comparable execution times.

Security is gaining increasing importance in automotive systems, driven by technical innovations. For example, automotive vehicles become more open systems, allowing the communication with other traffic participants and road infrastructure. Also, automotive vehicles are provided with increased autonomy which raises severe safety concerns, and consequently also security concerns—both concerns that interweave in such systems. In this paper we present a qualitative cybersecurity analysis by comparing different time-triggered (TT) communication networks. While TT communication networks have been analysed extensively for dependability, the contribution of this work is to identify security-related benefits that TT communication networks can provide. In particular, their mechanisms for spacial and temporal encapsulation of network traffic are instrumental to improve network security. The security arguments can be used as a design guide for implementing critical communication in flexible network standards like TSN.

In this work, we present Vicuna, a timing-predictable vector coprocessor. A vector processor can be scaled to satisfy the performance requirements of massively parallel computation tasks, yet its timing behavior can remain simple enough to be efficiently analyzable. Therefore, vector processors are promising for highly parallel real-time applications, such as advanced driver assistance systems and autonomous vehicles. Vicuna has been specifically tailored to address the needs of real-time applications. It features predictable and repeatable timing behavior and is free of timing anomalies, thus enabling effective and tight worst-case execution time (WCET) analysis while retaining the performance and efficiency commonly seen in other vector processors. We demonstrate our architecture’s predictability, scalability, and performance by running a set of benchmark applications on several configurations of Vicuna synthesized on a Xilinx 7 Series FPGA with a peak performance of over 10 billion 8-bit operations per second, which is in line with existing non-predictable soft vector-processing architectures.

In order to guarantee end-to-end latency and minimal jitter in distributed real-time systems, it is necessary to provide tight synchronization between computation and communication. This requires time-predictable execution of tasks across all processing nodes, and the use of a network protocol that can provide a global time base and bounded communication latency. TTEthernet is one such industrial communication protocol. This paper investigates the synchronization of the task execution schedule with the underlying communication schedule, and we propose an open-source software framework for time-triggered end-systems. We present the implementation of a static cyclic task schedule, on a time-predictable platform that is integrated within a TTEthernet network and synchronized with the communication schedule. We evaluate the presented framework by developing a simple one-sensor, one-actuator industrial control example, distributed over three nodes that communicate over a single TTEthernet switch. The presented real-time system can exchange messages with minimal jitter as the distributed tasks are synchronized over the TTEthernet network with about 1.6 us precision. Due to the tight time synchronization, the system can operate stably with zero missed frames, using a single receiver and a single transmitter buffer.

In this paper, we present an instruction filter, a simple architecture extension that adds support for fully predicated execution to existing processor cores that do not natively support it. This makes single-path code execution and hence high quality and easily derivable worst-case execution time (WCET) information available for a wide range of processors. We have implemented the single-path instruction filter for two processors and evaluated it on the TACLe benchmark collection. The results demonstrate that despite the seeming inefficiency of single-path code, our method does not substantially increase the WCET. Therefore, running single-path code on processors with our instruction filter represents a competitive method for time-predictable code execution.

Designed for real-time systems, the Patmos instruction-set architecture's features ensure a high degree of predictability.One such feature is its dual-issue pipeline, which can issue and execute bundles of up to two instructions at a time.Executing instructions in the second issue slot is a predictable way to increase the throughput of a processor, but without dedicated support from the compiler, this benefit cannot be unlocked.A compiler generates highly predictable programs by generating single-path code.This technique produces code that always follows the same trace of instructions.While Patmos' compiler can already produce single-path code, it does not assign any instructions to the second issue-slot.This limitation is unfortunate, as single-path code inherently possesses a high degree of instruction-level parallelism.In this paper, we present a singlepath code generation technique with support for dual-issue pipelines.It can also support different bundling algorithms, which allows changing algorithms without having to edit other parts of the compiler.We present a simple bundling algorithm plugged into the single-path code generator.It looks for branches and bundles the basic blocks on each path of the branch.While this specific bundling algorithm is too simple to provide a real-world benefit, it highlights the potential that further work on bundling algorithms can unlock.

Nodes connected to a time-triggered (TT) network can access the network interface in two different ways, synchronously or asynchronously, which greatly impacts communication timing and message lifespans (i.e., the time from writing a message to its send buffer till the time when the message is read by the receiver). In this paper we present a clear timing model to reason about the timing variation possible with TT interfaces. This model facilitates the quantitative analysis of the message lifespans of synchronous and asynchronous TT interfaces. Further, we develop a tool to search for node and network configurations that minimise or maximise message lifespans. We show that choosing the right configuration for synchronous interface access can reduce message lifespan significantly (we observed a factor of 9 even for small scenarios). While industrial practice typically is to choose a slot allocation a priory, we show that optimising the slot allocation in coordination with task scheduling gives an extra edge in obtaining minimal message lifespans. For nodes with synchronous interface access, the tool determines the parameters needed to obtain minimal message lifespan and jitter.

Distributed safety-critical systems require both time-predictable task execution and communication. On the processor, the execution of the tasks is dictated by a scheduling policy, while on the network, different industrial communication protocols can be deployed to guarantee bounded message latency. In this paper, we investigate the synchronization of the task execution with the underlying communication schedule, and we propose an open-source software framework. We implement a cyclic executive task scheduling policy on a time-predictable platform and synchronize the task execution with the underlying TTEth-ernet communication schedule. We evaluate our framework by developing a simple one-sensor, one-actuator industrial control example, distributed over three nodes. The presented real-time system can exchange messages with minimal jitter, and the distributed tasks synchronize to a precision of ≈ 1.6μs.

The Patmos instruction-set architecture is designed for real-time systems. As such, it has features that increase the predictability of code running on it. One important feature is its dual-issue pipeline: instructions may be organized in bundles of two that are issued and executed in parallel. This increases the throughput of the processor in a predictable manner, but only if the compiler makes use of it.Single-path code is a code-generation technique that produces predictable executions by always following the same trace of instructions. The Patmos compiler can already produce single-path code, but it does not use the second issue slot available in the processor. This is less than ideal because the single-path transformation results in code that has a high degree of instruction-level parallelism.In this paper, we present a single-path code generator that can produce bundled instructions. It includes generic support for bundling algorithms, such that implementing them is simple and does not require changing other parts of the compiler.We also present one such bundling algorithm plugged into the single-path code generator. With it, we show that we can produce dual-issue instructions to improve performance.

Real-time control systems must adequately react to changes in system state within a time limit determined by the dynamics of the controlled system, otherwise their stability might be compromised. It is therefore essential to determine the Worst-Case Execution Time (WCET) of the control algorithms to verify that they will always be able to satisfy that constraint. However, WCET analysis is a complex process, requiring manual intervention, and the computed bounds are often grossly overestimated. We avoid the difficulties of WCET estimation by making use of the single-path paradigm for the implementation of the control algorithm for a quadcopter. By using single-path code we do not only replace the cumbersome WCET analysis with a single measurement, we simultaneously avoid the detrimental effects of response-time variability. We show that single-path code can be applied to real-time controllers and that it is practical for dramatically simplifying WCET analysis as well as eliminating variability in the execution time. Our results show that despite its apparent inefficiency, the WCET of single-path code on a time-predictable soft microprocessor rivals that of a state-of-the-art superscalar processor.

Time-triggered communication facilitates the construction of multi-component real-time systems whose components are in control of their temporal behaviour. However, the interface of a time-triggered communication system has to be accessed with care, to avoid that the temporal independence of components gets lost. This paper shows two interfacing strategies, one for asynchronous interface access (in two variants, one being the new Rate-bounded Non-Blocking Communication protocol) and one for time-aware, synchronized interface access, that allow components to maintain temporal independence. The paper describes and compares these interfacing strategies.

Time-triggered communication facilitates the construction of multi-component real-time systems whose components are in control of their temporal behavior. However, the interface of a time-triggered communication system has to be accessed with care, to avoid that the temporal independence of components gets lost. This paper shows two interfacing strategies, one for asynchonous interface access (in two variants, one being the new Rate-Bounded Non-Blocking Communication protocol) and one for time-aware, synchronized interface access, that allow components to maintain temporal independence. The paper describes and compares the interfacing strategies.

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.

Time-predictability is an essential property of software components of safety-critical hard real-time systems. Single-path code generation produces code that forces every execution to follow the same trace of instructions, thus making the execution time of code independent of its input data. This supports the time predictability of components and simplifies their worst-case execution-time analysis. In this paper we present the implementation of a single-path code generator in a compiler for a time-predictable processor. The evaluation on a real-world application shows that single-path code generation is a practicable strategy for the construction of time-predictable software components.

Real-time systems need time-predictable platforms to allow static analysis of the worst-case execution time (WCET). Standard multi-core processors are optimized for the average case and are hardly analyzable. Within the T-CREST project we propose novel solutions for time-predictable multi-core architectures that are optimized for the WCET instead of the average-case execution time. The resulting time-predictable resources (processors, interconnect, memory arbiter, and memory controller) and tools (compiler, WCET analysis) are designed to ease WCET analysis and to optimize WCET performance. Compared to other processors the WCET performance is outstanding. The T-CREST platform is evaluated with two industrial use cases. An application from the avionic domain demonstrates that tasks executing on different cores do not interfere with respect to their WCET. A signal processing application from the railway domain shows that the WCET can be reduced for computation-intensive tasks when distributing the tasks on several cores and using the network-on-chip for communication. With three cores the WCET is improved by a factor of 1.8 and with 15 cores by a factor of 5.7. The T-CREST project is the result of a collaborative research and development project executed by eight partners from academia and industry. The European Commission funded T-CREST.

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.

As systems and electrical and electronic devices are becoming more and more complex, the number of requirements is increased accordingly. Therefore, the organization, the processing and the verification of requirements has become a necessity. In automotive applications, this necessity is more pronounced because of the safety regulations imposed by authorities. Semi-formal representation is an approach that helps making the requirements more understandable and rigorous. In particular, SysML has proved to have the capabilities to represent requirements, structure and behaviour of systems and devices in a diagram-based fashion, enabling the linking different elements that define the composition and the functionalities of the desired product. While for software systems and digital hardware it has been applied successfully, very little work has yet been done for analogue and analogue-mixed signal devices. This is mainly because of the particular behaviour of such devices and the continuous quantities related to them. In this paper, we describe the modelling of requirements for an electronic power switch in SysML. We show that the description of the requirements for analogue devices is possible and emphasize its utility in a real scenario.

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.

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.

When designing modern real-time systems, which have to deliver results at specified deadlines, knowing the worst-case execution time (WCET) of software components is of utmost importance. Although there has been much research in the field of WCET analysis in the last years, with a focus on improving the accuracy of processor models and WCET-calculation methods, researchers have paid little attention to exploring the impact of the instruction set architecture (ISA) on the time predictability of the code executing on a given real-time processor. In this paper we explore ISA extensions that allow compilers to generate highly time-predictable code. To this end, an existing instruction set has been extended by a number of instructions, and the LLVM compiler framework has been adapted to use these new instructions in its assembler-code generator. The timing behavior of the generated code has been evaluated by means of an instruction-set simulator. The results of the experiments allowed us to identify a promising combination of the newly introduced instructions. The use of these instructions leads to a reduction of the number of branches in the assembler code, thus improving time predictability while still providing competitive worst-case timing.

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.

Static program analyses like stack usage analysis and worst-case execution time (WCET) analysis depend on the actual machine code generated by the compiler for the target system. As the analysis of binary code is costly, hard to diagnose and platform dependent, it is preferable to carry out parts of these analyses on a higher-level program representation. To this end, the higher-level code and the machine code need to be related, a difficult task due to the complexity of modern optimizing compilers.

Divide-and-conquer approaches to worst-case execution-time analysis (WCET analysis) pose a safety risk when applied to code for complex modern processors: Interferences between the hardware acceleration mechanisms of these processors lead to timing anomalies, i.e., a local timing change causes an either larger or inverse change of the global timing. This phenomenon may result in dangerous WCET underestimation. This paper presents intermediate results of our work on strategies for eliminating timing anomalies. These strategies are purely based on the modification of software, i.e., they do not require any changes to hardware. In an effort to eliminate the timing anomalies originating from the processor's out-of-order instruction pipeline, we explored different methods of inserting instructions in the program code that render the dynamic instruction scheduler inoperative. We explain how the proposed strategies remove the timing anomalies caused by the pipeline. In the absence of working solutions for timing analysis for these complex processors, we chose portable metrics from compiler construction to assess the properties of our algorithms.

The steadily growing embedded-systems market comprises many application domains in which real-time constraints must be satisfied. To guarantee that these constraints are met, the analysis of the worst-case execution time (WCET) of software components is mandatory. In general WCET analysis needs additional control-flow information, which may be provided manually by the user or calculated automatically by program analysis. For flexibility and simplicity reasons it is desirable to specify the flow information at the same level at which the program is developed, i.e., at the source level. In contrast, to obtain precise WCET bounds the WCET analysis has to be performed at machine-code level. Mapping and transforming the flow information from the source-level down to the machine code, where flow information is used in the WCET analysis, is challenging, even more so if the compiler generates highly optimized code. In this article we present a method for transforming flow information from source code to machine code. To obtain a mapping that is safe and accurate, flow information is transformed in parallel to code transformations performed by an optimizing compiler. This mapping is not only useful for transforming manual code annotations but also if platform-independent flow information is automatically calculated at the source level. We show that our method can be applied to every type of semantics-preserving code transformation. The precision of this flow-information transformation allows its users to calculate tight WCET bounds.

This paper explores timing anomalies in WCET analysis.Timing anomalies add to the complexity of WCET analysis and make it hard to apply divide-and-conquer strategies to simplify the WCET assessment. So far, timing anomalies have been described as a problem that occurs when the WCET of a control-flow graph is computed from the WCETs of its subgraphs, i.e., from a series decomposition. This paper extends the state of the art by (i) showing that timing anomalies can as well occur in a parallel decomposition of the WCET problem, i.e., when complexity is reduced by splitting the hardware state space and performing a separate WCET analysis for hardware components that work in parallel, (ii) proving that the potential occurrence of parallel timing anomalies makes the parallel decomposition technique unsafe (i.e., one cannot guarantee that the calculated WCET bound does not underestimate the WCET), and (iii) identifying special cases of parallel timing anomalies for which the parallel decomposition technique is safe. The latter provides an important hint to hardware designers on their way to constructing predictable hardware components.

This position paper discusses the possibility to combine organic computing and model-driven design.

The analysis of the worst-case execution time (WCET) requires detailed knowledge of the program behavior. In practice it is still not possible to obtain all needed information automatically. In this paper we present the current state of the art of WCET analysis and point to the main problems to be solved. The most eminent problem is the state problem, i.e., the precise determination of possible processor states at different program locations. The path problem refers to the fact that current tools are not able to calculate all (in)feasible paths automatically. We discuss how the main open problems manifest themselves in static and in measurement-based WCET analysis methods.

The determination of upper bounds on execution times, commonly called worst-case execution times (WCETs), is a necessary step in the development and validation process for hard real-time systems. This problem is hard if the underlying processor architecture has components, such as caches, pipelines, branch prediction, and other speculative components. This article describes different approaches to this problem and surveys several commercially available tools 1 and research prototypes.

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

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.

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

We present a new measurement-based worst-case execution time (WCET) analysis method. Exhaustive end-to-end measurements are computationally intractable in most cases. Therefore, we propose to measure execution times of subparts of the application. We use heuristic methods and model checking to generate test data, forcing the execution of selected paths to perform run-time measurements. The measured times are used to calculate the WCET in a final computation step. As we operate on the source code level, our approach is platform independent except for the run-time measurements performed on the target host. We show the feasibility of the required steps and explain our approach by means of a case study.

Worst-case execution time (WCET) analysis has become an active research area over the last decade. Various techniques have been developed to improve the WCET calculation methods for numerous features of the hardware. In parallel, attention has been paid to integrate the analysis techniques into modern software engineering processes. In this paper we give an overview about the different aspects of WCET analysis. We clarify terms and categorise features of WCET analysis tools. Therefore we present a generic framework for WCET analysis and describe its fundamental operations. We present a classification scheme to test the applicability of WCET analysis tools for certain analysis requirements.

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

The demand for predictable timing behavior is characteristic for real-time applications. Experience has shown that this property cannot be achieved by software alone but rather requires support from the processor. This situation is analyzed and mapped to a design rationale for SPEAR (Scalable Processor for Embedded Applications in Real-time Environments), a processor that has been designed to meet the specific temporal demands of real-time systems. At the hardware level, SPEAR guarantees interrupt response with minimum temporal jitter and minimum delay. Furthermore, the processor provides an instruction set that only has constant-time instructions. At the software level, SPEAR supports the implementation of temporally predictable code according to the single-path programming paradigm. Altogether, these features support writing of code with minimal jitter and provide the basis for exact temporal predictability. Experimental results show that SPEAR indeed exhibits the anticipated highly predictable timing behavior.

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.

Performing worst-case execution time (WCET) analysis on machine code with program path annotation provided at high-level source code level requires the transformation of path annotations from the source-code level to assembly/object-code level. This path-information transformation can be done outside or integrated into the compiler during code compilation. The first approach is easier to implement but lacks for the support of strong code optimizations performed by the compiler because the external tool would have to make guesses about optimizations. In this paper we present an approach for the program code compilation that integrates the transformation of program path information into the compiler. Path information is transformed through all compiler stages to the adequate path information for the corresponding assembly code level. The WCET analysis tool processes the program at assembly code level with the correctly transformed program-path information to obtain accurate runtime bounds. Several experiments were performed to demonstrate the importance of supporting the transformation of path-information in aggressively optimizing compilers.

Traditional worst-case execution-time analysis (WCET analysis) computes upper bounds for the execution times of code. This analysis uses knowledge about the execution contest of the code and about the target architecture. In contrast, the WCET analysis for reusable and portable code has to abstract from parameters that are unknown until the code is finally used. The analysis is done in two steps. The first step computes abstract WCET information to support the reuse and portability of the WCET information. The second step uses the abstract WCET information to compute concrete WCET bounds when the application context and the timing parameters of the target system are known. The paper describes each of the two analysis steps. It demonstrates how WCET information can be made portable and reusable.

The Time-Triggered Architecture (TTA) is a distributed computer architecture for highly dependable real-time systems. The core building block of the TTA is the communications protocol TTP/C. This protocol has been designed to provide non-faulty nodes with consistent data in the presence of faulty nodes. To achieve this consistency the protocol assumes that a fault is either a reception fault or a consistent send fault of some node. Although the communications protocol of the TTA uses this rather optimistic failure mode assumption, the TTA can isolate and tolerate a broader class of faults. This is possible by making intensive use of the static knowledge present in a TTA distributed computer system. This off-line available knowledge allows to build interconnection networks which transform failure modes of nodes into failure modes the communications protocol can deal with. This paper will discuss three alternative implementations of interconnection networks for the TTA which have been designed to meet different failure mode assumptions.

The paper defines a simple subset of tasking and object oriented features of the Real-Time Specification for Java that support high-integrity real time applications. The subset has been chosen to facilitate the development of efficient applications whose temporal behavior needs to be exactly predictable.

Off-line scheduling and fixed priority scheduling (FPS) are often considered as complementing and incompatible paradigms. A number of industrial applications demand temporal properties (predictability, jitter constraints, end-to-end deadlines, etc.) that are typically achieved by using off-line scheduling. The rigid off-line scheduling schemes used, however do not provide for flexibility. FPS has been widely studied and used in a number of applications, mostly due to its simple run-time scheduling, and small overhead. It can provide more flexibility, but is limited with respect to predictability, as actual start and completion times of execution depend on run-time events. In this paper we show how off-line scheduling and FPS run-time scheduling can be combined to get the advantages of both the capability to cope with complex timing constraints and flexibility. The paper assumes that a schedule for a set of tasks with complex constraints has been constructed off-line. It presents a method to analyze the off-line schedule and derive an FPS task set with FPS attributes priority, offset, and period, such that the runtime FPS execution matches the off-line schedule. It does so by analyzing the schedule and setting up inequality relations for the priorities of the tasks under FPS. Integer linear programming (ILP) is then used to find a FPS priority assignment that fulfils the relations. In case the priority relations for the tasks of the off-line schedule are not solvable we split tasks into the number of instances, to obtain a new task set with consistent task attributes. Our schedule translation algorithm keeps the number of newly generated artifact tasks minimal.

The designers of real-time systems try to avoid an under-utilization of hardware by assigning only the absolutely necessary time budget to each task. In certain cases it is also acceptable to cut the time quantum assigned to a task below its worst-case needs, provided (a) a high percentage of executions complete within this quantum and (b) the quality of the aborted computations is sufficient for further processing. In this paper we study the effect of reserving less than the worst-case execution time for different sorting algorithms. We define five metrics and use these metrics to investigate into the quality of the partial results of the sorting algorithms at the point of their termination. Further, we evaluate the sensitiveness of the results to changes in the completion rate. We present a rating of the evaluated algorithms and show how to achieve the best tradeoff between the CPU-time allocation and completion rate.

Real-time system software must be guaranteed to meet the timing constraints demanded by the application. To give such guarantees, the real-time programmer needs detailed feedback about the temporal behavior of the programmed code. The author presents a tool that computes worst-case timing information for real-time programs. The tool, called WCET analyzer (WCET stands for Worst-Case Execution Time), derives an upper bound for the execution time of a given piece of program code and provides detailed information about the worst-case behavior of that code at the programming language level. The author describes the principle of operation of the tool and the results it produces.

Analytically derived worst case execution time (WCET) bounds are prone to errors, because they often rely on information provided by the user. The paper presents a method for testing the results of static WCET analysis. The proposed test method is a blackbox test method that uses a genetic algorithm (GA) for test case generation. Important properties of the method are: (a) that it requires minimal information about possible impact data from the user and (b) that the GA guides data generation into directions that have a good chance to yield the real WCET of the program under test. Experimental results show that GA based testing produces results of high quality.

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.>

The authors propose a system architecture, MARS, which supports a strict separation of the issues of synchronization and timeliness, data transformation, and the dependability aspects (e.g., error detection, error handling, and redundancy management. The systematic development of fault-tolerant real-time systems with guaranteed timeliness requires an appropriate system architecture and a rigorous design methodology. The authors propose a system with strict separation of the issues of synchronization, dependability aspects, and data transformation. Dependability aspects are handled by the architecture. Synchronization and programming in the large are handled at the design level. The programmer only has to be concerned with a sequential program for which he has to meet a so-called time budget. The architecture and many tools have been implemented and can be demonstrated on a fault-tolerant prototype application.>