A Task Scheduling Algorithm Based On Weight Ratio Of Makespan To Energy

Heterogeneous parallel system is one of the developing trends of high-performance and low-power computer system, and the research of low energy consumption for these systems is a hot issue in recent years. Due to the advantage of energy consumption optimization of DVFS technology and task scheduling, lots of task scheduling algorithms based on DVFS technology are proposed and achieve good results. However, these algorithms can not make a balance between task's makespan and energy consumption because they do not consider this two performance goals comprehensively. And these algorithms used average value of task's execution time and inter-task communication time in their task model, which is inaccurate and has a bad influence on the performance of task scheduling.The weight-ratio-based task scheduling algorithm(WTS), associated with DVFS technology, considers both the makespan and energy consumption and assigns tasks to their best suitable processors and voltage level based on the weight ratio of makespan to energy consumption, which can make a good balance between the makespan and energy consumption and maximize the weighted performance of system. At first assignment period, WTS algorithm assigns tasks to processors and voltage level which makes this task's weighted performance biggest. At reassignment period, this algorithm randomly chooses a task and reassigns this task to processor and voltage which enhances system weighted performance relative to the original assignment to further improve system Performance. Meanwhile, the WTS algorithm takes the uncertainty of task's execution time and inter-task communication time into account and use the approximate weight instead of the average value in the task model.To prove the WTS algorithm's validity, the simulation experiments compare it with two existing algorithms in terms of makespan, energy consumption, system weighted and relative weighted improvement respectively. The results of simulations show that WTS algorithm can make a good balance between the makespan and energy consumption and maximize the weighted improvement of system. In addition, WTS algorithm is also very competitive in terms of both makespan and energy consumption.