并行计算系统的负载平衡算法与并行执行时间预测

论文摘要

本文主要研究并行计算系统中的负载平衡算法与并行执行时间预测问题。为能较快平衡系统中的负载,提出了“均分负载”平衡算法。该方法先对各处理器结点的已有负载按网络中各处理器的速度进行划分,然后把这些划分好的小负载迁移到对应的处理器上,以平衡系统中各处理器的负载。分析表明:该算法时间性能较好,适于解决系统初始分配负载问题与系统负载极度失衡的平衡问题;但对于负载较平衡的系统,其负载迁移量很大。为减小负载迁移量同时保持较快的平衡速度,提出了“二分网络”平衡算法。该方法按网络的结点数把网络分为两子网络,然后按两子网络的处理速度之比进行两子网络间的负载迁移,递归上述过程,直到各子网络中只有一个结点时,系统经负载迁移后可达到平衡状态。该算法具有平衡负载速度较快、负载迁移量较小的优点,适于大多数条件下的负载平衡。针对环与线性阵列的负载平衡速度较慢与迁移量较大的问题,提出了“贪心线性推移”平衡算法。该算法的思想是:把重负载结点过重的那部分负载按线性或环的路径推移到下一邻居结点,循环推移直到整个系统负载平衡。此算法适用于任何具有哈密顿通路的图结构网络。一般情况下,其平衡过程的负载迁移量不大,且平衡负载速度较快。此外,还对网状网等网络结构的“贪心线性推移”平衡算法进行改进,而得到分两阶段的贪心线性推移平衡算法。实验与分析表明:当平衡条件减弱时,这种改进能较大地提高算法的时间性能。为解决由具有独立同分布随机执行时间的子任务组成的并行任务的执行时间预测问题,提出了基于Johnson分布的并行执行时间预测方法。该方法使用Johnson变换把并行子任务的执行时间分布变换成标准正态分布,然后利用正态分布的性质预测并行执行时间。这种方法不仅适于解决“最大”或“最小”的并行执行时间预测问题,而且适于任何求独立同分布随机变量的最大值与最小值问题。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 绪论
• 1.1 选题背景和研究意义
• 1.2 本领域研究现状
• 1.3 本文主要研究工作和创新点
• 1.4 论文结构
• 第二章 并行性理论概述
• 2.1 并行计算机的分类及其特点
• 2.2 并行计算机系统互连
• 2.2.1 静态互连网络
• 2.2.2 动态互连网络
• 2.3 负载平衡与执行时间预测技术
• 2.3.1 动态负载平衡
• 2.3.2 静态负载平衡
• 2.3.3 并行执行时间预测
• 2.4 本章小结
• 第三章 基于无限可分负载的平衡算法
• 3.1 引言与相关工作
• 3.2 定义和约定
• 3.3 负载平衡算法
• 3.3.1 “均分负载”平衡算法
• 3.3.2 “二分网络”平衡算法
• 3.3.3 “P分网络”平衡算法
• 3.3.4 “贪心线性推移”平衡算法
• 3.4 三种算法的性能比较小结
• 3.5 本章小结
• 第四章 基于Johnson变换的并行执行时间预测
• 4.1 引言
• 4.2 Johnson变换
• 4.3 正态样本的近似分布
• 4.4 并行执行时间预测模型的实现及其性能分析
• 4.5 并行搜索执行时间预测模型
• 4.6 实验结果
• 4.6.1 常用分布
• 4.6.2 实际程序的并行执行时间分布
• 4.7 本章小结
• 第五章 总结与展望
• 5.1 全文总结
• 5.2 研究展望
• 参考文献
• 发表论文和科研情况说明
• 致谢