Probabilistic Safe WCET Estimation for Weakly Hard Real-time Systems at Design Stages

Jaekwon Lee, Seung Yeob Shin, Lionel C. Briand, Shiva Nejati

TL;DR

This paper introduces SWEAK, a novel method for estimating safe Worst-Case Execution Times (WCET) for weakly hard real-time systems during the early design stages. SWEAK addresses the challenge of providing engineers with realistic WCET ranges that account for occasional deadline misses and complex industrial scheduling policies, enabling more informed design decisions.

What Problem Does This Paper Address?

Real-time systems are crucial in many industries, but their strict timing requirements can be challenging to meet. Weakly hard real-time systems offer some tolerance for deadline misses, but their schedulability still needs careful analysis, especially during the early design phases when implementations are not yet complete. At this stage, engineers often estimate WCETs as ranges based on domain knowledge. However, existing WCET estimation techniques are often too pessimistic, don't account for weakly hard constraints, or require source code, making them unsuitable for early design. This gap leads to difficulties in making informed design decisions and can result in overly conservative or unsafe system designs. SWEAK aims to bridge this gap by providing probabilistic safe WCET ranges that consider these complexities.

Methods

SWEAK employs a multi-stage approach:

  • Test Case Generation (Search): It uses a multi-objective meta-heuristic search (specifically NSGA-II) to generate test cases that are likely to cause deadline misses. The objectives are to maximize the magnitude and consecutiveness of these misses. This step accounts for context switching times.
  • Simulation: The generated test cases are fed into an industrial APS (Adaptive Partitioning Scheduler) simulator (APSSimulator) to evaluate schedulability under various WCET values. This produces a labeled dataset.
  • Learning (Logistic Regression): A logistic regression model is trained on the simulation data to distinguish between "safe" and "unsafe" WCET ranges. This model provides a probabilistic interpretation of the likelihood of violating weakly hard deadline constraints. Feature reduction (using random forests) and imbalance handling are employed to improve model accuracy and efficiency.
  • Model Refinement: The logistic regression model is refined iteratively by adding more samples around the predicted safe border and re-evaluating them.
  • WCET Range Selection: SWEAK identifies a "safe border" and suggests a "best-size point" on this border that maximizes the volume of the safe WCET hyperbox, offering engineers flexibility.

Datasets

  • Training Data: Generated through simulations using the APSSimulator based on test cases derived from the search step and sampled WCET values.
  • Evaluation Data:
    • An industrial system: ESAIL (from the satellite domain).
  • Synthetic systems: Generated using a procedure described in Algorithm 2, designed to mimic real-world systems and account for weakly hard constraints, APS partitions, and other complexities. These include systems with different partition configurations, scheduling policies, and multi-core setups.

Key Insights and Ideas

  • Probabilistic WCET for Weakly Hard Systems: The core innovation is extending probabilistic WCET estimation to weakly hard real-time systems, which is crucial for systems that can tolerate some deadline misses.
  • Leveraging Industrial Simulators: Integrating with an industrial APS simulator (APSSimulator) makes the approach more realistic and directly applicable to industry practices.
  • Multi-Objective Search for Worst-Case Scenarios: Using a multi-objective search to specifically target scenarios that maximize deadline misses is key to finding effective test cases for identifying unsafe WCET ranges.
  • Logistic Regression for Probabilistic Guarantees: The use of logistic regression provides a probabilistic interpretation of safe WCET ranges, allowing engineers to understand the confidence level associated with their design choices.
  • "Safe Border" Concept: Defining a "safe border" in the WCET space provides a clear boundary for acceptable WCET values, with engineers able to choose points on this border based on their needs.

Key Results

  • Superiority over Baseline: SWEAK significantly outperforms a random search baseline in maximizing the volume of safe WCET hyperboxes, indicating greater flexibility for engineers.
  • Reduced Deadline Violations: SWEAK-derived WCET ranges lead to a significantly smaller number of simulation runs violating deadline constraints compared to the baseline.
  • Conservative Probabilistic Estimates: SWEAK's model probabilities of violating deadline constraints are higher than empirical probabilities, providing a more conservative and thus safer estimate for engineers.
  • Scalability: SWEAK demonstrates good scalability, with execution times being linearly related to the number of tasks, processing cores, and simulation time. It completed experiments within a maximum of 22.1 hours, deemed acceptable for an offline analysis tool.
  • Practical Applicability: The approach is considered practical due to its use of an industrial simulator and its ability to provide results within a reasonable timeframe.

Limitations and Future Work

  • Randomness of SWEAK: The inherent randomness of SWEAK (due to search and simulation) is a threat to internal validity, though mitigated by multiple runs and statistical comparisons.
  • Parameter Tuning: While parameters were set based on guidelines and preliminary experiments, further tuning could potentially improve performance.
  • NSGA-II Biases: The paper acknowledges potential biases in NSGA-II with variable-length genomes, though argues it's less of an issue in their context.
  • Generalizability: External validity is a concern, as results might not generalize to all contexts. Further studies in different domains and user studies are needed.
  • Future Work:
    • Develop a real-time task modeling language to facilitate schedulability analysis and represent system behaviors.
  • Validate SWEAK with more case studies from diverse domains.
  • Conduct user studies to assess the practical usefulness of SWEAK's estimates for engineers.
  • Investigate how SWEAK assists engineers in making appropriate decisions during development.

Summary updated

BibTeX
@article{lee2024probabilistic,
  author = {Jaekwon Lee and Seung Yeob Shin and Lionel C. Briand and Shiva Nejati},
  title = {{Probabilistic Safe WCET Estimation for Weakly Hard Real-time Systems at Design Stages}},
  journal = {ACM Trans. Softw. Eng. Methodol.},
  year = {2024},
  doi = {10.1145/3617176},
}
Figure