Study On Grid Task Scheduling And Optimization Mechanism

The goal of Grid is to connect all kinds of distributed and heterogeneous computation resources together by the high speed network for solving large-scale application problems in coordination,realizing distributed sharing of wide area information resources,finally conforming the entire Internet into a super virtual computer and realizing comprehensive sharing of computation resources,memory resources,data resources,information resources,knowledge resources and expert resources.In Grid computing,a key point is how to carry out the most effective management and how to effectively complete all kinds of computing tasks by use of giant Grid resources.It needs to be solved by Grid task scheduling.The heterogeneity of Grid computation resources is extremely suitable for execution of applications in which there are many kinds of intrinsic parallelisms.It is the direction of Grid task scheduling technology to schedule application programs to be executed on heterogeneous computation nodes in order to obtain the most superior or the near superior performance targets.The goal that makes good use of resources to improve the performance of task scheduling can be achieved by constructing Grid task scheduling model and realizing task scheduling based on the model.Task scheduling is an important part of Grid computing.It has always been an active research area in international and domestic academic circles.The main work and contributions are presented in the following aspects:(1)A Grid task scheduling model is proposed and a Grid optimized directed hypergraph task scheduling algorithm,GODHTS,is proposed based on the model.In allusion to shortages of task scheduling in conventional distributed system,a basic Grid task scheduling model is constructed by combining hypergraph theory with characteristics of Grid environment for making task scheduling adapt to the characteristics of Grid environment and making good use of advantages of Grid.A hypergraph delamination model is constructed according to characteristics of tasks and resources.A distributed structure of scheduling is proposed according to scale-free and small world theory.Effective Grid task scheduling mechanisms are proposed based on the model.Mapping and scheduling from tasks to Grid resources are realized by making use of level structure,tab and bandwidth computing of Grid optimized directed hypergraph,and a Grid optimized directed hypergraph task scheduling algorithm, GODHTS,is proposed.The rationality and validity of the mechanism are proved by Analysis and simulation results.(2)A task scheduling mechanism based on multidimensional performance clustering of Grid service resources,MPCGSR,is proposed.Combined with scale-free and small world principle,multidimensional performance clustering of service resources is executed in advance based on Grid service resource hypergraph model constructed according to characteristics of Grid resources such as great quantities,heterogeneity and multiplicity.Tasks are matched to clustering resources and scheduled.Theory analysis and simulation results show that it is a effective Grid task scheduling mechanism and the algorithm is superior to kindred algorithms.(3)A resource hypergraph partitioning clustering based Grid task scheduling mechanism,RHPC,is proposed.In the mechanism,partitioning clustering of resource hypergraph is executed in advance based on Grid resource hypergraph model constructed according to characteristics of Grid resources.Tasks are matched to clustering resources and scheduled.Simulation results show that it is a effective Grid task scheduling mechanism that shortens the matching time between the task and the resource and improves the performance of task scheduling.(4)A directed hypergraph partitioning based Grid task scheduling algorithm, HPGTS,is proposed.According to characteristics of task scheduling in Grid and traditional DAG,a directed hypergraph model of Grid task based on partitioning is built by drawing advantages of directed hypergraph and combining hypergraph theory with characteristics of Grid environment.Based on the model,mapping and scheduling from tasks to Grid resources are realized by directed hypergraph partitioning of Grid tasks combined with trustworthy degree,and a directed hypergraph partitioning based Grid task scheduling algorithm,HPGTS,is proposed.Analysis and simulation results show that validity and superiority of the proposed model and algorithm are obvious. (5)A combined evolutionary computation based Grid task scheduling algorithm, CEGTS,is proposed.For heterogeneous and distributed Grid,a combined evolutionary computation based Grid task scheduling algorithm,CEGTS,is presented by combining the advantage of genetic algorithm with that of ant algorithm based on a double-deck genetic structure. Simulation results show that the proposed algorithm performs better than any other kindred scheduling algorithm in Grid.