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
  • 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
  • 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?