The complexity and size of Autonomous Driving (AD) software are comparably higher than that of software implementing other (standard) functionalities in the car. To make things worse, a big fraction of AD software is not specifically designed for the automotive (or any other critical) domain, but the mainstream market. This brings uncertainty on to which extent AD software adheres to guidelines in safety standards. In this paper, we present our experience in applying ISO 26262 -- the applicable functional safety standard for road vehicles -- software safety guidelines to industrial AD software, in particular, Apollo, a heterogeneous Autonomous Driving framework used extensively in industry. We provide quantitative and qualitative metrics of compliance for many ISO 26262 recommendations on software design, implementation, and testing.

This paper describes four impact case studies where real-time systems research has been successfully transferred into industrial practice. In three cases, the technology created was translated into a viable commercial product via a start-up company. This technology transfer led to the creation and sustaining of a large number of high technology jobs over a 20 year period. The final case study involved the direct transfer of research results into an engineering company. Taken together, all four case studies have led to significant advances in automotive electronics and avionics, providing substantial returns on investment for the companies using the technology.

Static timing analysis is the state-of-the-art practice of ascertaining the timing behavior of current-generation real-time embedded systems. The adoption of more complex hardware to respond to the increasing demand for computing power in next-generation systems exacerbates some of the limitations of static timing analysis. In particular, the effort of acquiring (1) detailed information on the hardware to develop an accurate model of its execution latency as well as (2) knowledge of the timing behavior of the program in the presence of varying hardware conditions, such as those dependent on the history of previously executed instructions. We call these problems the timing analysis walls. In this vision-statement article, we present probabilistic timing analysis , a novel approach to the analysis of the timing behavior of next-generation real-time embedded systems. We show how probabilistic timing analysis attacks the timing analysis walls; we then illustrate the mathematical foundations on which this method is based and the challenges we face in the effort of efficiently implementing it. We also present experimental evidence that shows how probabilistic timing analysis reduces the extent of knowledge about the execution platform required to produce probabilistically accurate WCET estimations.

Performance demand of Critical Real-Time Embedded (CRTE) systems implementing safety-related system features grows at an exponential rate. Only modern semiconductor technologies can satisfy CRTE systems performance needs efficiently. However, those technologies lead to high failure rates, thus lowering survivability of chips to unacceptable levels for CRTE systems. This paper presents SESACS architecture (Surviving Errors in SAfety-Critical Systems), a paradigm shift in the design of CRTE systems. SESACS is a new system design methodology consisting of three main components: (i) a multicore hardware/firmware platform capable of detecting and diagnosing hardware faults of any type with minimal impact on the worst-case execution time (WCET), recovering quickly from errors, and properly reconfiguring the system so that the resulting system exhibits a predictable and analyzable degradation in WCET; (ii) a set of analysis methods and tools to prove the timing correctness of the reconfigured system; and (iii) a white-box methodology and tools to prove the functional safety of the system and compliance with industry standards. This new design paradigm will deliver huge benefits to the embedded systems industry for several decades by enabling the use of more cost-effective multicore hardware platforms built on top of modern semiconductor technologies, thereby enabling higher performance, and reducing weight and power dissipation. This new paradigm will further extend the life of embedded systems, therefore, reducing warranty and early replacement costs.

While hardware caches are generally effective at improving application performance, they greatly complicate performance prediction. Slight changes in memory layout or data access patterns can lead to large and systematic increases in cache misses, degrading performance. In the worst case, these misses can effectively render the cache useless. These pathological cases, or ``cache risk patterns'', are difficult to predict, test or debug, and their presence limits the usefulness of caches in safety critical real-time systems, especially in hard real-time environments.In this paper, we explore the effect of randomized cache replacement policies in real-time systems with stringent timing constrains. We present simulation-based results on representative examples that illustrate the problem of performance anomalies with standard cache replacement policies. We show that, by eliminating dependencies on access history, randomized replacement greatly reduces the risk of these cache-based performance anomalies, enabling probabilistic worst-case execution time analysis.

The increasing demand for new functionalities in current and future hard real-time embedded systems like automotive, avionics and space industries is driving an increase in the performance required in embedded processors. Multicore processors represent a good design solution for such systems due to their high performance, low cost and power consumption characteristics. However, hard real-time embedded systems require time analyzability and current multicore processors are less analyzable than single-core processors due to the interferences between different tasks when accessing shared hardware resources. In this paper we propose a multicore architecture with shared resources that allows the execution of applications with hard real-time and non hard real-time constraints at the same time, providing time analizability for the hard real-time tasks so that they can meet their deadlines. Moreover our architecture proposal provides high-performance for the non hard real-time tasks.

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.

