Join任务图是一种并行处理的基本结构.目前已有的Join任务图的调度算法大多忽略了通信链路的竞争、延迟以及节省处理机的问题,导致算法在实际应用中效率较低.针对这一问题,提出一个基于通信竞争的Join任务图的调度算法,该算法通过对各通信边的串行化而在任务调度中集成通信竞争,其时间复杂度为O(vlogv),其中v表示图中的任务数.实验结果表明,相比其他算法,该算法就调度长度、使用的处理机数、加速比和效率而言为优,具有更强的实用性.%Join task graph is a structure of parallel processing. Most of existing scheduling algorithms for Join task graphs ignore the contention and delay in communication links and the economisation in processors, which leads to low efficiency in real applications. Aiming at this problem, this paper presents a communication contention-based scheduling algorithm for scheduling Join task graphs, the algorithm integrates the communication contention in task scheduling by serialising every communication edge, its time complexity is 0 (vlogv), where v is the number of tasks. Experimental evaluation validated that compared with other algorithms, the proposed algorithm is superior in terms of schedule length, number of the processors used, speedup and efficiency, and is more practicable.
展开▼
