Next:
...
Up:
Skewing
Previous:
Skewing
...
To see that this loop performs the same computation, lets work out its dependence structure.
First label each iteration with the element of
A
to which it assigns:
S
00
S
01
S
02
S
03
A
00
A
01
A
02
A
03
S
11
S
12
S
13
S
14
A
10
A
11
A
12
A
13
S
22
S
23
S
24
S
25
A
20
A
21
A
22
A
23
S
33
S
34
S
35
S
36
A
30
A
31
A
32
A
33
The loop body is
A[k
1
,k
2
-k
1
] := A[k
1
-1,k
2
-k
1
]+A[k
1
,k
2
-k
1
-1]
E.g. iteration
S
23
does:
A[2,1] := A[1,1]+A[2,0]