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

• 作者: 何琨 李柱铭 袁凌
• 来源期刊: 新型工业化
• 学科: 工学
• 关键词: 任务复制 任务聚簇 调度算法 有向无回路图 调度长度
• 年，卷（期）: 2012,（11）
• 所属期刊栏目: 学术研究
• 页码范围: 1-11
• 页数: 11页
• 分类号: TP311
• 字数: 6059字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何琨	华中科技大学计算机学院	31	263	10.0	16.0
2	袁凌	华中科技大学计算机学院	10	18	3.0	4.0
3	李柱铭	华中科技大学计算机学院	1	0	0.0	0.0