作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (2): 58-60. doi: 10.3969/j.issn.1000-3428.2010.02.021

• 软件技术与数据库 • 上一篇    下一篇

一种基于负载均衡性的网格任务调度算法

黄海于,何大可   

  1. (西南交通大学信息科学与技术学院,成都610031)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-01-20 发布日期:2010-01-20

Grid Task Schedule Algorithm Based on Load Balance

HUANG Hai-yu, HE Da-ke   

  1. (School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-01-20 Published:2010-01-20

摘要: 针对二分图匹配算法在任务之间存在时序关系时无法进行有效调度以及EFT算法没有充分考虑各处理机性能及网络通信状况的问题,提出基于二分图匹配的改进ETF算法。该算法综合考虑任务之间的时序关系、处理机的性能、处理机之间的通信情况及已处理任务的调度情况,利用二分图最佳匹配思想对局部任务进行调度。实验表明该算法具有较小的调度长度和较好的负载均衡性。

关键词: 异构计算环境, 任务调度, 二分图最佳匹配, ETF算法, 负载均衡性

Abstract: Among the task schedule algorithms, optimal bipartite matching can not be used for scheduling the DAG tasks directly, and the computing capabilities of machines and communication times used for data transfers between them are not considered in Earliest Time Path(ETF) algorithm. Considering such problems, an improved ETF task schedule algorithm based on optimal bipartite matching for heterogeneous computing environment is provided. Based on optimal bipartite matching for independent tasks and ETF algorithm, the algorithm considers not only the execution orders of the tasks and performance of the machines, but also the capabilities of communication between each machines and the results of the previous schedule results. Simulation experiments demonstrate that the algorithm can significantly improve the schedule performance in terms of schedule length and load balance.

Key words: heterogeneous computing environment, task schedule, optimal bipartite matching, Earliest Time Path(ETF) algorithm, load balance

中图分类号: