After interchange

S00

$\delta$ $\downarrow$

$\searrow^\delta$

S01

S11

$\delta$ $\downarrow$

$\searrow^\delta$

$\delta$ $\downarrow$

$\searrow^\delta$

S02

S12

S22

$\delta$ $\downarrow$

$\searrow^\delta$

$\delta$ $\downarrow$

$\searrow^\delta$

$\delta$ $\downarrow$

$\searrow^\delta$

S03

S13

S23

S33

$\searrow^\delta$

$\delta$ $\downarrow$

$\searrow^\delta$

$\delta$ $\downarrow$

$\searrow^\delta$

$\delta$ $\downarrow$

S14

S24

S34

$\searrow^\delta$

$\delta$ $\downarrow$

$\searrow^\delta$

$\delta$ $\downarrow$

S25

S35

$\searrow^\delta$

$\delta$ $\downarrow$

S36

for k2 := ? to ? do

  for k1 := ? to ? do

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

$\bullet$ The inner loop is now vectorisable.

$\bullet$ The skewed iteration space has N rows and 2N-1 columns, but still only N² actual statement instances.

$\bullet$ What are the appropriate loop bounds?