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

摘要：

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

关键词：任务复制、任务分簇、调度算法、DAG、任务粒度

所属期刊栏目：31

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金70471077;国家"九七三"重点基础研究发展规划项目基金2004CB318000;中国博士后科学基金20070420174

在线出版日期：2008-07-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：733-740