For describing the relation between memory accesses one needs:
Intuitive idea for the data dependence test: "a1 depends on a0" when a0 touches some memory cell before a1. The result of the data dependence test is a polyhedron describing the dependences. If there are no dependences, the dependence polyhedron is empty. The dependence polyhedron contains the following constraints:
- for each subscript f0 and f1 of array a0 and a1 we have f0 (i0) = f1 (i1)
- for some i0 in d0 and i1 in d1
- s0 and s1: the scattering polyhedra s0 and s1 relate the iteration domains d0 and d1 to the new extended iteration domain obtained by the s0 and s1 transforms.
- t0 lexicographically [smaller | equal] to t1: the scattering polyhedra s0 and s1 define the time of execution t0 and t1 of data references a0 and a1.
Data dependence polyhedron specification: Polyhedral dependences