Precise Scheduling of DAG Tasks with Dynamic Power Management

Ashikahmed Bhuiyan, Mohammad Pivezhandi, Zhishan Guo, Jing Li, Venkata Prashant Modekurthy, Abusayeed SaifullahECRTS 2023 · DOI

TL;DR

This paper tackles the challenge of minimizing energy consumption in real-time embedded systems that use Directed Acyclic Graphs (DAGs) for parallel task execution. They introduce a novel energy-aware scheduling framework that dynamically adjusts processor speeds and core allocation to save power while guaranteeing critical timing requirements, achieving up to 30% energy savings in experiments.

What Problem Does This Paper Address?

Modern embedded systems, from mobile phones to self-driving cars, increasingly rely on parallel processing to meet demanding computational needs. These systems often have strict real-time constraints, meaning tasks must complete within specific deadlines. Traditionally, scheduling algorithms focus on the "worst-case execution time" (WCET) to ensure these deadlines are always met. However, this approach is often overly pessimistic, leading to systems that are over-provisioned and consume more energy than necessary during typical operation.

The problem is to find a way to optimize energy consumption for these parallel real-time systems, specifically those modeled as DAGs, without sacrificing their critical timing guarantees. This is particularly challenging in clustered multi-core architectures where groups of cores operate at the same speed, and dynamic power management (DPM) techniques, which leverage idle time to reduce power, are difficult to apply effectively. The authors aim to minimize typical-case CPU energy consumption while ensuring worst-case timing correctness.

Methods

The paper proposes a multi-faceted approach to address this problem:

  • Dual Execution Time Estimates: Instead of relying solely on WCET, the authors require tasks to provide two estimates: a typical-case execution budget (less than WCET) and the WCET itself. The typical budget is used for energy optimization, while the WCET ensures safety.
  • Dynamic Power Management (DPM): The core of their energy-saving strategy is DPM. They leverage the fact that tasks rarely execute at their WCET by allocating fewer, lower-speed cores during typical operation. When a task does exceed its typical budget, additional high-speed cores are brought online to meet the WCET. This allows idle high-speed cores to enter a low-power sleep mode, reducing static power consumption.
  • Task Categorization: Tasks are categorized based on their typical and overload execution times relative to their deadlines and available core speeds. This categorization helps determine the optimal core allocation strategy.
  • Category 0: Light tasks that can be scheduled sequentially.
  • Category 1: Tasks that can be scheduled using only low-speed cores.
  • Category 2: Tasks that might require a combination of low-speed cores and potentially high-speed cores or increased low-speed core frequency.
  • Greedy Core Allocation Algorithm: An algorithm is presented to determine the minimum number of low-speed cores required for each task. If insufficient low-speed cores are available, it strategically assigns high-speed cores to compensate, prioritizing tasks that offer the greatest relative core saving.
  • Task-to-Cluster Assignment (Hungarian Algorithm): For multi-speed clustered platforms, they propose a Hungarian algorithm-based approach to assign tasks to clusters. This algorithm aims to minimize the overall energy consumption by considering the energy cost of running a task in different clusters with varying speeds and available core configurations.

Datasets

The paper does not introduce new datasets. Instead, it uses:

  • Randomly Generated Task Sets: For simulation-based evaluation, task sets are generated with varying parameters (number of tasks, execution budgets, critical path lengths, deadlines, and speed ratios).
  • Barcelona OpenMP Tasksuit (BOTS) [21]: For real-time platform experiments, the BOTS benchmark is used. This benchmark consists of 43 tasks that follow the DAG task model, allowing for evaluation of the proposed approach on a realistic workload.

Key Insights and Ideas

  • Typical-Case Optimization is Key: The most significant insight is that focusing on optimizing for typical-case execution, rather than solely worst-case, offers substantial energy savings without compromising safety. This is because real-world task execution is often much faster than the theoretical worst-case.
  • DPM on Clustered Architectures is Challenging but Achievable: Applying DPM effectively to clustered architectures, where cores within a cluster are synchronized, is a non-trivial problem. The paper demonstrates a way to manage this by intelligently allocating low-speed cores and only activating high-speed cores when absolutely necessary.
  • Task Categorization Enables Granular Control: The proposed categorization of tasks allows for a more nuanced approach to resource allocation, ensuring that each task receives the appropriate level of resources based on its criticality and execution profile.
  • Hungarian Algorithm for Optimal Cluster Assignment: Using the Hungarian algorithm for task-to-cluster assignment is a clever way to find an optimal solution for minimizing energy consumption across heterogeneous clusters, considering the complex interplay of task requirements and cluster capabilities.

Key Results

  • Simulation Results: Simulations on randomly generated task sets showed that the proposed approach achieved a schedulability ratio that was directly proportional to the low-speed core frequency, but not strongly correlated with task-set size. Power consumption increased with higher low-speed core frequencies.
  • Comparison with MCFS_Li [39]: The proposed approach demonstrated a power saving of at least 29.23% compared to the MCFS_Li approach, while still guaranteeing real-time correctness.
  • Real-Time Platform Experiments: Experiments on a 12-core Intel Xeon 2680 v3 platform showed energy savings of up to 30% compared to existing Linux governors. The paper also highlights that the proposed approach is robust to different task set sizes.
  • Energy Savings: The authors report up to 30% additional energy savings compared to existing approaches.

Limitations and Future Work

  • Limitations:
    • The current workload characterization assumes only two thresholds: typical execution length and WCET.
  • The paper acknowledges that the energy consumption model might not capture all nuances of modern processors, such as latencies in changing energy states or out-of-order throttling.
  • The real-time experiments used a non-real-time scheduler (CFS), which might not be ideal for strict real-time guarantees.
  • Future Work:
    • Investigate scenarios with more detailed information, such as multiple execution time thresholds or probabilistic execution time information.
  • Explore the impact of other factors on power consumption, including cache misses, context switches, bus accesses, and I/O usage.
  • Extend the evaluation to ARM big.LITTLE architectures and newer Intel processors.
  • Incorporate real-time schedulers for more rigorous real-time guarantees.

Summary updated

BibTeX
@inproceedings{bhuiyan2023precise,
  author = {Ashikahmed Bhuiyan and Mohammad Pivezhandi and Zhishan Guo and Jing Li and Venkata Prashant Modekurthy and Abusayeed Saifullah},
  title = {{Precise Scheduling of DAG Tasks with Dynamic Power Management}},
  booktitle = {ECRTS},
  year = {2023},
  doi = {10.4230/lipics.ecrts.2023.8},
}
Figure