通信竞争环境中Join任务图的一个调度算法  

A SCHEDULING ALGORITHM FOR JOIN TASK GRAPHS IN CONTENTION-BASED COMMUNICATION ENVIRONMENTS

作　　者：张建军[1] 李薇[1] 旷文[1] 

机构地区：[1]海军工程大学理学院,湖北武汉430033

出　　处：《计算机应用与软件》2012年第7期14-17,25,共5页Computer Applications and Software

基　　金：国家自然科学基金项目(60774029)

摘　　要：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.

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

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