Parallel Genetic Algorithm And Application Research Of Task Scheduling In Grid

The Grid Computing aims to provide an integrated computer platform among thelarge number of heterogenic resources, and has becoming an important developmenttrend for parallel and distributed computing technology. Among them, the taskscheduling is an important component of high performance computing, at the mean time,is also the key to ensure the effective executing of application.The problem of grid task scheduling can be stated as allocating the task of a gridsystem which involves program model and parallel computing system model,Scheduling algorithms should consider both of application and the characteristics of thetarget system, is a typical NP problem. Because of the strong capability of globalsearching, genetic algorithms have more advantages than the traditional schedulealgorithms when dealing with the task scheduling problem. However, there are somedisadvantages in basic genetic algorithm, such as low precision of the result and is tofall into the myth of “Premature convergence”. In this paper, we study the approach torealize parallel genetic algorithm based on MPI, which is applied to deal with the gridtask scheduling problems.The article first briefly analysis the basic principle of genetic algorithm, in view ofthe traditional genetic algorithm,s parallelism proposed a coarse-grained parallel geneticalgorithm from a global perspective. The algorithm adopts a distributed parallel mode,through the sub-population of individual migration strategy, effectively alleviate the“early convergence” and solving the low accuracy problem, simultaneously the elitistmechanism is introduced to improve the precision of the algorithm.Secondly, study the principle and process of grid task scheduling, and analyze thescheduling model, compared with the existing scheduling algorithms and ultimatelydetermine that using parallel genetic algorithm for task scheduling scheme, aiming atthe dependent relationship among the sub-tasks in grid environment and realizing theoptimal span of the task scheduling algorithm.At last, in view of the dynamic, heterogeneous, distributed grid computingenvironment, we adopt C language and Message Passing Interface (MPI) to realize theparallel genetic algorithm. Let the traditional algorithm and the new algorithm designedin this paper separately apply to the grid task scheduling problem and simulate in the grid environment PC Cluster, analysis the task scheduling span of different scale oftasks, the analysis results show that the new algorithm designed in this paper has thebetter search capability, it can achieve the optimal span in dealing with grid taskscheduling problem.