TL;DR
This paper introduces an extensible, model-based framework for planning the energy supply of real-time systems, specifically focusing on preemptive tasks. It proposes a novel technique to compute the minimal processor frequency required to guarantee task schedulability, outperforming traditional methods like Real-Time Calculus (RTC) in certain scenarios by achieving significant frequency reductions.
What Problem Does This Paper Address?
Modern cyber-physical systems (CPS) are becoming increasingly complex, integrating numerous hardware and software components. This complexity poses a significant challenge for energy efficiency, as simply reducing processor voltage and frequency (DVFS) can lead to missed deadlines. Furthermore, the trend towards compositional software design, where independent components are integrated, necessitates a robust energy supply plan for each component before runtime. Existing energy-aware scheduling algorithms and evaluation techniques struggle to keep pace with this complexity, often requiring simplified assumptions or lacking extensibility. This paper addresses the need for a more sophisticated and flexible approach to energy planning, specifically for preemptive real-time tasks, by providing a method to compute the minimum required processor frequency that ensures schedulability while minimizing energy consumption.
Methods
The core of this paper is a model-based compositional energy planning technique. This approach leverages the compositional framework for hierarchical scheduling systems, which models components as interfaces (resource demands) and resource models (resource supply).
Key methodological contributions include:
- Periodic Laxity Resource Model (PLRM): A new resource model designed to capture the worst-case supply pattern of processor frequency. It's defined by a period (Π), amount of resources (Θ), and a laxity (Λ), representing the time a resource supply can be delayed.
- Schedulability Conditions: The paper derives specific schedulability conditions for both Earliest Deadline First (EDF) and Rate Monotonic (RM) scheduling algorithms based on the PLRM.
- Formal Modeling with Timed Automata (TA): To enhance extensibility and handle complex scheduling mechanisms, the authors model scheduling units (components) and the PLRM resource model using Timed Automata (TA), specifically Stopwatch Automata (SWA). This allows for analysis using model-checking techniques.
- Model Checking for Analysis: UPPAAL, a model-checking tool suite, is used to verify the schedulability of components against the PLRM. The property checked is
A[] not error, whereerrorsignifies a missed deadline.
The process involves setting a frequency ratio for the PLRM, checking schedulability using model checking, and iteratively reducing the frequency until the minimum required ratio is identified.
Datasets
Not discussed in the paper. The evaluation uses a use-case of avionics software components from a prior work [13].
Key Insights and Ideas
- Frequency as a Periodic Resource: Viewing processor frequency as a periodic resource with a defined laxity is a novel way to model its supply and analyze its impact on real-time task schedulability.
- Model-Based Extensibility: Employing formal models (Timed Automata) and model checking provides a more extensible and flexible framework compared to traditional analytical techniques, allowing for the representation of more complex scheduling behaviors and system features.
- Optimized Frequency for RM: The proposed model-based approach demonstrates a significant advantage for RM scheduling, achieving lower required frequencies than the RTC-based method. This suggests that the framework can identify more precise energy-saving opportunities in such scenarios.
- Trade-offs in EDF: While the model-based approach is beneficial for RM, it shows a tendency to compute slightly higher frequencies for EDF compared to RTC. The authors attribute this to the over-approximation inherent in UPPAAL's stopwatch clock mechanism, highlighting a potential area for refinement.
Key Results
- The proposed model-based technique outperforms the classical Real-Time Calculus (RTC) method, requiring 36.21% less frequency ratio on average for scheduling units under RM.
- For RM cases, the model-based technique shows less sensitivity to the number of tasks compared to the RTC-based method when CPU utilization varies.
- In EDF cases, the RTC-based technique sometimes returns minimal frequencies equal to CPU utilization, while the model-based method returns slightly higher values, attributed to UPPAAL's analysis.
Limitations and Future Work
- Scalability of Model Checking: The authors acknowledge that model-checking techniques, while powerful, can suffer from state-explosion issues, making them less scalable than analytical methods for very large or complex systems. The verification time increases exponentially with the number of tasks.
- Over-approximation in UPPAAL: The UPPAAL model checker's analysis, particularly with stopwatch clocks, can lead to over-approximation, potentially resulting in slightly higher frequency ratios than strictly necessary in some cases (e.g., EDF).
- Future Work: The authors plan to develop an automated computation technique for frequency interfaces for components and apply this approach to energy-aware composition of hierarchical scheduling systems. They also aim to explore more complex scheduling mechanisms and system features.
Summary updated