基于动态关键路径与边消除的任务复制分配算法-西北工业大学学报.PDF

2013 12 Dec． 2013 年 月 西北工业大学学报 31 6 Journal of Northwestern Polytechnical University Vol．31 No．6 第 卷第 期 基于动态关键路径与边消除的任务复制分配算法 ， ， ， ， 尤涛 杨凯 杜承烈 钟冬 朱怡安 ( ， 7 10072) 西北工业大学计算机学院 西安 : ， 、 。 摘 要 当前的分布式任务调度算法中 都存在无法得到调度最优解 无法最小化处理器资源的问题 ， ， 针对并行与分布式系统中相关任务的静态调度 问题 以最小化调度长度为主要 目标 以减 少资源数为 ， 。 次要 目标 提出 了一种基于动态关键路径与边 消除的任务复制算法 该算法依据调度长度不增加原 ， 、 、 则 发展 了子节点无约束复制的调度长度不增加定理 子结点带约束复制的调度长度不增加原则 动 ， 。 态关键路径聚簇的调度长度不增加原则 从 而缩短 了任务 的执行 时间和占用资源的个数 整个算法 流程对任务计算时间与任务 间通信时 间未做任何 限制 。通过与相关工作的比较可以看 出: DDE 算法 在调度长度与处理器使用数 目上优于其他 同类算法。 : ; ; ; 关 键 词 分布计算 系统 任务静态调度 聚簇算法 任务复制 中图分类号:TP311 文献标志码:A 文章编号:1000-2758 (20 13)06-0985-06 ， TDS ［7］ OSA ［3］ 任务分配是指将任务按照一定的规则和约束条 算法中 以 和 算法最优也最具代表 ， 。TDS : (DAG) 件分配到相应的计算机或处理器中 而任务的执行 性 的主要算法思想是 将有向无环图 。 join ， 顺序则由任务调度算法来决定 任务调度的目的 中 节点与其友好前驱节点分配到同一处理器 : ; 。OSA TDS 是 减少并行运行任务间的通信开销和等待时间 使 以降低并行执行时间 算法去掉了 算法 任务的执行时间最短; ; ， TDS