Search

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.

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

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.

Dependable cyber-physical systems usually have stringent requirements on their response time, since failure to react to changes in the system state in a timely manner might lead to catastrophic consequences. It is therefore necessary to determine reliable bounds on the execution time of tasks. However, timing analysis, whether done statically using a timing model or based on measurements, struggles with the large number of possible execution paths in typical applications. The single-path code generation paradigm makes timing analysis trivial by producing programs with a single execution path. Single-path code uses predicated execution, where individual instructions are enabled or disabled based on predicates, instead of conditional control-flow branches. Most processing architectures support a limited number of predicated instructions, such as for instance a conditional move, but single-path code benefits from fully predicated execution, where every instruction is predicated. However, few architectures support full predication, thus limiting the choice of processing platforms. We present a novel approach that adds support for fully predicated execution to existing processor cores which do not natively provide it. Single-path code is generated by restructuring regular machine code and replacing conditional control-flow branches with special instructions that control the predication of subsequent code. At runtime an instruction filter interprets these predicate-defining instructions, computes and saves predicates and filters regular instructions based on the predicate state, replacing inactive instructions with a substitute that has no effect (e.g. a NOP). We are implementing this single-path filter for the LEON3 and the IBEX processors.

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.

When building real-time systems out of networked components, the use of temporal-firewall interfaces between the components supports a composable system design. This paper shows that, depending on the requirements of an application, the temporal-firewall interfaces of a time-triggered communication system can be accessed in two ways, either as data-sharing interfaces with asynchronous access or as time-aware interfaces with time-synchronized access. The paper describes each of these two ways of interfacing with a time-triggered communication system and characterizes their differences.

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.

With evolution in Cyber-Physical Systems, the dependence and conflicts among dependability attributes (safety, security, reliability, availability etc) have become increasingly complex. We can not consider these dependability attributes in isolation, therefore, combined approaches for safety, security and other attributes are required. In this document, we provide a matrix based approach (inspired from ANP (Analytical Network Process)) for combined risk assessment for safety and security. This approach allows combined risk assessment considering dependence and conflict among attributes. The assessment results for different dependability attributes (such as safety, security etc.) are provided in the ANP matrix. We will discuss approaches such as Fault Tree Analysis (FTA), Stochastic Colored Petri Net (SCPN) Analysis, Attack Tree Analysis (ATA), Failure Mode Vulnerability and Effect Analysis (FMVEA) for evaluation of concerned attributes and achieving our goal of combined assessment.

Trustable Worst-Case Execution-Time (WCET) bounds are a necessary component for the construction and verification of hard real-time computer systems. Deriving such bounds for contemporary hardware/software systems is a complex task. The single-path conversion overcomes this difficulty by transforming all unpredictable branch alternatives in the code to a sequential code structure with a single execution trace. However, the simpler code structure and analysis of single-path code comes at the cost of a longer execution time. In this paper we address the problem of the execu- tion performance of single-path code. We propose a new instuction-prefetch scheme and cache organization that uti- lize the \knowledge of the future" properties of single-path code to reduce the main memory access latency and the number of cache misses, thus speeding up the execution of single-path programs.

In this paper we address the problem of improving the instruction cache performance for single-path code. The properties of single-path code allow us to align single-path loops within the cache in order to reduce the number of cache misses during the loop execution. We propose an algorithm that categorizes loops in a simple way so that the loops can be aligned and NOP instructions can be inserted to support this loop alignment. Our experimental results show the predictability for cache misses in single-path loops and demonstrate the benefit of the single-path loop alignment.

This paper examines if monitoring of task-execution times can be used to detect errors, so that undesired system behavior and failures of real-time systems can be averted early. To this end, the paper investigates if respectively how the temporal behavior of algorithms changes in the presence of errors that have been caused by hardware faults. We used software-implemented fault injection on a number of benchmark programs to create errors and performed runtime measurements for the altered benchmarks to check if the observed execution times are below or above minimum respectively maximum execution-time bounds of the code. Our results show that up to 70% of errors that are undetectable with other standard techniques can be detected with this simple execution-time monitoring method. The method thus provides an additional layer of protection against errors. It can be implemented with reasonable effort and overhead.

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

Modern vehicles are increasingly software intensive and connected. The potential hazards and economic losses due to cyberattacks have become real and eminent in recent years. Consequently, cybersecurity must be adequately addressed among other dependability attributes such as safety and reliability in the automotive domain. J3061, officially published in January 2016 by SAE International, is a much anticipated standard for cybersecurity for the automotive industry. It fills an important gap which is previously deemed irrelevant in the automotive domain. In this paper, we report our activities of applying J3061 to security engineering of an automotive Electronic Control Unit (ECU) as a communication gateway. As an ongoing work, we share our early experience on the concept phase of the process, with a focus on the part of Threat Analysis and Risk Assessment (TARA). Based on our experience, we propose improvements and discuss its link to ISO 26262.

