The Duplication Based, Heterogeneous And Dynamic Scheduling Of Grid Computational Tasks

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 efficiently support a variety of applications, effective scheduling of grid tasks is an important issue, and becomes one of the research focuses. Considering the dynamism, heterogeneity, uncertainty of grid nature as well as QoS demands, task scheduling in grid environment becomes more difficult than traditional parallel task scheduling.In this paper, we examined three grid task scheduling strategies respectively, each of which emphasizes a specific problem: improving node's processor utilization with task duplication, approximation scheduling of multiprocessor tasks considering resource heterogeneity, and realtime scheduling with deadline constraints under dynamic grid environment. With these solutions combined, traditional parallel scheduling algorithms can be adapted to grid environment. First, we further exploit the algorithm of DAG partition and sub-graph reconfiguration, and propose a grid task duplication strategy emphasizing the increment of scheduling length. Using this strategy, the restriction problem between clusters is effectively solved. We also present a DAG scheduling algorithm based on task clustering and duplication, which is characterized by expanding and merging clusters, and has advantages in both scheduling length and processor utilization over the original algorithm. Second, we exploit the heterogeneous characteristics of grid in multiprocessor task scheduling. We analyze the problem of heterogeneous P₃|fix|C_max and propose a novel semi-normal scheduling strategy with the processor capacity factor. Third, we take the dynamism of grid resource into account in task scheduling, and combine the tendency-based load prediction method with the thrift dynamic scheduling algorithm, in order to satisfy deadline constraints and provide better success rate. Last, the problems requiring further studies are discussed.