并行系统中负载调度问题的研究

摘要

并行分布计算是当前计算机科学的热点之一。并行和分布式计算是求解各种计算密集型负载调度问题的有效手段，丽负载调度(包括负载的划分和传输)是影响并行与分布式计算性能的关键因素。并行系统中任务调度是指把一个应用中有先后关系的任务合理地分配到并行机的处理器上，使得整个应用完成时间最短。已经证明，这是一个NP难的问题，现阶段主要的研究是提出近似算法，提高调度的效率。本文研究了基于未知网络的并行异构系统中的可分负载调度问题，提出了一系列新的算法。本文的主要贡献包括： 1.提出未知网络资源下的可分负载的自适应调度算法。该算法提出了一种新的自适应的探测技术，采用了非固定的探测片段，能够根据当前网络状况自动确定探测片段的大小，并尽量减少分发给慢节点的探测片段数目。与已有针对未知网络参数的调度算法相比，本算法能够显著缩短负载的总处理时间，一般性能提升达到10％以上。 2. 提出未知网络资源下的总线型系统中多可分负载的调度算法。实际系统中多负载的情况更为常见，而且单可分负载调度在一定条件下可以理解为多可分负载调度。采用多阶段分发策略，能极大提高对系统计算资源的利用率。该算法将多阶段分发策略引入总线型系统的未知网络调度研究中，取得很好的调度结果。 3. 提出未知网络资源下的单层树系统中多可分负载的调度算法。单层树模型在实际应用中使用广泛，很多实际并行系统都能用单层树模型表示。基于单层树模型的异构系统调度策略，能够根据当前系统的结果调整偏差，自动调用探测过程。该算法以前面的新的探测技术和多阶段分发技术为基础，并有效运用于单层树异构系统中。试验结果表明，算法的优越性明显，较已有算法平均缩短调度时间约15％。 本文主要内容为：任务调度的背景介绍，包括并行计算，一般情况下的调度问题，主要解决办法；并行异构环境下调度问题的模型和研究现状：未知网络资源下单负载自适应可分负载调度算法研究；未知网络资源下总线型系统中多可分负载的调度算法研究；未知网络资源下的单层树系统多可分负载的调度算法研究；以后的研究方向。

目录

文摘

英文文摘

论文说明：图表目录

声明

第1章绪论

1.1并行计算简介

1.2并行调度

1.2.1调度问题的一般模型

1.2.2并行计算中的任务调度

1.2.3并行计算中任务调度的分类

1.3并行调度的关键技术

1.4研究内容和贡献

1.5论文的组织

第2章并行调度问题的模型和研究现状

2.1并行计算中的负载调度模型

2.1.1应用程序任务

2.1.2目标机器

2.1.3执行成本与通信成本

2.2静态任务调度的NP完全性及其最优算法

2.2.1静态任务调度的NP完全性

2.2.2静态任务调度的最优算法

2.2.3可分负载理论介绍

2.3静态任务调度的启发式算法

2.3.1贪心算法

2.3.2随机算法

2.4本章小结

第3章未知网络中的自适应可分负载调度

3.1可分负载调度的研究现状

3.2未知网络中的可分负载调度模型

3.3对PCD的改进算法

3.3.1 PDD和PCD回顾

3.3.2 PCD错误分析

3.3.3新算法(M-PCD)

3.4自适应探测和选择性分发算法

3.4.1 PSD算法介绍

3.4.2 M-PSD1

3.4.3 M-PSD2

3.4.4自适应探测和选择分发算法

3.5本章小结

第4章在总线结构未知网络中的多可分负载分布式调度策略

4.1多可分负载调度和未知网络中的调度研究现状

4.2总线模型及问题

4.3自适应的多可分负载处理策略

4.3.1一般的多阶段策略分析

4.3.2异构系统的调度策略

4.3.3未知网络中的组合策略

4.3.4非固定未知网络中的调度策略

4.4本章小结

第5章在单层树结构未知网络中的多可分负载的分布式调度策略

5.1当前调度研究的局限性

5.2单层树模型和相关工作

5.2.1模型介绍

5.2.2相关工作

5.3自适应多可分负载调度策略

5.3.1异构系统调度策略

5.3.2未知网络环境的调度策略

5.3.3非确定性未知网络的调度策略

5.3.4比较

5.3模拟实验

5.4本章小结

第6章总结

6.1本文的研究内容和成果

6.1.1研究内容

6.1.2研究方法

6.1.3研究成果和贡献

6.2进一步的工作展望

参考文献

致谢

攻读博士学位期间发表的论文