Skewing

Consider the following loop:

for k1 := 0 to 3 do

  for k2 := k1 to k1+3 do

S: A[k1,k2-k1] := A[k1-1,k2-k1]+A[k1,k2-k1-1]  

• The inner loop's control variable runs from k₁ to k₁+3.
• The iteration space of this loop has 4² iterations just like the original loop.
• If we draw the iteration space with each iteration S^K₁,K₂ at coordinate position (K₁,K₂), it is skewed to form a lozenge shape:

  S00	S01	S02	S03
  	S11	S12	S13	S14
  		S22	S23	S24	S25
  			S33	S34	S35	S36

• This loop performs the same computation as the original.