基于通信竞争的Fork-Join任务图的调度算法

被引：3

作者：

张建军 ^{[1
,2
]}

杨峰 ^{[2
]}

瞿勇 ^{[2
]}

机构：

[1] 华中科技大学计算机学院

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

来源：

计算机工程与设计 | 2009年 / 30卷 / 23期

关键词：

任务调度; 任务复制; Fork-Join任务图; 通信竞争; 关键任务; 调度长度;

D O I：

10.16208/j.issn1000-7024.2009.23.022

中图分类号：

TP301.6 [算法理论];

学科分类号：

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

摘要：

Fork-Join任务图是一种并行处理的基本结构,目前已有的Fork-Join任务图的调度算法大多没有考虑实际应用中通信链路的竞争及延迟以及节省处理机的问题,导致算法在具体应用中效率较低。因此,针对Fork-Join任务图,提出一个基于通信竞争的贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(vlogv),其中v表示任务集中任务的个数。实验结果表明,该算法相比其它算法具有较短的调度长度、较短的完成时间,使用的处理机数较少,具有更强的实用性。

引用

页码：5301 / 5304+5351 +5351

页数：5

共 6 条

[1]

基于任务复制的调度算法 [J].