全局数组数据流分析技术的研究与实现
Research and Implementation of Global Array Data-flow Analysis Technology
在分布存储结构的计算机系统中,尽可能地降低处理器间的通信开销、提高并行程序的执行效率是并行化编译必须要考虑的问题.目前的并行化技术主要针对循环级并行,循环中的数组是进行通信优化的主要对象.传统的依赖关系分析只能确定并行程序中需要通信的位置,不能确定所需通信的数组区域,以此为依据生成的通信代码中包含大量冗余通信.精确的数组数据流分析所得的信息能够作为精确数据通信代码生成的依据,但分析的范围局限在单个循环内部,无法消除跨循环边界的数据依赖关系引起的冗余通信.基于传统数据流分析进行通信优化可以获得范围更广的数据流信息,但优化对象只能精确到标量,无法对数组中的单个元素做进一步的分析.本文针对分布存储系统并行化编译中的通信优化问题,设计并实现了全局数组数据流分析算法.首先,对比了语法制导求解和迭代求解两种主要的数据流信息求解方法,在自动并行识别工具SW-KAP中间表示的基础上扩展了控制流图,构建了全局数据流分析的框架;其次,深入研究了数组区域的线性不等式表示和循环中数组的终写关系分析,提出了一种能够消除冗余通信的暴露集求解算法,并在SW-KAP中增加了对读引用的输入依赖和流依赖关系的分析,实现了循环中数组暴露集的自动求解;第三,结合全局数据流分析和循环内的精确数组数据流分析,设计并实现了全局数组数据流分析算法,获得了过程内跨越循环边界的精确数组数据流信息.本文所述算法已在自动并行识别工具SW-KAP中实现,全局数组数据流分析结果为编译器后端实现精确数据通信代码的生成提供了必要信息,测试结果表明算法设计正确,能够提供精确的数组通信信息,有效降低了自动并行识别生成的并行程序中的通信代价.
- 作者：
- 刘晓娴
- 学位授予单位：
- 解放军信息工程大学
- 专业名称：
- 计算机软件与理论
- 授予学位：
- 硕士
- 学位年度：
- 2009年
- 导师姓名：
- 赵荣彩
- 中图分类号：
- TP338.6
- 关键词：
- 分布存储结构；并行化编译；通信优化；数据流分析；线性不等式；暴露集
- Distributed Memory Computer System；Parallelizing Compilation；Communication Optimization；Data-flow Analysis；Linear Inequality；Exposed-set