程序并行识别方法及应用研究

论文摘要

并行计算就是在并行计算机或分布式计算机等高性能计算系统上所做的超级计算,其物质基础是高性能并行计算机。为了能在高性能并行计算机上生成高速运行的并行代码,并行化编译技术的研究和发展同样成为计算机科学研究领域的一个热点。串行程序自动并行化是并行编译技术最重要的内容之一,它自动将串行程序转换为等价的能在并行计算机上高效运行的并行程序,并且能克服并行计算机编程困难、软件移植困难的不足,降低并行程序开发成本。本文针对在编译阶段实现串行程序自动并行化课题提出了一系列的并行处理方法。首先研究了自动并行化中的并行粒度,通过对三种并行粒度的分析提出了一种中粒度并行的实现方法,其中主要提出了中粒度并行时的基本块的并行识别方法和并行优化方法,解决了并行处理时并行线程工作量与线程开销之间的矛盾,避免了在并行处理时可能出现的程序执行效率降低的现象;其次,针对占串行程序计算量主体的循环的自动并行化进行了研究,并且提出了关于紧嵌套循环的自动并行化方法,为了解决并行程序的硬件环境成本高的问题而提出的在多核系统下对紧嵌套循环进行自动并行化时的并行识别方法,数据划分方法和计算划分方法,实现了提高串行循环的执行速度,加大了程序自动并行化的应用力度;最后,设计了在并行化编译器中自动生成语法分析表时的一个自动并行处理算法,通过一个小的例子充分说明了并行的高效性。

论文目录

• 提要
• 第1章 绪论
• 1.1 研究背景
• 1.2 并行计算
• 1.2.1 并行计算的概念
• 1.2.2 并行计算的分类
• 1.2.3 并行计算的应用
• 1.2.4 并行算法
• 1.3 并行程序开发方法
• 1.3.1 并行层次与代码粒度
• 1.3.2 并行程序的开发策略
• 1.4 并行程序设计模式
• 1.4.1 并行程序设计模式的基本思路
• 1.4.2 并行程序设计模式
• 1.5 本文的主要工作和意义
• 1.6 本文的组织结构
• 第2章 并行化编译器的相关研究
• 2.1 并行化编译系统
• 2.2 并行化编译器
• 2.3 并行化编译器中 LL（1）分析表自动生成的并行算法设计
• 2.3.1 概述
• 2.3.2 相关定义和结论
• 2.3.3 LL（1）分析表自动生成的并行算法
• 2.3.4 算法实例
• 2.3.5 性能分析
• 2.4 本章小结和进一步的工作
• 2.4.1 小结
• 2.4.2 今后的工作
• 第3章 并行识别方法的研究
• 3.1 概述
• 3.2 依赖关系
• 3.2.1 依赖关系分析的基础知识
• 3.2.2 控制依赖关系
• 3.2.3 数据依赖关系
• 3.2.4 数据依赖关系分析
• 3.3 基于数据依赖关系的面向基本块的并行识别方法
• 3.3.1 前言
• 3.3.2 与算法相关的基础知识
• 3.3.3 面向基本块的并行识别算法
• 3.3.4 针对本算法的并行优化策略
• 3.3.5 算法性能分析
• 3.4 基于数据依赖关系的面向循环的并行识别方法
• 3.4.1 前言
• 3.4.2 循环中的依赖关系测试
• 3.4.3 循环变换技术
• 3.4.4 循环并行化
• 3.5 本章小结和进一步工作
• 第4章 并行识别在多核环境下的程序自动并行化中的应用
• 4.1 概述
• 4.2 片上多核处理器（CMP）
• 4.2.1 多核CPU概述
• 4.2.2 CMP硬件特性
• 4.2.3 基于多核CPU的并行计算
• 4.2.4 基于多核CPU并行计算的性能分析
• 4.3 任务划分和数据划分
• 4.3.1 数据划分
• 4.3.2 任务划分
• 4.4 基于CMP的任务划分方法
• 4.4.1 串行循环自动并行化中任务划分方法
• 4.4.2 基于任务量划分的紧嵌套循环的自动并行化方法
• 4.4.3 性能分析和优化
• 4.5 循环自动并行化中一种基于CMP的数据划分方法
• 4.5.1 基本概念
• 4.5.2 数据划分方法
• 4.5.3 性能分析
• 4.6 本章小结和进一步工作
• 第5章 总结与展望
• 5.1 全文工作总结
• 5.2 进一步工作
• 参考文献
• 致谢
• 攻读博士期间已发表和已录用的文章
• 摘要
• ABSTRACT