If the size of the computation is so smaller than the size of the array, we can do a reachability analysis and make the calculation fast.
Given: a single d-dimensional vector and a two loops of dimensions n1 and n2.
What if we annotate a point in the data dependence graph by the function at that point?
Do it for 2-dimensional and then 3-dimensional arrays.
Given: two polytopes, P1 and P2, of n-dimensions and one polytope P3 of 2d-dimensions (which we will call the tile polytope: given a tile size, we have an polytope.)
The input to each polytope is a the same facet. The output of the 2n-dimension polytope.
Given: two alpha programs with the following characteristics
Verify that the two programs do the same computation. Can it be done? Can it be done in a fast way?
So the statements and variables in Program2 are of two types
Consider the following situation. If we remove all the variables of type (2.), from program 2, then we are left with a memory mapping that is "similar" to the one in program1 and ofcourse, it has similar schedule to the one in program1. define similarity.
Simple question: prove that the transformation is right.
easy first step: give a transformation from the original n-d space to the transformed 2n-d space and also the reverse of it.
Let the orig space be I_n. Let the tile sizes be S. The 2n-d space is given by T .................
What are the representations of a Z-polyhedra?