Measurement-Based Timing Analysis of the AURIX Caches

Leonidas Kosmidis, Davide Compagnin, David Morales, Enrico Mezzetti, Eduardo Quiñones, Jaume Abella, Tullio Vardanega, Francisco J. Cazorla

TL;DR

This paper tackles the challenge of accurately predicting the worst-case execution time (WCET) of real-time systems that use caches, which introduce significant variability. They demonstrate that by combining software randomization of memory layouts with measurement-based probabilistic timing analysis (MBPTA), they can effectively capture and model this cache-induced jitter, leading to more reliable WCET estimates for automotive applications.

What Problem Does This Paper Address?

In real-time systems, especially in safety-critical domains like automotive, accurately predicting the worst-case execution time (WCET) of software is paramount. Caches, while beneficial for speeding up execution by storing frequently accessed data closer to the processor, introduce a significant problem: timing variability. The exact execution time of an instruction can depend on whether the data it needs is already in the cache (a "cache hit") or needs to be fetched from slower main memory (a "cache miss"). This variability, or "jitter," makes traditional deterministic timing analysis difficult, as it's hard to guarantee that the analysis covers the absolute worst-case scenario. The automotive industry, in particular, has been hesitant to fully embrace caches due to these timing analysis challenges. This paper aims to bridge this gap by providing a method to reliably analyze systems with caches using measurement-based techniques.

Methods

The core of this paper's contribution lies in its novel combination of two techniques:

  • Software Randomization (SSR): Instead of relying on hardware-level cache randomization, the authors employ Static Software Randomization (SSR). This technique generates multiple versions of the program's executable, each with a different, randomized memory layout for code and data. By running these different versions, the system effectively explores a wider range of potential cache layouts without needing direct hardware support for randomization. This is crucial because the target AURIX platform, while designed for determinism, still has caches that can introduce jitter.
  • Measurement-Based Probabilistic Timing Analysis (MBPTA): Building upon the randomized execution traces, the authors use MBPTA. Unlike traditional WCET analysis that aims for a single, absolute worst-case value, MBPTA provides a probabilistic WCET (pWCET) estimate. This means it generates a distribution of execution times, allowing users to determine the execution time bound that has an acceptable probability of being exceeded. This approach is particularly well-suited for handling the inherent variability introduced by caches. The paper leverages Extreme Value Theory (EVT) as a foundation for MBPTA.

Datasets

The paper uses a real-world automotive application: an Automotive Cruise Control System (ACCS), automatically generated from a Simulink model. This application was adapted to run on a customized version of the ERIKA real-time operating system on an AURIX TC277 processor board. The authors focus on two specific execution paths within this application, termed "Path1" and "Path2," representing worst-case and best-case observed scenarios for the given inputs. No new benchmarks were introduced; rather, a real-world application was adapted and analyzed.

Key Insights and Ideas

  • Caches Induce Significant Variability Even in "Deterministic" Architectures: The AURIX TC277 is designed with determinism in mind, featuring scratchpads to minimize jitter. However, the paper clearly demonstrates that its caches still introduce measurable execution time variability, highlighting that caches remain a challenge even in platforms aiming for predictability.
  • Software Randomization is a Practical Solution for Cache Analysis: SSR proves to be an effective and certification-aware method to expose cache-induced jitter. It allows the system to explore a wide range of cache layouts by simply running different program binaries, making it a viable alternative to hardware randomization, especially in embedded systems with constraints.
  • MBPTA Effectively Models Cache Jitter: The paper shows that MBPTA, when combined with SSR, can successfully model the probabilistic nature of cache-induced timing variations. This leads to more accurate and less pessimistic WCET estimates compared to traditional methods that might rely on broad engineering margins.
  • Probabilistic WCET Offers a Better Trade-off for Certification: The pWCET estimates derived are not only tighter than traditional MBTA with a 20% engineering margin but also provide a scientific basis for certification by quantifying the risk of exceeding a given execution time.

Key Results

  • Variability Exposure: SSR successfully exposed execution time variability in the range of 1.5-4.5% across different runs for the analyzed functions and paths.
  • Independence and Identical Distribution: Statistical tests (Ljung-Box and Kolmogorov-Smirnov) confirmed that the execution times collected using SSR and MBPTA were statistically independent and identically distributed (i.i.d.), a prerequisite for applying EVT.
  • Tighter WCET Estimates: For a cut-off probability of 10⁻¹², MBPTA provided 6-17% tighter WCET reduction compared to traditional MBTA with a 20% engineering margin.
  • Probabilistic Upper-Bounding: The derived pWCET curves consistently upper-bounded the observed execution times, demonstrating the effectiveness of the probabilistic analysis.

Limitations and Future Work

  • Path Coverage: The paper acknowledges that MBPTA, as used in this study, reasons about paths triggered by the test runs. While they used a controlled set of inputs to cover specific paths, they mention that solutions for broader path coverage in MBPTA exist and are a topic for future work.
  • Contention Jitter: The study focused on a single-core configuration to isolate cache effects. Future work aims to combine solutions to simultaneously handle cache jitter and contention jitter in multi-core systems.
  • Unknowns in Real-Time Systems: The paper notes that the unknowns in real-time systems also cover other factors like jitter due to different paths, which MBPTA can address with further techniques.

Summary updated

Abstract

Cache memories are one of the hardware resources with higher potential to reduce worst-case execution time (WCET) costs for software programs with tight real-time constraints. Yet, the complexity of cache analysis has caused a large fraction of real-time systems industry to avoid using them, especially in the automotive sector. For measurement-based timing analysis (MBTA) - the dominant technique in domains such as automotive - cache challenges the definition of test scenarios stressful enough to produce (cache) layouts that causing high contention. In this paper, we present our experience in enabling the use of caches for a real automotive application running on an AURIX multiprocessor, using software randomization and measurement-based probabilistic timing analysis (MBPTA). Our results show that software randomization successfully exposes - in the experiments performed for timing analysis - cache related variability, in a manner that can be effectively captured by MBPTA.
BibTeX
@inproceedings{kosmidis2016measurement,
  author = {Leonidas Kosmidis and Davide Compagnin and David Morales and Enrico Mezzetti and Eduardo Quiñones and Jaume Abella and Tullio Vardanega and Francisco J. Cazorla},
  title = {{Measurement-Based Timing Analysis of the AURIX Caches}},
  booktitle = {WCET},
  year = {2016},
  doi = {10.4230/oasics.wcet.2016.9},
}
Figure