Research Of Scheduling Algorithms Based On The DAG Model In Clusters

In recent years, cluster system becomes the major platform of high performance computing.While the parallel computing system has a huge potential in the calculation, the task scheduling is thekey technology. As for the scheduling problem, the parallel computing system usually divides tasksinto many sub-tasks, which can execute at the same time. Since, the DAG (directed acyclic graph)could be used to represent accurately the sub-tasks and the relationship among them, it is widely adoptin task scheduling algorithms. This paper aims at solving the scheduling problem in cluster systembased on DAG. The main contributions are as follows:Firstly, aiming at the scheduling problem in the homogeneous clusters, list scheduling algorithmis studied. After analyzing the limitations of the existing list scheduling algorithms, the paperproposes GDCP algorithm (a global scheduling algorithm based on dynamic critical path). In GDCPalgorithm, tasks on the critical path have the priority to be scheduled in each scheduling step, and theschedule length can be reduced monotonically by proposing a global search strategy to select asuitable processor to execute a task.Secondly, for the scheduling problem in the heterogeneous clusters, the genetic algorithm isapplied. Because of the deficiencies of conventional genetic algorithm on the population initialization,the paper presents a new scheduling algorithm ISGA, which is based on genetic algorithm andcombined with list scheduling technique. It uses the attribute values of tasks in the construction of thechromosome, and the quality of the population is improved effectively. Thus, the better schedulingperformance is obtained than other conventional algorithms.Thirdly, the paper applies the proposed algorithms, i.e. GDCP algorithm and ISGA algorithm tothe collaborative project named "parallel processing real-time monitoring system", which is initializedby State Grid Electric Power Research Institute, in order to verify their effectiveness in the practicalcomputing environment.