基于任务复制的分簇与调度算法

被引：14

作者：

何琨 ^{[1
]}

赵勇 ^{[2
]}

黄文奇 ^{[1
]}

机构：

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

[2] 华中科技大学控制科学与工程系

来源：

计算机学报 | 2008年 / 05期

基金：

中国博士后科学基金;

关键词：

任务复制; 任务分簇; 调度算法; DAG; 任务粒度;

D O I：

暂无

中图分类号：

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

学科分类号：

摘要：

针对并行与分布式系统中相关任务的静态调度问题,以最小化调度长度为主要目标,以减少资源数为次要目标,对待复制的重要祖先集定义了新的选择策略,提出了基于任务复制的动态关键前驱调度算法.改进了粒度的定义,证明了对任意DAG,算法有优于前人的性能下界.实验结果优于典型任务复制算法,特别是对经典EZ算例的解(调度长度为8)好于前人认为的理论最优解(调度长度为8.5),并证明了新的解为最优解.定义了DAG的补图,讨论了不允许任务复制时树型DAG的2-优度算法.

引用

页码：733 / 740

页数：8

共 5 条

[1] 分布式环境下多任务调度问题的分析与求解 [J].