| 调度Fork-Join任务图的贪心算法 |
| |
| 引用本文： | YANG Bin,张建军,YANG Feng.调度Fork-Join任务图的贪心算法[J].计算机工程与设计,2008,29(15). |
| |
| 作者姓名： | YANG Bin 张建军 YANG Feng |
| |
| 作者单位： | 海军工程大学理学院,湖北,武汉,430033 |
| |
| 基金项目： | 国家自然科学基金，海军工程大学校科研和教改项目 |
| |
| 摘 要： | 任务调度算法的目标是把组成并行程序的一组任务分配到多个处理器以使得程序的完成时间最短,这是一个NP完全问题.虽然许多算法在任务满足某些条件时能产生最优调度,但大多都忽略了节省处理器个数和最小化程序总的完成时间等问题.Fork-Join结构是一种并行处理的基本结构.因此,专门针对Fork-Join任务图,提出了一个能产生最优调度的新的贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(v2),其中,v表示任务集中任务的个数.实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理器数较少.
|
| 关 键 词： | 最优调度算法 任务复制 Fork-Join任务图 关键任务 加速比 |
Greedy algorithm for scheduling Fork-Join task graphs |
| |
| YANG Bin,ZHANG Jian-jun,YANG Feng.Greedy algorithm for scheduling Fork-Join task graphs[J].Computer Engineering and Design,2008,29(15). |
| |
| Authors: | YANG Bin ZHANG Jian-jun YANG Feng |
| |
| Affiliation: | YANG Bin1,ZHANG Jian-jun2,YANG Feng2(1.Department of Management,Naval University of Engineering,Wuhan 430033,China,2.College of Science,China) |
| |
| Abstract: | The goal of task scheduling algorithm is to allocate the tasks of a parallel program to processors in order to minimize the com-pletion time of the program.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 ... |
| |
| Keywords: | optimal scheduling algorithm task duplication Fork-Join task graph critical task speedup |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
