并行化或局部性优化经常对原程序中执行的运算重新排序。和所有的优化一样，只有当对运算的重新排序不会改变程序输出时才可以对这些运算重新排序。一般来说，我们不可能深人理解一个程序到底做了什么，代码优化通常选用一个较简单的、保守的测试方法来决定在什么时候可以肯定程序的输出不会受到优化的影响：检查在原程序中和在修改后的程序中，对同一内存位置的各个运算被执行的顺序是否一样。在当前的研究中，我们关注的是数组访问，因此数组元 素就是需要考虑的内存位置。

如果两个访问（不管是读还是写）指向两个不同的位置，显然它们是相互独立的（可以被重 新排序）。另外，读运算不会改变内存的状态，因此各个读运算之间是独立的。如果两个访问指向同一个内存位置并且其中至少有一个写运算，那么就说这两个访问是数据 依赖的。为了保证修改后的程序和原程序做同样的事情，每一对有数据依赖关系的运算在原程 序中的执行顺序必须在新的程序中得到保持。

回顾一下,可知存在三种类型的数据依赖：

1)真依赖，一个写运算后面跟一个对同一个内存位置的读运算。

2)反依赖，一个读运算后面跟一个对同一个内存位置的写运算。

3)输出依赖，是两个针对同一个位置的写运算。

在上面的讨论中，数据依赖是针对动态访问定义的。只要一个程序的某个静态访问的某个动态实例依赖于另一个静态访问的某个动态实例，我们就说第一个静态访问依赖于第二个静态访问。

我们可以很容易看出数据依赖关系如何应用到并行化中。比如，如果在一个循环的各个访问之间没有发现数据依赖关系，那么就可以很容易地把不同的迭代分配给不同的处理器。如何系统化地将这个信息应用到并行化中。

数组访问的数据依赖关系的定义

让我们考虑对同一个数组的两个静态访问，它们可能位于不同的循环中。第一个访问用访问函数和界限表示为F= <F,f,B,b > ,它位于一个深度为d'的循环嵌套结构中；第二个访问表示为F=<F’f，B'，b’>,它位于一个深度为的程序嵌套结构中。如果下面的条件成立，这两个访问就是数据依赖的。

1)它们中至少有一个是写运算，且

2)存在中的向量i和Zd中的向量使得

① Bi+b≥0

 B’i’+b≥0

③ Fi +f= F'i' +f‘

因为一个静态访问通常会产生多个动态访问，所以考虑它的多个动态访问是否可能指向同一个内存位置也是有意义的。为了寻找同一个静态访问的不同实例之间的依赖关系，我们假设并在上面的定义中加人附加条件i≠i ’以剔除平凡解。