Research On Scheduling Algorithm For Meta-task Of Grid Based On Execution-time Variance

Grid Computing is one special branching network computing which is contented with innovative ideas and huge potential. The goal to Gird Computing is the resource sharing and distributed teamwork. Task scheduling as one of important aspects in Grid High Performance Computing influences the performance of Grid Computing. As the grid works up to standardization, upsizing, merging in multi-technique, higher requirements are needed to task scheduling. Job scheduling algorithm becomes one of hotspots on the research of Grid.This paper introduces the property, the architecture, current situation on Grid Computing; analyses the target, mathematical model, static or dynamic algorithm. Based on the basic theory, I review the experience of job scheduling algorithm Min-Min, Max-Min, MAX-INT, in view of isomerism on the Grid; put forward a new improved algorithm Q_VARIANCE, on the aspect of opportunistic load balancing and makespan. First, this algorithm is based on meta-task; makes the variance to the execution time on each host as the metewand. Then, I use mathematical expectation as the boundary to the grouping of tasks, the bigger group on variance and the smaller group on variance. Divide batch tasks into a lot of turns on the base of one parameters of baseline. The number of the tasks each group assigned is based on some corresponding proportion. This algorithm improves the balance of the load and cuts down the makespan of tasks. Use the algorithm of MIN-MIN and MAX-INT as the contrast. This paper shows the experimental results on the comparison of the load balance and the makespan among Q_VARIANCE and three related algorithms, in the Gridsim under the NETBEANS. It turns out Q_VARIANCE has a very good performance and is adequate for e Arrays under any kinds. And it also gets better results than Min-Min and MAX-INT.In the end, except the conclusion of my work, this paper also looks forward to the developmental direction of this research. Pictures 14, tables 19, references 33.