基于LLVM的科学计算程序自动性能预测研究

摘要

得益于计算机硬件的发展，现在大规模计算和并行计算得到了空前的关注。其相关配套的性能分析和评测技术也提上议程。科学计算并行程序(下简称科学程序)的分析显然和以前的单进程程序有所区别。科学程序通常有计算密集、高度并行、很少依赖第三方库等特点。科学程序的并行通常是SPMD(Single Program Multiple Data)类型，常用MPI协议实现。
　　性能模型用于描述程序的特征。最直接的即是预测程序的执行时间，常为一组公式。而这里用一个起名为DwarfCode(下简称 DC)的程序作为性能模型来预测程序执行时间。DC是在原程序的基础上结合LLVM和编译技术来生成的。在IR阶段通过分析程序里的循环次数结合 LLVM的静态分支概率，生成计算每个基本块次数的指令并进行插桩；然后使用视点提升算法来调整插桩位置，同时寻找通信语句并生成计算通信量的指令来插桩。之后分析数据依赖进行删减，从而使得执行 DC花费的时间比原程序少，体现预测性。由于从原程序中删减得来，DC的输入和原来一致。运行DC生成包含预测的基本块次数的profiling文件，再结合机器特征能计算出预测的原程序执行时间。以及更为细致的预测的每个基本块执行次数和每个函数的时间，总共通信所花费的时间等等。
　　本文最大的贡献是提出了视点的概念，将静态分析方法和动态EdgeProfiling方法两个极端有机地统一起来。提出静态性等于预测性，动态性等于准确性的观点。本文最大的创新之处在于抛弃编译优化等价变换的固有观念，采用破坏性的删减的方法，在尽量不改变程序特征的前提下抛弃程序的输出结果，删减计算部分代码，运行DC的时间更少。提出预测代价和预测性价比的概念，指出在性价比大于1的时候，才有实施预测的意义。
　　本文指出性能模型由程序特征和机器特征所决定，将两者分离从而使得DC的输出满足迁移性，和目标平台无关。DC执行简单，使用方便。无需任何相关领域知识，无需任何参数设定，无需任何配置文件，无需了解代码结构。无需预先做任何训练。不仅磁盘空间开销小，而且时间开销和内存开销相对于原程序也小。
　　在CGPOP和EP的实验中，分析了DC的结果，通过对误差的分析，指出了分支概率误差的存在。最后将所有代码和测试数据开源，方便所有人重做实验，验证结果或是继续开发。

目录

封面

中文摘要

英文摘要

目录

第1章 绪论

1.1课题背景及研究目的和意义

1.2性能分析中的插桩技术介绍

1.3国内外研究现状

1.4实验对象CGPOP介绍

1.5实验对象NPB介绍

1.6实现平台编译框架LLVM的介绍

1.7 LLVM的静态分析与插桩技术

1.8高精度计时TSC

1.9使用到的一些基准测试

1.10本文的主要研究内容及组织结构

第2章 性能预测方法的整体设计

2.1术语和符号定义

2.2计算模型建模

2.3通信模型建模

2.4生成DwarfCode的整体过程

2.5基本块插桩部分

2.6通信插桩部分

2.7删减过程

2.8结合机器参数预测执行时间

2.9本章小结

第3章 基于LLVM的关键系统实现

3.1基本块插桩部分

3.2通信插桩MPIProfiling过程描述

3.3具体的删减过程

3.4运行DwarfCode

3.5机器特征与模型求解

3.6本章小结

第4章 实验结果与分析

4.1实验平台介绍

4.2目标平台的机器特征参数

4.3单元实验

4.4 CGPOP实验过程

4.5 EP实验

4.6本章小结

结论

参考文献

攻读硕士学位期间发表的论文及其他成果

声明

致谢