In safety-critical systems like autonomous vehicles, avionics, and medical devices, software must not only produce the correct output but must also do so within a strict time window. Traditionally, engineers have relied on finding a single, absolute Worst-Case Execution Time (WCET) to guarantee that deadlines are never missed.
However, as hardware has evolved to maximize average-case throughput via multi-core architectures, deep cache hierarchies, and complex pipelines, determining an absolute WCET has become nearly impossible. Luca Benini describes this as a fundamental "predictability gap": we can build high-performance processors, but we struggle to guarantee their real-time performance. When traditional static analysis tools attempt to model these complex interactions, they yield bounds so conservative and pessimistic that hardware must be massively over-provisioned. As Hiroshi Yamada et al. note in Message from the Chairs: RTCSA 2023, software-level timing guarantees have become deeply entangled with underlying hardware-level predictability.
To bridge this gap, a major research direction has shifted from absolute determinism to Probabilistic Timing Analysis (PTA). Instead of declaring that a program will never exceed a specific execution time, PTA models execution time as a statistical distribution. This allows system designers to define a probabilistic WCET (pWCET) bound associated with an acceptably small target probability of failure (e.g., $10^{-9}$ per hour). As argued by Jaume Abella et al. in SAFEXPLAIN: Safe and Explainable Critical Embedded Systems Based on AI and Francisco J. Cazorla et al. in Uncertainty Management in Dependable and Intelligent Embedded Software, accepting a quantifiable, infinitesimal statistical risk allows advanced software to safely leverage modern high-performance hardware.
The Core Mechanism: Extreme Value Theory
The primary tool for deriving a pWCET from empirical observations is Measurement-Based Probabilistic Timing Analysis (MBPTA). Rather than analyzing the source code line-by-line alongside a detailed hardware model, MBPTA executes the program on the target hardware multiple times and records the runtimes.
To find the absolute edge of the distribution's tail from a finite set of observations, MBPTA leverages Extreme Value Theory (EVT). EVT is a branch of statistics designed to model the risk of rare, extreme events (like 100-year floods) based on historical data. As explained by Mladen Slijepcevic et al. in Boosting Guaranteed Performance in Wormhole NoCs with Probabilistic Timing Analysis, EVT allows designers to mathematically discount pathological scenarios that have a vanishingly small likelihood of occurrence, yielding much tighter timing bounds.
Execution Time Observations ──> Check i.i.d. (via Randomization) ──> Apply EVT ──> pWCET Bound at 10^-9
However, EVT carries a strict mathematical prerequisite: the input data must consist of independent and identically distributed (i.i.d.) random variables. On standard commercial off-the-shelf (COTS) processors, execution times are not i.i.d. Instead, they are highly dependent on deterministic hardware states. For example, a cache miss on one loop iteration changes the cache state for the next iteration, creating systematic correlation and "messy," step-like timing data that violates EVT assumptions, as detailed by Jaume Abella et al. in Measurement-Based Worst-Case Execution Time Estimation Using the Coefficient of Variation.
Enforcing the i.i.d. Condition via Randomization
To make EVT valid, researchers introduce intentional randomization into the system. The goal is to transform deterministic hardware conflicts into independent random variables.
Hardware-Level Randomization
One approach is to modify the hardware components themselves. For instance, Mladen Slijepcevic et al. demonstrate that replacing deterministic arbitration with randomized logic in network-on-chip (NoC) routers successfully breaks systematic worst-case delays. Similarly, utilizing hardware with randomized cache placement and replacement policies ensures that memory access latencies follow predictable probabilistic distributions, as shown by Suzana Milutinovic et al. in Measurement-based cache representativeness on multipath programs.
Software-Level Randomization
Because most COTS processors lack randomized hardware features, researchers have developed software-level alternatives. Leonidas Kosmidis et al. introduce this concept with TASA: toolchain-agnostic static software randomisation for critical real-time systems. TASA randomizes memory layouts at the source-code level, forcing cache mapping configurations to behave randomly across different runs without requiring runtime overhead or compiler modifications.
This technique has proven highly effective for complex, proprietary accelerators. Ivan Rodriguez Ferrandez et al. successfully applied source-level software randomization to GPU memory layouts in Worst Case Execution Time and Power Estimation of Multicore and GPU Software: A Pedestrian Detection Use Case. By forcing deterministic hardware conflicts on a GPU to behave as i.i.d. variables, the authors derived provable timing guarantees for advanced automotive workloads without needing access to proprietary hardware internals.
Ensuring Representativeness and Managing Risk
A critical challenge in MBPTA is ensuring that the test campaign is representative—meaning it actually captures the potential for rare, high-latency events. If a rare cache conflict scenario is never triggered during testing, EVT will under-approximate the tail risk.
To solve this, Suzana Milutinovic et al. developed a method called ReVS (Representativeness Validation by Simulation) in On the assessment of probabilistic WCET estimates reliability for arbitrary programs. ReVS analyzes memory address sequences to calculate the exact number of execution runs required to ensure that pathological cache configurations are observed with a target statistical confidence. Furthermore, by combining program path normalization with statistical conflict analysis, Suzana Milutinovic et al. demonstrated in Measurement-based cache representativeness on multipath programs that a single execution trace can be mathematically extended to upper-bound all possible software paths and hardware cache states.
Once a valid distribution is established, designers can apply decision-theoretic thresholds. Hardik Shah et al. show in Weighted Execution Time Analysis of Applications on COTS Multi-core Architectures that a tree-based convolution method can define a cut-off execution time that safely reclaims performance overhead by ignoring infinitesimally rare timing paths. A similar philosophy appears in algorithm selection frameworks like Run2Survive, developed by Alexander Tornede et al., which models full survival functions to capture tail risks and avoid catastrophic timeouts.
Complementary Path: Predictable-by-Construction Design
While probabilistic analysis manages hardware uncertainty statistically, a parallel facet of this research direction seeks to eliminate uncertainty through predictable-by-construction design. Instead of accepting hardware complexity as a given, these approaches surgically modify hardware and software architectures to enforce determinism.
- Subsystem Partitioning: In CVA6-VMRT: A Modular Approach Towards Time-Predictable Virtual Memory in a 64-bit Application Class RISC-V Processor, Christopher Reinwardt et al. introduce modular hardware extensions like Translation Lookaside Buffer (TLB) partitioning and entry locking. These surgical modifications reduce execution time variability by up to 94% in virtualized environments with minimal silicon area overhead.
- Specialized Extensions: Luca Cuomo et al. demonstrate in Towards a RISC-V Open Platform for Next-generation Automotive ECUs that hardware-level extensions for interrupt management are essential to eliminate non-deterministic bottlenecks during context switching in real-time operating systems.
- Deterministic Accelerators: For deep learning workloads, Hammond Pearce et al. present a pipeline in Designing Neural Networks for Real-Time Systems that compiles Keras neural networks into restricted C code targeting specialized processors that completely lack non-deterministic features like traditional caches. Alternatively, Roger Pujol et al. argue in Vector Extensions in COTS Processors to Increase Guaranteed Performance in Real-Time Systems that CPU-based Vector Extensions (VExt) offer a superior middle ground, providing significant throughput acceleration while remaining fully compatible with existing deterministic safety-critical timing tools.
Key Foundational Work
Probabilistic design of multimedia embedded systems (2007) — contributed 1 concept elements to this direction.
Design for Time-Predictability (2004) — contributed 1 concept elements to this direction.