Safety-critical Cyber-physical Systems (CPS) in vehicles are becoming more and more complex and interconnected. There is a pressing need for holistic approaches for safety and security analysis to address the challenges. System-Theoretic Process Analysis (STPA) is a top-down safety hazard analysis method, based on systems theory especially aimed at such systems. In contrast to established approaches, hazards are treated as a control problem rather than a reliability problem. STPA-Sec extends this approach to also include security analysis. However, when we applied STPA-Sec to real world use cases for joint safety and security analysis, a Battery Management System for a hybrid vehicle, we observed several limitations of the security extension. We propose improvements to address these limitations for a combined safety and security analysis. Our improvements lead to a better identi cation of high level security scenarios. We evaluate the feasibility of the improved co-analysis method in a self-optimizing battery management system. We also discuss the general applicability of STPA-Sec to high level safety and security analysis and the relation to automotive cybersecurity standards.

Internet of Things represents a challenge in the automotive industry development, as it demands for innovation, integration, safety and security. These lead to highly sophisticated requirements set for the design process. The difficulty of managing natural language requirements may lead to inherent errors such as incompleteness, ambiguousness, etc. Adding formality to the requirements is recognized by the community to overcome these drawbacks. In this paper, we present a methodology for SoC design support by introducing semi-formalization to the requirements. The methodology allows the reuse by defining requirements patterns for the most frequently used components or mechanisms. The reuse of the requirement patterns drastically decreases the semi-formalization time and covers 60% of reusable components requirements. The methodology is applied on sophisticated automotive application: Airbag System.

Trustable Worst-Case Execution-Time (WCET) bounds are a necessary component for the construction and verification of hard real-time computer systems. Deriving such bounds for contemporary hardware/software systems is a complex task. The single-path conversion overcomes this difficulty by transforming all unpredictable branch alternatives in the code to a sequential code structure with a single execution trace. However, the simpler code structure and analysis of single-path code comes at the cost of a longer execution time. In this paper we address the problem of the execution performance of single-path code. We present a new cache organization that utilizes the principle of locality of single-path code to reduce cache miss latency and cache miss rate. The proposed cache memory architecture combines cache prefetching and cache locking, so that the prefetcher capitalizes on spatial locality while the locker makes use of temporal locality. The demonstration section shows how these two techniques can complement each other.

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.

The execution time of software for hard real-time systems must be predictable. Further, safe and not overly pessimistic bounds for the worst-case execution time (WCET) must be computable. We conceived a programming strategy called WCET-oriented programming and a code transformation strategy, the single-path conversion, that aid programmers in producing code that meets these requirements. These strategies avoid and eliminate input-data dependencies in the code. The paper describes the formal analysis, based on abstract interpretation, that identifies input-data dependencies in the code and thus forms the basis for the strategies provided for hard real-time code development.

The goal of this paper is to evaluate the real-time specification for Java proposal by performing several case studies. These case studies include: an extensible general resource controller; atomic action support infrastructure; unbounded and imprecise computations. They have been used previously by the Ada community to evaluate the efficacy of the Ada concurrency and real-time models. Our results indicate that the Real-Time Specification for Java is expressive enough to cope with the demands of real-time concurrent programming. If it can be implemented efficiently, it will provide an alternative to Ada 95 for programming real-time systems.

International audience; Real-time systems need to be time-predictable in order to prove the timeliness of all their time-critical responses. While this is a well-known fact, recent efforts of the community on concretizing the predictability of task timing have shown that there is no common agreement about what the term time-predictability exactly means. In this paper we propose a universal definition of time-predictability that combines the essence of different discussions about this term. This definition is then instantiated to concrete types of time-predictability, like worst-case execution time (WCET) predictability. Finally, we introduce the concept of a timing barrier as a mechanism for constructing time-predictable systems.

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.

Increasingly complex systems lead to an interweaving of security, safety, availability and reliability concerns. Most dependability analysis techniques do not include security aspects. In order to include security, a holistic risk model for systems is needed. In our novel approach, the basic failure cause, failure mode and failure effect model known from FMEA is used as a template for a vulnerability cause-effect chain, and an FMEA analysis technique extended with security is presented. This represents a unified model for safety and security cause-effect analysis. As an example the technique is then applied to a distributed industrial measurement 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.

Traditional worst-case execution time (WCET) analysis interfaces to the user either through high-level language source code or assembly/machine code. This paper demonstrates how WCET analysis can be integrated into high-level application design and simulation tools like Matlab/Simulink, thus providing a higher-level interface to WCET analysis. The paper shows necessary restrictions and adaptions to Matlab/Simulink that make code generated from the tool chain amenable to WCET analysis. It presents the interface between the Matlab/Simulink block set and WCET analysis and explains the steps performed during WCET analysis.

SETTA addresses the systems engineering of safety-critical distributed real¬time systems with a special focus on time-triggered architectures. An innovative meth¬odology and a corresponding engineering environment is developed which aims for a higher maturity at early development steps. Key features are the support for a virtual systems integration and the tighter interconnection between the functional development process and the safety analysis process. The supporting tool components are designed and implemented in the course of the SETTA project. The methodology is evaluated by pilot applications from the automotive, aerospace, and railway domain.

