Research Of Task Scheduling Algorithms For Heterogeneous Computing Environment

With the development of computer technology and the expansion of computer application scope, heterogeneous computing systems have been widely used in the parallel applications. As the key issues of parallel processing,task scheduling is more complex in the heterogeneous computing systems because of different process capability among processors, and it has become a difficult problem that is urgent to be solved.The objective of task scheduling is to reduce the total execution time on the condition that certain performance indicators and given constraints can be satisfied.Task scheduling problem has been proved to be a NP-complete problem in the most of situations,which make heuristic methods to be widely used in the research of scheduling problem.In this paper,we make a research of task scheduling in the heterogeneous computing systems,and two algorithms are proposed in the classic task model.The main research of this paper as below:(1)The list-scheduling algorithm driven by priority selects tasks to schedule on by single attribute.But in the case of that different tasks should have the same priority,it can not work well.Therefore a new synthesized heuristics algorithm called HCPFS was proposed. In the stage of task selection,there are three levels of priority in the algorithm to choose task. First, the tasks in critical path have highest priority, secondly the tasks with longer path to exit task will be selected, and then algorithm will choose tasks with more successors to schedule.In the stage of task assigning,we choose the processor which minimize the earliest finishing time of current task,we also take task duplication method and task insert method to make full use of processor resouces.(2)The start time, completion time and execution time of current task is often the accordance of task allocation,such method always takes unnecessary task duplication in the scheduling algorithm with duplication method. This paper presents an algorithm called HSFE which is based on minimizing the earliest completion time of the successors to be scheduled next time.Current tasks is allocated to one processor according to the relationship between current task and next task.When current task is the predecessor of next task,it will be scheduled to the processor which can minimize. the earliest completion time of next task.This method can suppress unnecessary replication of tasks, increase scheduling space,and improve system efficiency effectively.To validate the effectiveness of the algorithms proposed,we simulate them and other algorithm used for comparison, using a variety of test solutions from multiple angles. Experimental results show that HCPFS algorithms can suppress blindfold task scheduling when there are serveral tasks which one of priorities is same,and that HSFE algorithms can effectively suppress unnecessary replication task.They both achieve relatively better performance in a number of evaluation parameters,such as Schedule Length Ratio,Speedup and Average Task Duplication Ratio, and so on.