Compiler Design Module 141 : Affine Space Partitions

[compilerai]

7:10 In addition to identifying parallelism, we can also identify the reuse distance between two accesses, by using the approach we saw in the previous lecture module on "Group Reuse". Both accesses have the same "F" but different f1 and f2. So, the lexicographically first element of the solution space for "F(i1-i2) = f2-f1" is the reuse distance. In this example (after the transformation), the reuse distance is "(0 1)", i.e., O(1). On the other hand, the reuse distance of the original loop (before the transformation) was "(1 -1)", i.e., O(n) [n^{index of the last non-zero index in the reuse distance)].