任意可分负载的多轮调度算法

A Multi-Round Scheduling Algorithm of Data-Collection for Divisible Workload

为了提高并行计算中具有负载任意可分特性的大规模应用的任务响应速度,提出了一种针对带传输和计算延迟的三阶段多轮调度模型求解近似最优调度轮数的算法(DCMR).通过对特定的调度时序分析,得出闭合式方程组,然后利用二分法快速搜索并结合回溯调整法求解近似最优调度轮数,使计算时间尽可能多地与传输时间重叠,从而缩短了整个应用的执行时间.算法经仿真表明:在多种参数变化的情况下,可以求解出近似最优的调度方案;与经典的FIFO和LIFO算法相比具有更强的自适应能力;在计算时间明显大于传输时间的情况下,能够稳定地保持任务响应时间为理想时间的1.1倍左右.

A multi-round scheduling algorithm, datacollection multi-round （DCMR）, is presented to minimize the makespan of divisible workloads in parallel computing. A three-stage model is proposed and takes communication latency and computation start-up time into consideration. The algorithm provides a method to generate a near-optimal number of scheduling rounds. Close-form equations are given through analyzing a specific time sequence of load distribution, and then the bisection method, combined with back-forward adjustment, is used to get an asymptotically optimal number of scheduling rounds, which make the computation time overlap the communication time as much as possible and reduce the makespan, Simulation results show that the algorithm can find a near-optimal number of scheduling rounds under different network parameters. Compared with the classical algorithms such as FIFO and LIFO, the DCMR has higher adaptability. When the computation time dominates the communication time, the algorithm can keep the makespan at a rather low level which is about 1.1 times of the ideal time.