Energy-aware scheduling on heterogeneous multi-core systems with guaranteed probability

• Published in: Journal of parallel and distributed computing 2017-05, Vol.103, p.64-76
• Main Authors: Li, Ying, Niu, Jianwei, Atiquzzaman, Mohammed, Long, Xiang
• Format: Article
• Language: English
• Subjects: Accelerated search algorithm; Heterogeneous multi-core embedded system; Minimum energy model; Optimized energy scheduling; Probability statistics
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1016/j.jpdc.2016.11.014

The main challenge for embedded real-time systems, especially for mobile devices, is the trade-off between system performance and energy efficiency. Previous works mainly focused on finding an optimal tasks assignment with the minimum energy under the constraints of time or architecture. In this paper, we propose an Accelerated Search (AS) algorithm based on Dynamic Programming (DP) to obtain a combination of various task schemes which can be completed in a given time with the minimum possible energy by introducing the guaranteed probability and data migration energy. We adopt a DAG (Directed Acyclic Graph) to represent the dependent relation between tasks and develop a Minimum-Energy Model to find the optimal tasks assignment. The heterogeneous multi-core architectures can execute tasks under different voltage levels with DVFS (Dynamic Voltage and Frequency Scaling) which leads to different execution times and different consumption energies. We first design a Minimum Energy Under Probability Constraints (MEUPC) algorithm to assign a proper core and proper voltage level to each task to satisfy the probability constraints with the minimum energy and then a Leaf-Partition (LP) algorithm is used to determine the execution sequence on each core according to the position of the task in DAG. Finally, a Trading Energy For Time (TEFT) algorithm is proposed to explore the opportunity the parallelism of the tasks to reduce the execution time. The experimental results demonstrate that our approach outperforms state-of-the-art algorithms in this field (maximum improvement of 30.7%). •Propose an energy-aware algorithm to schedule task with guaranteed probability.•Design an accelerated search algorithm based on dynamic programming.•Express the relation of energy, time and probability based on energy-minimum model.•Propose task migration energy.•Establish a heterogeneous multi-core real-time system with DVFS.