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 balancing system performance with the need to tolerate occasional deadline misses, providing engineers with probabilistic WCET ranges to guide design decisions.
What Problem Does This Paper Address?
Real-time systems are crucial in many industries, but they often have strict timing constraints. While "hard" real-time systems must never miss a deadline, "weakly hard" systems can tolerate a certain number of missed deadlines without catastrophic failure. Estimating the WCET of tasks is vital for ensuring these systems meet their deadlines, but doing so accurately at the early design stage, when implementations and hardware are not finalized, is extremely difficult. Engineers typically resort to estimating WCET ranges. However, existing methods often struggle with the complexities of weakly hard constraints and advanced industrial scheduling policies, leading to either overly pessimistic estimates (hindering performance) or unsafe ones. This paper tackles the problem of finding safe WCET ranges for weakly hard real-time systems that are probabilistically determined and account for sophisticated scheduling policies.
Methods
SWEAK employs a multi-stage approach:
- Test Case Generation (Search): It uses a multi-objective search algorithm (NSGA-II) to generate test cases. These test cases are designed to maximize the likelihood of violating weakly hard deadline constraints, focusing on both the magnitude and consecutiveness of deadline misses. This is crucial for exploring the "worst-case" scenarios relevant to weakly hard systems.
- Simulation: A specialized simulator, APSSimulator (an extension of BlackBerry's industrial APS simulator), is used to evaluate the generated test cases. This simulation accounts for complex scheduling policies, context switching times, and task arrival patterns.
- Learning (Logistic Regression): The simulation results are used to create a labeled dataset. SWEAK then uses logistic regression to build a probabilistic model. This model learns to distinguish between "safe" and "unsafe" WCET ranges, providing a probability of violating deadline constraints. This probabilistic interpretation allows engineers to make informed trade-offs.
- Model Refinement: The logistic regression model is refined through techniques like feature reduction (using random forests) and imbalance handling to improve accuracy and efficiency. It also incorporates a "safe border" concept to define the upper bounds of safe WCET ranges.
Datasets
- Industrial System: ESAIL, a commercial microsatellite system.
- Synthetic Systems: The paper generated multiple synthetic systems based on guidelines from BlackBerry to represent realistic real-time systems with varying characteristics (e.g., number of tasks, aperiodic tasks, WCET ranges, number of cores, APS partitions). These systems were used for both training and evaluation.
Key Insights and Ideas
- Probabilistic WCET for Weakly Hard Systems: The core innovation is moving beyond deterministic WCET estimates to probabilistic ranges that explicitly account for the "weakly hard" nature of deadlines. This offers more flexibility than traditional hard real-time analysis.
- Maximizing Deadline Misses for Search: Instead of just finding worst-case execution times, SWEAK's search focuses on generating scenarios that maximize deadline misses. This is a clever way to explore the boundaries of weakly hard constraints.
- Logistic Regression for Probabilistic Interpretation: Using logistic regression allows SWEAK to provide a probability of deadline violation for given WCET ranges, enabling engineers to understand the risk associated with their choices.
- Conservative Estimates are Desirable: The paper highlights that SWEAK's model probabilities are often higher than empirical probabilities, leading to more conservative (safer) WCET estimates, which is beneficial for design.
- Impact of APS Complexity: The study demonstrates how SWEAK can handle complex industrial scheduling policies like APS, which are often a challenge for traditional analysis methods.
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 Violation Probability: SWEAK-derived WCET ranges lead to a significantly smaller chance of violating deadline constraints compared to the baseline.
- Accurate Probabilistic Predictions: SWEAK's logistic regression model provides probabilities that are closely aligned with empirical simulations, enabling conservative and reliable design guidance.
- Scalability: SWEAK is shown to be scalable, with execution times that are generally acceptable for an offline analysis technique (max 22.1 hours for extensive experiments). Execution time scales linearly with the number of tasks, cores, and simulation time, and quadratically with the number of WCET ranges.
Limitations and Future Work
- Randomness: The inherent randomness of SWEAK is acknowledged as a threat to internal validity, mitigated by extensive statistical comparisons.
- Parameter Tuning: While parameters were set based on guidelines and preliminary experiments, further tuning could potentially improve performance.
- Generalizability: The authors suggest that further validation with case studies from different domains and user studies is needed to confirm the general usefulness of SWEAK.
- Future Work: The authors plan to develop a real-time task modeling language to facilitate schedulability analysis and represent system behaviors. They also aim to investigate how SWEAK assists engineers in making design decisions.
Summary updated