Solving Energy-Aware Real-Time Tasks Scheduling Problem with Shuffled Frog Leaping Algorithm on Heterogeneous Platforms

Weizhe Zhang, Enci Bai, Hui He, Albert M. K. Cheng

TL;DR

This paper tackles the complex problem of scheduling real-time tasks on heterogeneous multiprocessor systems to minimize energy consumption while guaranteeing task deadlines. They propose a novel meta-heuristic algorithm based on the Shuffled Frog Leaping Algorithm (SFLA), which significantly outperforms existing methods like ACO and GA in terms of both energy savings and execution time.

What Problem Does This Paper Address?

Modern computing systems, especially those found in embedded and real-time applications (like gaming consoles or aerospace systems), are increasingly employing heterogeneous multiprocessor systems (HMS). These systems offer enhanced performance by using processors with different capabilities. However, scheduling real-time tasks on these HMS presents a significant challenge, particularly when aiming to reduce energy consumption without violating strict deadlines. Traditional approaches like Integer Linear Programming (ILP) become computationally intractable for large problems, while other heuristic methods, though faster, may not achieve optimal energy efficiency. This paper addresses the need for an efficient and effective algorithm that can simultaneously optimize for energy savings and meet real-time constraints on HMS.

Methods

The core of this paper is the adaptation and application of the Shuffled Frog Leaping Algorithm (SFLA) to the energy-aware real-time task scheduling problem on heterogeneous platforms (e-RTSP). SFLA is a meta-heuristic inspired by the foraging behavior of frogs, which involves dividing the population into sub-populations (memeplexes) that perform local searches and then exchange information to achieve a global optimum.

Key modifications and contributions include:

  • Problem Formulation: The e-RTSP is formally defined as a combinatorial optimization problem and then translated into an Integer Linear Programming (ILP) formulation.
  • Discrete SFLA Adaptation: Since e-RTSP is a discrete problem, SFLA, originally designed for continuous optimization, is adapted. This involves:
  • Encoding Scheme: A novel encoding scheme is developed to represent a scheduling solution as a "frog." This involves compressing a scheduling matrix into a one-dimensional array where the index represents the task and the value represents the assigned processor.
  • Fitness Function: A fitness function is designed to evaluate the quality of a schedule, considering both schedulability (meeting deadlines) and energy consumption.
  • Information Transfer Modes: Two discrete information transfer modes are introduced: "Divergent Information Transfer" and "Concentrated Information Transfer," to facilitate effective information exchange between frogs within and between sub-populations.
  • Enhancements for SFLA: To address common drawbacks of SFLA, the authors incorporate:
  • Precocity Remission: An algorithm is introduced to disturb the global best solution (Px) to maintain population diversity and prevent premature convergence.
  • Local Optimal Avoidance: A mechanism is implemented to prevent the algorithm from getting stuck in local optima by assigning higher selection probabilities to fitter frogs.
  • Convergence Acceleration: A neighborhood search is applied to the initial population to improve the quality of the starting solutions, leading to faster convergence.

Datasets

The paper utilizes two types of datasets for evaluation:

  • Synthetic Data Sets: These are generated following a methodology described in [11], incorporating variations in processor and task heterogeneity. The generation process involves creating utilization matrices based on various combinations of processor and task characteristics (e.g., "Consistent, High φτ, High φρ"). A total of 120 test instances are generated, with each instance run 10 times.
  • Real Data from Benchmarks: Data is sourced from the Embedded System Synthesis Benchmarks Suite (E3S) [37], which provides real-world data for various benchmarks (e.g., Automotive/Industrial, Networking). For their experiments, they select four specific processors and assign 46 tasks to them.

Key Insights and Ideas

  • SFLA's Adaptability: The paper demonstrates that SFLA, a meta-heuristic, can be effectively adapted to solve complex discrete optimization problems like energy-aware real-time task scheduling, which was not its primary design domain.
  • The Power of Hybridization: By combining population-based global search with sub-population-based local search, SFLA offers a powerful approach that leverages the strengths of both global exploration and local exploitation.
  • Addressing SFLA's Weaknesses: The proposed enhancements (precocity remission, local optimal avoidance, convergence acceleration) are crucial for making SFLA performant on this specific problem, highlighting that off-the-shelf meta-heuristics often require tailored modifications.
  • Energy vs. Time Trade-off: The results strongly suggest that significant energy savings can be achieved without a prohibitive increase in computation time, a critical factor for real-time systems.

Key Results

The experimental results demonstrate the effectiveness of the proposed SFLA-based algorithm (referred to as D-SFLA and C-SFLA depending on the information transfer mode):

  • Energy Consumption: D-SFLA uses 30% less energy than the Ant Colony Optimization (ACO) algorithm and 60% less energy than the Genetic Algorithm (GA) algorithm.
  • Execution Time: The D-SFLA algorithm finds feasible solutions significantly faster, being 20 times less time-consuming than ACO and 200 times less time-consuming than GA.
  • Feasible Solutions: The algorithm consistently finds feasible solutions, with D-SFLA and C-SFLA acquiring feasible solutions in less than 20 ms across various test conditions.
  • Comparison with ILP: Integer Linear Programming (ILP) is found to be the most time-consuming, taking nearly 1000 times longer than D-SFLA/C-SFLA. While ILP aims for optimality, its computational cost makes it impractical for large-scale problems.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Task Model Simplification: The current research focuses on independent, periodic real-time applications with hard deadlines.
  • Future Work:
    • Relaxing Task Model: Future work will consider more complex scenarios, including tasks with precedence constraints and inter-task communication.
  • Energy Model Expansion: The current energy consumption model primarily focuses on CPUs. Future research will investigate the additional energy consumption from memory access and I/O devices.

Summary updated

Abstract

Reducing energy consumption is becoming very important in order to keep battery life and lower overall operational costs for heterogeneous real-time multiprocessor systems. In this paper, we first formulate this as a combinatorial optimization problem. Then, a successful meta-heuristic, called Shuffled Frog Leaping Algorithm (SFLA) is proposed to reduce the energy consumption. Precocity remission and local optimal avoidance techniques are proposed to avoid the precocity and improve the solution quality. Convergence acceleration significantly reduces the search time. Experimental results show that the SFLA-based energy-aware meta-heuristic uses 30% less energy than the Ant Colony Optimization (ACO) algorithm, and 60% less energy than the Genetic Algorithm (GA) algorithm. Remarkably, the running time of the SFLA-based meta-heuristic is 20 and 200 times less than ACO and GA, respectively, for finding the optimal solution.
BibTeX
@inproceedings{zhang2015solving,
  author = {Weizhe Zhang and Enci Bai and Hui He and Albert M. K. Cheng},
  title = {{Solving Energy-Aware Real-Time Tasks Scheduling Problem with Shuffled Frog Leaping Algorithm on Heterogeneous Platforms}},
  booktitle = {Sensors},
  year = {2015},
  url = {https://openreview.net/forum?id=UWiempeFwI},
}

Loading related content...

Figure