Introduction: Note that sweeping the iteration space horizontally and vertically, as discussed above, are just two of the most common ways of visiting the iteration space. There are many other possibilities; for example, we can sweep the iteration space in Example 11.6 diagonal by diagonal, as discussed below in Example 11.15.
Example: We can sweep the iteration space shown in Fig. 11.11 diagonally using the order shown in Fig. 11.16. The difference between the coordinates j and i in each diagonal is a constant, starting with 0 and ending with 7. Thus, we define a new variable k = j — i and sweep through the iteration space in lexicographic order with respect to k and j. Substituting i = j — k in the inequalities we get:
To create the loop bounds for the order described above, we can apply Algorithm 11.13 to the above set of inequalities with variable ordering k, j.
Uj\ 5 k, 7
From these inequalities, we generate the following code, replacing i by j - k in array accesses.
f o r (k = 0; k <= 7; k )
f o r (j = k; j <= min(5 k,7); j )
Z [ j , j - k ] = 0;