The Study On Divisible Load Scheduling In Computing Grid

Task schedule is a NP-hard problem, it is a very important in parellelling and distribution computation. In the grid computing environment, designing an efficient schedule algorithm is very difficult because of the computing complexity. Task schedule is using certain task schedule rules and policies, then distributes the tasks to the computing nodes to get a better executing performance. The aim of the algorithm is using the least time to complete the computing.The divisible task schedule plays a very important part in grid computiong and arises in many fields of science and engineering. The design of a task schedule is the key in distribution computing. An efficient task schedule algorithm can be parallelized in master-worker model, so relevant scheduling strategies have been proposed to reduce application makespan. In this paper we research the UMR (Uniform Multi-Round) algorithm which is a classical algorithm in this field. By imposing the restriction condition that equal sized chunks are sent to workers within a round, the UMR algorithm makes it possible to compute an optimal number of rounds and use the computing resource completely. But the UMR algorithem doesn't consider the limited bandwidth, so it can be hardly used in the reality.We proposed a new multi-round task schedule algorithm LBMR (limited bandwidth multi-round algorithm) in this paper. It uses the design idea of UMR algorithm, but imports the condition of bandwidth, so it is more actual than UMR. The new algorithm can get a high executing effect in both abound and scarce bandwidth condition.Through the theory analysis and plenty of simulating experiments by the grid compuing toolkit GridSim, we compare the simulating results with UMR,MI,XMI algorithms,the new algorithm is improved in dividing and distributing algorithem, so the executing performance of LBMR is better than pervious algorithms, it can be widely used.