Interchange: condition

• This loop is interchangeable: the top-to-bottom, left-to-right execution order is also valid since all dependence constraints (as shown by the arrows) are still satisfied.
• How can you tell whether a loop can be interchanged?
• Look at it's dependence direction vectors:
  • If any dependence direction vector has the form (<,>), interchange is invalid
  • Because the arrows would be traversed backwards
• All other dependence directions are OK.

• ...