Study On Task Scheduling Problem In Heterogeneous Environment

The research of task scheduling method is one of the basic computer science subjects. In recent years, the emergence of multiprocessor structure poses new challenges to this subject. The task scheduling of multiprocessor system is to assign a number of tasks to processors, and make the task completion time shortest. Effective task scheduling method will greatly improve the computation ability of multiprocessor systems, and reduce unnecessary consumption. Due to the different characteristics of the processors, the task scheduling in the heterogeneous system is particularly complicated.In heterogeneous environment, task scheduling method mainly contains two steps: first, the application is divided into several tasks, the application model is generated and the parallelism of tasks is obtained as possible. Second, according to the application model, the tasks are assigned to appropriate processors by a certain task scheduling algorithm.The study objects of this paper are dependent task and independent task. The paper intends to conduct a deep study on the task scheduling method of the heterogeneous multiprocessor system. Through the improvement of dependent task scheduling algorithm and independent task scheduling algorithm, task completion time is shortened and computational complexity is reduced. The detailed work is as follows:(1) The application model is introduced from task model and process model. Comparison and analysis are made among the current task division method, task scheduling model and process model.(2) The exiting dependent task scheduling method is studied according to the Task Precedence Graph. The deficiency of Min-Min algorithm is found by analyzing the Min-Min algorithm. As for the processor performance are greatly different and short tasks outnumbers long tasks, Min-Min needs a long time to complete tasks and the load imbalance of processors appears. Therefore, this paper puts forward an improved algorithm which is called Div-Sub. Before assigning tasks, Div-Sub considers the current processor load, and schedule tasks to the appropriate processors which can complete the entire tasks in a shortest time. The simulation results show that Div-Sub is obviously 7% better than Min-Min in terms of the task scheduling time and it is an efficient dependent task scheduling algorithm.(3) The exiting independent task scheduling method is also studied according to the Directed Acycling Graph. This paper puts forward an improved algorithm which is called Accurate Priority Scheduling (APS) to modify the two kinds of deficiency of HEFT. One deficiency is HEFT calculates task priorities for only once and the priorities can't be changed. While APS can calculate priorities for a second time which can dynamically reflect the changes of task priorities. The other deficiency is HEFT calculates priorities by only one parameter which can cause inaccuracy, while APS adds a new parameter to assess the priority. The simulation results show that the task completion time of APS is in most cases 10% shorter than that of HEFT, which is a great improvement in terms of efficiency. APS is an efficient dependent task scheduling algorithm.