并行计算中基于反馈机制的动态负载平衡算法研究

摘要

分子动力学模拟是一种微观领域的模拟方法，在物理、化学、生物及材料等领域应用广泛。由于分子动力学模拟的计算量非常庞大，计算非常耗时，并行计算是解决该问题的必经之路。然而，负载不平衡导致并行的分子动力学模拟程序执行的时间仍然较长。因此，期望通过引入负载平衡算法，有效地优化分子动力学模拟程序，提高模拟效率。
　　 通过研究现有的动态负载平衡算法，针对激光诱导光化学反应的分子动力学模拟程序中最耗时模块的有关特点，给出了节点作业速度和负载平衡度的定义，提出了一种基于反馈机制的动态负载平衡算法。该算法以节点作业速度为负载指标;决策策略采用集中式策略，每轮循环结束后主节点都需收集各计算节点在该轮循环中执行的任务个数及对应的执行时间，计算并保存各节点的作业速度;每个反馈周期的第一轮循环之前主节点都将根据计算节点作业速度比分配任务;每个反馈周期结束后，主节点通过指数平均法预测下个反馈周期内各计算节点的工作速度、计算节点的加权负载平衡度，进而更新反馈周期。
　　 对照算法是始终将任务按数量平均分配到各个节点的静态负载平衡算法。将该动态负载平衡算法和对照算法都用Fortran+MPI编程实现，并分别加入到现有的分子动力学模拟程序中。通过对比实验发现，相对于平均分配任务的静态负载平衡算法，该动态负载平衡算法具有更好的负载平衡效果，在系统本身负载不平衡时能有效地缩短程序的并行执行时间。实验也证明，通过指数平均法来预测节点负载和更新反馈周期的复杂反馈策略，在负载平衡效果方面要好于每轮循环均反馈的简单反馈策略，进而表明引入复杂反馈策略具有必要性。
　　 整个研究表明，选取合适的负载指标是实现理想的动态负载平衡算法过程中的重点和难点;基于指数平均法的负载预测机制和反馈周期动态变化的反馈机制，显著地提高了动态负载平衡算法的负载平衡效果;设计合理的动态负载平衡算法能够有效减少并行程序的执行时间，在多数情况下其负载平衡效果都将超过静态负载平衡算法。

目录

声明

摘要

第一章 绪论

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．4 MPI

2．4．1 MPI的实现版本

2．4．2 MPI的最小子集

2．4．3 其他重要的MPI函数简介

2．4．4 MPI并行程序设计流程

2．4．5 MPI编程模式

2．5 本章小结

第三章 动态负载平衡算法研究

3．1 负载平衡概述

3．1．1 负载平衡的定义与目标

3．1．2 负载平衡算法的分类

3．2 动态负载平衡算法的一般步骤

3．2．1 收集负载信息

3．2．2 平衡决策

3．2．3 平衡操作

3．3 负载状态的判定

3．3．1 负载指标

3．3．2 负载状态函数

3．3．3 负载状态的预测

3．3．4 负载状态判定方法

3．4 任务迁移策略

3．4．1 两种迁移方式

3．4．2 任务迁移的复杂性

3．5 负载平衡度的定量评估算法

3．5．1 基于绝对离散度指标的评估算法

3．5．2 基于相对离散度指标的评估算法

3．6 理想的动态负载平衡算法的实现难点

3．6．1 理想的动态负载平衡算法应具备的条件

3．6．2 实现理想的动态负载平衡算法需解决的问题

3．7 本章小结

第四章 基于反馈机制的动态负载平衡算法的设计与实现

4．1 问题描述

4．2 基于反馈机制的动态负载平衡算法总体描述

4．2．1 基于反馈机制的负载平衡模型

4．2．2 算法基本原理

4．3 算法详细描述

4．3．1 决策策略

4．3．2 信息收集策略

4．3．3 反馈策略

4．3．4 任务分配策略

4．3．5 算法工作流程

4．4 算法实现

4．4．1 决策策略的实现

4．4．2 信息收集策略的实现

4．4．3 反馈策略的实现

4．4．4 任务分配策略的实现

4．4．5 算法实现后的工作流程

4．5 本章小结

第五章 测试及分析

5．1 实验内容

5．2 实验环境

5．2．1 系统配置

5．2．2 MPICH的安装配置

5．2．3 配置文件

5．2．4 实验程序和对照程序

5．2．5 干扰程序

5．3 程序的执行

5．4 实验结果及分析

5．4．1 干扰节点个数变化时的对照试验

5．4．2 计算节点个数变化时的对照试验

5．4．3 简单反馈与复杂反馈时的负载平衡度比较

5．5 算法评价

5．6 本章小结

第六章 结论及未来工作

6．1 结论

6．2 未来工作

致谢

参考文献

附录A 对本文4.3节负载平衡度定义的有关说明

附录B 读研期间从事的科研工作及取得的研究成果