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

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%).