Extensible Energy Planning Framework for Preemptive Tasks

Jin Hyun Kim, Deepak Gangadharan, Oleg Sokolsky, Axel Legay, Insup Lee

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, where error signifies 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

Abstract

Cyber-physical systems (CSPs) are demanding energy-efficient design not only of hardware (HW), but also of software (SW). Dynamic Voltage and Frequency Scaling (DVFS) and Dynamic Power Manage (DPM) are most popular techniques to improve the energy efficiency. However, contemporary complicated HW and SW designs requires more elaborate and sophisticated energy management and efficiency evaluation techniques. This paper is concerned about energy supply planning for real-time scheduling systems (units) of which tasks need to meet deadlines. This paper presents a model-based compositional energy planning technique that computes a minimal ratio of processor frequency that preserves schedulability of independent and preemptive tasks. The minimal ratio of processor frequency can be used to plan the energy supply of real-time components. Our model-based technique is extensible by refining our model with additional features so that energy management techniques and their energy efficiency can be evaluated by model checking techniques. We exploit the compositional framework for hierarchical scheduling systems and provide a new resource model for the frequency computation. As results, our use-case for avionics software components shows that our new method outperforms the classical real-time calculus (RTC) method, requiring 36.21% less frequency ratio on average for scheduling units under RM than the RTC method.
BibTeX
@inproceedings{kim2017extensible,
  author = {Jin Hyun Kim and Deepak Gangadharan and Oleg Sokolsky and Axel Legay and Insup Lee},
  title = {{Extensible Energy Planning Framework for Preemptive Tasks}},
  booktitle = {ISORC},
  year = {2017},
  doi = {10.1109/isorc.2017.14},
}
Figure