基于任务复制的分布式聚簇与贪心调度算法

摘要：

在分布式同构系统中调度相关任务以最小化完工时间的问题是并行任务静态调度中的一个重要问题，也是研究并行分布式异构系统中多任务调度问题的基础。本文利用任务复制以尽量减少调度长度为主要目标，提出了一个基于聚簇(clutering-based)的贪心关键前驱复制（Greedy Critical Predecessor Duplication, GCPD）算法。在借鉴基于优先级调度的CPFD算法的基础上，GCPD算法充分考虑了复制每个机器上可能减少开始时间的关键前驱节点，从而优化了任务复制的技术，进一步提高了调度的性能。测试了两组共一千多个算例，GCPD算法在每个算例上的调度长度均短于或等于典型的任务复制算法的调度长度。实验结果表明，GCPD算法在寻找最短调度长度(makespan)方面是一个相当有优势的算法。

关键词：任务复制、任务聚簇、调度算法、有向无回路图、调度长度

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

资助基金：博士学科点专项科研基金资助课题编号20090142120026

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

页数：共11页

页码：1-11