一种面向划分的数组数据流分析方法

Array Data-flow Analysis Method for Partition

传统数组数据流分析方法主要针对精确依赖测试、数组私有化等研究,无法为划分提供数组在循环间详细的定义-引用信息.本文提出了一种面向划分的数组数据流分析方法,通过定义-引用图来表示数组的数据流信息.首先根据嵌套循环的并行性和结构特点,建立定义-引用图的结点集.然后基于活跃-引用和精确数据流分析,在循环内求出数组的定义、引用等数组区域.最后根据数据流方程和过程间分析添加定义-引用边.通过对矩阵求逆等七个实际用例的实验结果表明,定义-引用图的引用能够使划分算法对并行收益做出准确的评估,并减少了生成代码的通信冗余,提升了并行程序的加速比.

The traditional analysis methods of array data-flow focus on accurate dependence testing and array privatization, etc. And they can＇t offer detailed information of array＇s define-use inter-loops. For partition, this paper proposes a new array data-flow analysis method, which represents array＇s data-flow information loops by define-use graph. The method establishes the vertex set of graph first according to loop＇s characteristics of parallelism and structure. Then it analyzes array section of definition and use in loop based on live-use and accurate flow analysis, and add define-use edges by data-flow equations and inter-procedural analysis. The experimental results on Matrix-Inversion and other six applications show that, define-use graph can make partition algorithm did a more accurate as- sessment of parallel benefits, reduce the communication redundancy of code generated and rise up the speedup.