## Tuesday, August 02, 2005

### checking for the validity of a transformation on unitary graphs

Given a d-dimensional vector and a computation on the vector, what are the problems that can be solved fastly? If we are also given that the dependence components in the associated computation are from the range {-1,0,+1}, can we find the equivalence of two computations? If so, give an algorithm to find the equivalence fastly.
--
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
---------
Program1:
• an parametrized n-dimensional polyhedral domain.
• A statement defined in all the points of the domain.
• A monodimensional time schedule, which is valid.
• A memory mapping
---------
Program2:
• A parametrized 2n-dimensional Z-polyhedral domain. The domain can be expressed as a affine transformation of the original domain.
• A collection of statements defined in all the points of the domain
• A mono-dimensional schedule, which is valid (define the schedule function)
• A memory mapping, which is an affine function of the one in program1.
-------------
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
• 1. ones that correspond to variables in program1.
• 2. ones that are additional variables (the buffers).
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?