Task Scheduling Research Based On Tree-based Grid

With the flourishing of grid computing in recent years, people has been trying to integrate the heterogeneous resources distributed around the world into a uniformly computing infrastructure. For a grid to support a variety of applications with high performance, effective scheduling of tasks is an important issue, and becomes one of the research focuses. Considering task data dependence, and the uncertainty of the grid topology as well as the heterogeneity, task scheduling in grid environment becomes more difficult than traditional parallel task scheduling.The directed acyclic graph model is commonly used in static scheduling of a parallel computing problem, in which the nodes represent the tasks and the directed edges represent the execution dependencies as well as the amount of communication. The critical path is a longest path in DAG. We modified the DAG model, uses list scheduling technique with dynamically critical path to reduce the overall finish time of a parallel program.This thesis presents a compile-time scheduling heuristic algorithm in a tree-based grid architecture using the DAG model first, which accounts for data dependence and heterogeneity of gird overhead, this technique uses dynamically critical path to select task nodes, and earliest finish time strategy to mapping tasks with processors at each step. Based on this, we developed a new algorithm for the high computing communication rate situation with task pre-collocate method.After the simulation and analysis, we found that, the two algorithms could get the anticipated schema both, the new algorithm can reduce the complexity efficiently in proper environment.At last, the dissertation concludes by summarizing the research and indicating its future way.