Research For DAG Based Parallel Tasks Scheduling Algorithm In Grid-Computing

Grid computing environment has increasingly grown a very cheap supercomputing environment beyond area limit. Task scheduling has become a hot research area recently, which guarantees the efficient use of grid resource. This paper is based on the research of power grid, proposes two DAG based scheduling algorithm in consideration of heterogeneous of grid and dependency of tasks. It is convenient to apply our algorithms to other computing grid.Considering real time and efficiency requirement of computing tasks from power system, if grid computing technology is applied to power system computing and simulation, it can be benefited from the strength of grid computing, and construct a completely heterogeneous power grid platform to satisfy high performance computing requirement from power system. Lots of Jobs in power grid contain sub-jobs depending on each other, which can be represented as a DAG. The scheduling problem in power grid can be considered as scheduling the DAG.The computing abilities of machines on the grid are different. Some types of sub-jobs can only be scheduled to specific machines, and some sub-jobs can be distributed on several machines to accelerate its execution. In order to measure this heterogeneousness of grid, we defined two concepts, job and machine calculability. And this paper proposed a DAG based heuristic, which utilizes the job and machine calculability, and supports resource reservation.Besides different calculability, grid suffers different network connections. Network between different resource domains are restricted and unstable. Our proposed another list algorithm based on this property. We try to schedule strong related tasks to the same domain, in order to reduce the cost of network communication.An extensive simulation study in SimGrid simulation platform was conducted to evaluate and compare the performance of the algorithms. It showed the general suitability and better performance of our enhanced list scheduling heuristics within heterogeneous Grid environments.