同构环境中Join任务图的一个调度算法  

A SCHEDULING ALGORITHM FOR JOIN TASK GRAPHS IN HOMOGENEOUS SYSTEMS

作　　者：张建军[1,2] 杨峰[2] 纪祥鲲[2] 

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

出　　处：《计算机应用与软件》2010年第7期14-16,23,共4页Computer Applications and Software

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

摘　　要：任务调度问题是一个NP完全问题。Join结构是一种并行处理的基本结构,虽然许多算法对Join任务图能产生最优调度,但大多都忽略了节省处理机个数和最小化程序总的完成时间等问题。因此,专门针对Join任务图,提出一个能产生最优调度的同构贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(v2),其中,v表示任务集中任务的个数。实验结果表明,相比其他算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少。The problem of task scheduling is known as an NP-Complete problem.The Join structure is a basic structure for parallel processing.Although quite a few algorithms are able to find an optimal schedule for Join task graphs,most of them neglect to economize processors and to minimize total completion time of the program,etc.This paper presents a homogenous greedy algorithm specifically for scheduling the Join task graphs,which can generate an optimal schedule with high speedup and total efficiency,its time complexity is O（v2）,where v represents the number of the tasks.Experimental results show that the proposed algorithm has shorter scheduling length,less completion time and fewer numbers of processors compared with other algorithms.

关 键 词：任务调度 调度算法 Join任务图 关键任务 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]