Array Data-Dependence Analysis

Three types of dependencies:

A static access in a program depends on another as long as there exists a dynamic instance of the first access that depends on some instance of the second.

Let two static array accesses be represented by <F,f,B,b> in a d-depth loop nest and <F',f',B',b'> in a d'-depth loop nest; then these accesses are data-dependent if

  1. At least one of them is a write reference and
  2. There exist vectors i in Z^d and i' in Z^d' such that
To search for dependencies between instance of the same static instance, we impose the additional constraint that i!=i'.

Example: 

for (i = 1; i<=10; i++) {
  Z[i] = Z[i-1];
}
What are all the data dependencies in this program (between the one read and one write access in the loop body): 
1 <= i <= 10
1 <= i' <= 10
i-1 = i'
What about data-dependencies between Z[i] and itself? 
1 <= i <= 10
1 <= i' <= 10
i = i
i != i'
The last constraint because it is a self-dependency test

Integer Linear Programming

Solving such equations involving equality and inequality relations between integers, requires integer linear programming (ILP) algorithms. In general, ILP is NP-hard, but several heuristics can get us to good solutions; further, the problem sizes expected in our analyses are fairly small. We do not discuss techniques to solve ILPs in this course, and just assume that we have tools available to do this.