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

被引：7

作者：

杨斌 ^{[1
]}

张建军 ^{[2
]}

杨峰 ^{[2
]}

机构：

[1] 海军工程大学管理工程系

[2] 海军工程大学理学院

来源：

计算机工程与设计 | 2008年 / 15期

关键词：

最优调度算法; 任务复制; Fork-Join任务图; 关键任务; 加速比;

D O I：

10.16208/j.issn1000-7024.2008.15.020

中图分类号：

TP301 [理论、方法];

学科分类号：

080201 [机械制造及其自动化];

摘要：

任务调度算法的目标是把组成并行程序的一组任务分配到多个处理器以使得程序的完成时间最短,这是一个NP完全问题。虽然许多算法在任务满足某些条件时能产生最优调度,但大多都忽略了节省处理器个数和最小化程序总的完成时间等问题。Fork-Join结构是一种并行处理的基本结构。因此,专门针对Fork-Join任务图,提出了一个能产生最优调度的新的贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为2,其中,表示任务集中任务的个数。实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理器数较少。

引用

页码：3864 / 3866+3894 +3894

页数：4