This paper presents a framework for combining low-level measurement data through high-level static analysis techniques on instrumented programs in order to generate WCET estimates, for which we introduce the instrumentation point graph (IPG). We present the notion of iteration edges, which are the most important property of the IPG from a timing analysis perspective since they allow more path-based information to be integrated into tree-based calculations on loops. The main focus of this paper, however, is an algorithm that performs a hierarchical decomposition of an IPG into an Itree to permit tree-based WCET calculations. The Itree representation supports a novel high-level structure, the meta-loop, which enables iteration edges to be merged in the calculation stage. The timing schema required for the Itree is also presented. Finally, we outline some conclusions and future areas of interest

With modern processors and more dynamic application requirements it is becoming increasingly difficult to produce tight upper bounds on the worst-case execution time of real-time tasks. As a result, at run-time, considerable spare CPU capacity (termed gain time) becomes available that must be usefully employed if cost effective real-time systems are to be engineered. In this paper we introduce a scheme by which gain time is exploited by retrospectively reassigning execution time from a task’s own budget to the gain time that later become available. As a result of changing the system’s execution history, spare capacity is immediately reallocated and hence preserved. The proposed scheme is shown to work with fixed priority dispatching, the use of servers to provide temporal firewalls, and other capacity sharing approaches. Evaluations are provided via simulations.

The run-time characteristics of Java, such as high frequency of method invocation, dynamic dispatching and dynamic loading, make Java more difficult than other object-oriented programming languages, such as C++, for conducting Worst-Case Execution Time (WCET) analysis. To offer a more flexible way to develop object-oriented real-time applications in the realtime Java environment without loss of predictability and performance, we propose a novel gain time reclaiming framework integrated with WCET analysis. This paper demonstrates how to improve the utilisation and performance of the whole system by reclaiming gain time at run-time. Our approach shows that integrating WCET with gain time reclaiming can not only provide a more flexible environment, but it also does not necessarily result in unsafe or unpredictable timing behaviour.

For priority based buses such as CAN, worst case response time analysis is able to determine whether messages always meet their deadlines. This can include system models with bounded network faults. However the worst-case scenario (the critical instant) used by the analysis is extremely pessimistic compared to the rest of the invocations in the hyperperiod. We use weakly hard constraints to provide upper bounds on the maximum number of missed deadlines under fault conditions. By allowing some deadlines to be missed (around the critical instant) the weakly-hard schedulability of the system can be guaranteed at much higher levels of faults. This paper presents a response time based formulation that provides a guarantee on the weakly-hard schedulability of messages. Simulation results based on CAN and the Latest Send Time-CAN protocol show that because of the pessimism of the approach, in fact almost all messages meet their deadlines.

Most WCET analysis techniques only provide an upper bound on the worst case execution time as a constant value. However, it often appears that the execution time of a piece of code depends on the sizes or values of its input data or local parameters. The WCET of a function call may vary depending on the caller and parameters. We propose an approach to express the WCET of a program or sub-program as a symbolic expression. The obtained parametric WCET can then be later evaluated using the knowledge of input data and system configuration parameters. In this paper we present the concept of scope-tree as a generalisation of the traditional syntax tree representation of programs. In addition to their WCET, scopes are associated with an expression stating their maximum execution frequency and some variable declarations. These variables may be used for example to express data-dependent number of iterations or non-rectangular loops. We also present how the scope tree may be used to express inter-scope relations (e.g. mutually exclusive paths, loop down-sampling). Finally, this paper presents the use of scope-trees and scope-tree modifications on an example.

Traditional approaches for worst case execution time (WCET) analysis produce values which are very pessimistic if applied to modern processors. In addition, end to end measurements as used in industry produce estimates of the execution time that potentially underestimate the real worst case execution time. We introduce the notion of probabilistic hard real-time systems which have to meet all the deadlines but for which a (high) probabilistic guarantee suffices. We combine both measurement and analytical approaches into a model for computing probabilistically bounds on the execution time of the worst case path of sections of code. The idea of the technique presented is based on combining (probabilistically) the worst case effects seen in individual blocks to build the execution time model of the worst case path of the program (such case may have not been observed in the measurements). We provide three alternative operators for the combination based on whether the information of their dependency is known. Experimental evaluation of a two case study shows extremely low probabilities of the values obtained by traditional analysis.

