PROARTIS will define novel hardware and software architectures for critical real-time embedded systems that, thanks to randomized timing behaviour, will ensure negligible probability of pathologically long execution times. This will enable a truly probabilistic worst-case execution time analysis that can be used in certification arguments.

Main Objectives

The overarching objective of the PROARTIS project is to facilitate a probabilistic approach to timing analysis. The proposed approach will concentrate on proving that pathological timing cases can only arise with negligible probability, instead of struggling to eradicate them, which is arguably not possible and could severely degrade performance. This will be a major turn from previous approaches that seek analyzability by trying to predict with cycle accuracy the state of hardware and software through analysis.

To summarize:
The central hypothesis of PROARTIS is that new advanced hardware/software features enabling truly randomized timing behaviour can be defined for use in critical real-time embedded (CRTE) systems. This paradigm shift will permit probabilistic analysis techniques to be used effectively in arguments of system verification and certification, by demonstrating that the probability of pathological execution times is negligible.

The techniques developed in PROARTIS will enable probabilistic guarantees of timing correctness to be derived. For example, if the reliability requirements placed on a sub-system indicate that the probability of a timing failure (a WCET violation) must be less than 10^-9 per hour of operation, then the analysis techniques developed in PROARTIS shall translate this requirement into a probabilistic worst-case execution time guarantee for the sub-system. Probabilistic analysis effectively provides a continuum of worst-case execution times (WCET) for different confidence levels. Thus a sub-system may have a probability of 10^-8 per hour of exceeding an execution time of 1.5 ms, and probabilities of 10^-9, and 10^-10 per hour of exceeding 1.55 ms and 1.59 ms, respectively. The main idea of PROARTIS is that for future CRTE systems, such probabilistic guarantees offer significant advantages over deterministic approaches which attempt to make absolute guarantees, thereby severely limiting the opportunity of use of advanced hardware features and inevitably attaining lesser performance.

Technical Approach

The technical approach of the project is to develop new hardware and software architectures that are amenable to probabilistic analysis, and to propose novel and effective probabilistic timing analysis methods. The project will work along three main axes:

1. Architectural Design Principles. Definition of hardware and software design guidelines that will allow CRTE system designers to benefit from randomisation properties. These properties permit to take benefit from high performance hardware features as well as more complex software systems.
2. Probabilistic Timing Analysis. Definition of a new analysis paradigm that exploits the randomisation properties of the proposed architecture. The new probabilistic approach will enable the timing analysis of the new high performance hardware features as well as more complex software systems. As a result of this new analysis paradigm, the project will develop a new probabilistic WCET analysis method and tool.
3. Verification and Certification. Based on the outcomes of (1) and (2), development of probabilistic arguments that can be used effectively in the verification and certification of CRTE systems.

Key Issues

The main challenge of the PROARTIS project is to foster a paradigm shift from deterministic to randomised timing behaviour in CRTE systems. In the past, strong arguments that could be used in certification have been based on understanding the behaviour of the whole system at the level of processor cycle. This approach is becoming increasingly untenable in practicality, error proneness and cost against new-generation hardware technologies, including of course the pervasive multi core systems. The PROARTIS project moves away from timing-deterministic systems towards timing-randomised systems that exhibit truly independent timing behaviour and therefore enable the application of the law of large numbers to (probabilistically) predict the behaviour of extreme (i.e., long) execution times. The benefits of this novel approach are potentially very large. Strong emphasis is put in the project on the issues that may arise with regard to system validation and on the quantification of the benefits that the approach developed may bring.

Expected impact

The PROARTIS project will facilitate the production of analysable CRTE systems on advanced hardware platforms with features such as memory hierarchies and multi core processors. PROARTIS has the following overall strategic industrial goals:

1. Increased performance, reliability and reduced costs by enabling CRTE systems to take full advantage of advanced hardware like deep memory hierarchies and multi core processors. The use of these features will allow designers to schedule more tasks while reducing the weight, power consumption and the size of the whole system and maintaining the desired predictability. It will also reduce the risk of temporal budget overruns. Application-level tasks will have an execution behaviour free (with sufficient low probability) from pathological temporal overruns.
2. Increased productivity by enabling software engineers to develop more complex real-time software systems through timing-aware systems that reveal crucial timing details while dramatically simplifying analysis. For example, memory latencies will be predicted with less effort, requiring knowledge only of the total number of memory accesses, rather than the exact memory addresses and memory access patterns.
3. Reduced time-to-market by enabling trustworthy WCET and other analyses for large-scale real-time systems that will dramatically reduce testing time.