'&$%Homework #2:• http://www.cs.cornell.edu/Courses/cs612/2002SP/assignments/ps2/ps2.htm• Due Thursday, March 7th.1'&$%Transformations and Dependences2'&$%Recall:• Polyhedral algebra tools for• determining emptiness of convex polyhedra• enumerating integers in such a polyhedron.• Central ideas:• reduction of matrices to echelon form by unimodularcolumn operations,• Fourier-Motzkin eliminationLet us use these tools to determine (i) legality of permutation and(ii) generation of transformed code.3'&$%Organization of lecture:• Using ILP to generate transformed code for loop permutation• What is a dependence?• Dependence abstractions (summaries): distance/direction• Computing dependence abstractions using ILP• How to avoid calling the ILP calculator:• ZIV,SIV subscripts and separability• GCD test• Caching of results4'&$%Questions: (1) How do we generate new loop bounds? (2) How do we modify the loop body? (3) How do we know when loop interchange is legal? DO I = 1, NX(I,J) = 5DO U = 1, NX(V,U) = 50 11 0IJ= UVDO J = I,N DO V = 1,ULoop permutation can be modeled as a linear transformation on iteration space:IJUVPermutation of loops in n-loop nest: nxn permutation matrix PP I = U5'&$%Code Generation for Transformed Loop NestTwo problems: (1) Loop bounds (2) Change of variables in body(1) New bounds:Original bounds: A ∗ I≤ b where A is in echelon formTransformation: U = T ∗ INote: for loop permutation, T is a permutation matrix=> inverse is integer matrixSo bounds on U can be written as A ∗ T−1U ≤ bPerform Fourier-Motzkin elimination on this system ofinequalities to obtain bounds on U.(2) Change of variables:I= T−1UReplace old variables by new using this formula6'&$%Example:-1 0 1 -1 0 1 1 00 11 0< -1N 0NUVIJUVDO I = 1, NX(I,J) = 5DO U = 1, NX(V,U) = 50 11 0IJ= UVDO J = I,N DO V = 1,U-1 0 1 -1 0 1JI< -1 1 0 N 0N elimination Fourier-Motzkin7'&$%< -1N 0NUV<< << <-1 0 1 -1 0 1 1 00 11 0 -1N 0NUV-1 1 1 0 0 1 0 -1Projecting out V from system gives U 1 NBounds for V are min(U,N) 1 VThese are loop bounds given by FM elimination.With a little extra work, we can simplify the upper bound of V to U.8'&$%Key points:• Loop bounds determination in transformed code is mechanical.• Polyhedral algebra technology can handle very general boundswith max’s in lower bounds and min’s in upper bounds.• No need for pattern matching etc for triangular bounds and thelike.9'&$%When is permutation legal?Position so far: if there is a dependence between iterations, thenpermutation is illegal.DO I = 1, 100DO J = 1, 100X(2I,J) = .... X(2I-1,J-1)...Is there a flow dependence between different iterations?1 ≤ Iw,Ir,Jw,Jr ≤ 100(Iw,Jw) ≺ (Ir, Jr)2Iw =2Ir − 1Jw = Jr − 1ILP decision problem: is there an integer in union of two convexpolyhedra?No => permutation is legal.10'&$%Permutation is legal only if dependence does not exist: toosimplistic.Example:DO I = 1, 100DO J = 1, 100X(I,J) = .... X(I-1,J-1)...Only dependence is flow dependence:1 ≤ Iw,Jw,Ir,Jr ≤ 100(Iw,Jw) ≺ (Ir,Jr)Iw = Ir − 1Jw = Jr − 1ILP problem has solution: for example, (Iw =1,Jw =1,Ir =2,Jr =2)Dependence exists but loop interchange is legal!11'&$%Point: Existence of dependence is a very “coarse” criterion todetermine if interchange is legal.Additional information about dependence may let us conclude thata transformation is legal.To get a handle on all this, let is first define dependence precisely.12'&$%Consider single loop case first:DO I = 1, 100X(2I+1) = ....X(I)...Flow dependences between iterations:Iteration 1 writes to X(3) which is read by iteration 3.Iteration 2 writes to X(5) which is read by iteration 5.....Iteration 49 writes to X(99) which is read by iteration 99.If we ignore the array locations and just think about dependencebetween iterations, we can draw this geometrically as follows:012345 910678IDependence arrows always go forward in iteration space. (eg. therecannot be a dependence from iteration 5 to iteration 2)13'&$%Intuitively, dependence arrows tell us constraints ontransformations.012345 910678ISuppose a transformed program does iteration 2 before iteration 1.OK!Transformed program does iteration 3 before iteration 1. Illegal!14'&$%Formal view of a dependence: relation between points in theiteration space.DO I = 1, 100X(2I+1) = ....X(I)...Flow dependence = {(Iw, 2Iw +1)|1 ≤ Iw ≤ 49}(Note: this is a convex set)012345 910678IIn the spirit of dependence, we will often write this as follows:Flow dependence = {(Iw → 2Iw +1)|1 ≤ Iw ≤ 49}15'&$%2D loop nestDO 10 I = 1,100DO 10 J = 1,10010 X(I,J) = X(I-1,J+1) + 1Dependence: relation of the form (I1,J1) → (I2,J2).Picture in iteration space:00011100110001110001110000001111110000001111110001110011000111000111000111000111000111001100011100011100011100011100000011111100001111000000111111000000111111000111000111000000111111000011110000001111110000001111110000001111110000001111110000001111110000001111110000000011111111IJsource target(I1,J1) (I2,J2)123 541234516'&$%Legal and illegal dependence arrows:Jillegal dependence arrowslegal dependence arrowsIf (A → B) is a dependence arrow, then A must belexicographically less than or equal to B.17'&$%Dependence relation can be computed using ILP calculatorDO 10 I = 1,100DO 10 J = 1,10010 X(I,J) = X(I-1,J+1) + 1Flow dependence constraints: (Iw,Jw) → (Ir,Jr)• 1 ≤ Iw,Ir,Jw, Jr ≤ 100• (Iw,Jw) ≺ (Ir,Jr)• Iw= Ir− 1• Jw= Jr+1Use ILP calculator to determine the following relation:D = {(Iw, Jw) → (Iw +1,Jw− 1)|(1 ≤ Iw ≤ 99) ∧ (2 ≤ Jw ≤ 100)}18'&$%If we have the full dependence relation, can we determine whenpermutation is legal?Let us look at geometric picture to understand when permutationis legal.DO I = 1, N DO J = 1,N X(I,J) = X(I-1,J-1)......0000111100001111000011110011010100001111000011110000111100110101000011110000111100001111001101010011001100110100110011001100110011010101001101001101000011110011001101001101000011110011000011110011000011110011001101000011110011000011110011000011110011001101001101000011110011IJ123 5412345IJ123 5412345DO I = 1,N DO J = 1,N X(I,J) = X(I-1,J+1)......Permutation is illegal Permutation is legalIntuitively, if an iteration is dependent on an iteration in its ”upperleft hand corner”, permutation is illegal. How do we express thisformally?19'&$%Legality