基于通信竞争的Fork-Join任务图的调度算法  

Scheduling algorithm of Fork-Join task graphs based on communication contention

作　　者：张建军[1,2] 杨峰[2] 瞿勇[2] 

机构地区：[1]华中科技大学计算机学院,湖北武汉430074 [2]海军工程大学理学院,湖北武汉430033

出　　处：《计算机工程与设计》2009年第23期5301-5304,5351,共5页Computer Engineering and Design

基　　金：国家自然科学基金项目(60273075);海军工程大学自然科学基金项目(HGDJJ05005)

摘　　要：Fork-Join任务图是一种并行处理的基本结构,目前已有的Fork-Join任务图的调度算法大多没有考虑实际应用中通信链路的竞争及延迟以及节省处理机的问题,导致算法在具体应用中效率较低。因此,针对Fork-Join任务图,提出一个基于通信竞争的贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(vlogv),其中v表示任务集中任务的个数。实验结果表明,该算法相比其它算法具有较短的调度长度、较短的完成时间,使用的处理机数较少,具有更强的实用性。The Fork-Join task graph is one of the basic modeling structures for parallel processing.However, many previous algorithms ignore the contention and delay on data links and the economization on processors in real applications, which leads to low efficiency.A communication contention based on algorithm for scheduling fork-join task graphs is presented, which can generate an sub-optimal sche-dule with high speedup and efficiency.The time complexity of the proposed algorithm is O（vlogv）, where v is the number of tasks.Simulation results show that the proposed algorithm has better scheduling length, less completion time and less number of processors than other compared algorithms and so practicable.

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

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