A hybrid algorithm for task scheduling on heterogeneous multiprocessor embedded systems

• Published in: Applied soft computing 2020-06, Vol.91, p.106202, Article 106202
• Main Authors: Taheri, Golnaz, Khonsari, Ahmad, Entezari-Maleki, Reza, Sousa, Leonel
• Format: Article
• Language: English
• Subjects: Evolutionary algorithms; Power consumption; Real-time embedded systems; Task graph
• ISSN: 1568-4946; 1872-9681
• DOI: 10.1016/j.asoc.2020.106202

Most of the scheduling algorithms proposed for real-time embedded systems, with energy constraints, try to reduce power consumption. However, reducing the power consumption may decrease the computation speed and impact the makespan. Therefore, for real-time embedded systems, makespan and power consumption need to be considered simultaneously. Since task scheduling is an NP-hard problem, most of the proposed scheduling algorithms are not able to find the multi-objective optimal solution. In this paper, we propose a two-phase hybrid task scheduling algorithm based on decomposition of the input task graph, by applying spectral partitioning. The proposed algorithm, called G-SP, assigns each part of the task graph to a low power processor in order to minimize power consumption. Through experiments, we compare the makespan and power consumption of the G-SP against well-known algorithms of this area for a large set of randomly generated and real-world task graphs with different characteristics. The obtained results show that the G-SP outperforms other algorithms in both metrics, under various conditions, involving different numbers of processors and considering several system configurations. [Display omitted] •We propose a hybrid task scheduling algorithm for heterogeneous computing systems.•The algorithm is based on spectral partitioning and genetic algorithm.•The spectral partitioning is used in the proposed algorithm to partition a task graph with timing and precedence constraints.•The genetic algorithm used in the proposed algorithm schedules subtasks in order to minimize the deadline miss ratio and makespan.•Experimental results show that our proposed method outperforms other well-known algorithms in terms of power consumption and makespan.