Generalized Inequality-based Approach for Probabilistic WCET Estimation
This work addresses timing correctness for real-time systems such as robot IoT and autonomous driving, but it is incremental as it builds on existing inequality-based methods to improve performance for heavy-tailed distributions.
The paper tackles the problem of probabilistic Worst-Case Execution Time (pWCET) estimation for real-time applications like autonomous driving, proposing a method that reduces pessimism in inequality-based approaches by incorporating saturating functions into Chebyshev's inequality, achieving safe and tighter bounds on synthetic and real-world data.
Estimating the probabilistic Worst-Case Execution Time (pWCET) is essential for ensuring the timing correctness of real-time applications, such as in robot IoT systems and autonomous driving systems. While methods based on Extreme Value Theory (EVT) can provide tight bounds, they suffer from model uncertainty due to the need to decide where the upper tail of the distribution begins. Conversely, inequality-based approaches avoid this issue but can yield pessimistic results for heavy-tailed distributions. This paper proposes a method to reduce such pessimism by incorporating saturating functions (arctangent and hyperbolic tangent) into Chebyshev's inequality, which mitigates the influence of large outliers while preserving mathematical soundness. Evaluations on synthetic and real-world data from the Autoware autonomous driving stack demonstrate that the proposed method achieves safe and tighter bounds for such distributions.