Research On Scheduling Algorithm For Parallel Job Modeled By Directed Acyclic Graph

The parallel computing mode called as workstation cluster is undoubtedly an important research focus in parallel and distributed computing field. At the same time, the parallel computing environment is expanded to wide area network from local area network with the development of internet technology. A new parallel and distributed computing mode named as grid computing based on the internet is becoming as popular as the workstation cluster. However, how to schedule the tasks of the parallel job is a key factor which affects the successful implement of the workstation cluster or gird computing. So the studying on the algorithms of multi-processor or multi-computer task scheduling is meaningful for both of theory and practicality.The problem about the task scheduling of the parallel job has been studied for a long time since the concept of the parallel processing and the parallel computing. The research results achieved by anterior scholars show that almost the task scheduling of parallel jobs is a NP-hard problem even under the simple model. So that acquiring an optimal solution about the task scheduling problem of the parallel jobs is unpractical under the premise of the acceptable time complexity. Reversely, the heuristic task scheduling algorithm is being widely adopted because it has many good attributes such as easy implement, nice performance and low time complexity. Based on the existed classical algorithms, we presents a series of the task scheduling algorithm include the static compile-time scheduling algorithm, the dynamic runtime scheduling algorithm and the real-time scheduling algorithm.The DAG(Directed Acycle Graph)model is adopted to describe the relation between tasks of parallel job in all proposed heuristic algorithms. This kind of model has better capacity to illuminate the actual state of parallel job than the other model. The factor of different processing capacity of CPU is also considered in proposed algorithms. First, two classical static task scheduling algorithms HEFT and CPOP in heterogeneous environment are investigated and analyzed. Based on these we propose a new static scheduling algorithm LBP in which the task's level and branches are regarded as the task priority. At present the almost static heuristic scheduling algorithms include HEFT and CPOP are list scheduling algorithm based on the critical path. But under the heterogeneous environment the tasks on the critical path are not always the urgent task. So the algorithm LBP abandons the idea about the critical path and considers the task level and branches as the task priority. The theory proved and experiments show that the algorithm LBP has not only the same time complexity as the algorithm HEFT and CPOP but also better scheduling performance than them.Otherwise, the algorithm LBP has natural parallel characteristic. Because the task scheduling algorithm is commonly inherent serial algorithm the study on the parallelizing of the static task scheduling algorithm is not often seen. Although the time complexity of the static heuristic scheduling algorithm is often lower, it may cost so much time to schedule the task when the scale of DAG is great. According to the relativity of data and operations in the algorithm LBP steps, we propose the parallel algorithm edition PLBP of the serial algorithm LBP. The algorithm PLBP has same scheduling performance as LBP proved by the relevant theory. Compare to the parallel scheduling algorithm HPMCP and PBSA in the literature, the algorithm PLBP has lower time complexity.Then, the static scheduling algorithm is limited to the premise that all parameters of tasks in DAG must be obtained before the task being scheduled. But this demand couldn't be satisfied in the scientific computation because the task parameter is only instantiated after its all father tasks are finished. So scheduling and executing of each task in DAG go along alternately. Analyzed on some classical dynamic scheduling algorithms, we emphasize the study on the dynamic scheduling algorithms PTGDS built on the model of PTG (Parameterized Task Graph). The idea of the algorithm LBP is taken in and the algorithm PTDGS is improved at both of synchronization of task scheduling and scheduling strategy. Ground on these we present the dynamic task scheduling algorithm IPTGDS of parallel job. The algorithm IPTGDS is proved to be valid and the results of simulation test show that the algorithm IPTGDS has better scheduling performance than PTGDS.Finally, some successful ideas of static and dynamic task scheduling algorithms based on DAG are introduced to the real-time processing system. A dynamic real-time task scheduling model is built under the heterogeneous environment. Ground on it a dynamic real-time scheduling algorithm DEFF is proposed. At the meantime, a classical dynamic real-time scheduling algorithm called the myopic algorithm is investigated. We present another new dynamic real-time scheduling algorithm BBDS base on the restricted backtracking according to the backtracking idea of the myopic algorithm. The algorithm BBDS differs from the myopic algorithm at: the myopic algorithm aims at the independent task set and the algorithm aims at the DAG; the algorithm BBDS has more precise and strict backtracking control than the myopic algorithm; the evaluation function adopted by the algorithm BBDS is improved. For the sake of meeting the fault-tolerant need of the real-time processing system, a fault-tolerant edition FTBBDS of the algorithm BBDS is designed. The theory proved shows that the time complexity both of the algorithm BBDS and FTBBDS is O(nm3). In the simulation tests, several main parameters which affect the scheduling success ratio of the algorithm DEFF, BBDS and FTBBDS are compared and analyzed.