Independent Task Oriented Periodic Tasks Scheduling And Topology Optimization Of Tree-based Grid

With the rapid development of the Internet, grid computing and cloud computingbecoming the effective tools to solve large scale and complex applications. Also it’s one of theimportant parts of national information infrastructure. Cloud computing originated from gridcomputing. To both of them, resource management and task scheduling are the criticalproblems to solve when we deal with practical applications.This paper based on independent tasks to analyze periodic scheduling and topologyoptimization under tree-based grid computing platform. The achievement of this research canbe used in grid computing and clouding computing. The main works in this paper are asfollows:(1) An integer linear programming model for scheduling independent tasks onsingle-level tree grid computing platform is presented, where resources have different speedsof computation and communication. By analyzing the procedure of solving the linearprogramming model, and getting the optimal number of tasks assigned to each computingnode, we find that a grid system composed of different nodes will be in one of three states,respectively: unsaturated, critical and redundant state, and some features and theories todetermine the state of grid system is obtained. Base on the fact that the optimal number oftasks assigned to each node is increasing linearly, as the number of tasks arriving to the masterare growing, the periodic scheduling of independent tasks on single-level grids is put forward,and the length of period is derived. And so, the problem of large-scale independent taskscheduling is simplified and resolved in one period, which reduces the computationalcomplexity dramatically. Test Results show that the idea of periodic scheduling is feasible.(2) Based on the result of independent task periodic scheduling on star-based grid, newtopology optimization of star-based grid is put forward: static and dynamic optimization, byanalyzing the linear programming model and different features that grid platform presentswhen it’s in diverse states. First of all, we give a way to measure the computing capability andutilization rate of resources on star-based grid, and then, for static optimization, identification problem of optimal grid topological structure is solved, and algorithm to build optimal gridplatform is suggested. For dynamic optimization, we discuss admitted strategies of a newnode on grid platform, when the topological structure of the grid happens to change. Thepolicy of scalability of topological structure of the grid is given, by mapping computingcapability to dynamic workloads.(3) After derived the solutions of periodic tasks scheduling and topology optimizationunder star-based grid, by introducing the Push-Pull method and using equivalent calculationand iteration change the tree-based grid into star-based grid. Then solve the periodicscheduling and topology optimization problems under tree-based grid.