Dependence of multi-dimensional array references
Dependence of multi-dimensional array references
复制标题
多维数组引用的依赖性
DOI：
10.1145/55364.55405
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
D. Wallace
中科院分区：
文献类型：
--
作者：
D. Wallace
准确的数据依赖性分析是超级计算机矢量化重组编译器的关键功能。然而，目前可用的数据依赖性分析算法存在局限性。那些执行速度很快的测试，例如 Banerjee Test [3]、[4]、[21]，其通用性非常有限。一般的都太慢了。 1 编译器设计者敏锐地意识到需要一种既通用又快速的算法。下面的算法简单而统一地满足了这一需求。
除了快速执行之外，该算法还具有三个主要特点： 它可以处理任意线性约束，其变量不限于循环控制变量
它可以同时处理任意数量的线性约束。
它只考虑整数解。
该算法将多个约束组织成一个约束矩阵，并使用源自线性规划技术的方法。我们将此称为约束矩阵算法。 Burke 和 Cytron [6] 讨论了处理大于一维的数组的线性化。 Towle [18] 也提到了这种方法。除非添加额外的约束，否则线性化是有限的；它不能处理任意附加约束，并且不将其解决方案限制为整数。
约束矩阵算法是专门针对与标准线性规划问题不同的目标而组织的。这个目标是证明缺乏解决方案[即缺乏依赖性）而不是最小化“目标函数”。此外，该算法被设计为在达到目标时“短路”，这是标准线性规划算法无法做到的。
为了简化说明，我们从依赖性的精确定义开始。为了为后面的算法提供一些动力并展示矩阵格式的优点，我们提出了两种特殊情况的方法（Solvable-Matrix 和 Matrix-GCD）。最后我们提出约束矩阵算法。
Accurate data dependence analysis is the key function in vectorizing-restructuring compilers for supercomputers. However, the data dependence analysis algorithms currently available have limitations. Those that execute quickly, such as the Banerjee Test [3], [4], [21] are very limited in generality. Those that are general are too slow. 1 Compiler designers have been keenly aware of the need for an algorithm that is both general and fast. The algorithm that follows fills this need simply and uniformly.
Aside from fast execution, this algorithm has three main features: It can deal with arbitrary linear constraints whose variables are not limited to loop-control variables
It can deal with any number of these linear constraints simultaneously.
It only looks at integer solutions.
The algorithm organizes the multiple constraints into a constraint matrix and uses a method derived from linear programming techniques. We refer to this as the Constraint-Matrix algorithm. Burke and Cytron [6] have discussed linearization to deal with arrays of greater than one dimension. This approach was also referred to by Towle [18]. Linearization is limited unless additional constraints are added; it cannot deal with arbitrary additional constraints and it does not restrict its solutions to integers.
The Constraint-Matrix algorithm is organized specifically for a goal that is different from the standard linear programming problem. This goal is to prove the lack of a solution [i.e. the lack of a dependence) rather than minimize an “objective function.” further, this algorithm is designed to “short-circuit” when its goal is reached, in a way that a standard linear programming algorithm cannot.
In order to simplify the exposition, we begin with a precise definition of dependence. To provide some motivation for the later algorithm and to show the advantages of the matrix format, we then present two special case methods (Solvable-Matrix and Matrix-GCD). Finally we present the Constraint-Matrix algorithm.