Applying Measurement-Based Probabilistic Timing Analysis to Buffer Resources

Leonidas Kosmidis, Tullio Vardanega, Jaume Abella, Eduardo Quiñones, Francisco J. Cazorla

TL;DR

This paper extends Measurement-Based Probabilistic Timing Analysis (MBPTA) to include buffer resources, which are crucial for modern complex hardware. They demonstrate that buffers, unlike caches, don't require time-randomization to be MBPTA-compliant, simplifying analysis and enabling tighter worst-case execution time (WCET) bounds for real-time systems.

What Problem Does This Paper Address?

Modern processors are increasingly complex, featuring intricate hardware like caches and buffers. This complexity makes it challenging to accurately predict the worst-case execution time (WCET) of software, which is critical for real-time embedded systems (e.g., automotive, aerospace). Traditional static timing analysis (STA) requires detailed knowledge of hardware internals, which is often proprietary and difficult to obtain. Measurement-Based Probabilistic Timing Analysis (MBPTA) offers an alternative by using observed execution times to derive probabilistic WCET bounds. However, MBPTA typically relies on the assumption that processor resources exhibit independent and identically distributed (i.i.d.) timing behavior. While this has been addressed for caches through time-randomization, the impact of buffer resources on MBPTA has been unclear. Buffers, used to decouple sender and receiver timing, can introduce stalls that propagate through the system, potentially violating the i.i.d. assumption and complicating WCET analysis. This paper aims to clarify how buffers fit into the MBPTA framework and how they can be analyzed.

Methods

The core contribution of this paper is to show that buffer resources can be integrated into MBPTA without requiring modifications to the hardware's timing behavior, provided the underlying processor resources already meet MBPTA requirements. The authors achieve this by:

  • Classifying Hardware Resources: They introduce a new classification of hardware resources based on their jitter characteristics (deterministic, probabilistic, or propagated) and history dependence. This framework helps understand how different resources impact MBPTA.
  • Analyzing Buffer Behavior: They demonstrate that buffers, while introducing stalls, do not create probabilistic jitter themselves. Instead, they propagate jitter from other resources. If the underlying probabilistic events (like cache hits/misses) are already i.i.d., the stalls introduced by buffers are also probabilistically determined and can be analyzed.
  • Empirical Verification: They conduct experiments using the EEMBC Autobench benchmark suite on a pipelined processor with caches and buffers. They employ statistical tests (Wald-Wolfowitz independence test and Kolmogorov-Smirnov identical distribution test) to verify that the execution times remain independent and identically distributed even in the presence of buffers.

Datasets

The paper uses the EEMBC Autobench benchmark suite for their empirical verification. They note that this suite reflects current real-world demands of automotive systems. They also mention that their analysis is path-based, meaning that while real-world programs have multiple paths, MBPTA considers each path individually.

Key Insights and Ideas

  • Buffers are MBPTA-Friendly (with caveats): Unlike caches, which often require time-randomization to be MBPTA-compliant, buffers do not inherently break the i.i.d. assumption. They propagate existing probabilistic jitter, rather than creating new probabilistic variations.
  • Jitter Propagation is Key: The paper highlights that buffers act as conduits for jitter. If the source of the jitter is probabilistic (e.g., cache behavior), the buffer stalls will also occur with a certain probability, making them amenable to MBPTA.
  • A Unified Resource Classification: The proposed classification of hardware resources provides a structured way to understand how different components interact with MBPTA, aiding in the design of MBPTA-compliant systems.
  • Empirical Validation is Crucial: The experimental results provide strong evidence that the theoretical analysis holds in practice, showing that the i.i.d. property is maintained even with buffers.

Key Results

The empirical verification showed that for the tested EEMBC benchmarks, the execution times passed both the independence test and the identical distribution test at a 5% significance level. This indicates that the presence of buffers, in conjunction with probabilistic cache behavior, did not violate the core assumptions required for MBPTA. The paper demonstrates that the probability of a buffer stall is directly tied to the probability of the underlying events (like cache misses), allowing for probabilistic analysis.

Limitations and Future Work

  • Path-Specific Analysis: MBPTA, as applied here, analyzes execution paths individually. While the paper argues this is sufficient, the complexity of analyzing all possible paths in large programs remains a challenge.
  • Hardware Support for i.i.d.: The paper assumes that the underlying processor resources (like caches) already provide the necessary probabilistic behavior for MBPTA. The analysis of buffers is contingent on this.
  • Future Work: The authors suggest that their classification of hardware resources can help in designing MBPTA-compliant processors. Further research could explore more complex buffer structures and their interactions with other advanced processor features. The paper also implicitly points to the need for robust tools that can automatically extract Execution Time Profiles (ETPs) for various hardware components.

Summary updated

Abstract

The use of complex hardware makes it difficult for current timing analysis techniques to compute trustworthy and tight worst-case execution time (WCET) bounds. Those techniques require detailed knowledge of the internal operation and state of the platform, at both the software and hardware level. Obtaining that information for modern hardware platforms is increasingly difficult. Measurement-Based Probabilistic Timing Analysis (MBPTA) reduces the cost of acquiring the knowledge needed for computing trustworthy and tight WCET bounds. MBPTA based on Extreme Value Theory requires the execution time of processor instructions to be independent and identically distributed (i.i.d.), which can be achieved with some hardware support. Previous proposals show how those properties can be achieved for caches. This paper considers, for the first time, the implications on MBPTA of using buffer resources. Buffers in general, and first-come first-served (FCFS) buffers in particular, are of paramount importance as the complexity of hardware increases, since they allow managing contention in those resources where multiple requests may be pending. We show how buffers can be used in the context of MBPTA and provide illustrative examples.
BibTeX
@inproceedings{kosmidis2013applying,
  author = {Leonidas Kosmidis and Tullio Vardanega and Jaume Abella and Eduardo Quiñones and Francisco J. Cazorla},
  title = {{Applying Measurement-Based Probabilistic Timing Analysis to Buffer Resources}},
  booktitle = {WCET},
  year = {2013},
  doi = {10.4230/oasics.wcet.2013.97},
}
Figure