Research On Scheduling Algorithms For Cross-domain Parallel Applications In Grid Environment

As a new generation distributed computing environment, Grids provides unprecedented computing capabilities. Grids connect and organize geographically dispersed computing resources like personal computers and Clusters to form a user-transparent virtual computing environment. Such environment can provide high performance computing to scientific researches and industrial applications. However, Grids resources are heterogeneous and self-administrated in nature. Resource availability in Grids is dynamically changed. On the one hand, geographically dispersed resources bring more communicating latencies to large-scale parallel applications. On the other hand, self-administrated management makes the resource co-allocation for parallel applications even more complicated.As a result, job scheduling subsystem becomes more and more important in a grid system. During the past decades, distributed job scheduling strategies in developed rapidly. However, current scheduling mechanisms can not fit the special requirement in grid environment. As the rapid development of grid environment, job scheduling mechanism for grid environment is becoming a critical issue in this area. Researchers have dedicated their efforts to this topic for years.In traditional cluster-based distributed environment, job scheduler can control the computing resources and manage the resource allocating policies directly. However, resources are managed by different local managers in Grids. Each local schedule programs have their own scheduling policies. Meta-schedulers in Grids can not control the resources completely. In this condition, scheduling mechanisms for Clusters are never suitable for Grids. An outstanding meta-scheduler must work beyond different local schedulers.More and more large-scale communication intensive parallel applications are now benefit from Grids. The cross-domain communicating latency becomes a significant issue in grid-enabled parallel applications. Although current network technologies bring more and more bandwidth to end-users, cross-domain parallel applications are still harass by the network latency. As a result, it is of great significant for us to do more research to solve the scheduling problems for cross-domain communication-intensive parallel applications.In this paper, a genetic-based scheduling algorithm is proposed to solve the scheduling problems of large-scale, cross-domain, communication-intensive parallel applications. The scheduling algorithm presented in this paper minimized the cross-domain communicating latency of a parallel application and used a resource pre-reservation mechanism to optimize resource co-allocation for a parallel application.The genetic algorithm used in this paper reduced random natural selections and choose a more steady selection operator. The scheduling algorithm proposed in this paper uses a gene variation method instead of the traditional cross-gene method. Such method can improve the introductory of the evolution of a new generation. Therefore, this method can ensure that outstanding individuals will survive and poor ones will get washed out.Because the cross-breeding is suitable for the problem in this paper, we use the variation instead. The best solution group goes down to the next generation. Successfully improved solutions of the middle group goes down to the next generation, the solutions which failed the improvement will be taken place by randomly generated solutions. Randomly generated solutions go down to the next generation as well.The scheduling issue of a parallel application is a NP-complexity problem. In this article, the author uses an introductory genetic algorithm to help the scheduling mechanism. The randomly variation of the scheduling decisions improves the entire scheduling solution; oriented selection operator helps to co-ordinate the conflict between the diversity of the sample space and selective pressure. As a result the scheduling algorithm successfully searched the solution space and came up with an optimized scheduling solution.Finally, we implemented a scheduling plug-in for parallel application in CSF meta-scheduler. With the support of the parallel application scheduling plug-in, current version of CSF supports both serial and parallel application scheduling. Through a serious of experiments between MPICH-G2 and CSF environment, we analysis and compare the execution time of parallel applications distributed by these schedulers. Compared with traditional mpi application submitting method, applying CSF's aggregated parallel jobs scheduling plugins to large communication contained MPICH-G parallel applications with different scales, the parallel job scheduling solution based on intensive guidance genetic algorithm represented by this paper could efficiently reduce the correspondence cost of cross-domain execution, and lower the correspondence delay, improved the whole grid computing system's performance.In conclusion, the scheduling algorithm proposed in this paper can minimize the communicating latency of large-scale, cross-domain, communication-intensive parallel applications; and improve the parallel computing capabilities of Grids.In the last section of this paper, we present some future plans of this work. The scheduling algorithm proposed in this paper is proved to be quite efficient and useful in cross-domain environment. In order to improve the efficiency of a grid system, we are planning to integrate our work to other outstanding scheduling algorithms in the future.