实用数据依赖分析方法

PRACTICAL DATA DEPENDENCE ANALYSIS

数据依赖分析是检测程序循环级并行性的基本步骤．基于数组下标对分类，本文提出了一个实用、有效的数据依赖分析方案．现有的依赖测试算法，都有循环正规化的假设，由于它存在某些弊端，我们抛弃这一假设，允许循环增量是任意整表达式．为此，本文对有关依赖的定义做了适当修改，并重新推导了某些重要结论，为处理循环增量为变量或表达式的情形，给出了弱形式下的ＧＣＤ和Ｂａｎｅｒｊｅｅ测试，该方案已在ＰＯＲＴ中实现．

Data dependence analysis is essential for detecting loop level parallelism in numerical programs. A dependence testing scheme based on classifying subscripts of array references is proposed in this paper. It revises the definitions of direction and distance vectors and improves several approaches for exact test and GCD-Banerjee test in order to avoid traditional loop normalization. Weak GCD and weak Baner ice tests are proposed which can be used when loop strides are variables. These schemes are in the PORT system, a parallelizing compiler system.