1. [10 pts.] Describe all data dependencies in the following code segment:
S1:
a++
S2:
b = a + b
S3:
c = a + d
S4:
d = c2
S5:
a - -
[10 pts.] What are the data dependencies, distance vectors and direction vectors for S1 and S2 in the following code segment?
for ( i = 0; i < MAX; i++ )
for ( j = 0; j < MAX; j++ )
S1: A[ i ][ j ] = A[ i+1 ][ j-1 ]
S2: B[ i ][ j ] = A[ i ][ j ]
Can these loops be re-ordered? Why or why not?
3. Given the following loop nest, for each value of BODY, which loop re-orderings are valid?
BODY
for ( i = 0; i < MAX; i++ ) (a.) [10 pts.] A[ i, j, k, m ] = B[ i-1, j-1, k-1, m-1]
for ( j = 0; j < MAX; j++ ) (b.) [10 pts.] A[ i, j, k, m ] = A[ i-1, j, k, m ]
for ( k = 0; k < MAX; k++ ) (c.) [10 pts.] A[ i, j, k, m+1 ] = A[ i, j, k+1, m ] + B[i]
for ( m = 0; m < MAX; m++ )
BODY( i, j, k, m)
The Ohio State University
