一个有效的Join任务图的调度算法  

An Efficient Scheduling Algorithm for Join Task Graphs

作　　者：蒋卫民[1] 张建军[2] 

机构地区：[1]92351部队 [2]海军工程大学理学院

出　　处：《计算机与数字工程》2011年第4期34-38,共5页Computer & Digital Engineering

基　　金：海军工程大学自然科学基金项目:现代模糊信息优化处理技术及其应用研究(编号:HGDJJ05005)资助

摘　　要：已有的Join任务图的调度算法大多不是基于通信竞争的环境而开发,且未考虑节省处理机的问题,使算法的应用效果不佳。因此,针对Join任务图,提出一个通信竞争环境的调度算法,该算法因串行通信边而改善其调度效率,时间复杂度为O(vlogv),其中,v为图中任务的个数。实验结果表明,与其他算法相比,该算法的调度长度较短且使用的处理机数较少,具有更高的加速比。Many previous algorithms were not developed under the communication contention environment and neglected to economize the processors in real applications,which led to poor efficiency.Aiming at join task graphs,this paper proposes a communication contention-aware scheduling algorithm,which can improve the scheduling efficiency by serializing the communication edges.The time complexity of the presented algorithm is O（vlogv）,where v is the number of tasks.Simulation results show that the proposed algorithm has shorter scheduling length,less number of processors and higher speedup than other compared algorithms.

关 键 词：任务调度 Join任务图 通信竞争 关键任务 调度长度 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]