A development process for safety-critical real-time computer systems has to emphasize the importance of time. On the one hand, such a development process has to be based on hardware and software technology that supports predictability in the time domain. On the other hand, the development process has to provide tools for assessing and verifying the correctness of the timing of both the hardware and the software components of the real-time systems being developed. Together with schedulability analysis, Worst-case execution time analysis (WCET analysis) forms the basis for establishing confidence into the timely operation of a real-time system. WCET analysis does so by computing (upper) bounds for the execution times of the tasks in the system. These bounds are needed for allocating the correct CPU time to the tasks of an application. They form the inputs for schedulability tools, which test whether a given task set is schedulable (and will thus meet the timing requirements of the application) on a given target system. While schedulability analysis is one of the traditional fields of investigation in real-time systems research, WCET analysis caught the attention of the research community only about ten years ago (Kligerman and Stoyenko, 1986; Mok et al., 1989; Puschner and Koza, 1989; Shaw, 1989). In the last decade, however, more and more research groups started to put a focus on WCET analysis. As a result, substantial progress has been made in this area in a relatively short time. After ten years of research in the field, it is appropriate to have a special issue on WCET analysis. It is the goal of this special issue to review the achievements in WCET analysis and to report about the recent advances in this field. In the following section we will define the problem area of WCET analysis and thus clarify the issue WCET analysis is dealing with— still many people mix up execution-time analysis and response-time analysis. We will then summarize the subproblems of WCET analysis and provide an overview of previous contributions to the state of the art in this field. At the end of the introduction we will give an overview to the research papers that have been selected for this special issue.

In hard real-time systems tasks must meet their deadlines under guarantee. Soft real-time tasks may miss deadlines occasionally, as long as the entire system can provide the specified quality of service. In this paper we investigate the hard and soft real-time performance of sorting algorithms and compare it to their average performance. We show in which way the adequacy of an algorithm depends on the demanded performance criterium (hard, soft, or non real-time). The results provide a guideline to select the right sorting algorithm for a given application.

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.

The computation of Worst-Case Execution Times (WCETs) of tasks involves the description of possible execution paths on source level, the translation of the program and the path information to the machine level, the timing analysis at the machine level, and the documentation of the timing at the source level. These steps of WCET analysis strongly suggest the cooperation between compilers and machine-level WCET tools, and in fact some prototype compilers/WCET analyzers exist. To this date there exists, however, no commercial compiler that supports WCET analysis. This paper describes a light-weight approach to WCET analysis that does not depend on a specific compiler and thus reduces the dependency on compiler builders. The approach uses a tool to read the path information contained in the source code and map this information onto the assembler program. A low-level WCET analysis tool then computes the desired timing information of the annotated assembler program. Experiments with a simple prototype tool demonstrate the feasibility of the approach for simple programs and a moderately optimizing compiler.

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.

The knowledge of program execution times is crucial for the development and the verification of real-time software. Therefore, there is a need for methods and tools to predict the timing behavior of pieces of program code and entire programs. This paper presents a novel method for the analysis of program execution times. The computation of MAximum eXecution Times (MAXTs) is mapped onto a graph-theoretical problem that is a generalization of the computation of a maximum cost circulation in a directed graph. Programs are represented by T-graphs, timing graphs, which are similar to flow graphs. These graphs reflect the structure and the timing behavior of the code. Relative capacity constraints, a generalization of capacity constraints that bound the flow in the edges, express user-supplied information about infeasible paths. To compute MAXTs, T-graphs are searched for those execution paths which correspond to a maximum cost circulation. The search problem is transformed into an integer linear programming problem. The solution of the linear programming problem yields the MAXT. The special merits of the presented method are threefold: It uses a concise notation to characterize the static structure of a program and its possible execution paths. Furthermore, the notation allows for a description of the feasible paths through the program code that characterizes the behavior of the code sufficiently to compute the exact maximum execution time of the program – not just a bound thereof. Finally, linear program solving does not only yield maximum execution times, but also produces detailed information about the execution time and the number of executions of every single program construct in the worst case. This knowledge is valuable for a more comprehensive analysis of the timing of a program.

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.In this article, we present a novel representation called control-flow relation graphs, which provide an accurate model of the control-flow relation between machine code and the compiler's intermediate representation. In order to facilitate the integration of our approach in existing compiler frameworks, we develop a construction algorithm that builds the control-flow relation graph from partial mappings provided by the compiler. The WCET calculation method for control-flow relation graphs processes flow information from both the intermediate representation and machine code. Furthermore, we demonstrate the transformation of flow information from the IR to the machine code level, in order to use existing industrial-strength WCET analysis tools operating on machine code. We implemented the construction algorithm within the LLVM compiler framework, along with an implementation of the combined WCET calculation method.The evaluation demonstrates that the approach is able to relate bitcode (LLVM's intermediate representation) and machine code in a precise way, with a WCET increase of at most 2% when using flow facts on the bitcode level, compared to equivalent ones on the machine-code level. As the methods presented in this article provide a cost-effective way to reuse platform independent flow information, they have the potential to simplify WCET analysis, and popularize its use in the development process of real-time systems.

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.