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

摘要

已有的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.