Data dependence analysis determines a description of the elements that are accessed more than once. In loop nests the classic description of data dependences are the distance and direction vectors.

Example :

DO I = 4, 8
  DO J = 3, 8
    A(I, J) = A(I-3, J-2) + 1
  END DO
END DO

At iteration I  7, J  4,

A(7, 4) = A(7-3, 4-2) + 1

so, A(4, 2) must be computed before A(7, 4). This relation on the elements of the array A can be summarized by the distance vector (3, 2) or by the direction vector (+, +).

For representing the dependence relations, the analyzer uses the chains of recurrences for representing integer functions. The conflicting elements are obtained by composition of functions.

Example: Given two accesses to the same array: {0, +, 5}_1 and {3, +, 7}_1, the overlapping iterations are described by the functions {2, +, 7}_x and {1, +, 5}_x. The first overlapping elements are:

{0, +, 5}(2) = {3, +, 7}(1) = 10
{0, +, 5}(9) = {3, +, 7}(6) = 45
[...]
{0, +, 5}({2, +, 7}_x) = {3, +, 7}({1, +, 5}_x)

The distance vectors are obtained by substraction of the overlapping functions. In the previous example, the dependence relation cannot be represented by a distance vector. In order to have a dependence relation that can be represented by a distance vector, the overlapping iteration functions should have same steps.

Another important aspect of the dependence analysis are the domains on which the dependences occur. The existence of dependences and the dependence domains are determined from the number of iterations in the loop. When the number of iterations cannot be exactly deduced at compile time, it has to be bounded by an approximation. See the article on the number_of_iterations for a detailed discussion.

None: Data_Dependence_Analysis (last edited 2008-01-10 19:38:42 by localhost)