Mitigating Software-Instrumentation Cache Effects in Measurement-Based Timing Analysis

Enrique Díaz, Jaume Abella, Enrico Mezzetti, Irune Agirre, Mikel Azkarate-askasua, Tullio Vardanega, Francisco J. Cazorla

TL;DR

This paper tackles the "probe effect" in measurement-based timing analysis (MBTA), where instrumenting code to measure execution time can alter that very timing due to cache effects. They propose a novel approach using "functionally-neutral" code (NOPs) to create a version of the program that behaves identically to the original but can be safely instrumented for analysis, ensuring the analysis results reliably bound the operational behavior.

What Problem Does This Paper Address?

In safety-critical real-time systems (like automotive or railway), accurately determining the worst-case execution time (WCET) of software is crucial. Measurement-based timing analysis (MBTA) is a common technique, but it requires instrumenting the code to collect timing data. This instrumentation, even if removed later, can subtly alter the program's behavior, particularly its interaction with CPU caches. This "probe effect" can lead to inaccurate WCET estimates. Specifically, inserting instrumentation code can change the memory layout of instructions, leading to different cache hit/miss patterns and potentially making the instrumented program faster than the original, thus invalidating the WCET upper bound. The challenge is to get accurate timing measurements without compromising the reliability of the WCET estimates for the final, uninstrumented operational code.

Methods

The authors propose a three-version approach:

  1. oprog (Original Program): The program as it would run in operation.
  2. fnprog (Functionally-Neutral Program): This version is derived from oprog by inserting NOP (No Operation) instructions at potential instrumentation points. The key idea is that NOPs are functionally neutral – they don't change program state, flags, or cause interrupts. This version is intended to be used in operation, ensuring functional equivalence and minimizing performance degradation compared to oprog. The number of NOPs is chosen to ensure that when they are later replaced by actual instrumentation code, the cache line alignment remains the same as in oprog.
  3. iprog (Instrumented Program): This version is derived from fnprog by replacing the NOPs with actual instrumentation instructions. Because the cache line alignment is preserved from fnprog, the timing effects of instrumentation are more predictable. The authors argue that iprog's execution time will reliably upper-bound fnprog's, and since fnprog is functionally equivalent to oprog, the WCET derived from iprog will be a valid upper bound for oprog.

Datasets

The paper evaluates their approach using:

  • EEMBC Automotive Benchmark Suite: Specifically, programs like a2time, aifftr, aifirf, aiifft, bitmnp, cacheb, canrdr, idctrn, and iirflt.
  • European Railway Traffic Management System (ERTMS) case study: Focusing on the on-board unit of the ERTMS, called European Train Control System (ETCS).

They used 10 different input sets for the ERTMS case study.

Key Insights and Ideas

  • The "Probe Effect" is More Than Just Instruction Latency: The most surprising insight is how significantly cache effects, triggered by changes in instruction memory layout due to instrumentation, can alter program timing. This can lead to instrumented code running faster than the original, undermining the core principle of WCET analysis.
  • NOPs as a Bridge: Using NOPs as placeholders for instrumentation is a clever way to decouple the functional equivalence and cache alignment concerns from the actual timing measurement. fnprog acts as a safe operational version, while iprog provides the necessary instrumentation data.
  • Functionally-Neutrality is Key for Certification: The use of NOPs makes it easier to argue for the functional equivalence of fnprog to oprog, which is critical for industrial qualification and certification.
  • Preserving Cache Alignment is Paramount: The core of their mitigation strategy relies on ensuring that the insertion of instrumentation code (replacing NOPs) does not change the cache line alignment of instructions relative to the fnprog version.

Key Results

  • Reduced Misalignment Impact: The proposed approach effectively mitigates the negative cache misalignment effects of instrumentation.
  • fnprog vs. oprog: fnprog shows a moderate increase in code size (7-14%) and execution time (5-10%) compared to oprog, depending on the number of NOPs inserted.
  • iprog vs. fnprog: iprog incurs higher execution time overheads (9-19%) compared to fnprog, as expected, due to the actual instrumentation instructions.
  • pWCET Estimates: For the EEMBC benchmarks, fnprog's pWCET estimates are close to oprog's, and iprog's pWCET estimates reliably upper-bound fnprog's. The railway case study shows even tighter results, with average pWCET increases of 8.7% for fnprog and 11.9% for iprog.
  • Illustrative Example: A small code fragment example demonstrated how a single instrumentation instruction could lead to iprog having a lower execution time than oprog due to cache effects, highlighting the problem their approach solves.

Limitations and Future Work

  • Hardware Platform and Tool Dependency: The authors plan to evaluate their fnprog approach on a real hardware platform and with a commercial timing analysis tool.
  • Non-Probabilistic Timing Analysis: They intend to extend their argumentation about the timing impact of iprog relative to fnprog to non-probabilistic timing analysis.
  • Automatic NOP Insertion: While they suggest compiler parameters for automatic NOP insertion, this is presented as a potential feature rather than a fully implemented aspect of their current work.
  • The "Argument" for Upper Bounding: The paper relies on arguments (A1 and A2) to prove functional equivalence and WCET upper bounding. While these arguments are detailed, their formal verification on all possible architectures and scenarios might be an ongoing effort.

Summary updated

Abstract

Measurement-based timing analysis (MBTA) is often used to determine the timing behaviour of software programs embedded in safety-aware real-time systems deployed in various industrial domains including automotive and railway. MBTA methods rely on some form of instrumentation, either at hardware or software level, of the target program or fragments thereof to collect execution-time measurement data. A known drawback of software-level instrumentation is that instrumentation itself does affect the timing and functional behaviour of a program, resulting in the so-called probe effect: leaving the instrumentation code in the final executable can negatively affect average performance and could not be even admissible under stringent industrial qualification and certification standards; removing it before operation jeopardizes the results of timing analysis as the WCET estimates on the instrumented version of the program cannot be valid any more due, for example, to the timing effects incurred by different cache alignments. In this paper, we present a novel approach to mitigate the impact of instrumentation code on cache behaviour by reducing the instrumentation overhead while at the same time preserving and consolidating the results of timing analysis.
BibTeX
@inproceedings{diaz2016mitigating,
  author = {Enrique Díaz and Jaume Abella and Enrico Mezzetti and Irune Agirre and Mikel Azkarate-askasua and Tullio Vardanega and Francisco J. Cazorla},
  title = {{Mitigating Software-Instrumentation Cache Effects in Measurement-Based Timing Analysis}},
  booktitle = {WCET},
  year = {2016},
  doi = {10.4230/oasics.wcet.2016.1},
}

Loading related content...

Figure