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

发布时间：2018-06-16 03:50

本文选题：异构分布式计算环境 + 有向无环图　；参考：《系统工程与电子技术》2016年02期

【摘要】：分布式计算环境中并行作业的任务调度策略直接影响应用程序的执行时间,寻找一种使任务执行时间最短的调度方案已被证明是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%,进一步提高了并行系统的资源利用率。
[Abstract]:The task scheduling policy of parallel jobs in distributed computing environment directly affects the execution time of applications. It has been proved that a scheduling scheme with the shortest task execution time has been proved to be a complete problem. Firstly, the formal description of heterogeneous distributed computing system is given, and the theoretical framework of static task scheduling problem is established. By analyzing and summarizing the core ideas and shortcomings of the longest dynamic critical path (LDP) algorithm. A parallel task scheduling optimization algorithm using node information flow to reduce CPU idle time fragmentation is proposed. The experimental results show that the improved algorithm is superior to the LDCP algorithm in terms of scheduling length, speedup ratio and computational efficiency, and the hierarchical node sorting algorithm, sorted nodes in leveled directed acyclic graph division SNLDD, is better than the LDCP algorithm, where, compared with the LDCP-SNLDD, the improved algorithm is superior to the LDCP algorithm in terms of scheduling length, speedup ratio and computational efficiency. The average scheduling length is reduced by 19.03 and 8.02, the speedup ratio is increased by 18.422 and 7.96 on average, the average computational efficiency is increased by 10.17 and 3.72, and the resource utilization ratio of the parallel system is further improved.
【作者单位】：海军陆战学院科研部;海军陆战学院教研部;
【基金】：国家自然科学基金(61401496) 军队院校实验室建设与管理重点课题(SYSLXH-2013035)资助课题
【分类号】：TP338.8

【相似文献】