Duplication And Dynamic-Priority Based Scheduling Algorithm In Grid Computing Systems

With the flouring of grid in recent years, a distributed suit of computing machines with diverse capabilities connect by diverse high speed links utilized to execute parallel programs. However, the performance of the parallel program execution in grid is highly dependent on the scheduling of the parallel program tasks onto these machines.In grid environment, the communication delay is a key in degrading the performance of the parallel program execution. But list-based scheduling algorithms fail to consider the communication cost, and a child node can't start until its immediate parents complete and send the message the child task need, leaving many idle time slots in a processor. In order to deal with this problem, a generic scheduling strategy, STDH (Selected Task-Duplication for Heterogeneous system), is presented, which improves the performance of list-based algorithm with the duplication. If there is a period of idle time on the processor, STDH attempts to insert all suitable immediate parent nodes of the current selected node, not only the critical parent, so as to reduce its waiting time on the processor, which is helpful to advancing the earliest starting time of this candidate task. On the one hand, the earliest starting time of some tasks could minimize the overall time of the scheduling, and on the other hand, the utilization of the processors could be raised. The experimental results show that STDH outperforms HEFT and HNDP in terms of finish time. Besides, while the ratio of total communication cost and total computation cost of the task graph becomes larger, STDH becomes better than the two others.Taking into account the system heterogeneity, the same task take different run time on different processors, the priority of one task may dynamically change in the scheduling process due to that the processor to assign the task node is not determined. So scheduling sequence determine statically in the listing phase is not reasonable because of the sequence can not change in the scheduling process, the priority computed in listing phase may be different from the real priority. In order to deal with this problem, the priority was determined dynamically in the scheduling process, in this way, the nodes which had the greatest influence to the scheduling length of the task graph would be selected to schedule first. In addition, if there were idle time slots in the processors, the predecessors of selected tasks would be duplicated to minimize the intra-processor communication cost. The experimental results show that the algorithm proposed in this paper is better than HEFT and Dynamic Decisive Path algorithm.