Next: ... Up: Nested loops Previous: ...

...

The same loop:

for I1 = 0 to 3 do

  for I2 = 0 to 3 do
S:   A[I1,I2] := A[I1 - 1,I2] + A[I1,I2 - 1]
For humans the easy way to understand this loop nest is to draw the iteration space showing the iteration-to-iteration dependences:


S00 0
$\rightarrow$  
$\delta$  
S01 0
$\rightarrow$  
$\delta$  
S02 0
$\rightarrow$  
$\delta$  
S03
$\delta$ $\downarrow$   $\delta$ $\downarrow$   $\delta$ $\downarrow$   $\delta$ $\downarrow$
S10 0
$\rightarrow$  
$\delta$  
S11 0
$\rightarrow$  
$\delta$  
S12 0
$\rightarrow$  
$\delta$  
S13
$\delta$ $\downarrow$   $\delta$ $\downarrow$   $\delta$ $\downarrow$   $\delta$ $\downarrow$
S20 0
$\rightarrow$  
$\delta$  
S21 0
$\rightarrow$  
$\delta$  
S22 0
$\rightarrow$  
$\delta$  
S23
$\delta$ $\downarrow$   $\delta$ $\downarrow$   $\delta$ $\downarrow$   $\delta$ $\downarrow$
S30 0
$\rightarrow$  
$\delta$  
S31 0
$\rightarrow$  
$\delta$  
S32 0
$\rightarrow$  
$\delta$  
S33

The diagram shows an arrow for each solution of each dependence equation.


next up previous
Next: ... Up: Nested loops Previous: ...