面向异构分布式计算环境的并行任务调度优化方法

Scheduling and optimizing algorithm for parallel tasks in heterogeneous distributed computing systems

分布式计算环境中并行作业的任务调度策略直接影响应用程序的执行时间,寻找一种使任务执行时间最短的调度方案已被证明是NP(non-deterministic polynomial)完全问题。首先给出了异构分布式计算系统的形式化描述,建立了静态任务调度问题的理论体系,通过分析总结最长动态关键路径(longest dynamic critical path,LDCP)算法的核心思想及存在的不足,提出一种运用结点信息流量减少CPU空闲时间碎片的并行任务调度优化算法,其时间复杂度为O(M×N^3)。实验表明改进后的算法在调度长度、加速比及计算效率3个指标上均优于LDCP算法和分层结点排序算法(sorted nodes in leveled directed acyclic graph division,SNLDD),其中,与LDCP、SNLDD相比,调度长度平均缩短19.03%、8.02%,加速比平均提升18.42%、7.96%,计算效率平均提高10.17%、3.72%,进一步提高了并行系统的资源利用率。

Strategies of parallel task scheduling have direct influences on me executing time of an applica-tion, but the perfect schedule which makes finishing time of the application shortest is a non polynomial comple tion time problem. By creating the mathematical models of heterogeneous distributed computing systems （DCS） and static task scheduling, the main procedure and deficiencies of the exist longest dynamic critical path algo- rithm （LDCP） is carefully analyzed. Further, an improved algorithm with time complexity O（M× N3） to de- crease idle time blocks of processors based on the node information flow quantity is proposed. Experiments show that the proposed algorithm outperforms the traditional algorithm and the sorted nodes in leveled directed acyclic graph division algorithm （SNLDD） in the schedule length, speedup and computation efficiency. The schedule length of the improved algorithm is shorter than those of the LDCP and SNLDD algorithms by 19.03% and 8.02%,respectively. The average speedup gained by the improved algorithm is greater than those of the LDCP and SNLDD algorithms by 18.42 %and 7.96 %, respectively. The computation efficiency of the improved algo rithm can get the amount of 10. 17% and 3. 72% increase than those of the LDCP and SNLDD algorithms. Hence, the proposed algorithm is sure to enhance the coefficient of the utilization for the whole system resources.