异构环境中Fork-Join任务图的调度算法  

Task scheduling algorithm for Fork-Join task graphs in heterogeneous environment

作　　者：张建军[1,2] 宋业新[2] 黄登斌[2] 

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

出　　处：《计算机工程与设计》2010年第3期486-490,共5页Computer Engineering and Design

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

摘　　要：目前已有的Fork-Join任务图的调度算法大多假定处理机为同构的,而没有考虑实际应用中处理机的异构性以及节省处理机的问题,导致算法在具体应用中效率较低。因此,对Fork-Join任务图的调度问题进行研究,提出了一个基于异构环境的贪心调度算法,该算法具有高的加速比和总体效率,其时间复杂度为2,其中,表示任务集中任务的个数。实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少,具有更强的实用性。Many previous scheduling algorithms for Fork-Join task graphs assumed homogeneous processors,while ignoring the heterogeneity of processors and the economization on processors in real applications,which led to low efficiency in real applications.A heterogeneity based greedy algorithm for scheduling Fork-Join task graphs is presented,which can generate a schedule with high speedup and efficiency.The time complexity of the proposed algorithm is 2,where 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 more practicable.

关 键 词：FORK-JOIN任务图 异构性 任务复制 贪心算法 调度长度 关键任务 加速比 

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