The key to the next generation real-time systems is flexible scheduling mechanisms that guarantee hard deadlines and use available spare resources to maximise total system utility. This is a multicriteria scheduling problem. It is argued that common approaches like eager slack usage and mandatory first schemes are not only not optimal but nor adequate for a wide class of process models. It is also shown that a late acceptance test model is preferable to an early acceptance test model due to the uncertainty of future behaviour of the system. The discussion is complemented with simulation results.

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.

A weakly hard real-time system is a system that can tolerate some degree of missed deadlines provided that this number is bounded and guaranteed off-line. In this paper we present an on-line scheduling framework called Bi-Modal Scheduler (BMS) for weakly-hard real-time systems. It is characterised by two modes of operation. In normal mode tasks can be scheduled with a generic scheduler (possibly best-effort). Weakly hard constraints are guaranteed to be satisfied by switching, whenever necessary, to a panic mode for which schedulability tests exist that guarantee that deadlines are met. Due to the sources of pessimism in the analysis (mainly WCET and critical instant assumptions) the worst case situations may never arise, thus almost all the time all deadlines are met, only at peak loads some deadlines may be missed, however the behaviour of the system is predicable and bounded This allows building systems which maximise resource usage during normal operation and that resort to a guaranteed and predictable performance degradation specified by the weakly hard constraints should a transient overload arise.

In a hard real-time system, it is assumed that no deadline is missed, whereas, in a soft or firm real-time system, deadlines can be missed, although this usually happens in a nonpredictable way. However, most hard real-time systems could miss some deadlines provided that it happens in a known and predictable way. Also, adding predictability on the pattern of missed deadlines for soft and firm real-time systems is desirable, for instance, to guarantee levels of quality of service. We introduce the concept of weakly hard real-time systems to model real-time systems that can tolerate a clearly specified degree of missed deadlines. For this purpose, we define four temporal constraints based on determining a maximum number of deadlines that can be missed during a window of time (a given number of invocations). This paper provides the theoretical analysis of the properties and relationships of these constraints. It also shows the exact conditions under which a constraint is harder to satisfy than another constraint. Finally, results on fixed priority scheduling and response-time schedulability tests for a wide range of process models are presented.

Addresses the problem of performing worst-case execution time (WCET) analysis of Java Byte Code (JBC), which may be generated from different compilers and from different source languages. The motivation for the framework presented is to provide WCET analysis which is portable and therefore more likely to be used in an industrial context. Two issues are addressed in this paper: how to extract data flow and control flow information from JBC programs, and how to provide a compiler-/language-independent mechanism to introduce WCET annotations in the source code. We show that an annotation mechanism based on calls to a static class with empty methods result in similar code when generated by Java or Ada compilers.

The issue of using the sporadic server (SS) for scheduling aperiodic tasks has received new attention under the POSIX standard as it has been proposed in P1003.1 d, the additional real-time extensions to POSIX. The SS has been traditionally considered a better approach to the deferrable server (DS) due to its supposed higher achievable utilisation. However, SS also has higher implementation complexity. Nevertheless, the analysis of the comparisons performed from several authors between DS and SS is not conclusive. A review on fixed priority servers is presented with a new parameter selection technique and comprehensive performance analysis based on simulation techniques. With this parameter selection, it is shown that no server performs significantly better than the other in most of the situations. This suggests that future POSIX revisions for real-time support should also consider mechanisms by which other types of servers could be implemented.

The problem of effectively scheduling soft tasks whilst guaranteeing the behaviour of hard tasks has been addressed in many papers and a large number of techniques have been proposed. The dual priority mechanism is an intuitively simple method with low overheads. A hard task is assigned two priorities. Upon invocation, the task starts executing with a low priority and it is promoted to a high priority at a time that will guarantee that its deadline is met. Soft tasks are assigned medium priorities; they can thus preempt any hard task that is executing before its promotion time. To increase the capacity for soft tasks, and therefore the effectiveness of the real-time system, hard tasks may be assigned a (/sub m//sup n/)-hard (read n in m) temporal constraint. This implies that the task must meet n deadlines in any m invocations. This paper addresses the combination of such constraints and dual priority scheduling. This approach reduces the gap between dynamic priority and fixed priority scheduling with the goal of reducing the average response time of soft tasks.