一种改进的可分割任务调度算法LBMR

LBMR : An Advanced Multi-Round Algorithms for Scheduling Divisible Loads

可分割任务调度在科学和工程计算领域中具有重要的地位,其有效调度算法的设计对并行分布式处理的计算效率至关重要。UMR(Uniform Multi-Round)算法通过限定每次传输到工作节点块的大小,使各工作节点始终处于计算状态,不仅实现了计算资源的最大利用,而且可计算出整个任务调度的最优路数。但是:由于该算法设计中并未考虑网络带宽的有限性,因而难以满足实际计算环境的需求。为此,本文在UMR算法中引入网络带宽限制,对该算法在此条件下进行重新设计,提出一种改进的多路可分割任务调度算法LBMR((limited bandwidth multi-roundal-gorithm)。理论分析和基于GridSim的模拟实验结果表明:与UMR、MI、EMI等同类调度算法相比,本算法改进了其调度性能,且具有更好的实用性。

Task schedule problem arises in many fields of science and engineering. It can be parallelized in master-worker fashion and relevant scheduling strategies have been proposed to reduce application makespan. By imposing the restriction that equal sized chunks are sent to workers within a round,the UMR algorithm makes it possible to compute an optimal numbe.r of rounds while modeling resource latencies. This paper proposes a new multi-round task schedule algorithm LBMR（limited bandwidth multi-round algorithm）. It uses the idea of UMR algorithm, but imports the condition of bandwidth, so it is more actual. Through plenty of simulated experiments by toolkit GridSim, we compare the results with UMR,MI,XMI algorithm, the performance of LBMR is better than pervious algorithms,it can be used widely.