基于PaRSEC的并行计算工作流调度算法研究

摘要

随着分布式并行计算的快速发展与广泛应用，分布式系统中的工作流计算模型已经成为解决大规模科学计算问题的重要途径。用户关心工作流的运行结果，而算法研究人员更注重工作流运行的过程，以求在某种或多种系统性能指标上获得尽可能优的结果。本文主要关注的系统性能指标是工作流应用的总体运行时间。工作流的调度问题是影响分布式系统性能的关键因素。调度算法的研究需要以工作流子程序运行时间预测为依据。现有的调度算法研究多以仿真方式对时间预测进行随机建模，而本文依托实际分布式环境通过实验统计的方法来制定时间预测模型，这是本文研究工作的一个特色。本文作者通过分析开源项目PaRSEC调度框架的源代码，理解其现有的调度算法，并结合该调度框架的特点，应用在线工作流调度算法PB(Priority-based Algorithm)提高其调度效果，这是本文研究工作的另一特色。近年来兴起的云计算技术在组织方式的本质上是一种分布式计算，因此本文的研究结果有望进一步应用到云计算工作流调度环境中，以获得更广泛的推广。
　　本文以开源分布式并行线性计算系统DPLASMA及其调度框架PaRSEC为研究对象，主要做出以下几个方面的研究工作:(1)分析分布式调度框架PaRSEC的源代码与工作原理;(2)理解DPLASMA中Cholesky矩阵分解过程;(3)整理DPLASMA集群搭建的主要步骤和注意事项;(4)跟踪和记录工作流任务执行的过程，统计分析任务的执行时间与数据的传输时间，在实验数据的基础上给出时间预测模型参数;(5)研究PaRSEC的数据分配策略与调度算法，结合PB算法对已有的调度算法做出优化。
　　通过本文的研究发现，相同任务的执行时间具有较大的波动性，而数据的传输时间具有更大的不确定性，常用的随机分布预测的方式具有较大的误差。DPLASMA中引入PB优先级优化后能够使调度算法的性能有所提高，验证了PB算法的优先级策略在实际工作流的调度中的效果。

目录

声明

摘要

第一章 绪论

1．1 研究的背景和意义

1．2 国内外的研究现状

1．3 本文的研究工作

1．4 本文的章节安排

第二章 研究对象概述

2．1 DAG图与调度算法介绍

2．2 PARSEC框架介绍

2．3 DPLASMA介绍

第三章 DPLASMA编译安装

3．1 DPLASMA软件依赖

3．2 DPLASMA源码下载

3．3 编译工具cmake安装

3．4 辅助工具的安装

3．4．1 autoconf安装

3．4．2 pkg-config安装

3．5 必备软件库与工具包的安装

3．5．1 PLASMA线性代数库安装

3．5．2 MPI并行计算库安装

3．5．3 hwloc硬件检测工具安装

3．5．4 PAPI性能测试工具安装

3．6 分析工具的安装

3．6．1 GTG记录信息生成工具安装

3．6．2 Vite可视化工具安装

3．6．3 Graphviz绘图工具安

3．7 DPLASMA编译与单机测试

第四章 分布式集群搭建

4．1 集群搭建介绍

4．2 实验集群的软硬件环境

4．3 MPI集群的搭建

4．3．1 SSH的安装与测试

4．3．2 远程无密码登陆

4．3．3 虚拟机系统的克隆与迁移

4．3．4 集群网络配置

4．3．5 文件远程传输

4．3．6 MPI集群测试

4．4 DPLASMA集群测试

4．5 DPLASMA集群完善

第五章 DAG信息的解析与分析

5．1 dot文件解析

5．2 profile文件解析

5．3 任务执行时间与数据传输时间分析

第六章 调度算法的研究与优化

6．1 PARSEC的数据分发

6．2 PARSEC的调度算法

6．2．1 LFQ调度算法

6．2．2 LHQ调度算法

6．2．3 PBQ调度算法

6．2．4 AP调度算法

6．2．5 GD调度算法

6．2．6 调度算法调度策略与性能对比

6．3 PB算法

6．4 调度算法的优化

第七章 总结与展望

7．1 总结

7．2 展望

参考文献

致谢