位置:成果数据库 > 期刊 > 期刊详情页
An optimizing algorithm of static task scheduling problem based on hybrid genetic algorithm
  • ISSN号:1671-8860
  • 期刊名称:《武汉大学学报:信息科学版》
  • 时间:0
  • 分类:TP316[自动化与计算机技术—计算机软件与理论;自动化与计算机技术—计算机科学与技术]
  • 作者机构:[1]海军陆战学院科研部,广东广州510430, [2]海军陆战学院教研部,广东广州510430
  • 相关基金:国家自然科学基金(61401496);军队院校实验室建设与管理重点课题(SYSLXH2013035)资助课题
中文摘要:

分布式计算环境中并行作业的任务调度策略直接影响应用程序的执行时间,寻找一种使任务执行时间最短的调度方案已被证明是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.

同期刊论文项目
同项目期刊论文
期刊信息
  • 《武汉大学学报:信息科学版》
  • 中国科技核心期刊
  • 主管单位:国家教育部
  • 主办单位:武汉大学
  • 主编:刘经南
  • 地址:湖北武汉珞珈山
  • 邮编:430072
  • 邮箱:whuxxb@vip.163
  • 电话:027-68778045
  • 国际标准刊号:ISSN:1671-8860
  • 国内统一刊号:ISSN:42-1676/TN
  • 邮发代号:38-317
  • 获奖情况:
  • 全国优秀科技期刊,全国优秀高校自然科学学报一等奖,湖北省优秀期刊称号
  • 国内外数据库收录:
  • 俄罗斯文摘杂志,荷兰地学数据库,荷兰文摘与引文数据库,美国工程索引,美国剑桥科学文摘,英国科学文摘数据库,日本日本科学技术振兴机构数据库,中国中国科技核心期刊,中国北大核心期刊(2004版),中国北大核心期刊(2008版),中国北大核心期刊(2011版),中国北大核心期刊(2014版)
  • 被引量:24217