| 【中文题名】 | 异构机群系统的可分负载调度算法研究 |
| 【英文题名】 | Study on Parallel Algorithm for Scheduling Divisible Loads on Heterogeneous Cluster Computing Systems |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-9-14 |
| 【中关键词】 | 异构机群系统,任务调度,并行算法,可分负载,返回信息,并行计算 |
| 【英关键词】 | heterogeneous cluster computing systems,task scheduling,parallel algorithms,divisible loads,return messages,parallel computing, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>计算技术、计算机技术>计算机的应用>计算机网络>一般性问题 |
| 【论文摘要】 |
异构机群系统利用工作站和个人计算机进行分布式并行处理，以较低的成本完成大规模、复杂问题的计算处理。相对于单一的并行计算机，异构机群系统具有较高的性价比，并且非常具有发展前景，但是同时也提出了许多富有挑战性的问题，任务调度就是其中的一个重要问题。如果任务调度问题得不到有效解决，那么可能导致异构机群系统效率低下，甚至可能不如单个计算机，严重的可能导致计算失效。
可分负载调度具有广泛的应用背景，且相对简单和易于分析，近几年得到了比较广泛的研究与应用。现有的异构机群系统调度算法大多是针对同构全互连机群系统设计的，很少考虑到处理机具有不同的通信、存储和计算能力等实际因素。对于处理机具有不同的计算速率、通信速率、通信延迟和存储能力的异构机群系统，本文研究可分负载调度算法及其性能。
在均匀多轮调度算法UMR的基础上，本文充分考虑处理机具有不同的计算速度、通信能力和存储容量的特性，通过允许计算和通信操作重叠执行，采取多次并行分配计算任务的方法，提出一种可分负载多轮调度算法UMRLM。算法分析与实验结果表明，一方面，UMRLM算法在调度时间上仍能取得与UMR算法相当的近似最优的调度时间长度；另一方面，... |
| 【论文题纲】 |
|
摘要 |
4-6 |
|
ABSTRACT |
6-10 |
|
第一章 绪论 |
10-20 |
|
1.1 引言 |
10-11 |
|
1.2 并行任务调度研究进展 |
11-17 |
|
1.2.1 基于DAG图并行任务调度研究进展 |
11-14 |
|
1.2.2 并行可分负载任务调度研究进展 |
14-17 |
|
1.2.2.1 问题的提出 |
14 |
|
1.2.2.2 国内外研究现状 |
14-17 |
|
1.3 论文选题的目的和意义 |
17 |
|
1.4 论文的主要研究内容 |
17-18 |
|
1.5 论文的组织 |
18-20 |
|
第二章 并行计算与并行任务调度 |
20-33 |
|
2.1 并行计算 |
20-23 |
|
2.1.1 并行计算的概念 |
20 |
|
2.1.2 当代并行计算机系统 |
20-23 |
|
2.2 机群系统 |
23-27 |
|
2.2.1 机群系统的概念 |
23 |
|
2.2.2 机群系统的优点 |
23-24 |
|
2.2.3 机群系统的关键技术 |
24-26 |
|
2.2.4 机群系统的研究现状 |
26-27 |
|
2.3 并行任务调度概述 |
27-32 |
|
2.3.1 并行任务调度分类 |
27-28 |
|
2.3.2 基于DAG图的并行任务调度 |
28-30 |
|
2.3.2.1 调度模型分类 |
28-29 |
|
2.3.2.2 DAG并行任务调度算法 |
29-30 |
|
2.3.3 可分负载调度理论基础 |
30-32 |
|
2.3.3.1 可分负载理论 |
30 |
|
2.3.3.2 可分负载调度 |
30-32 |
|
2.4 本章小结 |
32-33 |
|
第三章 异构机群系统的可分负载多轮调度算法 |
33-45 |
|
3.1 引言 |
33-34 |
|
3.2 拉格朗日数乘法 |
34 |
|
3.3 应用模型和计算平台描述 |
34-35 |
|
3.4 均匀多轮调度算法UMR |
35-37 |
|
3.5 处理机计算速度和通信能力及内存容量不同的异构机群系统的调度算法 |
37-40 |
|
3.5.1 负载块大小和调度轮数的确定 |
37-38 |
|
3.5.2 最后一轮调度的负载处理 |
38-40 |
|
3.6 实验 |
40-44 |
|
3.6.1 实验环境 |
40-41 |
|
3.6.2 实验结果分析 |
41-44 |
|
3.7 本章小结 |
44-45 |
|
第四章 异构机群系统上带返回信息的可分负载多轮调度算法 |
45-55 |
|
4.1 引言 |
45-46 |
|
4.2 应用模型和计算平台 |
46 |
|
4.3 异构计算环境下带返回信息的调度轮数可变的可分负载多轮调度算法 |
46-49 |
|
4.4 实验 |
49-54 |
|
4.4.1 实验环境 |
49 |
|
4.4.2 实验结果分析 |
49-54 |
|
4.5 本章小结 |
54-55 |
|
第五章 总结 |
55-58 |
|
5.1 本文的工作 |
55-56 |
|
5.2 本文的贡献与创新之处 |
56 |
|
5.3 进一步的工作 |
56-58 |
|
参考文献 |
58-64 |
|
致谢 |
64-65 |
|
攻读硕士学位期间参加的科研项目 |
65-66 |
|
攻读硕士学位期间录用发表论文情况 |
66 |
|
| 【DOI】 | LunWen.ID:2.2008.376052 |
