摘要
针对二分图匹配算法在任务之间存在时序关系时无法进行有效调度以及EFT算法没有充分考虑各处理机性能及网络通信状况的问题,提出基于二分图匹配的改进ETF算法。该算法综合考虑任务之间的时序关系、处理机的性能、处理机之间的通信情况及已处理任务的调度情况,利用二分图最佳匹配思想对局部任务进行调度。实验表明该算法具有较小的调度长度和较好的负载均衡性。
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.
出处
《计算机工程》
CAS
CSCD
北大核心
2010年第2期58-60,共3页
Computer Engineering
关键词
异构计算环境
任务调度
二分图最佳匹配
ETF算法
负载均衡性
heterogeneous computing environment
task schedule
optimal bipartite matching
Earliest Time Path（ETF） algorithm
load balance
