Skewing

 

Consider the following loop:

 for k   := 0 to 3 do

  for k   := k   to k  +3 do

S: A[k  ,k  -k  ] := A[k  -1,k  -k  ]+A[k  ,k  -k  -1]

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

  

• This loop performs the same computation as the original.

• ...
• ...
• After interchange
• ...
• Summary
• ...