Title | ||
---|---|---|
A hybrid algorithm for task scheduling on heterogeneous multiprocessor embedded systems |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1016/j.asoc.2020.106202 | Applied Soft Computing |
Keywords | DocType | Volume |
Power consumption,Real-time embedded systems,Evolutionary algorithms,Task graph | Journal | 91 |
ISSN | Citations | PageRank |
1568-4946 | 2 | 0.36 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Golnaz Taheri | 1 | 3 | 1.38 |
Ahmad Khonsari | 2 | 210 | 42.43 |
Reza Entezari-Maleki | 3 | 2 | 0.70 |
Leonel Sousa | 4 | 1210 | 145.50 |