基于任务复制的调度算法

被引：10

作者：

张建军 ^{[1
,2
]}

李庆华 ^{[1
]}

瞿勇 ^{[2
]}

机构：

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

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

来源：

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

关键词：

最优调度算法; 任务复制; 最优条件; 任务聚集; Fork-Join任务图;

D O I：

10.16208/j.issn1000-7024.2009.08.041

中图分类号：

TP316.4 [分布式操作系统、并行式操作系统];

学科分类号：

摘要：

任务调度是并行分布式计算系统中最具挑战性的NP完全问题之一。基于任务复制的调度是一种有效的调度方法。在通信开销较小的情况下,现已有许多算法能产生最优调度。但其最优条件要么比较苛刻,要么比较复杂。因此,针对这些算法存在的问题,提出一个新的基于任务复制的聚集调度(TDCS)算法,不仅其最优条件简单、宽松,而且该算法具有更小的时间复杂度O(log),其中,和分别表示任务集中任务的个数和最大入度。

引用

页码：1896 / 1899+2029 +2029

页数：5