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

Zhang W, Bai E, He H, Cheng AM - Sensors (Basel) (2015)

Bottom Line: 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.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.

View Article: PubMed Central - PubMed

Affiliation: School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China. wzzhang@hit.edu.cn.

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.

No MeSH data available.


Related in: MedlinePlus

The average runtime and feasible solution numbers of for ILP, GA, ACO, D-SFLA and C-SFLA algorithms: (a) average time; and (b) feasible solution number.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4507628&req=5

sensors-15-13778-f008: The average runtime and feasible solution numbers of for ILP, GA, ACO, D-SFLA and C-SFLA algorithms: (a) average time; and (b) feasible solution number.

Mentions: Figure 8 shows: (1) Average time: ILP is the most time-consuming to acquire feasible solutions, which is nearly 1000 times more than the D-SFLA and C-SFLA algorithms. GA and ACO also cost more time than D-SFLA and C-SFLA, which are 200 times and 20 times more, respectively, than the SFLA ones. The D-SFLA and C-SFLA algorithms can acquire the feasible solution in less than 20 ms in all the conditions. (2) Feasible solution number: The ACO algorithm can acquire all the 150 solutions, which has the best performance. The feasible solution numbers of ILP, GA and D-SFLA are almost the same, which is 7% less than that of the ACO algorithm. However, the feasible solution number of the C-SFLA algorithm is 20% less than that of the other algorithms. Thus, we choose the GA, ACO and D-SFLA to compare the energy consumption.


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

Zhang W, Bai E, He H, Cheng AM - Sensors (Basel) (2015)

The average runtime and feasible solution numbers of for ILP, GA, ACO, D-SFLA and C-SFLA algorithms: (a) average time; and (b) feasible solution number.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4507628&req=5

sensors-15-13778-f008: The average runtime and feasible solution numbers of for ILP, GA, ACO, D-SFLA and C-SFLA algorithms: (a) average time; and (b) feasible solution number.
Mentions: Figure 8 shows: (1) Average time: ILP is the most time-consuming to acquire feasible solutions, which is nearly 1000 times more than the D-SFLA and C-SFLA algorithms. GA and ACO also cost more time than D-SFLA and C-SFLA, which are 200 times and 20 times more, respectively, than the SFLA ones. The D-SFLA and C-SFLA algorithms can acquire the feasible solution in less than 20 ms in all the conditions. (2) Feasible solution number: The ACO algorithm can acquire all the 150 solutions, which has the best performance. The feasible solution numbers of ILP, GA and D-SFLA are almost the same, which is 7% less than that of the ACO algorithm. However, the feasible solution number of the C-SFLA algorithm is 20% less than that of the other algorithms. Thus, we choose the GA, ACO and D-SFLA to compare the energy consumption.

Bottom Line: 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.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.

View Article: PubMed Central - PubMed

Affiliation: School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China. wzzhang@hit.edu.cn.

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.

No MeSH data available.


Related in: MedlinePlus