并行化编译器中并行程序自动生成和性能优化技术研究

论文摘要

高性能计算机的广泛应用使得人们对高效并行软件的需求急剧增加。面对庞大、复杂且对时效性要求极高的计算任务，如何充分利用高性能计算机的软、硬件资源，加速计算任务的快速完成；面对多年来积累的已验证正确且十分有效的串行应用程序，如何将其移植到超级计算机上高效运行，这些问题长期以来一直是高性能计算领域最为关心和头痛的问题。并行化编译技术是解决这些问题的主要途径之一。所谓并行化编译技术就是指通过多种技术手段自动检测串行程序中潜在的并行性，并将串行程序转变为等价的高效并行程序的翻译技术。并行化编译研究伴随着高性能计算机的出现而开始，从已有研究成果来看并行化研究已取得了可喜的进步，然而迄今为止，并行化编译系统离实际工程应用还有距离，并行化编译领域还有很多内容需要深入的研究。 并行化的最终目标是生成符合目标机体系结构特点的高效并行程序，因此如何产生高效并行代码是并行化编译研究的一项重要内容。并行代码的生成和优化同目标机体系结构密切相关。本文以并行化编译器KAP(Kit of Automatic Parallelizer)的研究和开发为背景，针对目前广泛应用的两种目标并行结构：分布内存结构和共享内存结构，探讨了并行化过程中并行代码自动生成和并行程序性能优化的若干问题。 论文主要分为两大部分。第一部分以分布内存结构为目标，研究了并行化过程中的通信优化和消息传递类型并行程序自动生成问题。在分布内存结构上计算和数据被分布到各个处理机，应用程序的复杂性使得计算和数据不可能完全对齐，即处理机间通信不可避免，而且是影响程序性能的重要因素之一。因此，并行化过程中要尽可能降低和隐藏通信带来的额外开销，在代码生成时不仅要产生各处理机上的计算代码，还要产生处理机间的通信代码。这部分研究的主要内容和贡献包括： 1．提出了目标并行代码的冗余并行执行模型，依据该模型对程序控制流图进行扩展，在其中增加了程序的并行执行信息及数据分布和重分布信息。 2．建立了基于数据流分析的通信优化框架，并在数据流分析过程中引入依赖关系信息，在统一的优化框架下实现了通信延迟隐藏、消息向量化、消息结合和冗余通信消除等优化策略。测试表明，通信优化有效地减少了通信的消息数和数据量，隐藏了通信的开销，提高了程序的并行性能。 3．在数据流分析过程中以逻辑运算来描述数据流表达式，避免了传统集合运算的复杂性；通过单向数据流分析计算数据流表达式，使得优化算法具有线性时间复杂度。 4．依据冗余并行执行模型对并行计算中可能存在的各种通信情况进行了详细的分类，以符号系数线性不等式组的形式定义和描述各个通信集，针对通信集的不同特点提出了相应的通信代码产生算法，并给出了算法的正确性证明。

论文目录

• 摘要
• ABSTRACT
• 目录
• 表目录
• 图目录
• 第一章 绪论
• 1.1 并行化编译研究的意义
• 1.2 并行化编译研究的难点
• 1.3 并行化编译目标机体系结构分类
• 1.3.1 共享内存结构
• 1.3.2 分布内存结构
• 1.4 研究中使用的并行编程模型
• 1.4.1 消息传递编程模型和MPI
• 1.4.2 共享内存编程模型和OpenMP
• 1.5 并行化编译系统KAP
• 1.6 论文的主要工作和组织安排
• 1.7 基本概念、术语及约定
• 第二章 通信优化
• 2.1 引言
• 2.2 基础知识
• 2.2.1 冗余并行执行模型
• 2.2.2 扩展控制流图
• 2.2.3 非本地引用与通信
• 2.2.4 通信描述
• 2.3 通信分析
• 2.4 通信优化框架
• 2.4.1 预处理
• 2.4.2 算法的基本思想
• 2.4.3 数学描述
• 2.5 发送代码移动
• 2.5.1 初始化数据流变量
• 2.5.2 安全发送节点和最早发送节点
• 2.5.3 正确性证明
• 2.6 接收代码调整
• 2.6.1 匹配接收节点和最晚接收节点
• 2.6.2 正确性证明
• 2.7 冗余通信消除
• 2.8 算法复杂性分析
• 2.9 测试结果
• 2.10 相关研究
• 2.11 本章小结
• 第三章 消息传递并行程序的自动生成
• 3.1 引言
• 3.2 线性不等式组和循环嵌套
• 3.2.1 线性不等式组描述
• 3.2.2 利用线性不等式组生成循环嵌套
• 3.2.3 符号系数线性不等式组
• 3.3 计算代码生成
• 3.4 建立通信集
• 3.4.1 无循环携带依赖情况
• 3.4.2 存在循环携带依赖情况
• 3.4.3 其它通信
• 3.5 无循环携带依赖的通信代码生成
• 3.5.1 通信代码生成算法
• 3.5.2 算法证明
• 3.6 存在循环携带依赖的通信代码生成和优化
• 3.6.1 通信代码生成算法
• 3.6.2 通信优化
• 3.7 相关研究工作
• 3.8 本章小结
• 第四章 并行化生成OpenMP并行程序的性能优化
• 4.1 引言
• 4.2 并行化产生OpenMP程序分析
• 4.2.1 OpenMP程序的类型
• 4.2.2 并行化生成OpenMP程序的特点
• 4.3 并行区重构
• 4.3.1 并行区重构算法
• 4.3.2 修正变量的数据属性
• 4.4 Barrier同步优化
• 4.4.1 跨处理器依赖关系图
• 4.4.2 同步优化算法的基本思想
• 4.4.3 算法具体实现
• 4.4.4 算法证明与复杂性分析
• 4.5 测试结果
• 4.5.1 静态分析结果
• 4.5.2 动态测试结果
• 4.6 相关研究工作
• 4.7 本章小结
• 第五章 结束语
• 5.1 本文工作总结
• 5.2 下一步工作展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果