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:
oprog(Original Program): The program as it would run in operation.fnprog(Functionally-Neutral Program): This version is derived fromoprogby 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 tooprog. 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 inoprog.iprog(Instrumented Program): This version is derived fromfnprogby replacing the NOPs with actual instrumentation instructions. Because the cache line alignment is preserved fromfnprog, the timing effects of instrumentation are more predictable. The authors argue thatiprog's execution time will reliably upper-boundfnprog's, and sincefnprogis functionally equivalent tooprog, the WCET derived fromiprogwill be a valid upper bound foroprog.
Datasets
The paper evaluates their approach using:
- EEMBC Automotive Benchmark Suite: Specifically, programs like
a2time,aifftr,aifirf,aiifft,bitmnp,cacheb,canrdr,idctrn, andiirflt. - 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.
fnprogacts as a safe operational version, whileiprogprovides the necessary instrumentation data. - Functionally-Neutrality is Key for Certification: The use of NOPs makes it easier to argue for the functional equivalence of
fnprogtooprog, 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
fnprogversion.
Key Results
- Reduced Misalignment Impact: The proposed approach effectively mitigates the negative cache misalignment effects of instrumentation.
fnprogvs.oprog:fnprogshows a moderate increase in code size (7-14%) and execution time (5-10%) compared tooprog, depending on the number of NOPs inserted.iprogvs.fnprog:iprogincurs higher execution time overheads (9-19%) compared tofnprog, as expected, due to the actual instrumentation instructions.- pWCET Estimates: For the EEMBC benchmarks,
fnprog's pWCET estimates are close tooprog's, andiprog's pWCET estimates reliably upper-boundfnprog's. The railway case study shows even tighter results, with average pWCET increases of 8.7% forfnprogand 11.9% foriprog. - Illustrative Example: A small code fragment example demonstrated how a single instrumentation instruction could lead to
iproghaving a lower execution time thanoprogdue to cache effects, highlighting the problem their approach solves.
Limitations and Future Work
- Hardware Platform and Tool Dependency: The authors plan to evaluate their
fnprogapproach 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
iprogrelative tofnprogto 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