调度Fork-Join任务图的贪心算法  

Greedy algorithm for scheduling Fork-Join task graphs

作　　者：杨斌[1] 张建军[2] 杨峰[2] 

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

出　　处：《计算机工程与设计》2008年第15期3864-3866,3894,共4页Computer Engineering and Design

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

摘　　要：任务调度算法的目标是把组成并行程序的一组任务分配到多个处理器以使得程序的完成时间最短,这是一个NP完全问题。虽然许多算法在任务满足某些条件时能产生最优调度,但大多都忽略了节省处理器个数和最小化程序总的完成时间等问题。Fork-Join结构是一种并行处理的基本结构。因此,专门针对Fork-Join任务图,提出了一个能产生最优调度的新的贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为2,其中,表示任务集中任务的个数。实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理器数较少。The goal of task scheduling algorithm is to allocate the tasks of a parallel program to processors in order to minimize the completiontimeoftheprogram. This is known as an NP-Complete problem. Although some algorithms are able to find an optimal schedule under certain conditions, most of them ignore to economize processors and minimize total completion time. The Fork-Join structure is one of the basic modeling structures for parallel processing. A new greedy algorithm for scheduling fork-join task graph is presented, which can generate an optimal schedule with high speedup and efficiency, the time complexity of the proposed algorithm is O（v^2）, 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.

关 键 词：最优调度算法 任务复制 Fork—Join任务图 关键任务 加速比 

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