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.

Measurement-Based Probabilistic Timing Analysis (MBPTA) responds to the challenge of analysing the timing behaviour of real-time software running on hardware deploying high-performance features (e.g., data caches). MBPTA provides a WCET estimate that upper-bounds the execution time of the set of paths exercised with the data input vectors provided by the user. However, in several scenarios, the user is unaware of the input vector leading to the worst-case path. In this paper we present PUB, a new method that makes the WCET estimates obtained with MBPTA a trustworthy upper-bound of the probabilistic execution time of all paths in the program, even when the user-provided input vectors do not exercise the worst-case path. This significantly reduces the requirements imposed on the user to apply MBPTA. For Malardarlen and EEMBC respectively, PUB provides WCET estimates 5% and 11% higher than the WCET estimates computed with MBPTA.

This paper presents a quantification of the timing effects that advanced processor features like data and instruction cache, pipelines, branch prediction units, and out-of-order execution units have on the worst-case execution time (WCET) of programs. These features are present in processors (e.g. PowerPC) that are being widely used in embedded and real-time systems. We present an experimental evaluation of the execution time of a series of synthetic benchmarks and real-life case studies. The execution time is evaluated using extensive testing and a simple WCET technique. We show that the most important factor in reduction of execution time is cache size (both instruction and data cache). Other factors like branch prediction and out-of-order execution have minimal improvements that are cancelled out by the pessimism of the analysis. We also argue that some of the performance gain of advanced processor features also applies to the worst case and although WCET estimates may be more pessimistic the overall impact is that they result in lower WCET estimates.

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.

A fundamental requirement for hard real-time systems is the knowledge of tasks worst case execution times (WCET). Static worst-case execution time analysis (WCET analysis), thanks to the static analysis of a piece of source code, returns an upper bound of the time required to execute it on a given hardware. Taking into account modern architectural features makes it possible to determine tight WCET bounds. Several mechanisms that use modeling and simulate some architectural feature behaviors such as instruction cache, branch prediction mechanism and pipeline have been proposed in the literature. These methods have often been designed independently from each other which leads to an integration issue. This paper proposes to formalize (through data structures) three techniques for static simulation of instruction cache, pipeline and branch prediction in order to gather them in an integrated static WCET analysis framework. Performance improvements due to the integrated approach are also given.

An important issue in building operating systems for hard real-time applications is to compute the worst-case execution times (WCET) of the operating system activities. Traditionally, this has been achieved by an exhaustive testing of the operating system, with a careful attention on the testing conditions to reproduce the worst-case execution scenario. In this paper we explore the alternative approach of using static analysis to predict off-line the WCET of the system calls of a real-time kernel, the RTEMS kernel. We give qualitative and quantitative results on the analysis of RTEMS, and draw some conclusions on the extent to which static analysis can be used on operating system code.

This article deals with the direct problem of Galois theory (identify the Galois group of a polynomial).It starts from a classical method: factorization of Lagrange resolvents over the ground field -the factorizing type of wK~chenables to identify the Galois group.The aim of the article is to lower the degrees of the resolvents to factorize over the ground field.For instance, the degrees of the resolvents to factorize in order to identify the Galois group of an irreducible polynomial of degree 10 can be reduced from 420 with the former methods to 45 with that of the article when this Galois group is imprimitive (but the method applies to primitive groups too).Thk method is based on a new result of invariant theory, that enables to get down diagonally (i.e. from an uncle to a nephew) in the graph of subgroups of the symmetric group, whereas the traditional Stauduhar method required to get down directly (i.e. from a father to its sons) in this graph.