全局数组数据流分析技术的研究与实现

发布时间：2020-03-18 12:48

【摘要】：在分布存储结构的计算机系统中,尽可能地降低处理器间的通信开销、提高并行程序的执行效率是并行化编译必须要考虑的问题。目前的并行化技术主要针对循环级并行,循环中的数组是进行通信优化的主要对象。传统的依赖关系分析只能确定并行程序中需要通信的位置,不能确定所需通信的数组区域,以此为依据生成的通信代码中包含大量冗余通信。精确的数组数据流分析所得的信息能够作为精确数据通信代码生成的依据,但分析的范围局限在单个循环内部,无法消除跨循环边界的数据依赖关系引起的冗余通信。基于传统数据流分析进行通信优化可以获得范围更广的数据流信息,但优化对象只能精确到标量,无法对数组中的单个元素做进一步的分析。 本文针对分布存储系统并行化编译中的通信优化问题,设计并实现了全局数组数据流分析算法。首先,对比了语法制导求解和迭代求解两种主要的数据流信息求解方法,在自动并行识别工具SW-KAP中间表示的基础上扩展了控制流图,构建了全局数据流分析的框架；其次,深入研究了数组区域的线性不等式表示和循环中数组的终写关系分析,提出了一种能够消除冗余通信的暴露集求解算法,并在SW-KAP中增加了对读引用的输入依赖和流依赖关系的分析,实现了循环中数组暴露集的自动求解；第三,结合全局数据流分析和循环内的精确数组数据流分析,设计并实现了全局数组数据流分析算法,获得了过程内跨越循环边界的精确数组数据流信息。 本文所述算法已在自动并行识别工具SW-KAP中实现,全局数组数据流分析结果为编译器后端实现精确数据通信代码的生成提供了必要信息,测试结果表明算法设计正确,能够提供精确的数组通信信息,有效降低了自动并行识别生成的并行程序中的通信代价。
【图文】：

于写引用RZ，，使用LWT算法就可获得R，依赖于R:的范围。经过前面的分析可知，数组终写关系分析需要对自反输出依赖关系和不同写引用之间的单向输出依赖关系进行分析。算法流程如图18所示:首先对写引用进行自干扰分析，将写引用自身对同一数组元素的多次访问从非自干扰空间中去除，只留下一次访问;然后进行输出依赖分析，将该写引用与其它写引用之间有依赖关系的数组元素从自干扰空间中去除。在最后得到的终写迭代空间中，所有被访问的数组元素都不会在循环内被再次修改。写写引用集合J，外层循环 环迭 迭代空间了 了从从写引用集合刁中取出一 一 个 个写引用」，，4=.4二毛 毛 对对毛进行自干扰分析得到 到 其其非自干扰迭代空间编 编 林林留x进行输出依赖分析得 得 到 到其终写迭代空间 Ilwww将将二元组(志，IltJ写入中间 间 注注释
【学位授予单位】：解放军信息工程大学
【学位级别】：硕士
【学位授予年份】：2009
【分类号】：TP338.6

【相似文献】

相关期刊论文 前10条

1 谢卫，刘键;多变量数组下标表达式的分解与相关性测试[J];华中理工大学学报;1994年06期

2 孙彤,李三立,李晓明;并行化编译中的一种集成优化方法[J];软件学报;1996年12期

3 朱根江，谢立，孙钟秀;一种基于非正规域的区域依赖关系分析法[J];计算机学报;1994年03期

4 臧斌宇,陈彤,张瑜,朱传琪;有效的数组私有化方法:相关-覆盖方法[J];计算机学报;2000年01期

5 谢幸,陈国良,武继刚;分布存储并行机上的自动数据布局优化模型[J];计算机研究与发展;2000年10期

6 胡世亮,臧斌宇,凌冰,朱传琪;数据流分析中的区域覆盖技术[J];软件学报;2000年03期

7 任华;赵荣彩;张平;孟然;;基于精确数组数据流分析框架的通信优化[J];计算机工程与应用;2006年36期

8 马国凯,王欣[C,王鹏,臧斌宇,朱传琪;利用U模变换增加并行粒度与改善数据访问局部性的方法[J];计算机学报;2004年04期

9 陈清萍;李晓峰;郑世荣;;一种基于分解变换的并行化编译新技术[J];计算机科学;1998年01期

10 刘晓娴;赵荣彩;梁玲;;消除冗余通信的暴露集求解算法[J];计算机工程;2009年11期

相关博士学位论文 前2条

1 王轶然;分布式主存系统上自动数据和计算分解和相关研究[D];中国科学院研究生院（计算技术研究所）;2006年

2 张平;并行化编译器中并行程序自动生成和性能优化技术研究[D];解放军信息工程大学;2006年

相关硕士学位论文 前3条

1 刘晓娴;全局数组数据流分析技术的研究与实现[D];解放军信息工程大学;2009年

2 任华;数组数据流分析算法的优化和数组私有化技术的研究与实现[D];解放军信息工程大学;2007年

3 丁锐;分布存储结构的通信代码自动生成与优化[D];解放军信息工程大学;2009年

本文编号：2588738